Параллельное и распределенное программирование на С++

Хьюз Камерон

из Детройта в Толедо; из Толедо в Кливленд; из Кливленда в Кол^мбус; из Колумбуса Нью-Йорк.

Поэтому, несмотря на то, что компания ABC Bus Company не предоставляет прямого маршрута (из пункта А в пункт Б), она позволяет совершить переезд с большим количеством промежуточных остановок. Задача состоит в следую щ ем: как об этом может узнать наш агент? Агент на основе своих знаний об автобусных маршрутах должен обладать некоторым алгоритмом генерирования вывода о том, су щ ествует ли маршрут из Детройта в Нью-Йорк. Мы используем простой цепной метод. Просматриваем элементы множества BusTripKnowledge и находим первый маршрут из Детройта— из Детройта в Чикаго. Опрашиваем атрибут То этого элемента. Если бы он был равен значению «Нью-Йорк», процесс поиска был бы прекращен, поскольку мы нашли нужный маршрут. В противном случае сохраняем найденный (промежуточный) маршрут в стеке. Затем ищем маршрут с атрибутом From, равным «Чикаго». При этом может оказаться, что таких маршрутов не прелусмотрено вообще. Поскольку далее хранить элемент множества, соответствующий маршруту «Детройт-Чикаго»,

нет никакого смысла, мы удаляем его из стека, сделав пометку, что этот маршрут уже был рассмотрен. Затем повторяем поиск маршрута с отправлением из Детройта. Находим такой маршрут: «Детройт-Толедо». Проверяем, не равен ли его атрибут То значению «Нью-Йорк», и поскольку наши надежды не оправдались, сохраняем этот элемент в стеке. Затем ищем маршрут с атрибутом From, равным «Толедо». Находим маршрут «Толедо-Кливленд» и также помещаем его на хранение в стек. После это г о просматриваем маршруты в надежде найти элемент, у которого атрибут From был бы равен значению «Кливленд». Для каждо го найденного маршрута проверяем значение атрибута То. Если он равен значению " Нью-Йорк» , то промежуточные маршруты, помещенные в стек, представляют в целом маршрут из Детройта в Нью-Йорк, начало которого находится на «дне» стека, а его конечный пункт — в вершине. Если мы пройдем по всему списку маршрутов и не найдем ни одного с атрибутом То, равным значению «Нью-Йорк», или иссякнут возможные варианты проверки атрибута То для верхнего элемента стека, то мы, извлекал верхний элемент из стека, будем искать следующий элемент, значение атрибута From которого совпадает со значением атрибута То элемента, расположенного в вершине стека. Этот процесс повторяется до тех пор, пока стек не опустеет или мы все-таки не най дем нужный маршрут. Для определения, существует ли маршрут из пункта А в пункт Б, используется в данном случае упрощ ен ный метод DFS (Depth First Search — «поиск вглубь»).

Наш простой агент будет использовать этот DFS-метод для выяснения, существует ли маршрут из Детройта в Нью-Йорк. Выяснив этот факт, агент может обновить свои убеждения насчет Джона. Теперь агент убежден, что Джон поедет в отпуск. Предположим, мы внесли дополнительное прелусловие относительно отпуска Джона.

Если Джон обслужит 15 или больше новых клиентов, его доходы превысят (>) 150000.

Если доходы Джона превысят 150000 и существует маршрут из Детройта в Нью-Йорк, то Джон отправится в отпуск.

Теперь агент должен выяснить, превышают ли доходы Джона лумму 150000 и существует ли маршрут из Детройта в Нью-Йорк. Чтобы выяснить положение дел насчет доходов Джона, агент должен сначала узнать, обслужил ли Джон хотя бы 15 новых клиентов. Предположим, мы уверяем программного агента в том, что Джон обслужил 23 новых клиента. Затем агент должен убедиться в том, что его доходы превышают 150000. На основе содержимо г о множества BusTripKnowledge агент сумел прийти к выволу о существовании маршрута из Детройта в Нью-Йорк. На основании убеждений об автобусных маршрутах и 23 новых клиентах агент использует процесс прямого построения цепочки (т.е. рассуждений от исходных посылок к целевой гипотезе) и приходит к заключению, что Джон таки поедет в отпуск. Формат рассуж-дений этого процесса имеет такой вид.

