Разработка и исследование продукционной системы параллельного программирования

Тютюнник, Михаил Борисович

Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Разработка и исследование продукционной системы параллельного программирования

кандидата технических наук: Тютюнник, Михаил Борисович
город: Владивосток
год: 2010
специальность ВАК РФ: 05.13.11

Диссертация по информатике, вычислительной технике и управлению на тему «Разработка и исследование продукционной системы параллельного программирования»

Автореферат диссертации по теме "Разработка и исследование продукционной системы параллельного программирования"

На правах рукописи

Тютюнник Михаил Борисович

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

05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат

диссертации на соискание ученой степени кандидата технических наук

Владивосток 2010

Работа выполнена в лаборатории интеллектуальных систем Института автоматики и процессов управления Дальневосточного отделения РАН.

Научный руководитель доктор технических наук

Артемьева Ирина Леонидовна

Официальные оппоненты доктор физико-математических наук, профессор

Касьянов Виктор Николаевич

Защита состоится "Д" февраля 2011 г. в 12 часов на заседании диссертационного совета Д 005.007.01 при Институте автоматики и процессов управления ДВО РАН по адресу: 690041, г. Владивосток, ул. Радио, д.5.

С диссертацией можно ознакомиться в библиотеке Института автоматики и процессов управления Дальневосточного отделения РАН.

Автореферат разослан «¿X» декабря 2010 г.

Ученый секретарь

диссертационного совета Д 005.007.01

кандидат технических наук Харитонов Дмитрий Иванович

Ведущая организация Московский Энергетический Институт

(Технический Университет), г. Москва

к.т.н.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

1 Конфлюэнтные системы также называются коммутативными или системами, имеющими неподвижную точку.

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

Большой вклад в разработку моделей систем продукций, методов организации процесса логического вывода для таких систем, а также методов распараллеливания вывода для них внесли Д.А. Поспелов, В.Н. Вагин, Г.С. Осипов, И.П. Кузнецов, А.П. Еремеев, A.C. Клещев, B.JI. Стефанюк, A.B. Жожикашвили, Ю.А. Загорулько, Т.М.Яхно, A.C. Нариньяни, S. Vere, D.B. Lenat и многие другие.

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

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

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

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

Для достижения поставленной цели в диссертационной работе необходимо решить следующие задачи:

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

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

3. Разработать алгоритм управления выбором схем распараллеливания в процессе логического вывода.

4. Разработать методы реализации системы параллельного программирования.

5. Провести экспериментальное исследование системы параллельного программирования на реальных примерах.

Методы исследования. Для решения указанных задач использовались элементы математической логики, теории алгоритмов и исчислений, а также методы системного программирования, объектно-ориентированного программирования, параллельного программирования.

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

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

■ в рамках предложенной модели впервые разработаны схемы распараллеливания процесса логического вывода для системы конфлюэнтных продукций; получены оценки времени исполнения при различных схемах распараллеливания;

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

Практическая ценность работы состоит в том, что разработана система параллельного программирования, которая может быть использована при создании параллельных систем, основанных на правилах, предназначенных для решения задач разных классов на многоядерных персональных компьютерах, а также на кластерах.

Научные результаты диссертационной работы использованы в Дальневосточном государственном университете в учебном процессе при чтении курса лекций по спецдисциплинам «Системы искусственного интеллекта» и «Рекурсивно-логическое программирование» студентам специальности 010503.65 - «Математическое обеспечение и администрирование информационных систем» и выполнении практических заданий по ним.

Результаты работы нашли применение в научных исследованиях сотрудников кафедры ПО ЭВМ Института математики и компьютерных наук ДВГУ и сотрудников лаборатории интеллектуальных систем ИАПУ ДВО РАН.

Получено свидетельство о государственной регистрации программы для ЭВМ №2010614810 «Распараллеливающий компилятор для языка, основанного на правилах». Авторы: Артемьева И.Л., Тютюнник М.Б. Зарегистрировано в Реестре программ для ЭВМ 23 июля 2010 г.

2008, 2010), Международной конференции «Knowledge-Dialog-Solution» (Varna, Bulgaria, 2008), Международной конференции «First Russia and Pacific Conference on Computer Technology and Applications» (Vladivostok, Russia, 2010), Научной сессии МИФИ (Москва, 2006, 2007, 2008), Демидовской конференции «Фундаментальные и прикладные проблемы современной физики» (Москва, 2006), Международной научно-технической конференции «Искусственный интеллект. Интеллектуальные и многопроцессорные системы» (Кацивели, Украина, 2006, 2007), совместных семинарах отдела интеллектуальных систем ИАПУ ДВО РАН и базовой кафедры программного обеспечения ЭВМ ДВГУ при ИАПУ ДВО РАН (2005-2010).

Публикация результатов работы. По материалам диссертации опубликовано 28 печатных работ, из них 2 статьи в журналах, входящих в перечень ВАК (работы [12,15]). Основные публикации приведены в автореферате.

Структура и объём работы. Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы, включающего 100 наименований, и приложений. Основная часть работы изложена на 127 страницах, включая 18 рисунков, 14 диаграмм и 10 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

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

Глава 2 диссертации содержит описание модели расширенного языка, основанного на правилах. При разработке модели расширенного языка были проанализированы созданные в Институте автоматики и процессов управления ДВО РАН модель реляционных конфлюэнтных продукций, модель недоопределенных продукций, модель языка МАКРОРЕПРО, модель языка с ограниченными кванторами и основанные на этих моделях продукционные языки, а также класс языков прикладной логики, предназначенных для определения свойств различных предметных областей и используемых при создании систем, основанных на знаниях.

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

Все используемые в правилах предметные, функциональные и предикатные имена являются терминами предметной области. Все имена имеют сорт, который задается при описании имени. Значение имени может быть точным либо неточным, что задается характеристикой «определенность значения».

Правило (продукция) состоит из префикса и тела. Префикс есть последовательность описаний свободных переменных (vi :ti)(v2:t2)...(vm:t,n), где (Vj:t,) - описание переменной, для всех i=l,...,m V[ - переменная, tj - терм. Терм t] не содержит свободных переменных. Для i=2,..., ш свободными переменными терма t; могут быть только переменные V|, V2,...,Vj.]. Все переменные Vi, v2,..., vm попарно различны. Префикс может отсутствовать. Тело правила может быть одного из следующих видов:

(1) <префикс> Р Opl(AFi) & Opl(AF2) & ... & Opl(AFxl) & Op2(Fbt'i) & Op2(F2,t'î) & ... & Op2(Fx2;t'x2) & Op3(I,,t",) & Op3(I2,t"2) & ... & ОрЗ^зД'^) & S„ ...,

