РАСШИРЕННАЯ ПРОДУКЦИОННАЯ МАШИНА ВЫВОДА ДЛЯ РЕАЛИЗАЦИИ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ
Ключевые слова:
Продукционная система, параллельные вычисления, независимые подмножества продукций, конфликтные словаАннотация
Актуальность. В работе развивается теоретический подход организации параллельных
вычислений на основе продукционной модели управления потоком данных. Продукционная пара-
дигма параллельных вычислений имеет необходимые условия построения новых архитектур и ор-
ганизации высокопроизводительных параллельных вычислений. Рассматриваются продукционные
системы, управляющие наборами левых частей продукций (образцами). Цель – повышение эффек-
тивности параллельного вывода решений за счет сокращения непродуктивных затрат времени на
перебор возможных альтернатив в пространстве графа вывода. Метод решения основан на соз-
дании расширенной машины символьного вывода для реализации параллельных вычислений. Маши-
на символьного вывода – это абстрактная система, систематизирующая продукционный вывод
как последовательность четырех вычислительно-поисковых этапов. Машина вывода задает об-
щий вид однородной вычислительной системы. Главное отличие – декомпозиция базы продукцион-
ных правил на отдельные подмножества на основе алгебры продукций и структуризации отноше-
ний между продукциями. Вместо единой «плоской» структуры предлагается базу продукций де-
композировать на части – ввести систему независимых подмножеств продукций. Параллельный
вывод реализуется по отдельным подмножествам без потери общности, при этом перебор воз-
можных альтернатив является сокращенным. Каждое подмножество продукций имеет специ-
альное слово-маркер, по значению которого активизируется только одно подмножество продук-
ций. Оно загружается в операционную часть однородной вычислительной системы для параллель-
ного исполнения. Результаты. Показано, что количественные оценки сокращения времени вывода
зависят от общего числа продукций, количества образуемых подмножеств и их размера. Модели-
рование показало, что даже простейшая декомпозиция на два подмножества (одно подмножест-
во состоит из 2-х продукций) дает временной выигрыш (1,07-1,52) раз, пропорциональный общему
числу продукций. Выводы. Построенная расширенная машина символьного вывода является осно-
вой для последующего создания архитектуры однородной вычислительной системы с комбинацией
централизованного и локального управления, что позволяет вычислительным блокам однородной
операционной части параллельно работать без избыточного обращения к обшей памяти.