А -> В (В и С) -> D А С

D

Здесь:

А=ЕслиДжон обслужит не менее 15 новых клиентов, В = Доходы>150000,

С = Су щ ествует автобусный маршрут из Детройта в Нью-Йорк, D = Джон поедет в отпуск.

В этом примере агент убеждается, что эле м енты А и С истинны. С использование м правил ведения рассуждений агент заключает, что эле м енты В и D равны значению ИСТИНА. Следовательно, агент делает вывод о том, что Джон поедет в отпуск. Подобный вид обработки имеющихся данных можно было бы применить к агенту в ситуации, когда у директора фирмы в подчинении находятся сотни или даже тысячи служащих, и он хотел бы, чтобы агент регулярно составлял почасовой график работы для своих служащих. Директор намерен затем получать от агента справку о том, кто работал, кто находился в отпуске по болезни, а кто — в очередном отпуске и т.д. Агент должен обладать знаниями и полномочиями устанавливать график работы. Каждую неделю агент должен представлять ряд приемлемых графиков работы, очередных отпусков и сведений о пропусках по болезни. Агент в этом случае для получения результата использует простой метод прямого построения цепочки и метод DFS. Чтобы реализовать этот вид рассуждений, мы использовали такие типы данных, как struct и классы стеков и множеств. Эти классы используются для хранения знаний, предположений иметодов рассуждений. Они позволяют реализовать когнитивные структуры данных (Cognitive Data Structures — CDS). Для поддержки процесса рассуждений, а именно при опросе наших структур данных (стека и множества) мы использовали DFS-методы.

При сочетании метода прямого построения цепочки и метода DFS создается процесс, в соответствии с которым одно предположение может быть подтверждено на основе уже принятых предыдущих. Это очень важный момент, поскольку наш агент при достижении цели должен знать, что в действительности следует считать корректным. Такой подход также влияет на отношение к вопросам параллельного программирования. Тот факт, что агент рационален и действует в соответствии с правилами построения рассуждений, позволяет разработчику сосредоточиться на корректном моделировании задачи, выполняемой агентом, а не на стремлении явно управлять параллелизмом в программе. Минимальные требования параллелизма, выражаемые тремя «китами» — декомпозицией, взаимодействием и синхронизацией (decomposition, communication, synchronization — DCS), — по большей части относятся к архитектуре агента. Каждый агент для своего поведения имеет логическое обоснование. Это обоснование

должно опираться на хорошо определенные и хорошо понимаемые правила ведения рассуждений. Декомпозиция зачастую выражается в простом назначении агенту одного или нескольких основных указаний (директив). Декомпозиция работ в этом случае должна иметь естественный характер и в конце концов выразиться в параллельных или распределенных программах, которые нетрудно поддерживать и развивать. Взаимодействие агентов проще представить, чем взаимодействие анонимных модулей , поскольку границы между агентами более четки и очевидны. Каждый агент имеет цель, которая лежит на поверхности. Знания, или информация, необходимые каждому агенту для достижения его цели, в этом случае легко определяются. Чтобы позволить агентам взаимодействовать, разработчик может использовать простые MPI-функции или средства взаимодействия объектов, которые являются частью любой CORBA-реализации. При обеспечении взаимодействия агентов самыми сложными являются следующие моменты:

• посредством чего должно происходить взаимодействие;

• кому нужно взаимодействовать;

• когда должно происходить взаимодействие;

• какой формат должно иметь взаимодействие.

Ответы на эти вопросы должны быть изначально заложены в проект агентов. Теперь осталось лишь определиться с физической реализацией взаимодействия агентов. Для этого можно воспользоваться библиотеками, которые поддерживают параллелизм. Наконец, что касается проблем синхронизации, то с ними можно легко справиться, поскольку именно логическое обоснование агента сообщает ему, когда он может и должен выполнять действия. Следовательно, сложные вопросы синхронизации сводятся к простым вопросам сотрудничества. Благодаря этому упрощается и задача разработчика в целом. Теперь рассмотрим базовую структуру агента и возможности его реализации в С++.