Sb где P - условие правила, задаваемое формулой, Opl(AF,) & Opl(AF2) & ... & Opl(AFx0 & Op2(F,,f,) & Op2(F2,t'2) & ... & Орг^Д'хг) & Op3(I,,t",) & Op3(I2,t"2) & ... & ОрЗОхзД"^) & Si, ..., Sk - следствие правила, где Opl(AF|) & Opl(AF2) & ... & Opl(AFxi) - операторы формирования кортежей, определяемые формулами AFb ..., AFxi, Op2(Fi,t'i) & Op2(F2,t'2) & ... & Op2(Fx2,t'x2) - операторы формирования кортежей, определяемые функциональными термами Fb ..., Fx2 и значениями, представленными термами t'i, ..., t'^, соответственно, Op3(Ii,t"i) & Op3(I2,t"2) & ... & ОрЗ^'й) - операторы исключения вариантов, определяемые предметными именами Ii, ..., 1хз и значениями, представленными термами t"i, ..., t"^, соответственно, Sb ..., St - ограниченные кванторные операторы вида (& (v : t) f), причем f является конъюнкцией операторов, вид которых определен выше.

(2) <префикс> Р —> Mod(Sb ..., Sk), где Р - формула, Mod(Sb ..., Sk) - вызов модуля с именем Mod, которому передаются параметры - значения Sb ..., Sk; каждое S, является термом, значение которого есть имя.

Схема правила имеет вид:

(3)NameSch([.KOHCT]wb [,KOHCT]w2,..., [,KOHCT]w„): rule, где

NameSch-имя схемы, wb w2,..., wn - формальные параметры схемы, rule - тело

схемы (правило вида 1 или 2). Запись «[.КОНСТ]» означает, что «.КОНСТ» может отсутствовать. Отсутствие .КОНСТ означает, что соответствующим фактическим параметром может быть некоторое имя; в противном случае фактическим параметром может быть константа. Все переменные-параметры схемы должны использоваться в теле схемы.

Конкретизация схемы имеет вид:

(4) NameSch(zwb zw2, ..., zwn), где NameSch - имя схемы, zwi, zw2, ..., zw„ -термы - фактические параметры схемы. Схема правила является аналогом описания подпрограммы, а конкретизация схемы - аналогом вызова подпрограммы.

Логическим модулем называется конструкция вида <ModName, CallModsName, GlobD, LocD, R>, где ModName - имя модуля, CallModsName - множество имен вызываемых модулей, GlobD - множество описаний глобальных имен, LocD - множество описаний локальных имен, R- множество правил, схем и конкретизации схем.

Процесс логического вывода (ПЛВ) определяется как исчисление со входом. Рабочая среда модуля характеризуется множеством состояний. Состояние рабочей среды модуля Sj есть множество пар вида <n, value,(п)>, где п - имя, value,(n) - значение, сопоставленное этому имени в состоянии 5,. Начальное состояние 5i формируется в результате ввода исходных данных. Каждое следующее состояние получается из предыдущего в результате применения некоторого правила, конкретизации схемы или вызова модуля.

Для всех имен п, определенность значения которых есть "точное", выполнено: value,(n) = valuej(n) = valuei(n) для любых i и j. Для всех предметных имен, определенность значения которых "неточное", выполнено: valuc,+i(n) с value,(n) с value,(n) для любого i. Сопоставленное такому имени п неточное значение valuej(n) есть множество вариантов {Ci,c2,...,cm} (неточное значение), где с, (1 < i < т) - значение, принадлежащее множеству, задаваемому сортом имени п. В процессе логического вывода из этого множества исключаются варианты. Если при вводе исходных данных имени п не сопоставлено значение, то будем считать, что это значение есть ii ("неопределенное значение"). Такое значение не может изменяться в процессе логического вывода.

Для всех функциональных и предикатных имен, определенность значения которых "неточное", выполнено: valuej(n) с valuej+i(n) для любого i. Сопоставленное имени п неточное значение valuc,(n) есть множество кортежей {(Ci,C2,...,Cn,:Co)}, где с, (1 < i < ш) - значение, принадлежащее множеству, задаваемому сортом аргумента функции или предиката, указанному при описании имени п; для функционального имени с0 - значение, принадлежащее множеству, задаваемому сортом результата функции; для предикатного имени с0 € {истина, ложь}. Из приведенного соотношения valuei(n) с valuei+](n) следует, что на каждом шаге логического вывода к множеству кортежей value, (п) могут быть добавлены новые кортежи. При вводе исходных данных имени п может быть сопоставлено пустое множество кортежей. Будем обозначать argj(n) = {(сьс2,...,ст) I (ci,c2,...,cm:c0) e valuei(n)}.

Обозначим £, - подстановку вариантов вместо предметных имен, входящих в терм или формулу, 0 = {v^cj, ..., vnl/cm} - подстановка значений вместе переменных, Jsi((t, Е), 0) - значение терма или формулы t при замене предметных имен значениями, задаваемыми подстановкой !;, а переменных - значениями, задаваемыми подстановкой 0. Обозначим Hj - множество подстановок возможных при состоянии 6i. Если терм или формула t содержит предметные имена, определенность значения которых "неточное", то множество {J&((t, 9) ] £eEi} содержит более одного элемента. Оно задает множество вариантов значений терма или формулы. Зафиксируем имя п и вариант var е valuei(n). Обозначим Ej(n,var) - подмножество подстановок <;, возможных при состоянии 8,; имени п во всех подстановках сопоставлен вариант var.

Правило вида (1) (v,:ti)(v2:t2)...(vm:tj Р -> Opl(AF,) & Opl(AF2) & ... & Opl(AFx,) & Op2(Fbt'i) & Op2(F2,t'2) & ... & Op2(Fx2,t'x2) & Op3(Ibt",) & Op3(I2,t"2) & ... & Op3(Ix3,t"x3) & Si, ..., Sk применимо при текущем состоянии 5j рабочей среды, если выполнены следующие условия: для всех j, l<j<m множество {Jsi((tj, £), 0) I Е,еЕ,} состоит из одного элемента; существует подстановка значений вместо переменных, определяемая префиксом правила и состоянием 5|, при которой истинно условие правила; могут быть произведены изменения состояния рабочей среды.

В результате применения правила состояние рабочей среды изменяется в соответствии с семантикой формул Opl(AF[) & Opl(AF2) & ... & Opl(AFxi) & Op2(Fbt'i) & Op2(F2,t'2) & ... & Орг^,^) & Op3(I„t",) & Op3(I2,t"2) & ... & Op3(IX3,t"x3) & S,, ..., Sk. Опишем правила изменения состояния рабочей среды в зависимости от вида компонентов следствия.

Рассмотрим AFj = p(t|,...,tk), причем при описании предикатного имени р определенность значения С = неточное. Изменения состояния рабочей среды могут быть произведены при подстановке 0, если J6i(p(ti,...,tk), 0) = О. В этом случае valuei+i(p) = valuc,(p) и {(JSi((tb...,tk), 0): true)}, т.е. к множеству кортежей отношения с именем р добавляется кортеж, полученный из аргументов атомной формулы в результате выполнения подстановки 0, причем отношение с именем р на этом кортеже истинно. Будем говорить, что при подстановке 0 может быть совершен переход в противоречивое состояние, если -^¡(р^,...,^), 0) = false. В этом случае выполнение модуля завершается по противоречию.

Рассмотрим AFj = p(tb...,tk), причем при описании предикатного имени р определенность значения С = неточное. Изменения состояния рабочей среды могут быть произведены при подстановке 0, если J5i(p(ti,...,tk), 0) = П. В этом случае value,+i(p) = valuei(p) vj {(J5i((t|,...,tk), 0): false)}, т.е. к множеству кортежей отношения с именем р

добавляется кортеж, полученный из аргументов атомной формулы в результате выполнения подстановки 6, причем отношение с именем р на этом кортеже ложно. Будем говорить, что при подстановке 0 может быть совершен переход в противоречивое

состояние, если JsiCp(t.......... 0) = true. В этом случае выполнение модуля завершается

по противоречию.

Пусть Opj(Fj,t'j) имеет вид f(ti,...,tk) = t'j, причем при описании функционального имени f определенность значения С = неточное. Изменения состояния рабочей среды могут быть произведены при подстановке 0, если J6i(f(ti,...,tk) = t'j), 0) = П. В этом случае valuej+](f) = valuej(f) u {(Jsi((ti,...,tk), 0): Jsi(t'j, 0)}, т.е. к множеству кортежей функции с именем f добавляется кортеж, который образуют значения аргументов функционального терма, полученные в результате выполнения подстановки 0, и соответствующее этому кортежу значение функции с именем f, полученное из терма t'j в результате выполнения подстановки 0. Будем говорить, что при подстановке 9 может быть совершен переход в противоречивое состояние, если J5i(f(ti,--A), 0) * Js;(t'j, 0). В этом случае выполнение модуля завершается по противоречию.

Рассмотрим оператор исключения вариантов Op3(Ij,t"j), в котором использовано предметное имя Ij, при описании которого определенность значения С = неточное. Изменения состояния рабочей среды могут быть произведены при подстановке 0, если вариант Ja(t"j, 0) е valuei(Ij). В этом случае valuej+i(Ij) = value^Ij) \ {J6i(t"j, 0)}, т.е. в результате из множества вариантов, сопоставленных имени Ij в состоянии 5„ исключен тот вариант, который задан термом t"j. Будем говорить, что при подстановке 0 может быть совершен переход в противоречивое состояние, если value^Ij) \ {J5l(t"j, 0)} = 0. В этом случае выполнение модуля завершается по противоречию.

Рассмотрим Sj = (& (v: t) f)> где формула f не содержит операторов исключения вариантов. Тогда для каждого значения переменной v, принадлежащего множеству (Ja(t),0), состояние рабочей среды модуля изменяется в соответствии с семантикой операторов формирования кортежей.

Рассмотрим Sj = (& (v: t) f), где формула f содержит операторы исключения вариантов. Тогда для каждого значения переменной v, принадлежащего множеству (Jsi(t),0), состояние рабочей среды модуля изменяется в соответствии с семантикой выполнения таких операторов.

Правило вида (2) применимо при текущем состоянии 8, рабочей среды, если выполнены следующие условия: для всех j, l<j<m множество {J5l((tj, q), 0) | qeE,} состоит из одного элемента; существует подстановка значений вместо переменных, определяемая префиксом правила и состоянием 8j, при которой истинно условие правила. В результате выполнения правила происходит вызов модуля Mod, которому передаются значения, сопоставленные именам Sb ..., Sk. Эти значения входят в состояние 8i для вызываемого модуля. В результате выполнения модуля значения, сопоставленные именам Si.....Sk в состоянии 5j+i вызывающего модуля будут совпадать со значениями, сопоставленными этим именам в заключительном состоянии для модуля Mod.

Процесс логического вывода завершается, если достигнуто такое состояние 5Е (заключительное состояние), в котором не применимо ни одно из правил.

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

Теорема 1 (о конфлюэнтноети). Пусть Б, Б', Б" - состояния процесса логического вывода. Если существуют выводы Б => Б' и 8 => Б", то существует непротиворечивое состояние ПЛВ 8"' такое, что Б => 8' Б'" и Б => 8" => 8"'.

Теорема 2 (о конфлюэнтноети при наличии противоречия). Пусть Бр -противоречивое состояние ПЛВ. Тогда если существуют выводы 8 => 8' и 8 => 8", то существует вывод 8 => Э" => Эр.

Глава 3 диссертации содержит описание схем распараллеливания процесса логического вывода.

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

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

Рассмотрим схему распараллеливания процесса логического вывода на основе свойств информационного графа.

Управляющий процесс: НАЧАЛО вычислений: ц(Рг1 = число доступных процессов; Рж = 0. Блок 1. ЦИКЛ: Пока есть ¡СигРаге^эАф] = 0 или Р„ ф 0, делаем: Блок 2; Блок 3. Конец ЦИКЛА. Блок 4. КОНЕЦ вычислений.

Здесь Рг - множество свободных процессов, Р„ - множество занятых процессов, ц(Р) - число элементов множества Р.

Блок 1 (Запускаем все правила, соответствующие корневым вершинам): Для каждого свободного процесса] из Рг делаем:

Для каждого элемента 1 массива ¡СигРагеЩвАг: Если ¡СигРагсгизАф] = О, то Бегкад,, ¡,.]); ¡СигРагетзАф] = -1; Рг = Рг\ Ц}; Р„ = Р„и 0). Конец блока 1.

