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

Аннотация

Актуальность. Эффективные математические модели организации параллельных вычислений используют принципы одновременного выполнения правил над независимыми фрагментами данных, а также методы обработки символьной информации как объединяющей категории для различных типов данных. Продукционные системы в нотации А.А. Маркова (мл.) имеют необходимый потенциал для создания таких моделей, но стандартная схема управления в них является последовательной, что ограничивает применение таких продукционных систем в прикладных задачах. В связи с этим актуальной является задача синтеза модифицированных продукционных систем и схем управления в них,  направленных на распараллеливание вычислительного процесса обработки символьной информации. Целью исследования является уменьшение времени работы модифицированной продукционной модели за счет двунаправленной обработки цепочек символов. Метод решения основан на применении принципов двунаправленного грамматического разбора из теории синтаксического анализа, компиляции в алгоритмических продукционных системах и состоит в модификации стандартной схемы продукционных вычислений А.А. Маркова. Это достигается введением продукций с однократным срабатыванием, двунаправленным доступом к обрабатываемой строке, декомпозицией исходной системы на секции, введением набора охранных условий для разрешения конфликтов. Продукционная модель реализована для типовых задач символьной обработки: разметка слова и обращения слова. Результаты. Разработана структура модифицированной продукционной системы, преодолевающая ограничение стандартной схемы А.А. Маркова – последовательный характер вычислений. В результате проведенного исследования была создана формальная модель последовательно-параллельной обработки слов, разработана модифицированная схема управления и показана корректность вычислений. Моделирование на типовых задачах показало уменьшение времени обработки слов практически в 2 раза, что было достигнуто, в том числе, за счет исключения обязательного возврата на первую продукцию в схеме управления и агрегации продукций в секции. Заключение. Проведенное исследование подтвердило возможность и эффективность трансформации последовательных продукционных систем А.А. Маркова в последовательно-параллельные продукционные модели с выдачей корректного результата. Перспективная область применения – методы и программно-аппаратные средства в однородных вычислительных системах для высокопроизводительной обработки символьной информации