Реализация агентов в С++

Рассмотрим упрощенный вариант предыдущего примера агента и продемонстрируем, как его можно реализовать в С++. Цель этого агента — составлять график отпусков и выполнять подготовку к поездкам владельца компании ABC Auto Repair Company. В компании работают десятки служащих, и поэтому у хозяина нет времени заботиться о проведении своего очередного отпуска. Кроме того, если хозяин не получит определенного объема прибыли, об отпуске не может быть и речи. Поэтому владельцу компании хотелось бы, чтобы агент распланировал его отпуска равномерно по всему голу при условии процветания фирмы. По мнению владельца компании, главное, чтобы агент работал автоматически, т.е. после инсталляции на компьютере о нем можно было не беспокоиться. Когда агент определит, что подошло время для отпуска, он должен предъявить план проведения отпуска, забронировать места в отеле и проездные билеты, а затем по электронной почте представить хозяину маршрут. Владелец должен побеспокоиться только о формировании задания для агента. Он должен указать, куда желает отправиться и какой объем прибыли необходимо получить, чтобы запланированная поездка состоялась. Теперь рассмотрим, как можно спроектировать такой агент. Вспомним, что рациональный компонент (см. рис. 12.1) класса агента состоит из когнитивных структур данных и методов рассуждений (стратегий логического вывода). Когнитивные структуры данных (CDS) позволяют хранить убеждения, предположения, знания, заблуждения, факты и пр. Для доступа к этим когнитивным структурам данных в процессе решения проблемы и выполнения задач класс агента использует стратегии логического вывода. Для реализации CDS-структур данных и методов построения рассуждений можно использовать ряд контейнерных классов и алгоритмов, которые содержатся в стандартной библиотеке С++.

Типы данных предположений и структуры убеждений

Этот агент обладает убеждениями о показателях авторемонтной мастерской. Убеждения составляют информацию о том, сколько клиентов обслуживается в час, какова загрузка ремонтных секций в день и общий объем продаж (запчастей и услуг) за некоторый период времени. Кроме того, агент знает, что владелец фирмы любит путешествовать только автобусами. Поэтому агент хранит информацию об автобусных маршрутах, которые могут для отпускника оказаться привлекательными. В программе, насыщенной математическими вычислениями, используются в основном целочисленные значения и числа с плавающей точкой. В графических программах участвуют пиксели, линии, цвета, геометрические фигуры и пр. В агентно-ориентированной программе основными типами данных являются предположения, правила, утверждения, литералы и строки. Для построения типов данных, свойственных агентно-ориентированному программированию, мы будем опираться на объектно-ориентированную поддержку, прелусмотренную в С++. Итак, рассмотрим объявление класса предположения (листинг 12.1).

// Листинг 12.1. Объявление класса предположения

template<class C> class proposition {

//...

protected:

list<C> UniverseOfDiscourse;

bool TruthValue; public-virtual bool operator(void) = О;

bool operator&&(proposition &X);

bool operator||(proposition &X);

bool operator||(bool X);

bool operator&&(bool X);

operator void*;

bool operator!(void);

bool possible(proposition &X);

bool necessary(proposition &X);

void universe(list<C> &X);

//.. .

};

Предположение представляет собой утверждение, тема (предмет) которого подтверждается или отрицается предикатом. Предположение может принять значение ИСТИНА или ЛОЖЬ. Предположение можно использовать для фиксации одного убеждения, которое есть у агента. Кроме того, в качестве предположения может быть представлена некоторая другая информация, которая предлагается агенту и которую агент необязательно воспринимает как убеждение. Для представления предположений используется когнитивный тип данных, который должен быть таким же функциональным в агентно-ориентированной программе, как целочисленные и вещественные типы данных в математических программах. Поэтому, чтобы обеспечить некоторые основные операторы, применимые к предположениям, мы используем C++-средства перегрузки операторов. В табл. 12.4 показано, как такие операторы преобразуются в логические.