Здесь ¡СигРаге^эАг - копия ¡РагегЛзАг, при этом если в ИГ есть циклы, то значения элементов массива ¡СигРагегЛзАг такие: если ¡ЬоорЯоо1Аг[1] = 2, то

¡СигРагстзАф'] = ¡ЬоорАф']. ¡Ьоор1(оо1Аг - массив целых чисел размерности ц(Пт), в котором элемент 1 массива равен 2, если правило 1 является входом в цикл, равен 1 -если правило 1 принадлежит циклу, 0 - не принадлежит циклу. ¡ЬоорАг - массив целых чисел размерности ц(Пт), в котором элемент 1 массива равен -1, если правило 1 не принадлежит циклу, 0 - принадлежит циклу, и равен количеству прямых предков, не принадлежащих циклу, при условии, что правило \ является входом в цикл. ¡РагеШэАг - массив целых чисел размерности ц(Пт), в котором элемент 1 массива равен количеству прямых предков правила ¡.

Блок 2 (Принимаем результирующие 3.1. Если 1псМа1пх[1,к] = 1,

данные и синхронизируем их):

1. Яесу(г, 1, .0; Р„ = Рж \ 0>; Рг = Рг и Ш-

2. ¡СигРагетвАгШ = -2.

3. Для всех вершин к таких, что ¡СигРагеШзАг[к] > 0, делаем:

то ¡CurParentsAr[k]

iCurParentsAr[kJ -1; 3.2. Если iLooptAr[i] > 0, и iCurParentsAr[k] = -2, и iLoopAr[k] > 0, и THEN(i) n IF(k) # 0, то ¡ChangedLoopArfk] = 1.

4. Data = Data uZ;

Конец блока 2.

Recv(Z, i, j) принимает из процесса j набор данных Z, которые являются результатом вычисления правила i. iChangedLoopAr - массив целых чисел размерности цСПД в котором элемент i массива равен 1, если циклическое правило i было сначала вычислено, а потом для объектов, входящих в его условие, появились новые значения; иначе элемент i равен 0. IncMatrix - двумерный массив размерности ц(Пт) х ц(Пт), где элемент (ij) матрицы равен 1, если j-тое правило является прямым потомком i-того правила, иначе элемент равен 0.

Блок 3 (Загружаем свободные процессы правилами, готовыми к вычислению):

Для каждого свободного процесса ] делаем:

Для каждого элемента 1 массива ¡СигРаге^Аг: Если ¡СигРагег^Аф] = 0, то 8епё(Сй, ¡, ]); ¡СигРагсШзАф] = -1.

Если Р„ = 0, и нет элементов к массива ¡СигРагеШБАг таких, что ¡СигРагеп1зАг[к] = 0, то:

Для каждого элемента I массива ¡СигРагег^Аг: Если ¡СигРагетвАф] = -2 и ¡ЬоорАг[(] > 0, то: Для всех вершин э: Если ЬоорМай1х[1,5]=1 и

¡СигРагсп(зАг[5]>0, То ¡СигРагетэАгИ = 0; Переход в Блок 3. Конец блока 3.

Блок 4 (Готовим правила, соответствующие циклическим вершинам, к повторным вычислениям): Если существуют элементы 1 массива 1СЬаг^ес1ЬоорАг такие, что ¡СЬа^е<ЗЬоорАг[1] = 1, то: Для всех правил делаем: Если к - (дальний) потомок правила

то iChangedLoopAr[k] = 1.

Для каждого элемента t массива iChangedLoopAr: Если iChangedLoopArft] = 1, то iCurParentsAr[t] =

¡Parents Ar[t];

Если iLoopAr[t]>l, то iCurParentsAr[t]=0. Переход в Блок 3. иначе:

Конец блока 4.

Здесь iChangedLoopAr - массив целых чисел, в котором элемент с номером i равен 1, если циклическое правило i было сначала вычислено, а потом для объектов, входящих в его условие, появились новые значения; иначе элемент с номером i равен 0. LoopMatrix - двумерный массив размерности ц(Пт) х ц(Пт), копия массива IncMatrix, в которой обнулены все вершины, не имеющие предков или потомков. Зависимый процесс: wCalc(i, Z, Q);

НАЧАЛО вычислений: wSend(Q, i);

wRecv(Z, i); КОНЕЦ вычислений

Здесь wRecv(Z, i) - процедура, которая принимает из управляющего процесса набор данных Z, который содержит значения объектов, входящих в условие правила i; wSend(Q, i) - процедура, которая пересылает в управляющий процесс набор данных Q, которые являются результатом вычисления правила i; wCa!c(i, Z, Q) - процедура, вычисляющая правило i с помощью логического вывода.

Утверждение. Время выполнения программы Г при применении схемы 1 лежит в пределах: (It¡) / р(Р) < Т' < Zt¡, где £t¡ - сумма времен выполнения каждого правила, а ц(Р) - максимальное число независимых ветвей ИГ.

В работе даны теоретические оценки времени выполнения программы при применении различных схем.

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

Рассмотрим ограничения, налагаемые архитектурой многопроцессорной системы и структурой ИГ. Пусть в модуле ш количество правил равно ц(П,„), для него определено максимальное количество процессов Popt, которые можно выполнять параллельно друг с другом, при условии, что правила сначала вычисляются полностью и количество доступных рабочих процессов равно ц(Р). В реальных задачах логический модуль может содержать сотни правил, а ветвистость его информационного графа может быть крайне малой. С другой стороны, реальные кластеры предоставляют не более нескольких десятков процессов. В этом случае ц(Р) « ц(Пт), но так как в этом случае нельзя одновременно вычислять более Popt правил, то будет правильней рассмотреть отношение чисел Popt и ц(Р). В случае, когда Popt < ц(Р), получаем простаивающие на протяжении всех вычислений рабочие процессы, с другой стороны, если Popí > ц(Р), можно в какие-то моменты времени задействовать все процессы. Также на использование процессов влияет строение графа, который может иметь разную ветвистость на разных уровнях.

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

В работе объединены оба способа распараллеливания правил, в результате чего система параллельного программирования использует максимальное количество доступных процессов в каждый момент времени в соответствии со схемами, описанными в главе 3. Для этого система производит вычисление всех готовых к выполнению правил из ИГ. Если после этого остались незадействованные рабочие процессы, система передает этим процессам вычисление правил-потомков, предки которых находятся в обработке, при этом происходит обмен вновь вычисленных кортежей между процессами, обрабатывающими связку правил «предок-потомок».

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

1. Находятся все готовые к выполнению правила-вершины ИГ. Если в следствии готового к выполнению правила находится вызов модуля, управляющий процесс передает управление на вычисление свободному рабочему процессу из множества ц(Р). Если в следствии готового к выполнению правила нет вызова модуля, то оно передается на вычисление свободному рабочему процессу из множества ц(Р). Если свободных процессов после этого не осталось, переход на шаг 4, иначе шаг 2.

2. Из ИГ выбираются правила-вершины такие, чтобы их единственным предком была вершина, которая находится в обработке. Каждое найденное правило передается на вычисление в свободный рабочий процесс, при этом данный процесс может получать результирующие кортежи от процесса, обрабатывающего правило-предок. Если свободных процессов после этого не осталось, переход на шаг 4, иначе шаг 3.

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

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

5. Если в ИГ существуют вершины, входящие в циклы, и в результате выполнения правил, соответствующих этим вершинам, появились новые значения объектов, которые входят в условия циклических правил, то строится подграф, в который входят все правила, являющиеся потомками данных циклических правил. ИГ заменяется на построенный подграф, и вновь производятся вычисления с шага 1. Если в ИГ циклов нет или при вычислении циклов новых значений не появилось, то переход на шаг 6.

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

Зависимый процесс выполняет алгоритм 2.

1. Рабочий процесс принимает от управляющего номер правила и входные данные и начинает выполнение правила.

2. Если во время выполнения правила пришла команда на прием кортежей из другого процесса, то данный процесс принимает присланные кортежи и синхронизирует с имеющимися данными.

3. Если во время выполнения правила пришла команда пересылать вычисленные кортежи в другой процесс, то все вычисленные кортежи пересылаются в указанный процесс.

ан Среда разработки модульных логических программ

Редактор модульных логических программ Редактор данных Редактор источников данных

разработчик и ь

Компилятор СП (Анализатор, Генератор, Компилятор С++)

и ь

Исполняемая программа, реализующая ПЛВ

-гт -тт

Интерфейс запуска исполняемой программы на многоядерном ПК -а- Интерфейс запуска исполняемой программы на кластерной ЭВМ

Рис. 1. Схема взаимодействия пользователей с СП (тонкая стрелка - взаимодействия пользователя с программой, толстая стрелка - взаимодействие между программами)

4. После выполнения правила все результирующие данные пересылаются в управляющий процесс.

Разработаны две версии системы продукций: первая версия создана для работы на отдельном многоядерном персональном компьютере (рис. 1), вторая версия для вычислений требует доступа к многопроцессорной кластерной ЭВМ.

Если исполняемая программа сгенерирована для использования на кластерной ЭВМ, то пользователю необходимо использовать интерфейс запуска программы на кластере.

программный компонент - | | информационный компонент - 1 1

передача данных - •<—

Рис. 2. Архитектурно-контекстная диаграмма компилятора СП

Система продукций состоит из набора компонентов, в ее состав входят среда разработки, анализатор, генератор (рис. 2), процедуры поддержки ПЛВ, процедуры взаимодействия с СУБД, шаблон генерируремой программы.

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

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

1 2 4

Учс Ь о

о < Ь о

оо ■ ■ *оо

оо •■ ■ ~оо

ОО • ■ ЧЮ

С)

