Введение к работе
Актуальность темы. В начале 80-х годов в ряде ведущих стран мира было объявлено о начале работ над национальными проектами создания ЭВМ пятого поколения. В наиболее известном из них, японском проекте, предполагалось, что ЭВМ нового поколения должна содержать: машину баз знаний (МБЗ), машину логического вывода (МЛВ) и "дружественный" интерфейс пользователя. Основное внимание при этом уделялось разработке машины логического вьгаода. Базовым языком проекта был выбран язык логического программирования Пролог.
Практика показала, что характеристики, полученные в результате исследований, оказались несколько ниже ожидаемых, и практического варианта машины пятого поколения (из отдельных более или менее удачных проектов МБЗ и 1,!ЛВ) так и не было создано. Однако, некоторая "экологическая икса" для данного направления имеется,и проблема создания мощных систем логического вывода (СЛВ) по-прежнему остается актуальной
Одной из причин недостаточного распространения ЭБ!Д нового поколения явилась низкая производительность машин логического вывода. Действительно, для решения реальных задач обработки знаний необходимо быстродействие порядка 1 GLIPS, а существующие МЛВ, большинство из которых спроектированы на базе Пролог-процессоров, обладают производительностью 1-10 MLIPS, и имеются принципиальные ограничения производительности, заложенные в стандартной (фон-неймановской) архитектуре машин, приспособленной, в основном, под нужды процедурных языков, и в последовательном, по своей сути, методе SLD-резолюций, на котором основан язык Пролог.
Таким образом, для выхода на принципиально новые уровни производительности, необходимо ориентироваться на новые параллельные методы логического вывода (ЛВ) и новые типы архитектур.
Целью работы является исследование методов и средств повышения производительности систем логического вывода за счет использования ускоренного метода дедуктивного логического вывода.
В соответствии с поставленной целью в работе решаются следующие основные задачи:
разработка метода ускоренного логического вывода (МУЛВ);
разработка и анализ формальной модели логико-потоковых вычислений;
разработка архитектуры процессора логического вывода (ПЛВ) с сокращенным набором команд;
исследование вопросов организации и проектирования мультипроцессорной системы логического вывода;
разработка системы моделирования машины логического вывода .
Методы исследования основаны на использовании теории- множеств и теории графов, математической логики , теории моделирования, методов научного анализа и синтеза, теории вычислительных систем и теории логического программирования.
Научная новизна. В результате проведенных исследований получены следующие научные результаты;
предложен метод ускоренного логического вывода, отличающийся декларативной' формой представления данных и оригинальной процедурой двунаправленного вывода, разрешающей проблемы связанных переменных;
определена формальная потоковая модель, позволяющая вести параллельную асинхронную обработку данных;
разработана абстрактная машина логического вывода для аппаратной поддержки ускоренного метода. Определены структура абстрактной машины и система команд, отличающаяся многоуровневос-тью и небольшим количеством элементов на каждом уровне;
Практическая ценность работы заключается в следующем:
проанализированы базовые архитектурно-структурные решения потоковых ПЛВ, и сформулированы принципы построения ПЛВ и его основных подсистем - процессора команд и исполнительного процессора;
предложена обобщенная структура мультипроцессорной системы логического вывода , поддерживающей параллельную высокоскоростную распределенную обработку;
разработана диалоговая система моделирования однопроцес-сороной системы логического вывода.
Внедрение результатов работы. Полученные в диссертационной работе теоретические и практические результаты используются в рамках курсов "Системы искусственного интеллекта" и "Вычислительные системы и комплексы" ВятГТУ.
Апробация работы. Основные положения и результата диссертационной работы докладывались на научно-технических конференциях профессорско-преподавательского состава ЛЭТИ им, В.И Ульянова (Ленина) в 1991-1994 гг., а так же на международной научно-тохнической конференции "Исснуственнкй интеллект - 94" в городе Рыбинске.
Публикации. По теме диссертация опубликовано б печатных работ: 5 статей и 1 депонированная рукопись.
Структура и обьем работы. Диссертационная работа состоит из введения, четырех глаз с выводами, заключения, списка литературы, включавшего 105 наименований, списка сокращений к трех приложений. Основная часть работы изложена на 150 страницах машинописного текста. Работа содср-кпт 51 рисунок и 7 таблиц
СОДЕРНАН'ДЕ PAB0TU
Во введении обоснована актуальность темы, сформулированы цель и основные задачи исследования.
В первой главе рассматривается современное состояние развития систем логического вывода, которое характеризуется усилиями разработчиков по созданию новых языков параллельного логического программирования, новых моделей выполнения логических программ, новых архитектурно-структурных решений параллельных С Л В.
Также проведен анализ наиболее известных методов логического вывода и предложена их классификация с выделением различий по:
форме представления правил;
направленности вывода;
основным применяемым законам логики;
принципам доказательства теорем;
стратегии и тактике управления выводом.
В настоящее время наибольшее распространение получил метод логического вывода, заложенный в основу языка Пролог - метод на базе принципа резолюций и хорновских дизъюнктов. Однако в процессе исследований, и практического применения Пролога стало очевидно, что при решении более объемных задач метод резолюций перестает удовлетворять пользователей, главным образом, по быстродействию, а также в связи с возникающими сложностями при формальном описании задач. Развитие последовательных версий языка Пролог с целью его адаптации к уже существующим мультипроцессорным и мультиыашинным архитектурам оказалось неэффективным. Разработчики новых языков параллельного логического программирования столкнулись с определенными трудностями: при реализации И- параллелизма - наличке связанных переменных в правилах; при реализации ЮШ-параллелизма - возможность комбинаторного взрыва. Поэтому существует необходимость в разработке нового эффективного метода логического вывода с высоким быстродействием (прежде всего за счет параллельной обработки), в котором процесс вывода не зависел бы от порядка выбора обрабатываемых дизъюнктов и последовательности расположения правил в описании задачи.
Далее рассмотрены некоторые модели параллельного выполнения логических программ и некоторые подходы к организации параллельных СЛВ. Отмечено, что основные особенности алгоритма работы неймановского компьютера (последовательное выполнение программы, централизованное управление, обработка данных с перезаписью памяти, и т.д.) затрудняют реализацию эффективной параллельной обработки и тем самым не позволяют создать ЭВМ с требуемой производительностью. Для повышения производительности СЛВ и решения проблемы семантического разрыва необходимо разработать новые принципы организации вичислений в ЭВМ. Одним из возможных решений является разработка динамических потоковых моделей вычислений и машин с потоковой архитектурой.
В первой главе также рассмотрены критерии оценки производительности как потоковых, так и традиционных систем логического вывода. Кроме того проанализированы характеристики наиболее распространенных тестовых задач ЛВ.
Во второй главе описаны формальные система (ФС) для логики высказываний и логики предикатов, в рамках которых
удобно исследовать различные методы логического вывода. ФС определяется множеством < T,H,A,R >, где:
Т - множество констант, переменных и оператороз;
Н - множество правил конструирования формул;
А - множество аксиом;
R - множество правил вывода.
Различные наборы множеств Т, Н, A, R определяют различные формальные системы. Описанные ФС отличаются от известных аксиоматических систем наличием двух дополнительных правил вывода:
1. Правило поглощения:
X і- О, 1 і- X V V р 1 н Y ;
X-Z у- 0, li-XVY, UZVf в Ь? ;
1 н R, R (- X V Z, lhXVY, lt-ZVY t lv-Y.
2. Празило упрощения :
1 і- X, Y-Z i-O >= (X v Y)-Z і- 0
Кроме этого, выражение (X V Y)-Z t- 0 истинно, если Z t- О или X V Y і- 0 : Z н О P (X V Y)-Z і- О или XvYhO с (XVY)-Zi-O
В предлагаемых ФС решается задача, формулируемая следующим образом : для заданного множества предложений (посылок) А. , А . ..., А определить, выводится ли из этих посылок предло-
12 п
жение (заключение) В.
В рамках ФС для логики высказываний разработан.метод ускоренного логического вывода (МУЛВ), в основу которого положены:
двунаправленный вывод;
использование принципа остатков для доказательства теорем;
применение стратегии "сначала вширь" и тактики упрощения на каждом шаге ЛВ;
использование эвристических оценок для предотвращения комбинаторного взрыва.
Для описания сути метода введем следующие обозначения : V = < М, г, Q, М, г > - процедура вывода, где:
М = < R ,R,...,R ,...,R > - множество исходных правил ;
R = L1 v L1 V ... V L1 V ... V L1 - i-e правило, состоящее
112 J J * і
из литералов L ;
г = г Л г Л...л г л...л г - выводимое правило, состоящее из дизъюнктов г , причем каждый дизъюнкт состоит из литералов L :
k s
г =LhVLkV..,V Lkv...V L" ;
к 1 2 s S
Q - признак окончания вывода,принимающий одно из трех значений:
Y - вывод успешно завершен (правило г следует из множества правил М);
N - вывод завершен неудачно (празило г не выводимо из множества правил II) ;
G - требуется продолжение вывода для нового выводимого правила ;
М - новое множество исходных правил ; -г - новое множество выводимых правил.
Обозначим также :
R = {L1 , L1 ,..., Ll,..., L1] - множество литералов, входящих в
исходное правило R ;
г = {Lk, Lk,..., Lk,. .. , Lk} - множество литералов, входящих в
1с 1 2 s S
дизъюнкт г выводимого правила г;
г = U г - множество литералов, входящих в выводимое
k = 1 к
правило г,
Процедура ускоренного логического вывода применима, если
И * и и г * 0, где а - пустое множество.
На каждом шаге ЛВ выполняются следующие действия : 1. Проверяется основное условие осуществимости вывода правила г из множества М :
U R п г * а для каждого к =» 1,К.
2. Для ks.-дого дизъюнкта г правила г формируется мно
жество Мв базовых правил :
Мв = {RB\ RBk RB*..., RBk] , где
к 12 q Q
M8 e И и RBk л г * а
k q I ' к
3. Для каждого дизъюнкта г формируется множество дМв ос-
k к
татков базовых правил и проверяется частное условие успешного завершения вывода :
„В г „Bk nBk nBk aBk1 --„
дм = ІлН , дК , . . . , лк , . . . , дК і , где
к 1 2 q О
дКрк- остаток правила R по дизъюнкту г ;
q q i<
iRBk= RBk / (RSkn г ), q = TTQ. q q q k
Если при определении остатков для какого-либо правила Rske Мв выполняется условие:
< - г, означающее совпадение дизъюнкта г с исходным правилом RB, то
k W
see остатки, соответствующие данному дизъюнкту, из дальнейшего рассмотрения исключаются. В случае, если данное условие выполняется для всех к = 1,К , то вывод считается успешно завершенным (Q=Y) и переходим к п.7, иначе к п.4.
4. Проверяется общее условие завершения вывода. Для этого
для каждого г составляется функция Г , равная конъюнкции aRBil:
1С k q
Далее каждая функция Г упрощается в соответствии с законами логики высказываний.
Формируется и анализируется функция F = V F , k = 1,К. :
а) если F = О, то вызод успешно завершен CQ=Y) и переходим к
п.7;
б) если F = 1, то вывод невозможен (Q=N) и переходим к п.7;
в) если 7-і, где f - логическая формула, отличная от О и 1, то
требуется продолжение вывода (Q=G), поэтому переходим к п.5;
5. Формируется новое множество исходных правил :
К в
м = и / л м
1 ' 1с к = 1
Если U = и, то Q = N я переходим к п.7, иначе к п.6
6. Формируется и упрощается новое выводимое правило. Функ
ция F инвертируется и представляется в виде :
F = f Л f Л Л f Л Л f
12 J J
После упрощения получаем новое выводимое правило
г =Г = гЛгЛ,..Л>-.Л...Лг , где г - дизъюнкт.
12 *v V v ,
и формируем признак продолжения JIB (Q = G) .
7. Фиксируются выходные параметры Q, М, г . На этом шаг ЛВ
заканчивается и, в зависимости от значения признака Q, выдается
ответ или производится переход к следующему шагу вывода, но уже
с новой системой правил.
Поскольку логика высказываний не имеет широкого практического применения, го данная идея была реализована для логики предикатов . Отмечено, что предлагаемый метод несет в себе возможность широкого распараллеливания процесса обработки на нескольких уровнях. Причем, за счет особенностей алгоритма решается основная проблема, препятствующая реализации И-параллелизма при ЛВ - проблема связанных переменных.
Проведенный на основе тестовых задач сравнительный анализ метода ускоренного логического вывода и наиболее распространенного метода ЛВ - метода резолюций, показал, что ускоренный метод позволяет на определенном классе задач не только значительно
(в несколько раз) повысить быстродействие, но и сокращает объем производимых вычислений, что особенно важно при наличии ресурсных ограничений. Кроме того, ускоренный метод допускает более естественное и экономное описание задачи, что дает возможность реализозать параллельные вычисления без дополнительных усилий со стороны программиста.
В третьей главе основываясь на отличительных особенностях процедуры выполнения логического вывода ускоренным методом предложена формальная потоковая модель процессов, позволяющая вести параллельную высокоскоростную распределенную обработку данных. Модель поддерживает все четыре типа параллелизма, присущие МУЛВ:
на уровне систем;
на уровне правил;
на уровне матриц остатков;
на уровне предикатов.
Выполнен анализ схемы потока логических вычислений. Активация процессов происходит недетерминированно и асинхронно, под воздействием сообщений (пакетов данных), передаваемых от других процессов, причем все вершины могут обрабатываться параллельно (за исключением связи родитель-наследник). На уровне систем (V-лроцессов) отсутствует необходимость сохранения внутреннего состояния вершин. Используя особенности МУЛВ удалось сократить количество типов сообщений в формальной модели до двух: CREATE и END,
Практическая ценность разработанной модели заключается в возможности построения высокоэффективного процессора логического вывода.
Вводится понятие абстрактной машины логического вывода (AM), соответствующее по уровню описания известной машине Уоррена. Определены структура AM и система команд, отличающаяся иерархичностью и небольшим количеством элементов на каждом уровне. Для повышения быстродействия AM и более полной реализации преимуществ МУЛВ используется двухуровневая организация вычислительного процесса: динамическая на уровне операторов и статическая на урозне команд. Данный подход позволяет сочетать эффективность
динамического управления и производительность статической организации вычислительного процесса. Использование самоопределяемого (тегированного) представления команд и данных позволяет сократить объем памяти машины ЛВ и повысить скорость выполнения программ на языке высокого уровня. Рассмотрены алгоритмы функционирования основных элементов AM и форматы сообщений, передаваемых между узлами AM.
Переход от AM к тому или иному техническому проекту разработки ПЛВ базируется на современной концепции абстрактной машины , отражая общую идеологию реализации логического вызода в высокопроизводительных прикладных системах. В рамках этого направления разрабатываются как специализированные системы (например, Пролог-процессоры), так и системы на базе универсальных ЭВМ. В данной работе выбран вариант создания специализированной СЛВ.
Далее проанализированы базовые архитектурно-структурные решения (АСР) потоковых ПЛВ и сформулированы принципы построения ПЛВ и его основных подсистем - процессора команд (ПК) и исполнительного процессора (ИП). На уровне структуры обосновано решение объединить в единый модуль исполнительный процессор к блок рабочей памяти (РП). Система команд ПЛВ ориентирована на обработку тегированных данных, путем включения команд установки, проверки и перехода по значению тега. Использование ассоциативной памяти пакетов позволяет упростить определение готовности команд. Выбранная структура ПЛВ (с мультиплексированием ИП), позволяет ввести еще два типа параллелизма:
параллельную выборку и исполнение команд;
параллельную обработку нескольких команд на исполнительных процессорах.
Однако для получения требуемой производительности при решении масштабных задач обработки знаний необходимо создавать системы логического вывода, состоящие из сотен и даже тысяч ПЛВ.
Основываясь на современных тенденциях проектирования вычислительных систем, ориентированных на высокоскоростную параллельную обработку, предлагается обобщенная многоуровневая структура мультипроцессорной СЛВ для аппаратной поддержки ускоренного метода (МПСЛВ МУЛВ). Особенностью данной системы является распределенная конфигурация с локальным адресным пространством на верхнем уровне обработки (обработки систем правил) и конфигурация с
общей памятью на уровне обработки правил и матриц остатков. Данная структура СЛВ наиболее полно соответствует особенностям МУЛВ и организации вычислительного процесса в AM и позволяет реализовать следующие типа параллелизма:
параллельную обработку систем правил на V-процессорах;
параллельную обработку правил на ПЛВ;
параллельную обработку матриц остатков и предикатов на исполнительных процессорах;
параллелизм при обращении к общей памяти и кэш-памяти;
параллелизм между выполнением логического вывода ка ИП и обработкой сообщений на ПК.
В четвертой главе приведены сравнительные оценки эффективности потоковых ПЛВ и ПЛВ с архитектурами традиционного типа. Получены оценки для определения условий достижения выигрыша от использования потокового принципа управления, объединения ИП и РП в общий модуль, использования ассоциативной памяти.
Также выполнен анализ эффективности различных архитектурных решений СЛВ по среднему времени решения задачи, информационной и обменной сложности, с учетом количественных характеристик эталонных задач в условиях ресурсных ограничений. Так, например, производительность (среднее время получения всех решений логической задачи) для однопроцессорной системы (Т ), системы, состоящей из R процессоров (Т ), и предлагаемой мультипроцессорной системы для аппаратной поддержки ускоренного метода (Т ) вычисляется по формулам:
d Nond
Т, = (1-а) F — t + « N - t
1 and л 1 1
. Г . ] . t + 1/2 . F 1 t ,
L 2R N (N-l)J " L 2R J u
T = 1/2
[
I Je-1 ї /Я -t
1-(1-«) N t
J var R
N + 1 N"
где: - R - количество процессоров в системе;
t ,t ,t - среднее время выполнения одной операции (время обработки одной вершины) на соответствующей СЛВ;
N - общее число вершин в графе задачи;
N - число обрабатываемых вершин для МУЛВ;
N - число ИЛИ-вершин;
- N - число И-вершин;
- N - число И-вершин со связанными переменными;
va г *
<х - вероятность отказа ветви;
к - средний коэффициент связности переменных;
- d - средняя длина ветви в графе.
Проведенный анализ позволяет утверждать, что:
информационная сложность МПСЛВ МУЛВ меньше других систем логического вывода;
обменная сложность МПСЛВ МУЛВ меньше других многопроцессорных (в том числе потоковых) СЛВ;
по производительности МПСЛВ МУЛВ на определенных классах
N'
задач имеет преимущество до 2R rj раз;
- с увеличением объема задачи (увеличением количества вер
шин в графе) преимущество МПСЛВ МУЛВ над остальными системами
возрастает.
Для доказательства корректности алгоритмов функционирования основных элементов абстрактной машины и проверки полноты ее системы команд была разработана диалоговая система моделирования (ДСМ) однопроцессорной потоковой машины логического вывода, реализующей ускоренный метод. ДСМ позволяет проверить работоспособность ускоренного метода ЛВ, безопасность динамической модели МУЛВ, провести анализ эффективности сокращения количества типов сообщений в AM и организации буфера готовности команд в виде LIFO-стека. Развитый дружественный интерфейс пользователя делает систему моделирования пригодной для применения в учебном процессе .