РАСШИРЕННАЯ ПРОДУКЦИОННАЯ МАШИНА ВЫВОДА ДЛЯ РЕАЛИЗАЦИИ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ

Аннотация

Актуальность. В работе развивается теоретический подход организации параллельных вычислений на основе продукционной модели управления потоком данных. Продукционная пара- дигма параллельных вычислений имеет необходимые условия построения новых архитектур и ор- ганизации высокопроизводительных параллельных вычислений. Рассматриваются продукционные системы, управляющие наборами левых частей продукций (образцами). Цель – повышение эффек- тивности параллельного вывода решений за счет сокращения непродуктивных затрат времени на перебор возможных альтернатив в пространстве графа вывода. Метод решения основан на соз- дании расширенной машины символьного вывода для реализации параллельных вычислений. Маши- на символьного вывода – это абстрактная система, систематизирующая продукционный вывод как последовательность четырех вычислительно-поисковых этапов. Машина вывода задает об- щий вид однородной вычислительной системы. Главное отличие – декомпозиция базы продукцион- ных правил на отдельные подмножества на основе алгебры продукций и структуризации отноше- ний между продукциями. Вместо единой «плоской» структуры предлагается базу продукций де- композировать на части – ввести систему независимых подмножеств продукций. Параллельный вывод реализуется по отдельным подмножествам без потери общности, при этом перебор воз- можных альтернатив является сокращенным. Каждое подмножество продукций имеет специ- альное слово-маркер, по значению которого активизируется только одно подмножество продук- ций. Оно загружается в операционную часть однородной вычислительной системы для параллель- ного исполнения. Результаты. Показано, что количественные оценки сокращения времени вывода зависят от общего числа продукций, количества образуемых подмножеств и их размера. Модели- рование показало, что даже простейшая декомпозиция на два подмножества (одно подмножест- во состоит из 2-х продукций) дает временной выигрыш (1,07-1,52) раз, пропорциональный общему числу продукций. Выводы. Построенная расширенная машина символьного вывода является осно- вой для последующего создания архитектуры однородной вычислительной системы с комбинацией централизованного и локального управления, что позволяет вычислительным блокам однородной операционной части параллельно работать без избыточного обращения к обшей памяти.