Рис. 3. Элементарные информационные графы

Глава 5 диссертации содержит результаты экспериментального исследования системы параллельного программирования.

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

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

Было использовано девять элементарных информационных графов (рис. 3): (1) ИГ имеет одну начальную вершину и в каждую вершину (кроме начальной) входит одна дуга (рис. 3.1); (2) ИГ, в каждую вершину которого (за исключением начальной) входит единственная дуга, и из каждой вершины которого (за исключением конечной) входит единственная дуга, т.е. все вершины графа образуют цепочку, начинающуюся с начальной вершины и заканчивающуюся конечной (рис. 3.2); (3) ИГ содержит п независимых друг от друга цепочек вершин (рис. 3.3); (4) ИГ состоит из п вершин, причем единственная корневая вершина соединена с (п-2) потомками, каждый из которых соединен дугой с единственной конечной вершиной (рис. 3.4); (5) ИГ содержит п независимых друг от друга одиночных вершин и не содержит дуг (рис. 3.5); (6) ИГ состоит из п вершин, (п-1) из которых образуют цикл (рис. 3.6); (7) единственная вершина ИГ соответствует правилу, содержащему префикс; (8) ИГ состоит из п вершин, (п-1) из которых являются начальными, причем все начальные вершины соединены дугой с единственной конечной вершиной (рис. 3.7); (9) ИГ состоит из п вершин, к из которых являются начальными (к<п), и одна - конечной; каждая ¡-ая вершина (кроме начальных) имеет п^ (гщ <п) предков и одного потомка (рис. 3.8).

Все эксперименты разбиты на группы, номер которой соответствует номеру типа элементарного информационного графа в приведенном выше списке. Для каждого типа графа в одной группе экспериментов создавалась одна или несколько программ.

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

Каждый эксперимент исполнялся несколько раз на одном и том же наборе входных данных, в описании результатов экспериментов приведено среднее время работы тестового приложения, которое равно сумме времен, деленных на количество тестовых прогонов. Следует отметить, что на скорость вычислений влияет время работы служебных процессов операционной системы, протокола MPI, задержки в коммуникациях. Особенно это проявляется в том случае, когда время выполнения правил маленькое (десятые доли секунды).

Для примера №1 (см. рис. 4) максимальное время выполнения программы, когда каждое правило выполнялось последовательно, составило 212,7 сек. при 1 рабочем процессе, минимальное - 108,5 сек. В параллельном режиме ускорение равно 1,96 при 9 рабочих процессах. Для примера №2 максимальное время работы составило 140,6 сек., минимальное - 26,6 сек. В параллельном режиме ускорение равно 5,28 при 9 рабочих процессах. Для примера №3 максимальное время работы составило 365,2 сек., минимальное - 37,6 сек. В параллельном режиме ускорение равно 9,71 при 13 рабочих процессах. Для примера №4 максимальное время работы составило 155,7 сек., минимальное - 52,8 сек. В параллельном режиме ускорение равно 2,94 при 9 рабочих процессах.

Пример №3 Пример №4

Рис. 4. Время выполнения программ при различных экспериментах

Кроме того, были проведены эксперименты на реальных задачах (медицины, вычислительной математики, химии), одним из которых был пример решателя одного из классов задач поиска путей синтеза химических соединений из предметной области «химия». Приведем время работы примера по поиску путей синтеза химических соединений на различном числе процессоров:

Таблица 1. Время решение задачи поиска путей синтеза химических соединений

Число процессоров 1 2 4 6 9

модуль 1 32,1 сек 24,7 сек 12,9 сек 13,1 сек 13,1 сек

При последовательном выполнении (число рабочих процессоров равно 1) время работы составило 32,1 секунды. При параллельном режиме при увеличении числа процессоров время уменьшилось и при 6 процессорах составило 13,1 секунды. По сравнению с последовательным режимом ускорение равно 2,4 при 6 рабочих процессорах. Уменьшение времени работы связано с распараллеливанием вычислений с использованием схемы распараллеливания по информационному графу. Тем самым данные примеров подтверждают утверждения, приведенные в главе 3.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ:

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

2. На основе расширенной модели языка разработаны и исследованы схемы распараллеливания процесса логического вывода для системы конфлюэнтных продукций; описана организация процесса параллельного выполнения логического модуля, когда отдельному процессу предлагается роль диспетчера (управляющий процесс), остальным процессам - роль обрабатывающего процесса (зависимые процессы). Определение информационного графа обобщено на случай модульной логической программы. Предложены следующие методы распараллеливания: на основе множества активных правил, на основе свойств информационного графа, для правил с префиксом, путем разбиения области значений объектов внутри правила, распараллеливание модулей, вызываемых из одного модуля, а также распараллеливание модульной программы.

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

4. Разработаны методы реализации системы параллельного программирования, а также ее архитектура. Система включает в себя такие компоненты, как среда разра-

ботки модульных логических программ, компилятор, набор процедур поддержки процесса логического вывода и процедур взаимодействия с СУБД. Описана схема взаимодействия пользователей с системой, архитектурно-контекстные диаграммы компилятора и исполняемой программы.

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Артемьева И.Л., Тютюнник М.Б. Реализация прототипа конфлюэнтной системы продукций на многопроцессорной ЭВМ. // Высокопроизводительные вычисления на кластерных системах. Материалы второго межд. научно-пр. сем. / Под. ред. проф. Р.Г. Стронгина. Нижний Новгород: Изд-во Нижегородского государственного университета. - 2002. - С. 289-294.

