Мивары: 25 лет создания искусственного интеллекта - [53]

6.3.3. Описание реализованного алгоритма распараллеливания вычислений

В настоящий момент распараллеливание вычислений реализовано в следующем виде:

1. на вход программы так же подаются список переменных и список правил. Программа формирует массив из известных параметров и правил;

2. основной процесс разбивает общее количество правил на доступное ему количество процессов;

3. далее основной процесс высылает каждому доступному процессу правило (или несколько правил) и массив известных параметров;

4. каждый отдельный процесс просматривает правило и, если ему хватает известных параметров для расчета, то производит расчет;

5. после окончания расчета доступный процесс отсылает головному результат. Если расчет был невозможен, то параметр поиска возвращается ненайденным;

6. после того как основной процесс дождется окончания работы всех доступных процессов, он проверяет, найдены ли искомые переменные. Если не найдены, то заново идет рассылка.

Программа перестает работать, если:

· найдены все искомые параметры;

· все доступные процессы выполнили работу, но новых параметров не было найдено.

Блок-схема работы параллельной программы представлена на рисунке 73.

Рисунок 73 – Блок-схема работы параллельной программы

6.3.4. Особенности программной реализации ПК MivarLogicParallel

ПК MivarLogicParallel написан на стандартизированном процедурном языке Си, разработанном для программирования в операционной системе Unix. Это обусловлено тем, что для приложения типа ПК MivarLogicParallel необходимы такие языковые особенности, характерные для языка Си, как:

· простая языковая база, из которой вынесены в библиотеки многие существенные возможности типа математических функций или функций управления файлами;

· ориентация на процедурное программирование, обеспечивающая удобство применения структурного стиля программирования;

· система типов, предохраняющая от бессмысленных операций;

· непосредственный доступ к памяти компьютера через использование указателей;

· передача параметров в функцию по значению, а не по ссылке (при этом передача по ссылке выполняется с помощью указателей).

Для реализации многопоточности при разработке MivarLogicParallel использовалась технология The Message Passing Interface (MPI). Эта технология – это хорошо стандартизованный механизм для построения параллельных программ в модели обмена сообщениями.

Большинство современных реализаций MPI поддерживают версию 1.1. В настоящее время стандарт MPI версии 2.0 используется в современных реализациях, но с ограничениями, так как некоторые функции могут быть не реализованы или реализованы только частично.

Отметим, что в MPI 1.1 поддерживаются следующие функции:

1. передача и получение сообщений между отдельными процессами;

2. коллективные взаимодействия процессов;

3. взаимодействия в группах процессов;

4. реализация топологий процессов.

В следующей версии MPI 2.0 дополнительно поддерживаются функции:

1. динамическое порождение процессов и управление ими;

2. односторонние коммуникации (Get/Put);

3. параллельный ввод и вывод;

4. расширенные коллективные операции (процессы могут выполнять коллективные операции не только внутри одного коммуникатора, но и в рамках нескольких).

6.3.5. Описание программной реализации в ПК MivarLogicParallel распараллеливания вычислений при нахождении маршрута логического вывода по линейному матричному методу

Алгоритм работы MivarLogicParallel включает три основных этапа.

Этап 1. Из входного xml-документа главный процесс root с идентификационным номером "0" считывает данные матрицы параметров и правил: размерность, имена и идентификационные номера параметров, значения (если они известны), правила, их связь с параметрами.

Для работы с параметрами создана структура Param, содержащая четыре поля, имеющих следующий смысл:

· уникальный идентификатор параметра;

· значение параметра;

· флаг, равный единице, если значение параметра известно, нулю – в иных случаях;

· имя параметра.

Для выполнения работы с правилами была построена минимальная структура Rules, содержащая всего четыре поля, имеющих следующий смысл:

· количество неизвестных параметров, которые используются в правиле;

· номер определяемого данным правилом параметра (считается, что все правила имеют вид a1 = a2*a3*…*an, где a1 – определяемый (выходной, искомый) параметр, * – некоторые действия, a2, a3…an – прочие (входные) параметры, используемые в данном правиле);

· массив, содержащий единицы на позициях, соответствующих номерам известных параметров, нули – на позициях неизвестных параметров;

· массив, содержащий единицы на позициях, соответствующих номерам используемых данным правилом параметров, нули – на остальных.

Root-процесс просматривает все параметры и, если находит те, значения которых известны, записывает их номера в массив curr и рассылает их вместе с правилами всем остальным процессам.

Этап 2. Каждый процесс получает массив, состоящий из номеров известных параметров, и массив правил. Процесс выбирает из массива правил свой блок, равный M/size (где M – общее число правил, size – количество процессов), с которым далее будет иметь дело.