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

• Автор: Тютюнник, Михаил Борисович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Владивосток
• Количество страниц: 162 с.

ОГЛАВЛЕНИЕ
Введение
Глава 1. Языки и системы, основанные на правилах, и методы их реализации обзор литературы

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

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

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

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

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

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

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. Схема распараллеливания 1
3.2. Распараллеливание правил внутри модуля с использованием информационного графа
3.2.1. Определение информационного графа
3.2.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. Описание экспериментов группы 1
5.1.2. Описание экспериментов группы 2
5.1.3. Описание экспериментов группы 3
5.1.4. Описание экспериментов группы 4
5.1.5. Описание экспериментов группы 5
5.1.6. Описание экспериментов группы 6
5.1.7. Описание экспериментов группы 7
5.1.8. Описание экспериментов группы 8
5.1.9. Описание экспериментов группы 9
5.2. Экспериментальное исследование системы параллельного программирования на примерах реальных задач
5.2.1. Системы решения упрощенной задачи медицинской диагностики. Случай для заболеваний задано одно клиническое проявление
5.2.2. Системы решения упрощенной задачи медицинской диагностики. Случай для заболеваний задано несколько клинических проявлений
5.2.3. Система решения задачи Дирихле для уравнений эллиптического типа
5.2.4. Задача поиска путей синтеза химических соединений
5.3. Рекомендации по разработке параллельного решателя задач
5.4. Обсуждение
Заключение
Литература


При сопоставлении продукции с ситуацией определяются конкретизаторы этою шаблона. X5, т. X. Результатом применения продукции является ситуации б Т, определяемая по формуле I рх. Отмечается, что для многих систем продукций . Продукционная сеть определяется как тройка 8,Т,Р, где 8 и Т объекты некоторой категории, а Р множество продукций, действующих из Э в Т. Продукция может быть либо простой, задаваемой указанной выше диаграммой, либо рекурсивной. Последняя представляет собой тройку р, , Р, где р X8, ц УТ морфизмы, а продукционная сеть, действующая из X в У. Термин система продукций был введен в работах Поста 9. В настоящее время он обозначает одновременно и множество продукционных правил, и программную систему, в которой программа представляется множеством правил. Часто в литературе для второго случая используется термин система, основанная на правилах. Далее в работе будем пользоваться этими двумя понятиями, чтобы разделять оба случая. Система продукций Поста задастся своим алфавитом и системой подстановок, каждая из которых называется продукцией и имеет вид а,У Ь 1. Ь, слова в алфавите С. Пусть некоторое слово Ь начинается словом а,. Выполнить над Ь продукцию это значит вычеркнуть из Ь начальный отрезок а и к оставшемуся слову приписать справа слово Ь,. К этому классу продукций можно отнести и порождающие грамматики, введенные М. Хомским , . В большинстве систем, основанных на правилах, используемых при создании экспертных систем, условие и заключение продукций являются однотипными утверждениями Продукции различаются синтаксисом условия и заключения, набором операций, которые могут применяться к текущему состоянию, правилами определения применимости. Многие из существующих коммерческих оболочек экспертных систем являются продукционными. Если система продукций позволяет в процессе вывода только добавлять новые данные или только удалять существующие, то результат сс работы не зависит от порядка применения правил. Такая система продукций называется конфлюэнтной. Если система позволяет как добавлять, так и удалять данные в процессе вывода либо изменять ранее полученные данные, то результат ее работы зависит от порядка применения правил. Такая система не является конфлюэнтной. Рассморим примеры продукционных систем указанных двух типов. В 0 реляционная система продукций определяется как пятерка С, V, , . Здесь С множество констант обозначаемых строчными буквами V конечное множество символов переменных, принимающих значения в области констант обозначаются заглавными буквами множество литералов вида i. С и V, начальная ситуация, определяемая как конъюнкция литералов Р конечное множество правил вида ан i условие применимости антецедент, следствие консеквент, р аспект грань, а. Продукции предназначены для описания всевозможных преобразований исходной ситуации к некоторой ситуации а. Продукция применима к ситуации а тогда и только тогда, когда а0 с а. V переменные. Если продукция р . О и рб 0 а а0 п р0 0. Результат работы зависит от порядка применения продукций. Одним из наиболее известных языков для продукционных систем является 5, разработанный в университете КарнегиМеллона , . Состояние порождающего процесса, называемое рабочей памятью i , состоит из элементов, где каждый элемент задается именем класса объекта п совокупностью пар атрибут, значение. Правая часть продукции задает условие применимости продукции и состоит из последовательности образцов, каждый из которых представляет собой частичной описание элемента рабочей памяти. Условие правила считается выполненным, если для каждого образца из правой части продукции существует элемент рабочей памяти, который соответствует этому образцу. Образцы могут содержать константы, переменные и предикаты. С помощью переменных можно задавать условия на значения атрибутов разных образцов. Левая часть продукции в 5 состоит из последовательности действий. В. динамических системах используются правила вида ,,, где С предусловие условие правила, А множество фактов, добавляемых в результате применения правила П, множество фактов, удаляемых при применении правила II.