2. Артемьева И.Л., Тютюнник М.Б. Методы распараллеливания вычислений для системы параллельного программирования на основе декларативных продукций. // II межд. конф. «Параллельные вычисления и задачи управления», Москва, 2004: сб. тр. [Электронный ресурс]. М: ИПУ РАН. - 2004. - С. 727-737.

3. Артемьева И.Л., Тютюнник М.Б. Прототип системы конфлюэнтных продукций для МВС-1000. // Информатика и системы управления. - 2004. - №2. - С. 133-143.

4. Тютюнник М.Б. Прототип продукционной системы параллельного программирования. // Тез. докл. Открытого Дальневосточного конкурса программных средств студентов, аспирантов и молодых специалистов. - 2004. - С. 45-49.

5. Артемьева И.Л., Тютюнник М.Б. Схемы распараллеливания вычислений для системы конфлюентных продукций. // Информатика и системы управления. - 2005. -№2.-С. 102-112.

6. Артемьева И.Л., Тютюнник М.Б. Анализ схем распараллеливания вычислений для системы конфлюэнтных продукций. // Научная сессия МИФИ-2006, сб. научи. тр. в 16 томах, т. 3. М: МИФИ. - 2006. - С. 128-129.

7. Артемьева И.Л., Тютюнник М.Б. Методы управления распараллеливанием вычислений в системе конфлюэнтных продукций. // Искусственный интеллект. НАНУ, Институт проблем искусственного интеллекта, Донецк. - 2006. - №4. - С. 107117.

8. Артемьева И.Л., Тютюнник М.Б. Распараллеливание вычислений для системы конфлюэнтных продукций с использованием информационного графа. // III межд. конф. «Параллельные вычисления и задачи управления», Москва, 2006: сб. тр. [Электронный ресурс]. М.: ИПУ РАН. - 2006. - С. 1161-1171.

9. Тютюнник М.Б. Использование информационного графа при распараллеливании вычислений для системы конфлюэнтных продукций. // Информатика и системы управления. - 2006. -№1. - С. 181-192.

Ю.Артемьева И.Л., Тютюнник М.Б. Метод распараллеливания вычислений для модульных систем продукций. // Научная сессия МИФИ-2007, сб. научн. тр. в 17 томах, т. 3. М.: МИФИ. - 2007. - С. 118-119.

П.Артемьева И.Л., Тютюнник М.Б. Модель модульного языка декларативных конфлюэнтных продукций с ограниченными кванторами. // Искусственный интеллект. НАНУ, Институт проблем искусственного интеллекта, Донецк. - 2007. - №3. -С. 120-132.

12. Артемьева И.Л., Тютюнник М.Б. Модульная система конфлюэнтных продукций для многопроцессорной вычислительной системы. // Программные продукты и системы. - 2007. - №2. - С. 38-39.

13. Artemieva I.L., Tyutyunnik М.В. Parallelization of Logical inference for confluent rule-based system. // International Book Sériés «Information Science and Computing». Book 1 «Algorithmic and Mathematical Foundations of the Artificial Intelligence». - 2008. -PP.81-87.

14. Артемьева И.Л., Тютюнник М.Б. Методы управлением логического вывода для продукционной систем // Управление созданием и развитием систем, сетей и устройств телекоммуникаций. Тр. научн.-пр. конф., СПб.: НОЦ «Перспектива». - 2008. -С. 60-63.

15. Артемьева И.Л., Тютюнник М.Б. Управление распараллеливанием логического вывода для системы, основанной на правилах. // Научно-технические ведомости СПбГПУ. - 2008. - №3. - С. 99-103.

16. Артемьева И.Л., Тютюнник М.Б. Экспериментальное исследование системы параллельного программирования // Сб. научн. тр. научной сессии МИФИ-2008 в 15 томах. - Т. 10 «Интеллектуальные системы и технологии». М: МИФИ. - 2008 - С. 9798.

17. Артемьева И.Л.. Тютюнник М.Б. Исследование распределенной системы логического программирования. // IV межд. конф. «Параллельные вычисления и задачи управления», Москва, 2008: сб. тр. [Электронный ресурс]. М.: ИПУ РАН. - 2008. -С. 1150-1160.

18. Artemieva I.L., Tyutyunnik М.В. Parallel Logical Inference for Confluent Rule-Based System. // First Russia and Pacific Conférence on Computer Technology and Applications (RPC 2010): [Electronic res.]. - Vladivostok, Russia. - 2010. - PP. 171-176.

19. Артемьева И.Л., Никифорова Н.Ю., Тютюнник М.Б. Экспериментальные исследования свойств системы параллельного программирования. // V межд. конф. «Параллельные вычисления и задачи управления», Москва, 2010: сб. тр. [Электронный ресурс]. М: ИПУ РАН. - 2010. - С. 1157-1176.

20. Тютюнник М.Б. Система параллельного логического программирования РЕПРО-С. // Тез. докл. Открытого Дальневосточного конкурса программных средств студентов, аспирантов и молодых специалистов «Программист-2010». - 2010. - С. 2023.

21. Артемьева И.Л., Тютюнник М. Б. Распараллеливающий компилятор для языка, основанного на правилах. Свидетельство о государственной регистрации программы для ЭВМ №2010614810.

Личный вклад автора. Все результаты, составляющие основное содержание диссертации, получены автором самостоятельно. В работах [11,12] автору принадлежит модель расширенного языка, в [2,5,6,8,10,13,18] - схемы распараллеливания процесса логического вывода, в [7,14,15] - методы управления выбором схем, в [1,3] -методы реализации параллельной системы продукций, в [16,17,19] - описание результатов экспериментального исследования системы, в [21] — реализация распараллеливающего компилятора.

Тютюнник Михаил Борисович

Разработка и исследование продукционной системы параллельного программирования

Автореферат

Подписано к печати 21.12.10 Усл. печ. л. 1,0 Уч.-изд. л. 0,8

Формат 60x84/16 Тираж 100 Заказ 41

Издано ИАПУ ДВО РАН. Владивосток, ул. Радио, 5 Отпечатано участком оперативной печати ИАПУ ДВО РАН Владивосток, ул. Радио, 5

Оглавление автор диссертации — кандидата технических наук Тютюнник, Михаил Борисович

Введение

Глава 1. Языки и системы, основанные на правилах, и методы их реализации (обзор литературы)

1.1. Теоретические основы

1.2. Классы систем продукций

1.3. Системы, основанные на правилах

1.4. Методы реализации систем, основанных на правилах

1.5. Методы оптимизации процесса логического вывода для систем, основанных на правилах

1.6. Методы организации параллельных вычислений для сис1ем, основанных на правилах

1.7. Постановка задачи диссертационного исследования

Глава 2. Модель расширенного языка, основанного на правилах

2.1: Модель языка. Синтаксис

2.1.1. Описание логического модуля

2.1.2. Оп исание имен

2.1.3. Согласование сортов объектов одного модуля

2.1.4. Синтаксис термов, используемых в правилах

2.1.5. Синтаксис формул, используемых в правилах

2.1.6. Синтаксис правил

2.1.7. Схемы правил и конкретизации схем

2.2. Модель языка. Семантика

2.2.1. Рабочая среда модуля

2.2.2. Согласование сортов объектов разных модулей

2.2.3. Определение значений термов и формул для состояния рабочей среды

2.2.4. Применимость правил

2.2.5. Семантика схем и конкретизации схем

2.2.6. Процесс выполнения модуля

2.3. Свойства процесса логического вывода

2.4. Обсуждение

Глава 3. Разработка и исследование схем распараллеливания процесса логического вывода

3.1. Распараллеливание правил внутри модуля с использованием множества активных правил

3.1.1. Определение множества активных правил

3.1.2. Схема распараллеливания №

3.2. Распараллеливание правил внутри модуля с использованием информационного графа

3.2.1. Определение информационного графа

3.2.2. Схема распараллеливания №

3.3. Распараллеливание правил внутри модуля с использованием информационного графа с передачей кортежей при неполном вычислении правила

3.4. Распараллеливание вычислений для правил с префиксом

3.5. Распараллеливание вычислений путем разбиения области значений объектов внутри правила

3.6. Распараллеливание вычислений для сети модулей

3.7. Распараллеливание вычислений для одиночных модулей

3.8. Обсуждение

Глава 4. Разработка алгоритма управления выбором схем распараллеливания и методов реализации системы параллельного программирования

4.1. Алгоритм управления схемами распараллеливания

4.2. Требования к системе параллельного программирования

4.3. Архитектура системы параллельного программирования

