И.Л. Артемьева, М.Б. Тютюнник

МОДУЛЬНАЯ СИСТЕМА КОНФЛЮЕНТНЫХ ПРОДУКЦИЙ ДЛЯ МНОГОПРОЦЕССОРНОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ^*

В данной работе описывается модульная система параллельного программирования на основе конфлюэнтных продукций. Преимуществом такой системы является то, что результат вычислений не зависит от порядка применения правил и вызова модулей.

Введение

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

Характеристики языка системы продукций

Исследования по онтологиям и разработке на их основе СОЗ позволили сформулировать требования к языку конфлюентной системы продукций. Язык должен:

- позволять представлять метод решения задачи как совокупность методов решения подзадач, описываемых модулями; в любом модуле должен быть задан его интерфейс, т.е. описание данных, который модуль позволяет использовать другим модулем, либо который требуются для его работы; должна быть возможность явного задания условия вызова модуля, то есть среди правил могут существовать правила, правая часть которых есть вызов модуля;

- позволять использовать операции над числовыми данными и множествами, а также ограниченные логические и математические кванторы, являющиеся аналогами циклов в правилах;

- допускать правила, зависящие от параметров (схемы правил); схема задает множество правил, то есть ее можно рассматривать как аналог подпрограммы в алгоритмическом языке.

Распараллеливание процесса решения задач

Программная система, входом которой является программа на некотором языке, является языковым процессором этого языка. Существуют два класса языковых процессоров: интерпретаторы и компиляторы. Описываемая в работе программная система является компилятором. Модульная программа, записанная на входном языке системы, поступает на вход анализатора, который проверяет синтаксическую и семантическую правильность записи правил и формирует внутреннее представление программы. Одним из компонентов внутреннего представления является информационный граф модульной программы. Генератор объектного кода анализирует свойства информационного графа и строит объектную программу, реализующую параллельную схему для метода решения задачи, записанного на входном языке. Таким образом, компонентами программной системы являются лексический, синтаксический и семантический анализаторы, подсистема построения информационного графа, подсистема анализа информационного графа и выбора схемы распараллеливания процесса решения задач, генератор объектного кода.

Информационный граф модульной программы является двухуровневым, верхний уровень которого представляет собой граф программы, состоящей из модулей, а нижний уровень описывает графы каждого модуля, состоящего из правил. Верхний уровень описывает связи между модулями по передаче данных, а нижний – связи между правилами.

Можно выделить три группы схем распараллеливания процесса логического вывода. В схемах первой группы для распараллеливания вычислений используется верхний уровень графа, то есть эти схемы используются при распараллеливании вычислений на уровне модулей программы. В схемах второй группы для распараллеливания используются связи между правилами или множествами правил внутри одного модуля; эти связи описывает информационный граф модуля. Схемы третьей группы используются при распараллеливании вычислений внутри отдельного правила.

Естественной схемой распараллеливания процесса решения задач является схема, в которой каждый параллельный процесс соответствует одному правилу программы. Управляющий процесс координирует работу зависимых, передавая и принимая от них данные. Такая схема реализована в прототипе системы. Эксперименты с прототипом показали, что для некоторых классов задач время решения на многопроцессорной системе близко к n/k, где n – время решения задачи на однопроцессорной ЭВМ, а k - число процессоров.