4.3.1. Редактор модульных логических программ

4.3.2. Редактор источников данных

4.3.3. Редактор данных

4.4. Компилятор системы параллельного программирования

4.4.1. Анализатор

4.4.2. Генератор

4.4.3. Компилятор С++

4.5. Исполняемая программа, реализующая ПЛВ

4.6. Методы реализации

4.6.1. Описание шаблона программы

4.6.2. Представление информационных структур

4.7. Обсуждение

Глава 5. Экспериментальное исследование системы параллельного программирования

5.1. Экспериментальное исследование свойств системы параллельного программирования на модельных данных

5.1.1. Описание экспериментов группы

5.1.2. Описание экспериментов группы

5.1.3. Описание экспериментов группы

5.1.4. Описание экспериментов группы

5.1.5. Описание экспериментов группы

5.1.6. Описание экспериментов группы

5.1.7. Описание экспериментов группы

5.1.8. Описание экспериментов группы

5.1.9. Описание экспериментов группы

5.2. Экспериментальное исследование системы параллельного программирования на примерах реальных задач

5.2.1. Системы решения упрощенной задачи медицинской диагностики. Случай: для заболеваний задано одно клиническое проявление

5.2.2. Системы решения упрощенной задачи медицинской диагностики. Случай: для заболеваний задано несколько клинических проявлений

5.2.3. Система решения задачи Дирихле для уравнений эллиптического типа

5.2.4. Задача поиска путей синтеза химических соединений

5.3. Рекомендации по разработке параллельного решателя задач

5.4. Обсуждение 126 Заключение 127 Литература 128 Приложение 1. Программы, используемые при экспериментах на модельных данных 137 Приложение 2. Программы, используемые при экспериментах на реальных задачах

Введение 2010 год, диссертация по информатике, вычислительной технике и управлению, Тютюнник, Михаил Борисович

Актуальность проблемы. Продукционные языки и системы, основанные на правилах, являются важной технологией при создании информационных систем [97], называемых системами с базами правил (или с базами знаний, представленными в виде правил). Представление задачи в виде множества правил является более естественным способом по сравнению с алгоритмом и не требует от разработчика программной системы специальных знаний по организации вычислительного процесса: управление этим процессом реализует языковой процессор языка, основанного на правилах. При использовании систем продукций для решения реальных прикладных задач к настоящему времени разработаны базы знаний объемом в тысячи правил. В современных проектах по созданию Семантического Интернета также предполагается использование правил как средств, расширяющих возможности языка для представления онтологии OWL (Web Ontology Language) и позволяющих описывать бизнес-логику программных систем, создавать адаптеры между информационными системами и определять различные сложные запросы к информационным компонентам программных систем [97].

Если в системе, основанной на правилах, результат решения задачи зависит от порядка применения правил, в механизме вывода неявно присутствует управление выбором правил при решении задачи либо в систему продукций вводятся явные средства для задания управления (т.е. для задания алгоритма управления) [83 ]. В системах конфлюэнтных1 продукций [51] результат логического вывода не зависит от порядка применения правил, что не требует введения явных или неявных средств управления процессом решения задачи, позволяя рассматривать конфлю-энтные системы продукций не только как средство для представления знаний, но и как средство для задания метода решения задачи, т.е. как язьгк программирования метода. Поэтому системы конфлюэнтных продукций являются важным классом продукций. На основе модели конфлюэнтных продукций были созданы системы СИНАП и РЕПРО [6,7], которые использовались для построения многих прикладных экспертных систем.

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

Развитие компьютерной архитектуры и сетевых технологий, появление новых научных и прикладных задач, требующих большого объема вычислений, отставание быстродействия существующих последовательных компьютерных комплексов и теоретическая ограниченность роста их производительности привели к необходимости применения многопроцессорных и многоядерных компьютерных систем (МВС), выдвинув параллельные вычисления на одно из центральных мест в современном программировании и вычислительных технологиях. Это, в свою очередь, потребовало развития языков программирования и создания параллельных языковых процессоров для них. Для систем продукций, реализующих обратный вывод (в частности, систем, основанных на языке Пролог и его модификациях) [42], к "настоящему времени описаны методы организации параллельного вывода.

Большой вклад в разработку моделей систем продукций, методов организации процесса логического вывода для таких систем, а также методов распараллеливания вывода для них внесли Д.А. Поспелов, В.Н. Вагин, Г.С. Осипов, И.П. Кузнецов, А.П. Еремеев, A.C. Клещев, B.J1. Стефанкж, A.B. Жожикашвили, Ю.А.Загорулько, Т.М. Яхно, A.C. Нариньяни, S. Vere, D.B. Lenat и многие другие.

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

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

Для достижения поставленной цели в диссертационной работе необходимо решить следующие задачи:

3. Разработать алгоритм управления выбором схем распараллеливания в процессе логического вывода.

4. Разработать методы реализации системы параллельного программирования.

5. Провести экспериментальное исследование системы параллельного программирования на реальных примерах.

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

Практическая ценность работы состоит в том, чго разработана система параллельного программирования, которая может быть использована при создании параллельных систем, основанных на правилах, предназначенных для решения задач разных классов на многоядерных персональных компьютерах, а также на кластерах.

Получено свидетельство о государственной регистрации программы для ЭВМ №2010614810 «Распараллеливающий компилятор для языка, основанного на правилах». Авторы: Артемьева И.Л., Гютюнник М.Б. Зарегистрировано в Реестре программ для ЭВМ 23 июля 2010 г.

Апробация работы. Основные научные и практические результаты работы докладывались и обсуждались на следующих международных и отечественных конференциях и семинарах: Дальневосточной математической школе-семинаре имени академика Е.В. Золотова (Владивосток, Хабаровск, Находка, 2003-2008), открытом Дальневосточном конкурсе программных средств студентов, аспирантов и молодых специалистов «Программист» (Владивосток, 2004, 2010), II - V международных конференциях «Параллельные вычисления и задачи управления» (Москва, 2004, 2006, 2008, 2010), Международной конференции «Knowledge-Dialog-Solution» (Varna, Bulgaria, 2008), Международной конференции «First Russia and Pacific Conference on Computer Technology and Applications» (Vladivostok, Russia, 2010), Научной сессии МИФИ (Москва, 2006, 2007, 2008), Демидовской конференции «Фундаментальные и прикладные проблемы современной физики» (Москва, 2006), Международной научно-технической конференции «Искусственный интеллект. Интеллектуальные и многопроцессорные системы» (Кацивели, Украина, 2006, 2007), совместных семинарах отдела интеллектуальных систем ИАПУ ДВО РАН и базовой кафедры программного обеспечения ЭВМ ДВГУ при ИАПУ ДВО РАН (2005-2010).

Публикация результатов работы. По материалам диссертации опубликовано 28 печатных работ (работы [17-25,30-38,71-78,84,85]), из них 2 статьи в журналах, входящих в перечень ВАК (работы [25,37]).

Структура и объём работы. Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы, включающего 100 наименований, и 2 приложений. Основная часть работы изложена на 127 страницах, включая 18 рисунков, 14 диаграмм и 10 таблиц.

Заключение диссертация на тему "Разработка и исследование продукционной системы параллельного программирования"

Заключение

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

2. На основе расширенной модели языка разработаны и исследованы схемы распараллеливания процесса логического вывода для системы конфлюэнтных продукций; описана организация процесса параллельного выполнения логического модуля, когда отдельному процессу предлагается роль диспетчера (управляющий процесс), остальным процессам - роль обрабатывающего процесса (зависимые процессы). Определение информационного графа обобщено на случай модульной! логической программы. Предложены следующие методы распараллеливания: на основе множества активных правил, на основе свойств информационного графа, для правил с префиксом, путем разбиения области значений объектов внутри правила, распараллеливание модулей, вызываемых из одного модуля, а также распараллеливание модульной программы.

4. Разработаны методы реализации системы параллельного программирования, а таюке ее архитектура. Система включает в себя такие компоненты, как среда разработки модульных логических программ, компилятор, набор процедур поддержки процесса логического вывода и процедур взаимодействия с СУБД. Описана схема взаимодействия пользователей с системой, архитектурно-контекстные диаграммы компилятора и исполняемой программы.

Библиография Тютюнник, Михаил Борисович, диссертация по теме Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

1. Артемьева И.Л. и др. Инструментальный комплекс для реализации языков представления знаний. //Программирование. - 1983. - №4. - С. 78-89.

2. Артемьева ИЛ. и др. Развитие инструментального комплекса на базе реляционного языка. // Языки представления знаний и вопросы реализации экспертных систем. Владивосток. 1984. - С. 123-137.

3. Артемьева ИЛ. Методы недоопределенного вывода в системах продукций. // Управляющие системы и машины. 1991. - №7. - С. 88-93.

4. Артемьева И.Л. Разработка и исследование системы недоопределенного вывода для декларативных продукций. Дисс. . канд. техн. наук: 05.13.1 1: защищена 25.09.92: утв. 25.12.92 / Артемьева Ирина Леонидовна. Владивосток. - 1992. - 190 с.

5. Артемьева И.Л., Высоцкий В.И., Рештаненко Н.В. Модель онтологии предметной области (на примере органической химии). // НТИ. Сер.2. - 2005. - № 8. - С. 19-27.

6. Артемьева И.Л., Горбачев С.Б., Клещев A.C. и др. Вопросы реализации реляционного языка программирования. // Теоретические основы компиляции. Новосибирск. 1980. - С. 37-48.

7. Артемьева И.Л., Горбачев С.Б., Клещев A.C. и др. Инструментальный комплекс для реализации языков представления знаний. // Программирование. 1983,-№4.-С. 78-89.

8. Артемьева И.Л., Клещев A.C. Вывод в системах продукций с недоопреде-ленными объектами. Процесс рассуждений, определяемый модульной базой знаний. // Препр. Владивосток: ИАПУ ДВО АН СССР. 1992. - 31 с.

9. Артемьева И.Л., Клещев A.C. Вывод в системах продукций с недоопреде-ленными объектами. Процесс логического вывода. // Препр. Владивосток: ИАПУ ДВО АН СССР. 1992.-41 с.

10. Артемьева И.Л., Клещев A.C. Расширенная модель декларативных продукций. // Препр. Владивосток: ИАПУ ДВО АН СССР. 1991. - 36 с.

11. Артемьева И.Л., Клещев А.С и др. Оптимизация программ и вычислений для реляционного языка программирования. // Методы трансляции и конструирования программ. Новосибирск: ВЦ СО АН СССР. 1986. - С. 4349.

12. Артемьева И.Л., Клещев A.C. Необогащенные системы логических соотношений. Часть 1. // НТИ, сер. 2. 2000. - №7. С. 18-28.

13. Артемьева И.JT., Клещев A.C. Необогащенные системы логических соотношений. Часть 2. // НТИ, сер. 2. 2000. - №8. - С. 8-18.

14. Артемьева И.Л., Клещев A.C., Лифшиц А .Я. и др. Генератор экспертных систем СИНАП. Описание языка представления знаний. // Препр. Владивосток: ИАПУ ДВО АН СССР. 1987. - 35 с.

15. Артемьева И.Л., Клещев A.C., Лифшиц А .Я. и др. Генератор экспертных систем СИНАП. Описание ядра языка представления знаний. // Препр. Владивосток: ИАПУ ДВО АН СССР. 1987. - 45 с.

16. Артемьева И.Л., Лифшиц А.Я., Плис Г.Я. Принципы реализации генератора экспертных систем РЕПРО. // Методы и средства создания и исследования экспертных систем. Владивосток: ДВО АН СССР. 1991. -С. 118-129.

17. Артемьева И.Л., Тютюнник М. Б. Распараллеливающий компилятор для языка, основанного на правилах. Свидетельство о государственной регистрации программы для ЭВМ №2010614810.

18. Артемьева И.Л., Тютюнник М.Б. Анализ схем распараллеливания вычислении для системы конфлюэнтных продукций. // Научная сессия МИФИ-2006, сб. научн. тр. в 16 томах, т. 3, Москва: МИФИ. -2006. С. 128-129.

19. Артемьева И.Л., Тютюнник М.Б. Исследование распределенной системы логического программирования. // IV межд. конф. «Параллельные вычисления и задачи управления», Москва, 2008: сб. тр. Электронный ресурс. М.: ИПУ РАН. 2008. - С. 1150-1160.

20. Артемьева И.Л., Тютюнник М.Б. Модель модульного языка декларативных конфлюэнтных продукций с ограниченными кванторами. // Искусственный интеллект. НАНУ, Институт проблем искусственного интеллекта, Донецк. 2007. - №3. - С. 120-132.

21. Артемьева И.Л., Тютюнник М.Б. Модульная система конфлюэнтных продукций для многопроцессорной вычислительной системы. // Программные продукты и системы. 2007. - №2. - С. 38-39.

22. Артемьева И.Л., Тютюнник М.Б. Продукционная система РЕПРО-С. Интерфейс и компиляция логического модуля. // Препр. Владивосток: ИАПУ ДВО РАН. 2009. - 40 с.

23. Артемьева И.Л., Тютюнник М.Б. Продукционная система РЕПРО-С. Описание языка. Часть 1. // Препр. Владивосток: ИАПУ ДВО РАН. 2009. - 28 с.

24. Артемьева И.Л., Тютюнник М.Б. Продукционная система РЕПРО-С. Описание языка. Часть 2. // Препр. Владивосток: ИАПУ ДВО РАН. 2009. - 36 с.

25. Артемьева И.Л., Тютюнник М.Б. Продукционная система РЕПРО-С. Подсистема поддержки разработки. // Препр. Владивосток: ИАПУ ДВО РАН. -2009. 36 с.

26. Артемьева И.Л., Тютюнник М.Б. Прототип системы конфлюэнтных продукций для МВС-1000. // Информатика и системы управления. 2004. -№2.-С. 133-143.

27. Артемьева И.Л., Тютюнник М.Б. Распараллеливание процесса логического вывода для систем конфлюэнтных продукций. // Демидовская конференция «Фундаментальные и прикладные проблемы современной физики», Москва. 2006 г.

28. Артемьева И.Л., Тютюнник М.Б. Схемы распараллеливания вычислений для системы конфлюентных продукций. // Информатика и системы управления. 2005. - №2. - С. 102-112.

29. Артемьева И.Л., Тютюнник М.Б. Методы управления распараллеливанием вычислений в системе конфлюэнтных продукций. // Искусственный интеллект. НАНУ, Институт проблем искусственного интеллекта, Донецк. -2006. №4. -С. 107-117.

30. Артемьева И.Л., Тютюнник М.Б. Управление распараллеливанием логического вывода для системы, основанной на правилах. // Научно-технические ведомости СПбГПУ. 2008. - №3. - С.99-103.

31. Артемьева И.Л., Тютюнник М.Б. Экспериментальное исследование системы параллельного программирования. // Сб. научн. тр. научной сессии МИФИ-2008 в 15 томах. Т. 10 «Интеллектуальные системы и технологии» - 2008. Москва: МИФИ. - С. 97-98.

32. Артемьева И.Л., Яценко О.С. Модель декларативных продукций с обобщенными кванторами. // Преп. Владивосток: ИАПУ ДВО РАН. 1998. - 3 1 с.

33. Бобровский С. Как японцы компьютерный мир осчастливили. (088) 14х 1997. 15.04.1997. PC Week/RE. Электронный ресурс. URL: http://www.pcweek.ru/ themes/detail.php? 1D=41250. (дата обращения: 14.05.2010).

34. Братко И. Программирование на языке Пролог для искусственного интеллекта: Пер. с англ. М.: Мир. - 1990. - 560 с.

35. Вагин В.Н., Головина Е.Ю., Загорянская A.A., Фомина М.В. Достоверный вывод в интеллектуальных системах. // Под ред. В.Н. Вагина, Д.А. Поспелова. М.: ФИЗМАТЛИТ. - 2004. - 704 с.

36. Вагин В.Н., Еремеев А.П. Параллелизм в продукционных моделях представления знаний. // Техническая кибернетика. М.: Наука. 1994. - №2. - С. 48-55.

37. Виноградов А.Н., Жилякова Л.Ю., Осипов Г.С. Динамические интеллектуальные системы. 4.1. Представление знаний и основные алгоритмы. // Известия РАН. Теория и системы управления, М: Наука. 2002. - №6. - С.87- 94.

38. Гаврилов C.B., Малышков A.M., Плесневич Г.С. Бинарная модель данных и знаний. // КИИ-2002, Восьмая национальная конференция по ИИ с международным участием. Труды конференции, Том 1. Москва Физмаглит. -2002. С. 398-405.

39. Гладкий A.B. Формальные грамматики и языки. М.: Наука, 1973.

40. Еремеев А.П. Параллельная модель для продукционной системы табличного типа. // М.: Наука. 1990. - №5. - С. 171-180.

41. Жожикашвили A.B., Стефанюк В.Л. Алгебраическая теория продукционных систем. // Восьмая нац. конф. по искусственному интеллекту с между-нар. участием. Сб. тр. в 3 томах. Москва: Физматлит. 2002. - Т.1. - С. 428436.

42. Иванов A.C. Модель представления продукционных баз знаний на ЭВМ. // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика. 2007. - Т. 7. - № 1. - С. 83-88.

43. Информационно-аналитический центр. Электронный ресурс. URL: http://parallel.ru/ (дата обращения: 14.05.2010).

44. Клещев A.C. Реляционная модель вычислений. // Программирование. -1980. -№4.-С. 20-29.

45. Клещев A.C. Математические основы информатики. Лекции по курсу. // Находка: Институт технологии и бизнеса. 2003. - 84 с.

46. Клещев A.C. Реализация экспертных систем на основе декларативных моделей представления знаний. // Препр. Владивосюк: ДВО АН СССР. -1988.-45 с.

47. Клещев A.C. Реляционный язык как программное средство для искусеi-венного интеллекта. // Преп. Владивосток: ДВНЦ АН СССР. 1980. - 17 с.

48. Клещев A.C., Артемьева И.Л. и др. Методы трансляции и конструирования программ, 1986.

49. Клещев A.C., Артемьева И.Л., Коган Б.И., Лифшиц А .Я. Матвеева Т.О. Орлова Л.Д., Плис ГЛ., Сысоева Э.Н. Система поддержки целостности реляционных баз данных для ЕС ЭВМ. // Алгоритмы и программы. 1986. -№6.-С. 11.

50. Клещев A.C., Самсонов В.В. МАКРОРЕПРО язык спецификации компиляции баз знаний в базы правил. // Препр. Владивосток: ДВО РАН. - 1992. -25 с.

51. Кузнецов И.П., Мацкевич А.Г., Семантико-ориентированные системы на основе баз знаний. // М.: Издательство МТУСИ. 2007. - 173 с.

52. Мальцев А.И. Алгебраические системы. // М.: Наука, гл.ред.физ.-мат. лит. 1970. - 392 с.

53. Матвеева Т.О. Оптимизация вычислений в системах декларативных продукций на основе анализа информационных графов. // Препр. Владивосток: ИАПУ ДВО PAII. 1992. - 37 с.

54. Нариньяни A.C. Недоопределенность в системах представления и обработки знаний. //Изв. АН СССР. Техн. кибернетика. 1986. - №5. - С. 3-28.

55. Параллельное программирование. Центр информационных технологий. Электронный ресурс. URL: http://itcentre.ru/programming/science-work/parallel-programming/ЗОб/ (дата обращения: 14.05.2010).

56. Попов Э.В. Экспертные системы: Решение неформализованных задач в диалоге с ЭВМ. // М.: Наука. Гл. ред. фпз.-мат. лиг. 1987. - 288 с.

57. Попов Э.В., Фридман Г.Р. Алгоритмические основы интеллектуальных роботов и искусственного интеллекта. // М.: Наука. 1976. - 455 с.

58. Родзина О.Н. Кластерная обработка продукционных правил в базе знаний интеллектуальных САПР. // Известия Южного федерального университета. Технические науки. 2009. - Т. 93. - № 4. - С. 141-146.

59. Савяк В. Эффективные кластерные решения. 2002. Электронный ресурс. URL: http://www.ixbt.com/cpu/clustering.shtml (дата обращения: 14.05.2010).

60. Самсонов В.В., Сорокин B.C., Черняховская М.Ю. Экспериментальная медицинская экспертная система Консультант-2. // Проблемы проектирования экспертных систем: Тез. Докл. Всесоюз. школы-совещания. 4.2 Москва. 1988.-С. 238-239.

61. Стефанюк B.JL, Жожикашвили A.B. Сотрудничающий компьютер: проблемы, теории, приложения. // Ин-т проблем передачи информ. РАН. М.: Наука. - 2007. - 274 с.

62. Тютюнник М.Б. Выбор схем распараллеливания вычислений в системе конфлюэнтных продукций. // ХХХГ Дальневосточная математическая школа-семинар им. академика Е.В.Золотова: тезисы докладов. Владивосток: Изд-во ИПМ ДВО РАН. 2006. - С. 200.

63. Тютюнник М.Б. Методы реализации параллельной системы продукций. // XXXII Дальневосточная математическая школа-семинар им. академика Е.В.Золотова: тезисы докладов. Владивосток: Изд-во ИПМ ДВО РАН. -2008. С. 34-35.

64. Тютюнник М.Б. Прототип продукционной системы параллельного программирования. // Тез. докл. открытого Дальневосточного конкурса программных средств студентов, аспирантов и молодых специалистов. 2004. - С. 45-49.

65. Тютюнник М.Б. Система параллельного логического программирования РЕПРО-С. // Тез. докл. Открытого Дальневосточного конкурса программных средств студентов, аспирантов и молодых специалистов. — 2010. С. 20-23.

66. Тютюнник М.Б. Экспериментальное исследование прототипа параллельной системы продукций. // XXXII Дальневосточная математическая школа-семинар им. академика Е.В.Золотова: тезисы докладов. Владивосток: Изд-во ИПМ ДВО РАН. 2007.

67. Успенский В.А., Семенов А.А. Теория алгоритмов: основные открытия и приложения. // М: Наука. 1987. - 288 с.

68. Уинстои П. Искусственный интеллект. // М.: Мир. 1980.

69. Уотермен Д. Руководство по экспертным системам: Пер. англ. // М.: Мир. -1989.-388 с.

70. Черняховская М.Ю. Представление знаний в экспертных системах медицинской диагностики. // Владивосток, ДВНЦ АН СССР. 1983. - 212 с.

71. Яхно Т.М. Системы продукций: структура, технология, применение. // Новосибирск: ВЦ СО АН СССР. 1990. - 127 с.

72. Artemieva I.L., Tyutyunnik М.В. Parallel Logical Inference for Confluent Rule-Based System. // First Russia and Pacific Conference on Computer Technology and Applications (RPC 2010): Electronic res.. Vladivostok, Russia. 2010. -P. 171-176.

73. Bhawmik S., Athawale P.V., Palchaudhuri P. KET A tool for building expert systems. // Institution of Electronics and Telecommunication Engineers. - 1988. -Vol 34.-№3.-P. 184-192.

74. Duda R. et al. Model design in PROSPECTOR consultant system for mineral exploration. // Expert Systems in the Microelectronic Age. Edinburgh University Press. 1979. - P. 153-167.

75. Feigenbaum E. The art of artificial intelligence: Themes and case studies of knowledge engineering. // The fifth International Joint Conference of Artificial Intelligence. Boston: MIT. 1977. - P. 1014-1029.

76. Forgy C. RETE: A fast algorithm for many pattern/many object pattern match problem. //Artificial Intelligence. 1982. - Vol. 19. - P. 17-38.

77. Funabashi M., Mori K. Knowledge based control systems software for building expert systems EUREKA-II. // Hitachi Rev. 1998. - V. 37. - №4. - P. 267-274.

78. Gupta A., Pandarung N., Rosenbloom P. Comparison of the Rete and Treat Productio Matchers for Soar (A Summary). // Pr. AAAI-88. 1988. - Vol. 2. - P. 693-698.

79. Ishida T. Optimizing Rules in Production System Programs. // Pr. AAAI-88. -1988. Vol.2. - P. 699-704.

80. McDermott J. et al. The efficiency of certain production system implementation. //Pattern-Directed Inference Systems. 1978. - P. 155-176.

81. Miranker D.P. TREAT: A Better Match Algorithm fo A1 Production Systems. // Pr. AAAI-87. 1987. - Vol. 2. - P. 42-47.

82. Post E. Formal reduction of the general combinatorial. // Am. J. Math. 1943. -Vol. 65.-№2. - P. 197-215.

83. RIF Production Rule Dialect. W3C Working Draft 11 February 2010. Электронный ресурс. URL: http://www.w3.org/TR/2010/WD-rif-prd-20100211/ (дата обращения: 14.05.2010).

84. RIF Use Cases and Requirements. W3C Working Draft 18 December 2008. Электронный ресурс. URL: http://www.w3.org/TR/rif-ucr/ (дата обращения: 14.05.2010).

85. Shortliffe E.H. Computer-based medical consultation: MYCIN. // NY: Academician Elsevier. 1976.

86. Van Melle. A domain independent production rule system for consultation programs. // Proc. Of IJCAI-6. Tokyo. 1979. - P. 923-925.

87. Vere S.A. Relational production systems. // Artificial Intelligence. 1977. - №8. - P. 47-68.

Похожие работы

Информатика, вычислительная техника и управление
05.13.00