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

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

РГБ ОД

Страбыкпн Дмитрий Алексеевич .

1 7 ДПр

МАШИНЫ ЛОГИЧЕСКОГО ВЫВОДА НА ОСНОВЕ ТЕОРИИ ПАРАЛЛЕЛЬНЫХ ДЕДУКТИВНЫХ И АБДУКТИВНЫХ ВЫЧИСЛЕНИИ

Специальности: 05.13.13 - Вычислительные машины, комплексы, системы и сети; 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

Автореферат

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

Санкт-Петербург - 2000

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

Научный консультант:

доктор технических наук, профессор Пузанков Д.В.

Официальные оппоненты:

доктор технических наук, профессор В.Н. Вагин

доктор технических наук О.Г. Кокаеа

доктор технических наук, профессор B.C. Фомичев

Ведущая организация - Институт точной механики и вычислительной техники им. С.А. Лебедева Российской АН

Защита состоится " 25 " апреля 2000 г. в часов на заседании диссертационного совета Д 063.36.08 Санкт-Петербургского государственного электротехнического университета "ЛЭТИ" по адресу: 197376 Санкт-Петербург, ул. Проф. Попова, 5.

С диссертацией можно ознакомиться в библиотеке университета. Автореферат разослан ".?/ " марта 2000 г.

Ученый секретарь диссертационного совета Экало А. В.

Ъ8И>. О

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

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

Проблема создания высокопроизводительных МЛВ имеет три составляющие.

Первая составляющая связана с разработкой методов логического вывода. Здесь, вероятно, отправным методом следует считать разработанный Дж. Робинсоном (1965 г.) метод резолюций. Существуют и другие не менее сильные методы логического вывода: метод Маслова, вывод на основе интерпретаций Бета, сравнений по образцу (pattern matching) и др. Тем не менее, именно для метода резолюций была разработана Р. Ковальским идея процедурной интерпретации логического вывода, которая дала начало собственно логическому программированию как языку, технологии и парадигме. Несомненно, что среди языков логического программирования ведущее место в этом отношении занимает язык ПРОЛОГ и его многочисленные версии. Создание программного обеспечения для описания задачи и реализации логического вывода образуют вторую составляющую проблемы.

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

Весьма продуктивным здесь оказался подход, основанный на использовании абстрактных ПРОЛОГ-машин, и, прежде всего, широко известной абстрактной машины Д. Уоррена.

Большинство современных машин логического вывода реализовано на базе ПРОЛОГ-процессоров, основным недостатком которых является низкая производительность. Чтобы повысить быстродействие ПРОЛОГ-машин, были

предприняты попытки модифицировать "чистый" ПРОЛОГ в его параллельные версии. Однако должного эффекта не было достигнуто, поскольку в основе языка ПРОЛОГ лежит последовательный принцип SLD-резолюции. Производительность созданных ПРОЛОГ-машин не превышает уровня 10 MLIPS, в то время как для масштабных задач требуется производительность порядка 1 GLIPS.

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

Основная часть исследований, посвященных теории и методам лопгче-ского вывода, проводится в России под эгидой Ассоциации искусственного интеллекта. Большое влияние на развитие исследований в этой области искусственного интеллекта оказали работы Д.А. Поспелова, Г.С. Осипова, В.Н. Вагина, В.К. Финна, В.Ф. Хорошевского, Е.А. Сидоренко и др. Теоретические основы построения высокопроизводительных проблемно-ориентированных вычислительных систем были заложены в работах Э.В. Евреинова, Ю.Т. Косарева, И.В. Прангишвили, В.Б. Смолова, Е.П. Балашова, Д.В. Пузанкона, A.B. Каляева, В.В. Корнеева и др. Важные результаты на пути создания высокопроизводительных ПРОЛОГ-машин получили В.А. Вишняков, Д.Ю. Буландже, О.В. Герман, B.C. Фомичев, А.И. Водяхо, A.A. Власов и др. В предлагаемой работе решение данной проблемы рассматривается в рамках научного направления "Высокопроизводительные системы обработки данных и знаний".

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

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

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

1. Разработка основ теории параллельных дедуктивных и абдуктивных вычислений, в том числе:

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

- разработка методов параллельного дедуктивного вывода;

- разработка методов параллельного абдуктивного вывода.

2. Разработка и исследование модели вычислений и абстрактной машины логического вывода, в том числе:

- разработка основ языка декларативного логического программирования;

- разработка модели параллельных логических вычислений для дедуктивного и абдуктивного вывода;

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

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

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

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

- разработка базовых архитектурно-структурных решений для создания быстродействующих процессоров логического вывода;

- исследование вопросов оценки эффективности и применения машин логического вывода.

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

Научная новизна. В результате проведенных исследований получены следующие научные результаты.

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

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

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

4. Разработаны основы языка декларативного программирования -АЛОГ. Семантика языка АЛОГ базируется на методах параллельного дедуктивного и абдуктивного вывода, разработанных в рамках исчисления предикатов 1Р. Отличительными особенностями языка являются: использование дизъюнк-

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

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

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

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

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

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

Внедрение результатов. Диссертационная работа является обобщением результатов, полученных автором в Ленинградском электротехническом институте им. В. И. Ульянова /Ленина/ и в Вятском государственном техническом

университете в процессе выполнения в 1975-1998 годах научно-исследовательских работ, в том числе: "Диалоговые микропроцессорные системы управления цифровыми приборами" (Ленинград, КБ "Импульс"), "Применение микропроцессорных систем в высшей школе. Диалоговые микропроцессорные системы управления экспериментальными установками" (Г/б № 6.30.11), "Теория и применение машин логического вывода" (в рамках проблемного совета "Высокопроизводительные системы обработки данных и знаний" АТНРФ).

Результаты исследований внедрены в серийное производство в составе первых отечественных приборов со встроенными диалоговыми системами управления "Генератор импульсов Г5-90" и "Ритмокардиоскоп РКС-02", а также использованы в лабораторных установках по микропроцессорной технике. Теоретические и практические материалы диссертации использованы в учебном процессе Вятского государственного технического университета при разработке лекционных курсов и лабораторных практикумов по дисциплинам: "Организация ЭВМ, комплексов и систем", "Микропроцессоры и микропроцессорные системы" и "Системы искусственного интеллекта". Написаны и опубликованы три учебных пособия.

Апробация работы. Основные научные и практические результаты исследований по теме диссертации докладывались и обсуждались на Всесоюзной конференции "Однородные вычислительные системы и среды" (Киев, 1975), Всесоюзных совещаниях "Микропроцессоры" (Рига, 1975, 1978), Всесоюзном совещании "Автоматизация проектирования средств вычислительной техники и перспективы применения микропроцессоров" (Минск, 1978), ГУ Всесоюзном научно-техническом совещании "Интерактивная технология в САПР" (Таллин, 1981), областных научно-практических конференциях "Научный потенциал вузов народному хозяйству" (Киров, 1987, 1989), IV Национальной конференции с международным участием "Искусственный интеллект-94" (Рыбинск, 1994), научно-технических конференциях "Диагностика, информатика, метрология, экология, безопасность" (Санкт-Петербург, 1995, 1997), международной конференции "Новые информационные технологии и системы" (Пенза, 1996), II международной научно-технической конференции "Моделирование и исследование сложных систем" (Москва, 1998), региональной научно-технической конференции "Наука-производство-технология-экология" (Киров, 1998), VI научно-технической конференции "Искусственный интеллект - 98" (Пущино, 1998). Под руководством автора по тематике исследований выполнены и успешно защищены три кандидатские диссертации.

Публикации. Материалы диссертации опубликованы в 63 работах. Из них одна монография, 3 учебных пособия, 29 статей, 16 тезисов докладов на научных конференциях, 14 авторских свидетельств.

Структура и объем диссертации. Диссертация состоит из введения, шести глав, заключения, списка использованной литературы, включающего 222 наименования, и четырех приложений. Основная часть работы изложена на 299 страницах машинописного текста. Работа содержит 81 рисунок и 19 таблиц.

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

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

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

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

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

Одним из важнейших вопросов при построении логических исчислений является экспликация логического следования. В соответствии с принятой в работе точкой зрения задача адекватной экспликации логического следования может быть удовлетворительно решена за счет описания класса всех корректных утверждений вида Хн> У, где X и У суть формулы, смысл и значение логических констант которых задаются некоторым совершенно независимым от понимания знака (н») способом. Иными словами, логические связки в формулах, между которыми устанавливается отношение логического следования, должны быть четко определены до экспликации самого логического следования и независимо от нее. Очевидно, что в распространенных сегодня имшшкативных исчислениях, в формулах которых не только главный знак импликации, но и все возможные ос-

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

Исчисление I строится следующим образом.

Алфавит. Исходными символами исчисления являются: бесконечное число алфавитно-упорядоченных переменных: аДсДа^Ь],...; пропозициональные логические константы: 1-(истина), О-(ложь), V-(дизъюнкция), &-(конъюнкция) и - - (отрицание); скобки; ь-> - знак непосредственного логического следования; => - знак логического вывода.

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

Секвенции. Выражение вида Хн> У есть формула логического следования (секвенция), если и только если X и У - пропозициональные формулы.

Аксиомы. А1.рь>р. А2.ря>-»яр. АЗ. (р^с})п-»ргудг.

Правила доказательства (вывода). Наибольший интерес представляют следующие правила.

Л1. Правило переноса.

1) Для конъюнктивного сомножителя: рХн> Y=>Xl->Yv р .

2) Для дизъюнктивного слагаемого: Хь->Уу я Хн> У.

172. Правило разъединения-соединения.

1) Для конъюнктивных сомножителей: Хь->У7оХ|-»У,Х|->2.

2) Для дизъюнктивных слагаемых: XvYl->ZoX^-»

ПЗ. Правило предположения. ЫЯ, l^->XvZ, ll->YvZ => \\-tZ, если 1) ХУн>0 или (иначе) 2) X V У. Правило предположения (ПЗ) естественным образом обобщается на К секвенций: ll->X\vZ, 1 н> Х2-/2,..., =>

lн>Z, если ХА—Хк.!-» О, или (иначе) Ян Х^ V X2v...v Хк.

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

Построение абдуктивпых объяснений. Пусть знания представлены множеством М дизъюнктов основных посылок и дано множество т дизъюнктов наблюдения. Задачей абдуктивного вывода является нахождение такого множества Мп дизъюнктов дополнительных посылок (абдуктивного объяснения наблюдения), что МиМв => ш и МиМо - совместно.

Определено понятие суперпозиции секвенций, с помощью которого определены понятия вывода логического следствия и схемы логического вывода в исчислении I (рис.1). Доказана теорема, связывающая понятие логического следования с понятием противоречивости для логического вывода с помощью правила предположения.

7)МРНЖ; 8) 11—> Б;

11) Км V; 12) 5ин> X; 13) > У; 14)Хь->2.

Посылка:

1)АВн>С; 2)1н>0; 3) СОн>Е; 4)Ен>Ц

5) 1 Р; 6)И-ЖуТ;

Заключение: ABM^->ZvY.

Рис.1

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

Операция деления дизъюнктов. Обозначим множества литералов, входящих в дизъюнкты Д и с1, через О ¡= {Ь1, .Ь'з,..., Ь Ь1^},

с! }, а через 0 - пустое множество. Кроме того, символ "-"

будем использовать как знак разности множеств. Операция деления дизъюнкта О на дизъюнкт с1, результатом которой является остаток Ь, записывается так: О-г <1=Ь. Операция представляет собой исключение из дизъюнкта В литералов, содержащихся в дизъюнкте 6. Результат операции - остаток Ь определяется по следующим правилам: 1) если Вг>3 = 0,то Ь=];2) если V ей ,то Ь=0; 3) если бп<1*0 и Й-ё = Ь, Б *0,то гдеЬ5бЬ.

Процедура вывода. Специальная процедура вывода, названная процедурой деления дизъюнктов, основана на операции деления дизъюнктов и правиле предположения (ПЗ). Для удобства описания процедуры введем ряд обозначений.

У=<М,с1^,М1,т> - процедура деления дизъюнктов, в которой: М={П1Д)2,..-Л,...Д31} - множество дизъюнктов исходных секвенций;

- дизъюнкт ¡-й секвенции, состоящий из литералов

Ц; - дизъюнкт заключения, состоящий из литералов

Ц; q - признак окончания вывода, имеющий три значения: "О" - вывод завершен успешно, "1" - вывод завершен неудачно, "С' - требуется продолжение вывода; М] — новое множество дизъюнктов исходных секвенций; т - новое множество дизъюнктов выводимых секвенций.

Процедура вывода применима, если М*0 и Кг 1 (¡=1,...Д), иначе сразу устанавливается признак В процедуре выполняются следующие действия.

1. Все дизъюнкты исходных секвенций делятся на дизъюнкт выводимой секвенции: Ь^Б^с!, ¡=1,...,1.

2. Составляется секвенция для проверки первого условия правила пред-

I

положения (ПЗ): д Ь; и производится ее анализ: ¡=1

1) если все остатки Ьг=1, то вывод невозможен и <5=1; производится переход к пункту 5;

I

2) выражение дЬ(н-»0 упрощается путем перемножения дизъюнктов и

¡=1

исключения конъюнкций, содержащих сомножители вида ЬЬ (ОЬ), и производится проверка: не является ли это выражение теоремой исчисления I. Если преобразуемая таким образом секвенция оказывается теоремой исчисления I (0(-> 0), то вывод успешно завершается (ч=0) и производится переход к пункту 5; в противном случае выполняется следующий пункт.

3. Полученное после перемножения дизъюнктов и упрощения выражение является дизъюнктивной формой вида: в которой

Это выражение преобразуется с помощью правила разъединения - соединения (П2) в множество секвенций: ..Ь^р 0, р=1,2,...,Р. Затем каждая такая секвенция с использованием правила переноса (П1) преобразуется в секвенцию вида: 1ь-> Хр, правая часть которой трансформируется в новый дизъюнкт. Полученные таким образом секвенции в соответствии со вторым условием правила предположения (ПЗ) рассматриваются, как новые выводимые секвенции и их дизъюнкты включаются в множество т. Устанавливается значение признака окончания вывода q=G.

4. Формируется новое множество дизъюнктов исходных секвенций: М)=М-Мо, где Мо — подмножество дизъюнктов множества М, для которых выполняется условие И

5. Конец процедуры.

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

Процесс вывода заканчивается, когда на очередном шаге обнаруживается дизъюнкт, для которого вывод невозможен (q=l), или для всех выводимых на данном шаге дизъюнктов будут сформированы признаки успешного завершения вывода (q=0). Логический вывод методом деления дизъюнктов можно предста-

Для описания метода используется индексная функция i(h), которая определяется для индексной переменной t следующим образом: i(l)=T, t=l,...,T; i(2)=t.tt=i(]).tiCI), t¡(l)=l,..., Т,-(1>; i(3)=t.ME (E=t.tt), ¡(3)=1(2)Лю, tiW=l,...,T¡(2); и т. д. В общем случае: i(h+l)=i(h).t¡m, tl(ll)=l,..., T¡(h). Считается, что ¡(0) означает отсутствие индекса у индексируемой переменной (T¡(0)=T), а также что i(l)=i(O).t¡(0)=t. Обозначим через h номер шага вывода, а через Q общий признак окончания вывода, тогда описание метода можно представить в следующем виде.

1. Определение начальных значений: h=l, M¡m=M, i(l)=t; t=l,...,T, где T-число выводимых секвенций (число дизъюнктов в выводимой секвенции).

2. Выполнение процедур текущего (h-ro) шага. Для выводимых дизъюнктов множества m на первом шаге (h=l), а в последующем (h>l) для дизъюнктов множеств m¡0,.i), полученных в процедурах предыдущего шага, характеризуемых признаками ql(>i)=G выполняются следующие процедуры:

V¡(h)=<M¡(h.1),d¡(11))q[(ll),M„;i,),mi(h)>, ¡(Ь)=](Ь-1)Д;р,.1); t¡(í,.¡)=],...,T¡(h.¡).

3. Формирование и проверка общего признака окончания вывода (Qh) и переход к следующему шагу или завершение вывода.

в

Qh= V гДе A=t¡(h-i)> B=T¡(h.i).

А=1

Если Qh=G, то h увеличивается на единицу и процесс продолжается (выполняется пункт 2), иначе вывод завершается. Причем при Qi,=0 вывод завершается успешно, а при Qh=l - неудачно.

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

вить схемой процесса логического вывода (рис.2).

d, м

' mi~{du,dj,2,di.j,dM} ^ qt—G Q,=G

h=2 Qr-G

h=3 Qj-0

qi.i2=0 qiu=0 qi¡.i=0 Рис .2

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

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

Посылки:

1)Х|->Е; 2)Аь-*В;

3)В)->С; 4)1.ь->2;

5)11-» Л; 6)11СР(->0; 7) г(-> в; 8)Оь-»У.

Заключение (наблюдение): Хн>0

-о-

Дополнительные посылки: ЕН> AVL, ЕН^РУЬ.

Рис.3

2. Методы параллельного логического вывода делением дизъюнктов.

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

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

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

• операция деления днзъюнктов выполняется с учетом унификации литералов и в общем случае порождает не один, а множество остатков;

• используется два типа процедур деления дизъюнктов: частичного и полного;

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

• допускается многократное использование дизъюнктов посылок в процессе логического вывода;

• полученные ранее остатки сохраняются и предусматривается защита от зацикливания процесса логического вывода.

2.2. Базовый метод дедуктивного вывода. Разработан базовый метод дедуктивного логического вывода на знаниях, представленных выражениями предикатов первого порядка. Метод отличается от известных содержанием выполняемых преобразований и широкими возможностями по распараллеливанию процесса вычислений.

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

"Производная" Д1ПЪЮНКТа Ь[Ь], содержащего литерал 1„, по лите-

ралу Ь' дизъюнкта (3 определяется следующим образом:

если литералы Ь и I/ не унифицируются;

дЬ'

дЬ1Ьи, если литералы Ь и Ь' унифицируются и дизъюнкт Ь[Ь] содер-дЬ'

жит только литерал Ь;

д^ГЦ-^ если литералы Ь и Ь' унифицируются и дизъюнкт Ь[Т.] со-дЬ'

держит более одного литерала. Здесь Ь(Ъ]^ к Г., т.е. представляет собой остаток, получающийся из дизъюнкта Ь[Ь] после применения к нему унифицирующей подстановки А. и исключения литералаЬ.

Введена матрш^ "производных", содержащая все производные одного дизъюнкта по литералам другого. Матрица "производных" дизъюнкта Ь по дизъюнкту (1 вычисляется следующим образом:

Ц[М] =

= Ак

зи 1

где 3=1,...,1 и к=1,...,К, причем J - число литералов в дизъюнкте Ь, а К - в дизъюнкте <1.

Частичное деление дизъюнктов. Частичное деление дизъюнктов выполняется с помощью специальной процедуры образования остатков, в которой порождение остатков осуществляется с помощью вычисления матриц "производных". Процедура предполагает, что посылки и заключение представлены в виде дизъюнктов. Процедура образования остатков (о =<Ь,с1^,п> имеет

следующие параметры: Ь - остаток-делимое (дизъюнкт посылки), используемый для получения остатков; (1 — остаток-делитель (дизъюнкт заключения), участвующий в образовании остатков; q - частный признак решения, имеющий три значения: "О"- получен хотя бы один нулевой остаток, "1"- все полученные остатки равны единице, "§"- получено более одного остатка, не равного единице при отсутствии нулевых остатков; п={<Ь(,<1е>, 1=1,...,Т} - множество пар, состоящих из нового остатка-делимого Ь, и соответствующего ему остатка-делителя ¿о сформированных в результате применения процедуры со .

Полное деление дизъюнктов. Полное деление дизъюнктов направлено на получение так называемых конечных остатков. Остаток-делимое Ь является для остатка-делителя (1 конечным, если применение к нему процедуры со =<Ь,с1^,п> не порождает новых отличных от единицы остатков. Конечным может быть исходный остаток Ь или вновь полученный остаток Ьъ если соответствующие им матрицы "производных" состоят только из единиц. В базовом методе дедуктивного вывода при полном делении дизъюнктов в результирующее множество остатков включаются только основные остатки, к которым относятся однолитеральные конечные остатки, а также конечные остатки с двумя и более литералами, не содержащими переменных. Полное деление дизъюнктов выполняется с учетом фактов (однолитеральных исходных дизъюнктов). Множество основных остатков N от деления дизъюнкта посылки Б на дизъюнкт заключения (1 позволяет найти процедура О =<ВД(5,>}>, в которой О - признак решения, имеющий три значения: "О" - решение найдено, "1" - дизъюнкт Б не имеет по дизъюнкту <1 остатков, отличных от единицы, "в" - получено множество остатков, отличных от единицы.

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

(4=1).

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

\у=<МДо,р,т> - базовая процедура вывода, в которой: М={В|ДЭ2,...,В1,...Д)1} - множество дизъюнктов исходных секвенций, О,—Ь1, - дизъюнкт 1-й секвенции, состоящий из литералов

Ц; (1=1^1^.- дизъюнкт секвенции-заключения, состоящий из литералов Ьк; о=<с,С> - пара множеств текущих остатков, состоящая из мно-

жеста остатков, образованных до выполнения (с) и после выполнения (С) процедуры; р - признак окончания вывода, имеющий три значения: "О"- вывод завершен успешно, "1"- вывод завершен неудачно, "О" - требуется продолжение вывода для полученных выводимых секвенций; т - множество дизъюнктов новых выводимых секвенций.

Базовая процедура вывода использует в качестве субпроцедуры С2 -процедуру формирования остатков.

Базовый метод вывода, Вывод методом деления дизъюнктов заключается в многократном применении \у-процедур и состоит из ряда шагов. На каждом шаге вывода \у-процедуры применяются к имеющимся выводимым и исходным дизъюнктам, образуя новые выводимые дизъюнкты, используемые на следующем шаге. Процесс вывода заканчивается, когда на очередном шаге обнаруживается дизъюнкт, для которого вывод невозможен (р=1), или для всех выводимых на данном шаге дизъюнктов будут сформированы признаки успешного завершения вывода (р=0). Метод деления дизъюнктов применим, если выводимые дизъюнкты не являются тавтологиями, а их конъюнкция - противоречием.

Шаг вывода к Для каждого выводимого дизъюнкта ¿.(щ всех множеств Ш;(ь-1) выполняются лу-процедуры:

™вд=<МДао,о1<ч,р1(ь),тад>,

Формируется и проверяется общий признак окончания вывода Ь-го шага:

Б

= V Рад. где А'Пф.ц»В=т!(ь-1У

А-=1

Если Рь=0, то Ь увеличивается на единицу и процесс продолжается (выполняется (Ь+1)-й шаг вывода), иначе вывод завершается. Причем при Рь=0 вывод завершается успешно, а при Рь=1 - неудачно.

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

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

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

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

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

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

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

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

Логический вывод методами деления дизъюнктов характеризуется четырьмя уровнями параллелизма:

1) уровень обработки систем дизъюнктов (все системы, состоящие из дизъюнктов исходных посылок и дизъюнкта заключения, могут обрабатываться одновременно);

2) уровень обработки пар дизъюнктов (процедуры полного деления дизъюнктов во всех парах "исходный дизъюнкт - дизъюнкт заключения" систем дизъюнктов могут быть выполнены параллельно);

3) уровень обработки пар остатков (процедуры частичного деления дизъюнктов для всех пар "остаток делимого - остаток делителя" в процессе полного деления дизъюнктов могут выполняться одновременно);

4) уровень обработки пар литералов (унификация всех пар литералов, один го которых принадлежит дизъюнкту делимого, а другой — дизъюнкту делителя, может выполняться одновременно).

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

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

соответствующие механизмы вычислений, основанные на механизмах управления и передачи данных.

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

3.2. Основы языка логического программирования АЛОГ. Естественное и даже неизбежное развитие языковой технологии отрывает процесс программирования от выделения в целом модели вычисления. При этом основная идея программирования все более опирается на абстрактную спецификацию проблем, нежели на описание методов их решения. В языках логического программирования данная идея проявляется в переходе от процедурных языков программирования к декларативным. Однако даже такой широко известный язык, как ПРОЛОГ, объявленный первоначально декларативным языком, имеет достаточно большую процедурную составляющую. Это вынуждает программиста при разработке программы детально продумывать и процесс ее будущего выполнения с учетом особенностей и ограничений модели вычислений, используемой в ПРОЛОГЕ. Рассматриваемый в работе язык декларативного программирования АЛОГ не имеет такой жесткой связи между программой и процессом ее выполнения.

Язык декларативного логического программирования. В основе языка АЛОГ лежит исчисление предикатов 1Р. АЛОГ во многом напоминает такие языки, как ПРОЛОГ и ДЕЙТ АЛОГ, но имеет и ряд существенных отличий, обусловленных возможностью программирования абдуктивного вывода и использованием дизъюнктов общего вида.

Структура языка основана на понятиях атома, переменной, функтора, предиката, терма, литерала и дизъюнкта.

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

торое есть атом, и арностью (числом аргументов). Предикат представляется так же, как и функтор. Каждый предикат определяет отображение домена D, на котором он задан, в множество значений {true, false}. Термами являются атомы и переменные. Структурированные термы строятся рекурсивно с помощью применения функторов к другим термам. Литералом называется терм или его отрицание, если самым внешним символом терма является символ предиката.

Дизъюнкт представляет собой совокупность литералов. Существуют два типа дизъюнктов: исходные (D) и выводимые (d). Исходные дизъюнкты, состоящие из единственного литерала, называются фактами. Следует заметить, что в соответствии с методом преобразования произвольных выражений исчисления предикатов IP в множество дизъюнктов каждый дизъюнкт является замкнутой формулой. Это означает, что дизъюнкт не содержит свободных переменных и имя переменной, появляющейся в нем, имеет смысл только в пределах дизъюнкта.

Программа Р представляется в виде двух конечных множеств дизъюнктов: M={D],...J)m} и m={di,...,dm}. Программе в исчислении предикатов IP соответствует следующая формула: Di&D2&...&Dm=> d[&d2...&drt.

Элементарной подстановкой называется пара: <переменвая, терм>. Элементарная подстановка представляется в виде одноместного псевдопредиката, определяемого как терм, самым внешним символом которого является переменная. Подстановка - это совокупность элементарных подстановок.

Решением г считается подстановка, состоящая из псевдопредикатов, именами которых являются переменные выводимых дизъюнктов.

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

Предикатом задания на. логический вывод является предикат tasMyiBmsK, R,H,Q,P,QA). В этом предикате переменные V - вид вывода, Нпзах

- максимальное число шагов и R - форма решения являются входными и определяют условия проведения логического вывода. Входным переменным до начала логического вывода присваиваются значения из соответствующих множеств значений: Ve {dv, av}, dv - дедуктивный вывод, av — абдуктивнъгй вывод; Hmaxe {1,2,3,4,...}; Re {one, all}, one - поиск одного решения, all - поиск всех решений. Остальные переменные в предикате задания являются выходными: Н

- фактически выполненное число шагов вывода, Q - признак наличия решений дедуктивного вывода, Р - признак возможности продолжения дедуктивного вывода, QA - признак наличия решений абдуктивного вывода. Значения этих переменных определяются после завершения лопгческого вывода, причем Не {1,2,3,4,...}, a Q,P,QAe {yes, по}.

Семантика языка АЛОГ основана на методах параллельного дедуктивного и абдуктивного вывода, разработанных в рамках исчисления предикатов первого порядка IP. Язык АЛОГ имеет следующие отличия от наиболее распространенных языков логического программирования:

•для описания посылок и заключения используются не только дизъюнкты Хорна, но и дизъюнкты общего вида, в которые могут быть преобразованы произвольные выражения логики предикатов;

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

•порядок записи литералов в дизъюнктах и дизъюнктов в программе на языке АЛОГ не влияет на результаты логических вычислений, т.е. язык является действительно декларативным.

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

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

4. Разработка архитектуры и программ абстрактной машины параллельного логического вывода. Анализируются архитектуры параллельных ЭВМ и высокопроизводительных машин логического вывода, разрабатывается абстрактная векторная машина параллельного логического вывода и интерпретатор АЛОГ-программ, исследуется организация абстрактных многопроцессорных машин параллельного логического вывода.

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

коммутационной средой, Для описания наиболее сложных из реально существующих многопроцессорных машин достаточно '3-4 уровней иерархии. Критерий классификации машин по числу потоков команд и данных, предложенный Флинном, остается одним из наиболее употребительных. Машины с множественным потоком команд и множественным потоком данных используются для непосредственной реализации моделей параллельных вычислений. Причем, в зависимости от применяемого механизма управления это могут быть директивные, потоковые или запросные машины. В зависимости от сложности реализованных в машине примитивных операций выделяют три типа архитектур: с расширенным набором команд (CISC), с сокращенным набором команд (RISC) и с языком высокого уровня. Кроме того, можно выделить три способа интерпретации команд: схемный, микропрограммный и программный, а также четыре механизма адресации данных: дескрипторный, самоопределяемых данных, потенциальной адресации и стековой адресации.

При построении MJIB, ориентированных на ПРОЛОГ используются два основных подхода. В первом случае создаются машины, внутренним языком которых является ПРОЛОГ (ПРОЛОГ-машикы). Во втором случае создаются машины, системы команд которых базируются на концепции абстрактной машины Уоррена, и предполагается использование компилятора для преобразования логической программы во внутренний язык машины.

4.2. Абстрактная АЛОГ-машнна. Отмечается, что фундаментальное различие между обычными программами, написанными на традиционных императивных языках программирования и программой на языке АЛОГ, представляющей собой формальное описание логической задачи в виде секвенций, заключается не столько в процедурном характере первых и декларативном характере второй, а главным образом в том, что во втором случае структура управления полностью отделена от информации, вводимой в форме секвенций. Т.е. система секвенций может рассматриваться как набор данных, над которым необходимо произвести определенные действия, а сами эти действия заранее известны и могут уже храниться в памяти, или при необходимости вводиться в машину отдельно от данных.

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

можность применения векторной обработки информации для данных со сложной структурой.

Определена система команд абстрактной машины параллельного логического вывода. Система команд имеет следующие особенности.

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

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

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

4.3. Интерпретатор АЛОГ-программ. Разработан интерпретатор АЛОГ-программ, представляющий собой программу абстрактной машины параллельного логического вывода. В отличие от программ на языке АЛОГ, которые фактически выражают условия логических задач, разработанная программа представляет собой алгоритм логического вывода, записанный с помощью системы команд абстрактной машины. Программы логических задач выступают для абстрактной машины в качестве исходных данных. При этом программу абстрактной машины можно считать неизменной.

Программа абстрактной МЛВ имеет следующие особенности.

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

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

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

4.4. Организация абстрактных многопроцессорных машин. Исследованы три подхода к построению МЛВ методом деления дизъюнктов: реализация

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

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

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

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

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

МЛВ, основанная на принципе концентрации ресурсов, имеет следующие преимущества перед машинами с потоковым и запросным управлением.

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

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

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

5. Исследование принципов организации п функционирования высокопроизводительных машин и разработка архитектуры процессора логического вывода. Анализируются принципы организации параллельных ЭВМ, исследуются принципы построения и функционирования высокопроизводительных МЛВ и разрабатывается архитектура процессора логического вывода.

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

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

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

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

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

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

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

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

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

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

Определена система данных. В ПЛВ принято тегированное представление данных. Несмотря на большое число типов данных все данные представляются с помощью только трех форматов элементарных структур данных. Данные сложной структуры представляются в виде векторов, элементами которых являются ссылки на другие вектора. Исключение составляют наиболее часто используемые данные: литералы, функторы и элементарные подстановки. Элементами векторов этих данных являются не ссылки, а сами объекты данных. Такое решение позволяет уменьшите время наиболее часто выполняемых преобразований.

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

Определена система команд. Система команд ПЛВ имеет следующие основные особенности.

1) Сокращенный набор команд (27 основных команд), разделенный в зависимости от выполняемых операций на три типа команд: управления, пересылки и обработки. Все команды имеют единый формат и за исключением отдельных команд пересылки выполняются за один такт.

2) Команды управления, кроме выполнения традиционных функций, обеспечивают анализ тегов и поддерживают работу с регистровыми кадрами (выделение, объявление, аннулирование) и заказами (задание массива выполняемых подпрограмм, переключение на другую программу).

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

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

ность преобразования кода имени подпрограммы в начальный адрес этой подпрограммы в памяти программ, осуществляемое преобразователем начального адреса. Для внутренних обменов информацией в ПЛВ используется система из четырех 32-разрядных магистралей. При объеме внутренней кэш-памяти 16 Кбайт для реализации ПЛВ требуется около 3 млн. транзисторов. Быстродействие ПЛВ на стандартной тестовой программе детерминированной конкатенации списков при тактовой частоте 500 МГц составляет порядка 10 МЫР8.

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

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

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

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

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

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

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

Приложения. Рассмотрены решения задач дедуктивного и абдуктивного вывода (приложение 1), подпрограмма унификации на языке ассемблера ПЛВ (приложение 2), оценка аппаратурных затрат ПЛВ (приложение 3), характеристика проекта по созданию установки автоматического контроля качества пиломатериалов (приложение 4).

ЗАКЛЮЧЕНИЕ

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

При решении проблемы в диссертационной работе получены следующие результаты.

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

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

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

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

4. Разработаны методы параллельного дедуктивного и абдуктивного логического вывода на знаниях, представленных выражениями предикатов первого порядка. Логический вывод методами деления дизъюнктов характеризуется четырьмя уровнями параллелизма (системы дизъюнктов, дизъюнкты, остатки, литералы). Установлено, что логический вывод обобщенным методом может протекать параллельно даже в случае рекурсивного характера исходных правил. Показано, что метод абдуктивного вывода позволяет получать многолитеральные дополнительные посылки, обеспечивающие дедуктивный логический вывод целого класса заключений.

5. Разработаны основы декларативного языка логического программирования АЛОГ. Семантика языка АЛОГ основана на методах параллельного дедуктивного и абдуктивного вывода, разработанных в рамках исчисления предикатов первого порядка 1Р.

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

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

8. Разработана программа абстрактной машины параллельного логического вывода - интерпретатор АЛОГ-программ. В отличие от программ на языке АЛОГ, которые фактически выражают условия логических задач, разрабо-

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

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

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

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

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Страбыкин Д.А. Логический вывод в системах обработки знаний / СП6ГЭ-ТУ; Под ред. Д. В. Пузанкова. - СПб: Изд-во СПбГЭТУ, 1998. - 164 с.

2. Страбыкин Д.А. Организация машин параллельного логического вывода / ВятГТУ - Киров: Изд-во ВятГТУ, 1999. - 189 с.

3. Страбыкин Д.А., Бакшаев A.M. Практикум по микропроцессорным устройствам с использованием диалоговых систем управления / ГГУ - Горький: Изд-во ГГУ, 1989.-105 с.

. 4. Страбыкин Д.А., Флаксман М.Л. Практикум по архитектуре микроЭВМ с использованием диалоговых систем управления / КирПИ - Киров: Изд-во КирПИ, 1993.-80 с.

5. Страбыкин Д.А. Параллельный логический вывода в системах обработки знаний // ВЕСТНИК ВВО АТН РФ, Сер. Высокие технологии в радиоэлектронике, информатике и связи. - 1998. - № 2 (6). - С. 25-29.

6. Балашов Е.П., Пузанков Д.В., Страбыкин Д.А. Многофункциональное использование элементов в вычислительных устройствах // Кибернетика. - 1983. - № 6. -С. 39-44.

7. Барановский A.A., Матвеев В.Д., Страбыкин Д.А. Автоматизированная система оперативного врачебного контроля на основе микроЭВМ / КирПИ. - Киров, 1980. -5 е.-Деп. ЦНИИТЭИ приборостроения 12.06.81, № 1510.

8. Водяхо А.И., Мельцов В.Ю. Страбыкин Д.А. Система параллельного логического вывода // Структуры и математическое обеспечение вычислительных средств. СПб., 1994, С. 60-64. - (Изв. ГЭТУ; Вып. 476).

9. Добрых К.П., Страбыкин Д.А. Пакет программ для лабораторного практикума по архитектуре микроЭВМ // Наука-производство-технология-экология: Сб. материалов регион, науч.-техн. конф., Киров, 14-28 мая 1998 г. - Киров, 1998. - Т. 1. - С. 73-74.

10. Долженкова М.Л., Страбыкин Д.А. Метод построения логического вывода для не полностью определенных задач / КирПИ. - Киров, 1993. -15 с. - Деп. ВИНИТИ 12.09.93, № 2559-В93.

11. Долженкова М.Л., Страбыкин Д.А. Объектно-ориентированная машина аб-дуктивного логического вывода //ВЕСТНИК ВВО АТН РФ, Сер. Высокие технологии в радиоэлектронике, информатике и связи. - 1998. - № 2 (6). - С. 32-36.

12. Долженкова М.Л., Страбыкин Д.А. Организация параллельной системы логического вывода // Новые информационные технологии и системы: Матер, междунар. конф. - Пенза, 1996. -Ч. 1.- С. 45-46.

П.Жданов A.A. Страбыкин Д.А. Адаптация диалога в цифровых измерительных приборах со встроенными микроЭВМ / КирПИ. - Киров, 1988. -7 с. - Деп. ЦНИИТЭИ приборостроения 23.02.88, № 4108.

14. Лукоянычев В.Г., Страбыкин Д.А., Шкебельский В.В. Встроенный дисплей телевизионного типа на основе микропроцессора для отображения информации в медицинских приборах // Техника средств связи. - 1985. - Вып. 3. - С. 83-88.

15. Матвеев В.Д., Милков Л.А., Страбыкин ДА. Цветные видеодисплеи для систем машинной графики // Интерактивная технология в САПР: Тез. докл. IV Всесо-юз. науч. - техн. совещ., Таллин, 12-17 окт. 1981 г.-Таллин, 1981, С. 105-106.

16. Матвеев В.Д., Страбыкин Д.А., Бахшаев A.M. Компьютерный практикум на основе имитационного моделирования микропроцессорных устройств // Управление и обработка информации. - Киров, 1998. - С. 67-72. - (Сб. науч. тр. / ВятГТУ; Вып. 3).

17. Мельцов В.Ю., Родионов Е.П., Страбыкин Д.А. Диалоговые программаторы ПЗУ и ПЛМ // Научный потенциал вузов народному хозяйству: Тез. докл. Обл. науч.-практ. конф., Киров, 12-15 мая 1987 г. - Киров, 1987. - С. 62-63.

18. Мельцов В.Ю., Родионов Е.П., Страбыкин Д.А. Диалоговый программатор интегральных микросхем памяти // Приборы и системы управления. - 1990. - № 8. - С. 21-22.

19. Мельцов В.Ю., Страбыкин Д.А. Метод параллельного логического вывода / КирПИ. - Киров, 1992. -17 с. - Деп. ВИНИТИ 12.11.92, № 3240-В92.

20. Мельцов В.Ю., Страбыкин Д.А. Потоковая машина параллельного логического вывода // Моделирование и исследование сложных систем: Докл. П междунар. науч.-техн. конф., Кашира, 12-15 июня. М.,1998. - Ч. 2: Обработка информации и вычислительные процессы в компьютерных системах. - С. 271-279.

21.Нестерук В.Ф., Пузанков Д.В., Страбыкин Д.А. Принципы организации процессоров на основе многофункциональных регулярных структур // Однородные вычислительные системы и среды: Матер. IV всесоюзн. конф., Киев, 17-21 окт.' 1975 г. -Киев, 1975.-Ч. 1.-С.243.

22. Нестерук В.Ф., Страбьпсин Д.А. Принципы организации ассоциативного поиска информации в запоминающем устройстве И Вычислительная техника и системы управления. - Омск, 1975. - С. 64-69. - (Сб. науч. тр. / ОПИ; Вып. 2).

23. Организация интегральной памяти микропроцессорных систем / Гельман А.Ю., Кочетков В.Е., Пузанков Д.В., Страбыкин Д.А. // Автоматизация проектирования средств вычислительной техники и перспективы применения микропроцессоров: Тез. докл. всесоюзн. совещ., Минск, 18-26 мах 1978 г. - Л., 1978. - С. 50-52.

24. Программная сетевая модель многопроцессорной машины логического вывода / Страбьпсин Д.А., Мельцов В.Ю., Долженкова М.Л., Рыков О.В. П Диагностика, информатика, метрология, экология, безопасность - 97 (ДИМЭБ-97): Тез. докл. науч.-техн. конф., Санкт-Петербург, 1-3 июля 1997 г. - СПб., 1997. - С. 253-254.

25. Пузанков Д.В. Страбьпсин Д.А. Метод сокращения аппаратурных затрат за счет многофункционального использования элементов // Автоматика и вычислительная техника. -1985. - № 2. - С. 84-89.

26. Родионов Е.П., Страбыкин Д.А. Диалоговый программатор ПЛМ К Управляющие системы и машины. - 1988. -Хз 4. - С. 11-16.

27. Родионов Е.П., Страбыкин Д.А. Метод сжатия и восстановления текста для экономии памяти микропроцессорных систем / КирПИ. - Киров, 1985. -14 с. - Деп. ВИНИТИ 21.11.85, № 3220.

28. Рыков О.В., Страбыкин Д.А. Метод ускоренного логического вывода / КирПИ. -Киров, 1993. -16 с. - Деп. ВИНИТИ 10.04.93, № 743-В93.

29. Система оперативного врачебного контроля на основе микроЭВМ с отображением информации на ЭЛТ / Барановский А. А., Князев К.К., Лукоянычев В.Г., Страбыкин Д.А. // КирПИ. - Киров, 1980. -8 с. - Деп. ЦНИИТЭИ приборостроения 12.06.81, №580.

30. Страбыкин Д.А. Абстрактная машина логического вывода методом деления дизъюнктов // Наука-производство-технология-экология: Сб. материалов регион, науч.-техн. конф., Киров, 15-27 мая 1999 г. - Киров, 1999. - Т. 2. - С. 22-24.

31. Страбыкин Д.А. Анализ задач проектирования диалоговых микропроцессорных систем управления измерительными приборами // Электронное моделирование. - 1987. Т. 9, № 1.-С. 65-70.

32. Страбыкин Д.А. Диалоговая система управления приборами и процессами // Научный потенциал вузов народному хозяйству: Тез. докл. Обл. науч.-практ. конф., Киров, 12-15 мая 1987 г.-Киров, 1987.-С. 11.

33. Страбыкин Д.А. Диалоговые микропроцессорные системы для управления приборами // Известия ВУЗов. Приборостроение. - 1988. - Т.З, № 4. - С. 25-29.

34. Страбыкин Д.А. Логический вывод методом деления дизъюнктов при решении антитрестовской задачи // Научный вестник Кировского филиала Московского гуманитарно-экономического института. Киров, 1998. — JSs 1.-С. 182-192.

35. Страбыкин Д.А. Микропроцессор с регулярной структурой на основе интегральных модулей памяти // Микропроцессоры: Тез. докл. 2-го всесоюзн. совещ., Рига, 3-12 июня 1977 г.-Рига, 1977.-Ч. 1 - С. 23-25.

36. Страбыкин Д.А. Микропроцессор с таблично-алгоритмическим операционным устройством // Микропроцессоры: Тез. докл. всесоюзк. совещ., Рига, 5-12 окт. 1975 г. -Рига, 1975. -С. 81-82.

37. Страбыкин Д.А. О функциональных возможностях полупроводниковых интегральных запоминающих устройств // Вычислительная техника. - Л., 1978. - Вып. 7: Многофункциональные регулярные вычислительные структуры. - С. 81-88.

38. Страбыкин Д.А. Обобщенное проектирование микропроцессорных систем / КирПИ. - Киров, 1986. -13 с. - Деп. ЦНИИТЭИ приборостроения 21.05.86, № 3350.

39. Страбыкин Д.А. Организация вычислительных процессов в многопроцессорной машине параллельного логического вывода // Наука-производство-техвология-экология: Сб. материалов регион, науч.-техн. конф., Киров, 14-28 мая 1998 г. - Киров, 1998,-Т. 1.-С. 53-54.

40. Страбыкин Д.А. Основы языка декларативного программирования машины параллельного дедуктивного и абдуктивного вывода // ВЕСТНИК ВВО АТН РФ, Сер. Проблемы обработки информации. - 1998. - Вып. 1. - С. 7-11.

41. Страбыкин Д.А. Параллельный логический вывод методом деления дизъюнктов //Управление и обработка информации. - Кзгров, 1998. - С. 89-101. - (Сб. науч. тр. / ВятГТУ; Вып. 3).

42. Страбыкин Д.А. Управление цифровыми измерительными приборами с помощью встроенных микроЭВМ // Приборы и системы управления. - 1983. - X» 11. - С. 11-13.

43. Страбыкин Д.А. Экспериментальное исследование микропроцессорных устройств с помощью диалоговых систем управления // Микропроцессорные средства и системы. - 1987. - № 4. - С. 62-64.

44. Страбыкин Д.А., Долженкова МЛ. Метод и программа построения логического вывода для не полностью определенных задач // Искусственный интеллект-94: Сб. науч. тр. Нац. конф. с междунар. участием, Рыбинск, 15-21 сент. 1994 г. - Рыбинск, 1994.-Т. 2.-С. 300-304.

45. Страбыкин Д.А., Долженкова М.Л., Рыков О.В. Система логического вывода для не полностью определенных задач // Диагностика, информатика, метрология, экология, безопасность - 95 (ДИМЭБ-95): Тез. докл. науч.-техн. конф., Санкт-Петербург, 4-6 июля 1995 г. - СПб., 1995. - С. 160-161.

46. Страбыкин Д.А., Носов А.А. Организация движения графиков на экране измерительного прибора / Редакция журнала Приборы и системы управления - М., 1984. -7 с. - Деп. ЦНИИТЭИ приборостроения 22.12.84, № 2695-Б84.

47. Страбыкин Д.А., Рыков О.В. Логический вывод методом параллельной редукции и его аппаратная поддержка // Искусственный интеллект-94: Сб. науч. тр. Нац. конф. с междунар. участием, Рыбинск, 15-21 сенг. 1994 г. - Рыбинск, 1994. - Т. 2. - С. 296-300.

45. Толканов В,А, Страбыкин Д.А. Программа обучения игре в шахматы // Наука-производство-технология-экология: Сб. материалов регион, науч.-техн. конф., Киров, 14-28 мая 1998 г.-Киров, ¡998.-Т. 1.-С. 84-86.

49. Формальная система дедуктивного логического вывода в рамках логики высказываний / Водяхо А.И., Мельцов В.Ю., Солдатов В.В., Страбыкин Д.А. // Изв. ТЭТУ. - С-Пб., 1993. - Вып. 458. - С. 7-13.

50. А. с. 494768 СССР, МКИ в 11с 17/00. Постоянное запоминающее устройст- ' во / Балашов Е.П., Пузанков Д.В., Страбыкин Д.А. (СССР). - № 2045402/18-24; Заявл. 18.07.74; Опубл. 05.12.75, Бюл. № 45. - 2 с.

51. А. с. 511628 СССР, МКИ G 11С 11/00. Логическое запоминающее устройство / Балашов Е.П., Пузанков Д.В., Страбыкин Д.А. (СССР). - № 2045407/24; Заявл. 18.07.74; Опубл. 25.04.76, Бюл. № 15. - 3 с.

52. А. с. 639019 СССР, МКИ О 11С 17/00. Постоянное запоминающее устройство / Страбыкин Д.А. (СССР). -№ 2435329/18-24; Заявл. 29.12.76; Опубл. 25.12.78,-Бюл. № 47. - 2 с.

53. А. с. 836681 СССР, МКИ G 11С 11/00. Постоянное запоминающее устройство / Матвеев В.Д., Прокашев H.A., Страбыкин Д.А., Шибанов Э.И. (СССР). - № 2813869/18-24; Заявл. 17.08.79; Опубл. 30.04.81, Бюл. № 16. - 3 с.

54. А. с. 826418 СССР, МКИ G 11С 17/00. Запоминающее устройство / Матвеев В.Д., Соловьев А.Н., Страбыкин Д.А., Шибанов Э.И. (СССР). - № 2790950/18-24; Заявл. 05.07.79; Опубл. 07.06.81, Бюл. № 21. - 4 с.

55. А. с. 942141 СССР, МКИ G 11С 11/00. Запоминающее устройство / Прокашев H.A., Соловьев А.Н., Страбыкин Д.А., Шибанов Э.И., Пестов А.Ю. (СССР). - № 2966795/18-24; Заявл. 22.07.80; Опубл. 07.07.82, Бюл. № 25. - 7 с.

56. А. с. 970463 СССР, МКИ G 11С 11/00. Запоминающее устройство / Страбыкин Д.А., Родионов Е.П. (СССР). - № 3273471/18-24; Заявл. 14.04.81; Опубл. 30.10.82, Бюл. № 40. - 3 с.

57. А. с. 1038965 СССР, МКИ G 09G 1/18. Устройство для отображения информации / Лукояничев В.Г., Носов A.A., Прокашев H.A., Страбыкин Д.А. (СССР). - N° 3433944/18-24; Заявл. 05.05.82; Опубл. 30.08.83, Бюл. № 32. -4 с.

58. А. с. 1108486 СССР, МКИ G 09G 1/16. Устройство для отображения информации на экране телевизионного приемника / Лукояничев В.Г., Матвеев В.Д., Прокашев H.A., Страбыкин Д.А. (СССР). - № 3449084/18-24; Заявл. 03.06.82; Опубл. 15.08.84, Бюл. №30.-4 с.

59. А. с. 1269180 СССР, МКИ G 09G 1/16. Устройство для отображения информации на экране электронно-лучевой трубки / Носов A.A., Пестов А.Ю., Прокашев H.A., Страбыкин Д.А. (СССР). - № 3757722/24-24; Заявл. 21.06.84; Опубл. 07.11.86, Бюл. К» 41.-5 с.

60. А. с. 1256084 СССР, МКИ G 09G 1/16. Устройство для отображения информации на экране электронно-лучевой трубки / Куперман М.Н., Лигошский Г.В., Носов A.A., Прокашев H.A., Страбыкин Д.А., Широкий С.П. (СССР). - № 3806150/24-24; Заявл. 22.10.84; Опубл. 07.09.86, Бюл. № 33. - 4 с.

61. А. с. 1357997 СССР, МКИ G 09G 1/16, 1/28. Устройство для отображения символьной информации на экране цветного телевизионного приемника / Страбыкин Д.А., Пестов А.Ю., Родионов Е.П., Носов A.A. (СССР). - № 3994211/24-24; Заявл. 23.12.85; Опубл. 07.12.87, Бюл. № 45. - 3 с.

62. А. с. 1354242 СССР, МКИ G 09G 1/16. Устройство для отображения информации на экране электронно-лучевой трубки / Носов A.A., Пестов А.Ю., Родионов Е.П., Страбыкин Д.А. (СССР). - № 3999168/24-24; Заявл. 27.12.85; Опубл. 23.11.87, Бюл. №43.-12 с.

63. А. с. 1251178 СССР, МКИ G 11С 15/00. Ассоциативное запоминающее устройство / Страбыкин Д.А., Родионов Е.П., Пестов А.Ю., Носов A.A. (СССР). - № 3844270/24-24; Заявл. 16.01.85; Опубл. 15.08.86, Бюл. № 30. - 3 с.

ВВЕДЕНИЕ.

1. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ

ДЛЯ ДЕДУКТИВНОГО И АБДУКТИВНОГО ВЫВОДА.

1.1. Анализ машин и методов логического вывода.

1.1.1. Машины логического вывода.

1.1.2. Формальные системы и методы.

1.2. Исчисление высказываний 1.

1.2.1. Исходный базис.

1.2.2. Основные теоремы и производные правила вывода.

1.2.3. Вывод логических следствий.

1.3. Дедуктивный вывод делением дизъюнктов.

1.3.1. Метод параллельного дедуктивного вывода.

1.3.2. Модификация метода.

1.3.3. Методы резолюции и деления дизъюнктов.

1.4. Абдуктивный вывод делением дизъюнктов.

1.4.1. Задача абдуктивного вывода.

1.4.2. Построение абдуктивных объяснений.

1.4.3. Метод параллельного абдуктивного вывода.

1.4.4. Абдукция и индукция в логике высказываний.

1.5. Выводы по главе 1.

2. МЕТОДЫ ПАРАЛЛЕЛЬНОГО ЛОГИЧЕСКОГО ВЫВОДА ДЕЛЕНИЕМ ДИЗЪЮНКТОВ.

2.1. Исчисление предикатов IP.

2.1.1. Исходный базис.

2.1.2. Преобразование произвольных выражений в множество дизъюнктов.

2.1.3. Унификация литералов.

2.2. Базовый метод дедуктивного вывода.

2.2.1. Частичное деление дизъюнктов.

2.2.2. Полное деление дизъюнктов.

2.2.3. Базовая процедура вывода.

2.2.4. Базовый метод вывода.

2.2.5. Эффективность метода.

2.3. Обобщенный метод дедуктивного вывода.

2.3.1. Связанные дизъюнкты и согласование решений.

2.3.2. Модифицированное частичное деление дизъюнктов.

2.3.3. Модифицированное полное деление дизъюнктов.

2.3.4. Обобщенная процедура вывода.

2.3.5. Обобщенный метод параллельного вывода.

2.4. Метод абдуктивного вывода.

2.4.1. Особенности абдуктивного логического вывода.

2.4.2. Формирование дополнений и процедура вывода.

2.4.3. Согласование значений общих переменных.

2.4.4. Построение абдуктивных объяснений.

2.4.5. Метод параллельного абдуктивного вывода.

2.5. Выводы по главе 2.

3. РАЗРАБОТКА МОДЕЛИ ПАРАЛЛЕЛЬНЫХ ЛОГИЧЕСКИХ ВЫЧИСЛЕНИЙ.

3.1. Анализ моделей вычислений.

3.1.1. Краткая характеристика.

3.1.2. Параллельные логические вычисления.

3.2. Основы языка логического программирования

АЛОГ.

3.3. Модель параллельных логических вычислений.

3.3.1. Дедуктивные логические вычисления.

3.3.2. Детализация схемы логических вычислений.

3.3.3. Процессы абдуктивного вывода.

3.3.4. Особенности модели.

3.4. Выводы по главе 3.

4. РАЗРАБОТКА АРХИТЕКТУРЫ И ПРОГРАММ АБСТРАКТНОЙ

МАШИНЫ ПАРАЛЛЕЛЬНОГО ЛОГИЧЕСКОГО ВЫВОДА.

4.1. Анализ архитектуры параллельных ЭВМ.

4.1.1. Особенности архитектуры мультипроцессорных ЭВМ.

4.1.2. Особенности архитектуры машин логического вывода.

4.2. Абстрактная АЛОГ-машина.

4.2.1. Назначение абстрактной машины.

4.2.2. Система данных.

4.2.3. Система команд.

4.3. Интерпретатор АЛОГ-программ.

4.3.1. Логический вывод.

4.3.2. Шаг вывода.

4.3.3. Вычисление признаков.

4.3.4. Согласование решений.

4.4. Организация абстрактных многопроцессорных машин.

4.4.1. Потоковая машина.

4.4.2. Объектно-ориентированная машина.

4.4.3. Машина на основе принципа концентрации ресурсов.

4.5. Выводы по главе 4.

5. ИССЛЕДОВАНИЕ ПРИНЦИПОВ ОРГАНИЗАЦИИ И ФУНКЦИОНИРОВА

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

5.1. Организация параллельных ЭВМ.

5.1.1. Особенности структуры параллельных ЭВМ.

5.1.2. Особенности структуры машин логического вывода.

5.2. Организация машин логического вывода методом деления дизъюнктов.

5.2.1. Анализ подходов к построению машин.

5.2.2. Четырехуровневая машина с директивным управлением.

5.2.3. Трехуровневая машина с потоковым управлением.

5.2.4. Двухуровневая машина с запросным управлением.

5.2.5. Одноуровневая машина на основе принципа концентрации ресурсов.

5.3. Архитектура процессора логического вывода.

5.3.1. Форматы данных.

5.3.2. Программно-доступные регистры.

5.3.3. Система команд и подпрограмм.

5.3.4. Подпрограмма унификации литералов.

5.3.5. Организация процессора.

5.4. Выводы по главе 5.

6 АНАЛИЗ ЭФФЕКТИВНОСТИ И ПРИМЕНЕНИЕ МАШИН ЛОГИЧЕСКОГО ВЫВОДА.

6.1. Анализ эффективности многопроцессорных машин логического вывода.

6.1.1. Показатели относительной эффективности архитектурно-структурных решений

6.1.2. Оценка производительности.

6.1.3. Оценка информационной, обменной и аппаратной сложности.

6.1.4. Сравнительный анализ эффективности.

6.2. Система моделирования машин логического вывода.

6.2.1. Общая характеристика системы.

6.2.2. Программные модели.

6.2.3. Интерфейс пользователя.

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

6.3.1. Диалоговые системы управления.

6.3.2. Применение логического вывода.

6.4. Выводы по главе 6.

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

Проблема создания высокопроизводительных MJIB имеет три составляющие.

Первая составляющая связана с разработкой методов логического вывода. Здесь, вероятно, отправным методом следует считать разработанный Дж. Робинсоном (1965 г.) метод резолюций. Существуют и другие не менее сильные методы логического вывода: метод Маслова, вывод на основе интерпретаций Бета, сравнений по образцу (pattern matching) и др. Тем не менее, именно для метода резолюций была разработана Р. Ковальским идея процедурной интерпретации логического вывода, которая дала начало собственно логическому программированию как языку, технологии и парадигме. Несомненно, что среди языков логического программирования ведущее место в этом отношении занимает язык ПРОЛОГ и его многочисленные версии. Создание программного обеспечения для описания задачи и реализации логического вывода образуют вторую составляющую проблемы.

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

Весьма продуктивным здесь оказался подход, основанный на использовании абстрактных ПРОЛОГ-машин, и, прежде всего, широко известной абстрактной машины Д. Уоррена.

Большинство современных машин логического вывода реализовано на базе ПРОЛОГ-процессоров, основным недостатком которых является низкая производительность. Чтобы повысить быстродействие ПРОЛОГ-машин, были предприняты попытки модифицировать "чистый" ПРОЛОГ в его параллельные версии. Однако должного эффекта не было достигнуто, поскольку в основе языка ПРОЛОГ лежит последовательный принцип SLD-резолюции. Производительность созданных ПРОЛОГ-машин не превышает уровня 10 MLIPS, в то время как для масштабных задач требуется производительность порядка 1 GLIPS.

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

Основная часть исследований, посвященных теории и методам логического вывода, проводится в России под эгидой Ассоциации искусственного интеллекта. Большое влияние на развитие исследований в этой области искусственного интеллекта оказали работы Д.А. Поспелова, Г.С. Осипова, В.Н. Вагина, В.К. Финна, В.Ф. Хорошевского, Е.А. Сидоренко и др. Теоретические основы построения высокопроизводительных проблемно-ориентированных вычислительных систем были заложены в работах Э.В. Евреинова, Ю.Т. Косарева, И. В. Прангишвили, В. Б. Смолова, Е.П. Балашова, Д. В. Пу-занкова, А.В. Каляева, В.В. Корнеева и др. Важные результаты на пути создания высокопроизводительных ПРОЛОГ-машин получили В.А. Вишняков, Д.Ю. Буландже, О.В. Герман, B.C. Фомичев, А.И. Водяхо, А.А. Власов и др.

В предлагаемой работе решение данной проблемы рассматривается в рамках научного направления "Высокопроизводительные системы обработки данных и знаний"' .

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

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

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

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

- разработка методов параллельного дедуктивного вывода;

- разработка методов параллельного абдуктивного вывода .

2. Разработка и исследование модели вычислений и абстрактной машины логического вывода, в том числе:

- разработка основ языка декларативного логического программирования;

- разработка модели параллельных логических вычислений для дедуктивного и абдуктивного вывода;

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

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

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

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

- разработка базовых архитектурно-структурных решений для создания быстродействующих процессоров логического вывода;

- исследование вопросов оценки эффективности и применения машин логического вывода.

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

Научная новизна. В результате проведенных исследований получены следующие научные результаты.

1. Для представления знаний в машинах логического вывода предложена формальная система - исчисление высказываний I, отличающаяся от известных набором аксиом и правил доказательства, а также не традиционной экспликацией логического следования. На основе исчисления I разработано исчисление предикатов первого порядка IP, в котором доказаны необходимые теоремы и производные правила вывода, позволяющие применять известные способы преобразования произвольных выражений исчисления IP в дизъюнкты и проводить логический вывод.

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

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

4. Разработаны основы языка декларативного программирования - АЛОГ. Семантика языка АЛОГ базируется на методах параллельного дедуктивного и абдуктивного вывода, разработанных в рамках исчисления предикатов IP. Отличительными особенностями языка являются: использование дизъюнктов общего вида, возможность представления заключения конъюнкцией дизъюнктов, ориентация на получение множества решений, полная декларативность.

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

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

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

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

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

Внедрение результатов. Диссертационная работа является обобщением результатов, полученных автором в Ленинградском электротехническом институте им. В. И. Ульянова /Ленина/ и в Вятском государственном техническом университете в процессе выполнения в 1975-1998 годах научно-исследовательских работ, в том числе: "Диалоговые микропроцессорные системы управления цифровыми приборами" (Ленинград, КБ "Импульс"), "Применение микропроцессорных систем в высшей школе. Диалоговые микропроцессорные системы управления экспериментальными установками" (Г/б № 6.30.11), "Теория и применение машин логического вывода" в рамках проблемного совета "Высокопроизводительные системы обработки данных и знаний" АТН РФ).

Результаты исследований внедрены в серийное производство в составе первых отечественных приборов со встроенными диалоговыми системами управления "Генератор импульсов Г5-90" и "Ритмокардиоскоп РКС-02", а также использованы в лабораторных установках по микропроцессорной технике. Теоретические и практические материалы диссертации использованы в учебном процессе Вятского государственного технического университета при разработке лекционных курсов и лабораторных практикумов по дисциплинам: "Организация ЭВМ, комплексов и систем", "Микропроцессоры и микропроцессорные системы" и "Системы искусственного интеллекта". Написаны и опубликованы три учебных пособия.

Апробация работы. Основные научные и практические результаты исследований по теме диссертации докладывались и обсуждались на Всесоюзной конференции "Однородные вычислительные системы и среды" (Киев, 1975), Всесоюзных совещаниях "Микропроцессоры" (Рига, 1975, 1978), Всесоюзном совещании "Автоматизация проектирования средств вычислительной техники и перспективы применения микропроцессоров" (Минск, 1978), IV Всесоюзном научно-техническом совещании "Интерактивная технология в САПР" (Таллин, 1981), областных научно-практических конференциях "Научный потенциал вузов народному хозяйству" (Киров, 1987, 1989), IV Национальной конференции с международным участием "Искусственный интеллект-94" (Рыбинск, 1994), научно-технических конференциях "Диагностика, информатика, метрология, экология, безопасность" (Санкт-Петербург, 1995, 1997), международной конференции "Новые информационные технологии и системы" (Пенза, 1996), II международной научно-технической конференции "Моделирование и ис

15 следование сложных систем" (Москва, 1998), региональной научно-технической конференции "Наука-производство-технология-экология" (Киров, 1998), VI научно-технической конференции "Искусственный интеллект - 98" (Пущино, 1998).

Под руководством автора по тематике исследований выполнены и успешно защищены три кандидатские диссертации.

Публикации. Материалы диссертации опубликованы в 63 работах. Из них одна монография, 3 учебных пособия, 2 9 статей, 16 тезисов докладов на научных конференциях, 14 авторских свидетельств.

Структура и объем диссертации. Диссертация состоит из введения, шести глав, заключения, списка использованной литературы, включающего 222 наименования, и четырех приложений. Основная часть работы изложена на 2 99 страницах машинописного текста. Работа содержит 81 рисунок и 19 таблиц.

6.4. Выводы по главе 6

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

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

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

356 проектированию ДСУ. Эффективность предложенного подхода подтверждается разработкой и внедрением ряда ДСУ. На примере ДСУ системы управления энергообъединением и установки автоматического контроля качества пиломатериалов показана целесообразность и эффективность использования машин логического вывода методом деления дизъюнктов. Кроме этого показана целесообразность применения логического вывода методом деления дизъюнктов при решении антитрестовских задач.

357

ЗАКЛЮЧЕНИЕ

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

При решении проблемы в диссертационной работе получены следующие результаты.

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

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

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

4. Разработаны методы параллельного дедуктивного и абдуктивного логического вывода на знаниях, представленных выражениями предикатов первого порядка. Логический вывод методами деления дизъюнктов характеризуется четырьмя уровнями параллелизма (системы дизъюнктов, дизъюнкты, остатки, литералы). Установлено, что логический вывод обобщенным методом может протекать параллельно даже в случае рекурсивного характера исходных правил. Показано, что метод абдуктивного вывода позволяет получать многолитеральные дополнительные посылки, обеспечивающие дедуктивный логический вывод целого класса заключений.

5. Разработаны основы декларативного языка логического программирования АЛОГ. Семантика языка АЛОГ основана на методах параллельного дедуктивного и абдуктивного вывода, разработанных в рамках исчисления предикатов первого порядка IP.

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

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

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

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

10. Определено множество вариантов построения многопроцессорной машины логического вывода в зависимости от

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

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

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

362

1. Амаяма М., Танака Ю. Архитектура ЭВМ и искусственный интеллект: Пер. с япон. - М.: Мир, 1993.

2. Анкудинов Г.И. Синтез структуры сложных объектов. Логико-комбинаторный подход. Л.: ЛГУ, 1986.

3. Балашов Е.П. Эволюционный синтез систем.- М.: Радио и связь, 1985.

4. Балашов Е.П., Пузанков Д.В. Проектирование информационно-управляющих систем. М. Радио и связь, 1987.

5. Балашов Е.П., Пузанков Д.В., Страбыкин Д.А. Многофункциональное использование элементов в вычислительных устройствах // Кибернетика. 1983. - № 6. - С. 39-44.

6. Барановский А.А., Матвеев В.Д., Страбыкин Д.А. Автоматизированная система оперативного врачебного контроля на основе микроЭВМ / КирПИ. Киров, 1980. -5 с. -Деп. ЦНИИТЭИ приборостроения 12.06.81, № 1510.

7. Борзенко И.М. Адаптация, прогнозирование и выбор решения в алгоритмах управления технологическими объектами. М.: Энергоатомиздат, 1984.

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

9. Буланже Д.Ю. Абстрактная архитектура процессора логического вывода // Системы и средства информатики. -1990 Вып. 1. С.13-89.

10. Бурцев B.C. Тенденции развития суперЭВМ. / Вычислительные машины с нетрадиционной архитектурой. СуперЭВМ. М., 1990. С. 3-26.

11. Бусленко Н.П. Моделирование сложных систем. -М.: Наука, 1975.

12. Вагин В.Н. Дедукция и обобщение в системах принятия решений. М. : Наука. Гл. Ред. Физ. -мат. лит. 1988. -(Пробл. искусств, интеллекта).

13. Вагин В.Н., Луцкий К.В. Абдуктивный вывод в системах принятия решений. //Сб. научных трудов Национальной конференции с международным участием "Искусственный интеллект 94". Рыбинск. 1994, том 2.

14. Вагин В.Н., Салапина Н.О. Программная реализация системы параллельного вывода PIS с использованием графа связей. // КИИ-98 Шестая национальная конференция с международным участием. Сб. науч. тр. Пущино 1998. т.1. -с. 250-256.

15. Вишняков В.А., Буланже Д.Ю., Герман О.В. Аппаратно-программные средства процессоров логического вывода. М.: Радио и связь. 1991.

16. Водяхо А.И., Горнец Н.Н., Пузанков Д.В. Высокопроизводительные системы обработки данных: Учебное пособие для вузов.- М.: Высш. шк., 1997.

17. Водяхо А.И., Долженкова М.Л. Объектно-ориентированная модель логических вычислений // Сборник научных трудов ВятГТУ. Киров, 1998. - с. 234-240.

18. Водяхо А.И., Мельцов В.Ю. Страбыкин Д.А. Система параллельного логического вывода // Структуры и математическое обеспечение вычислительных средств. С-Пб., 1994, С. 60-64. (Изв. ТЭТУ; Вып. 476).

19. Водяхо А.И., Смолов В.В., Плюснин В.У., Пузанков Д.В. Функционально ориентированные процессоры Л.: Машиностроение. 1988.

20. Воеводин В.В. Математические модели и методы в параллельных процессах. М.: Наука, 1986.

21. Высокоскоростные вычисления. Архитектура, производительность, прикладные алгоритмы и программы суперЭВМ. / Ред. Я. Ковалик. М.: Радио и связь, 1988.

22. Гаек П., Гавранек Т. Автоматическое образование гипотез: математические основы общей теории. М. : Наука. Гл. Ред. Физ. -мат. лит., 1984.

23. Гордиенко Е.К., Захаров В.Н. Управление процессами в базах знаний // Изв. АН СССР. Техн. кибернетика. 1989.- N 5. - С.175-193.

24. Гордиенко Е.К., Захаров В.Н., Миронов А.Ю. Реализация параллельных алгоритмов логического вывода в матричной однородной среде // Изв. АН СССР. Техн. кибернетика. 1989.- N 5.

25. Гото А., Танака X., Мотоока Т. Высокопараллельный механизм вывода модель трансформации целей и архитектура машины. // Язык Пролог в пятом поколении ЭВМ. - М. :Мир, 1988.-с.262-309.

26. Диринг М.Ф. Архитектура машин для искусственного интеллекта // Реальность и прогнозы искусственного интеллекта. М., 1989.- С. 209-230.

27. Добрых К.П., Страбыкин Д.А. Пакет программ для лабораторного практикума по архитектуре микроЭВМ // Наука-производство-технология-экология: Сб. материалов регион. науч.-техн. конф., Киров, 14-28 мая 1998 г. Киров, 1998. - Т. 1. - С. 73-74.

28. Долженкова M.J1. Объектно-ориентированная машина абдуктивного логического вывода. Автореферат диссертации на соискание ученой степени канд. тех. наук. С.-Пб., 1998 .

29. Долженкова M.JT. Параллельная система логического вывода/ ВятГТУ. М.,1996. - Деп. в ВИНИТИ, №3585 - В96.

30. Долженкова M.JI., Страбыкин Д.А. Метод построения логического вывода для не полностью определенных задач / КирПИ. Киров, 1993. -15 с. - Деп. ВИНИТИ 12.09.93, № 2559-В93.

31. Долженкова М.Л., Страбыкин Д.А. Объектно-ориентированная машина абдуктивного логического вывода // ВЕСТНИК ВВО АТН РФ, Сер. Высокие технологии в радиоэлектронике. 1998. - № 2 (б). - С. 32-36.

32. Долженкова М.Л., Страбыкин Д.А. Организация параллельной системы логического вывода // Новые информационные технологии и системы: Матер, междунар. конф. Пенза, 1996. -Ч. 1.- С. 45-46.

33. Евреинов Э.В., Косарев Ю.Г. Однородные универсальные вычислительные системы высокой производительности. Новосибирск: Наука, 1966.

34. Ершов Ю.Л., Палютин Е.А. Математическая логика. М.: Наука. Гл. Ред. Физ. -мат. лит. 1987.

35. Ефимов Е.И. Решатели интеллектуальных задач. -М.: Наука, 1989.

36. Жданов А.А. Страбыкин Д.А. Адаптация диалога в цифровых измерительных приборах со встроенными микроэвм / КирПИ. Киров, 1988. -7 с. - Деп. ЦНИИТЭИ приборостроения 23.02.88, № 4108.

37. Интеллектуальные системы принятия проектных решений / Алексеев А.В., Борисов А.Н., Вилюмс Э.Р., Слядзь Н.Н., Фомин С.А. Рига: Зинатне, 1997.

38. Искусственный интеллект : В 3-х кн. Кн.2. Модели и методы: Справочник /Под ред. Д.А. Поспелова. М. : Радио и связь, 1990.

39. Искусственный интеллект : В 3-х кн. Кн.З. Программные и аппаратные средства : Справочник / Под ред. В.Н. Захарова, В.Ф. Хорошевского. М.: Радио и связь, 1990.

40. Каган Б.М. Электронные вычислительные машины и системы. М.: Энергоатомиздат. 1985.

41. Калиничеко J1.А., Рыбкин В.М. Машины баз данных и знаний. М.: Наука. Гл. Ред. Физ. -мат. лит. 1990.

42. Каляев А.В. Многопроцессорные системы с программируемой архитектурой. М.: Радио и связь, 1984.

43. Караванова Л.В., Прохорова Э.Г., Степановская И. А. Распараллеливание скалярных вычислений в системах искусственного интеллекта // Вопр. кибернетики.- 1993.- N 160.- с. 31-40.

44. Клокисин В. Ф., Мелиш К.С. Программирование на языке Пролог. М.: Мир., 198 7

45. Ковальски Р. Логика в решении проблем: Пер. с англ. М. : Наука. Гл. Ред. Физ. -мат. лит. 1988. (Пробл. искусств, интеллекта).

46. Корнеев В.В. Архитектура вычислительных систем с программируемой структурой. Новосибирск: Наука, 1985.

47. Корнеев В.В. Параллельные вычислительные системы. М.: НОЛИДЖ, 1999.

48. Корнеев В.В., Киселев А.В. Современные микропроцессоры. М.: НОЛИДЖ, 1998.

49. Кохонен Т. Ассоциативная память. М.: Мир,1980.

50. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. М.: Энергоатомиздат. 1988.

51. Кун С. Матричные процессоры на СБИС. М.:Мир,1991.

52. Куприянов М.С., Петров Г.А., Пузанков Д.В. Процессор PENTIUM: архитектура и программирование. /ГЭТУ -СПб., 1995.

53. Кухтенко А.И. Основные направления развития теории управления сложными системами. // Сложные системы управления № 4. Сб. Академии наук Украинской ССР. 1968. - С. 6-24.

54. Ларионов A.M. и др. Вычислительные комплексы, системы и сети / A.M. Ларионов, С.А. Майоров, Г.И. Новиков. Л.: Энергоатомиздат, 1987.

55. Левин В.К. Высокопроизводительные мультимикро-процессорные системы. // Информационные технологии и вычислительные системы. 1995. Т. 1, № 1. - С. 1-9.

56. Логический подход к искусственному интеллекту: от классической логики к логическому программированию: Пер. с франц. /Тейз А., Грибомон П., Луи Ж. и др. М. : Мир. 1990.

57. Логическое программирование: Пер. с англ. и фр. /Под ред. В.Е. Агафонова. М.:Мир,1988.

58. Лозовский B.C. Семантические сети. // Представление знаний в человеко-машинных и робототехнических системах. М.: ВИНИТИ, 1984., с. 84-120.

59. Лорьер Ж.-Л. Системы искусственного интеллекта : Пер. с франц. М.: Мир, 1991.-568с.

60. Лукоянычев В.Г., Страбыкин Д.А., Шкебельский В. В. Встроенный дисплей телевизионного типа на основе микропроцессора для отображения информации в медицинских приборах // Техника средств связи. 1985. - Вып. 3. - С. 83-88.

61. Малпас Дж. Реляционный язык Пролог и его применение: Пер. с англ. /Под ред. В.Н. Соболева. М.: Наука. Гл. ред. физ. мат. лит., 1990.

62. Малюгин В.Д. Параллельные логические вычисления посредством арифметических полиномов. М. : Наука. Физ. мат. лит. 1997.

63. Марселлус Д. Программирование ЭС на Турбо Прологе: Пер. с англ. /Предисл. С.В. Трубицина. М. : Финансы и статистика, 1994.

64. Матвеев В.Д., Милков JI.A., Страбыкин Д.А. Цветные видеодисплеи для систем машинной графики / / Интерактивная технология в САПР: Тез. докл. IV Всесоюз. науч. -техн. совещ., Таллин, 12-17 окт. 1981 г. Таллин, 1981, С. 105-106.

65. Матвеев В.Д., Страбыкин Д.А., Бакшаев A.M. Компьютерный практикум на основе имитационного моделирования микропроцессорных устройств // Управление и обработка информации. Киров, 1998. - С. 67-72. - (Сб. науч. тр. / ВятГТУ; Вып. 3).

66. Мельцов В.Ю. Потоковая система дедуктивного логического вывода. Автореферат диссертации на соискание ученой степени канд. тех. наук. С.-Пб., 1996.

67. Мельцов В.Ю., Родионов Е.П., Страбыкин Д.А. Диалоговые программаторы ПЗУ и ПЛМ // Научный потенциал вузов народному хозяйству: Тез. докл. Обл. науч.-практ. конф., Киров, 12-15 мая 1987 г. Киров, 1987. - С. 6263.

68. Мельцов В.Ю., Родионов Е.П., Страбыкин Д.А. Диалоговый программатор интегральных микросхем памяти // Приборы и системы управления. 1990. - № 8. - С. 21-22.

69. Мельцов В.Ю., Страбыкин Д.А. Метод параллельного логического вывода / КирПИ. Киров, 1992. -17 с. - Деп. ВИНИТИ 12.11.92, № 3240-В92.

70. Минский М. Структура для представления знаний. -М. : Мир., 197 8.

71. Многофункциональные регулярные вычислительные структуры / Е.П. Балашов, В.П. Смолов, Г.А. Петров, Д.В. Пузанков. М.: Сов. Радио. 1978.-288 с.

72. Невзорова О.А. Машинное обучение и задачи обработки естественного языка. Новости искусственного интеллекта №1, Журнал Ассоциации искусственного интеллекта. М., 1998.

73. Нестерук В.Ф., Страбыкин Д.А. Принципы организации ассоциативного поиска информации в запоминающем устройстве // Вычислительная техника и системы управления. -Омск, 1975. С. 64-69. - (Сб. науч. тр. / ОПИ; Вып. 2).

74. Новикова Г.М. Концептуальный подход к формализации задачи управления // КИИ-98 Шестая национальная конференция с международным участием. Сб. науч. тр. Пущино 1998. т.1. - С 158-168.

75. Органик Э. Организация системы Интел 432. М. : Мир, 1987.

76. Осипов Г.С. Приобретение знаний интеллектуальными системами. Основы теории и технологии. М.: Наука. Физматлит, 1997. - 112 с.

77. Осипов Г.С. Приобретение знаний на основе взаимодействия методов анализа текста и автоматизированного интервью эксперта. Переславль-Залесский. 1994.

78. Осуга С. Обработка знаний. М.: Мир, 1989.

79. Перспективы развития вычислительной техники: В 11 кн.: Справочное пособие /Под ред. Ю.М. Смирнова. Кн. 2. Интеллектуализация ЭВМ /Кузин Е.С., Ройтман А.И., Фоминых И.Б., Хахалин Г.К. М.: Высш. шк., 1989.

80. Плесневич Г.С. Естественный вывод для задачи "СТИМРОЛЛЕР". // КИИ-98 Шестая национальная конференция с международным участием. Сб. науч. тр. Пущино 1998. т.1.- с. 257-263.

81. Поспелов Д.А. Интеллектуальные интерфейсы для ЭВМ новых поколений //Электронная вычислительная техника.- 1991. Вып. 3.

82. Поспелов Д.А. Ситуационное управление: теория и практика. М.: Наука, 1986.

83. Представление и использование знаний / Под ред. X. Уэно, М. Исидзука. М.: Мир, 1989.

84. Приобретение знаний: Пер. с япон. /Под ред. С.Осуги, Ю.Саэки. М.: Мир. 1990.

85. Пузанков Д.В. Страбыкин Д.А. Метод сокращения аппаратурных затрат за счет многофункционального использования элементов // Автоматика и вычислительная техника.- 1985. № 2. - С. 84-89.

86. Разработка ЭВМ нового поколения: Архитектуры, программирование, интеллектуализация // Сб. научных трудов ВЦ СО АН СССР. Новосибирск, 1989.

87. Родионов Е.П., Страбыкин Д.А. Диалоговый программатор ПЛМ // Управляющие системы и машины. 1988. -№ 4. - С. 11-16.

88. Родионов Е.П., Страбыкин Д.А. Метод сжатия и восстановления теста для экономии памяти микропроцессорных систем / КирПИ. Киров, 1985. -14 с. - Деп. ВИНИТИ 21.11.85, № 3220.

89. Рыков О.В. Организация машин параллельного логического вывода информационно-управляющих систем. Автореферат диссертации на соискание ученой степени канд. тех. наук. Киров, 1999.

90. Рыков О.В., Бурков А.Б. Программная модель директивной машины логического вывода. // Труды региональной науч.-тех. конф. "Наука-Производство-Технология-Экология-98" Т.1., ВятГТУ., Киров., 1998., С.57-58.

91. Рыков О.В., Страбыкин Д.А. Метод ускоренного логического вывода / КирПИ. Киров, 1993. -16 с. - Деп. ВИНИТИ 10.04.93, № 743-В93.

92. Сидоренко Е.А. Логическое следование и условные высказывания. М.: Наука. АН СССР. 1983.

93. Система оперативного врачебного контроля на основе микроЭВМ с отображением информации на ЭЛТ / Барановский А. А., Князев К.К., Лукоянычев В.Г., Страбыкин Д.А.

94. КирПИ. Киров, 1980. -8 с. - Деп. ЦНИИТЭИ приборостроения 12.06.81, № 580.

95. Слейгл Дж. Искусственный интеллект. М. : Мир,1973.

96. Сравнительная оценка производительности процессоров "Квант-10", "Квант-20" и транспьютера Т-800 / Виксне П.Е., Каталов Ю.Т., Конотопцев В.Н., Корнеев В.В., Ярмолинский И.П. // Вопросы радиоэлектроники. Сер. ЭВТ. -1994. Вып. 2. - С. 60-65.

97. Стерлинг J1., Шапиро Э. Искусство программирования на языке Пролог : Пер. с англ. М.: Мир,1990.

98. Страбыкин Д.А. Абстрактная машина логического вывода методом деления дизъюнктов // Наука-производство-технология-экология: Сб. материалов регион, науч.-техн. конф., Киров, 15-27 мая 1999 г. Киров, 1999. - Т. 2. -С. 22-24.

99. Страбыкин Д.А. Анализ задач проектирования диалоговых микропроцессорных систем управления измерительными приборами // Электронное моделирование. 1987. Т. 9, № 1. - С. 65-70.

100. Страбыкин Д.А. Диалоговая система управления приборами и процессами // Научный потенциал вузов народному хозяйству: Тез. докл. Обл. науч.-практ. конф., Киров, 12-15 мая 1987 г. Киров, 1987. - С. 11.

101. Страбыкин Д.А. Логический вывод методом деления дизъюнктов при решении антитрестовской задачи // Научныйвестник Кировского филиала Московского гуманитарно-экономического института. Киров, 1998. № 1. - С. 182192.

102. Страбыкин Д.А. Исследование вопросов проектирования вычислительных устройств на основе многофункциональных регулярных структур. Автореферат диссертации канд. тех. наук. JI., 1978 .

103. Страбыкин Д.А. Микропроцессор с регулярной структурой на основе интегральных модулей памяти // Микропроцессоры: Тез. докл. 2-го всесоюзн. совещ., Рига, 312 июня 1977 г. Рига, 1977. - Ч. 1 - С. 23-25.

104. Страбыкин Д.А. Микропроцессор с таблично-алгоритмическим операционным устройством // Микропроцессоры: Тез. докл. всесоюзн. совещ., Рига, 5-12 окт. 1975 г. Рига, 1975. - С. 81-82.

105. Страбыкин Д.А. О функциональных возможностях полупроводниковых интегральных запоминающих устройств // Вычислительная техника. JI., 1978. - Вып. 7: Многофункциональные регулярные вычислительные структуры. - С. 8188.

106. Страбыкин Д.А. Обобщенное проектирование микропроцессорных систем / КирПИ. Киров, 1986. -13 с. - Деп. ЦНИИТЭИ приборостроения 21.05.86, № 3350.

107. Страбыкин Д.А. Организация машин параллельного логического вывода / ВятГТУ Киров: Изд-во ВятГТУ, 1999. - 189 с.

108. Страбыкин Д.А. Основы языка декларативного программирования машины параллельного дедуктивного и абдуктивного вывода // ВЕСТНИК ВВО АТН РФ, Сер. Проблемы обработки информации. 1998. - Вып. 1. - С. 7-11.

109. Страбыкин Д.А. Параллельный логический вывод методом деления дизъюнктов // Управление и обработка информации. Киров, 1998. - С. 89-101. - (Сб. науч. тр. / ВятГТУ; Вып. 3).

110. Страбыкин Д.А. Параллельный логический вывода в системах обработки знаний // ВЕСТНИК ВВО АТН РФ, Сер. Высокие технологии в радиоэлектронике. 1998. - № 2 (6) . -С. 25-29.

111. Страбыкин Д.А. Управление цифровыми измерительными приборами с помощью встроенных микроэвм // Приборы и системы управления. 1983. - № 11. - С. 11-13.

112. Страбыкин Д.А. Экспериментальное исследование микропроцессорных устройств с помощью диалоговых систем управления // Микропроцессорные средства и системы. -1987. № 4. - С. 62-64.

113. Страбыкин Д.А., Бакшаев A.M. Практикум по микропроцессорным устройствам с использованием диалоговых систем управления / ГГУ Горький: Изд-во ГГУ, 1989. -105 с.

114. Страбыкин Д.А., Носов А.А. Организация движения графиков на экране измерительного прибора / Редакция журнала Приборы и системы управления М., 1984. -7 с. -Деп. ЦНИИТЭИ приборостроения 22.12.84, № 2 695-Б8 4.

115. Страбыкин Д.А., Рыков О.В. Логический вывод методом параллельной редукции и его аппаратная поддержка // Искусственный интеллект-94: Сб. науч. тр. Нац. конф. с междунар. участием, Рыбинск, 15-21 сент. 1994 г. Рыбинск, 1994. - Т. 2. - С. 296-300.

116. Супер-ЭВМ: Сб. н. тр. /АН СССР Под ред. B.C. Бурцева. М.: Наука, 1989.

117. Такеути Г. Теория доказательств: Пер. с англ. -М.: Мир. 1978.

118. Танев И.Т., Фомичев B.C. Параллельная мультипроцессорная Пролог-система.//Известия ЛЭТИ, 1992.-вып.444.-с.101-106.

119. Тимофеев А.В. Роботы и искусственный интеллект. М.: Наука, 1978. 192 с.

120. Толканов В,А, Страбыкин Д.А. Программа обучения игре в шахматы // Наука-производство-технология-экология: Сб. материалов регион, науч.-техн. конф., Киров, 14-28 мая 1998 г. Киров, 1998. - Т. 1. - С. 84-86.

121. Томита С., Танака X. и др. Компьютеры на СБИС: В 2-х кн. Пер. с япон. /Мотоока Т. М. : Мир, 1988, Кн. 1, 2.

122. Транспьютероподобный 32-разрядный RISC-процессор с масштабируемой архитектурой / Виксне П.Е., Каталов Ю.Т., Корнеев В.В., Панфилов А.П., Трубецкой

123. A. В., Черников В. М. // Вопросы радиоэлектроники. Сер. ЭВТ. 1994. - Вып. 2. - С. 4 9-7 9.

124. Тульский В.П. Средства связи символьного процессора ЕС2702 с универсальной ЭВМ. Препринт. М.,1987.- ИПМ АН СССР, N 169.

125. Финн В.К. Об обобщенном ДСМ -методе автоматического порождения гипотез. Семиотика и информатика. М.: ВИНИТИ, Вып. 29, 1989, с. 93-123.

126. Финн В.К. Правдоподобные рассуждения в интеллектуальных системах типа ДСМ. Итоги науки и техники. Информатика. М.: ВИНИТИ, Т.15, 1991, с. 54-101.

127. Формальная система дедуктивного логического вывода в рамках логики высказываний / Водяхо А.И., Мельцов

128. B.Ю., Солдатов В.В., Страбыкин Д.А. // Изв. ТЭТУ. СПб., 1993. - Вып. 458. - С. 7-13.

129. Фути К. К вычислительным системам пятого поколения.// Язык Пролог в пятом поколении ЭВМ. М. : Мир, 1988.-с.5-30.

130. Ханенко В.Н. Информационные системы. -JI. : Машиностроение. Ленингр. отд-ние, 1988.

131. Хант Э. Искусственный интеллект. М. : Мир,1978 .

132. Цай В.А. Использование языка Пролог для представления знаний // Препринт ВЦ СО АН СССР. 1987 -№716.

133. Чен Ч., Ли Р. Математическая логика и автоматическое доказательство теорем. М.: Наука. 1983.

134. Чери С., Готлоб Г., Танка Л. Логическое программирование и базы данных: Пер. с англ. М. : Мир. 1992.

135. Шпаковский Г.И. Архитектура параллельных ЭВМ: Учебное пособие для вузов. Минск.: Университетское, 1989.

136. ЭВМ пятого поколения. Концепции, проблемы, перспективы /Под ред. Мото-Ока Т.: Пер. с англ. М.: Финансы и статистика. 1984.

137. Экспертные системы. Принципы работы и примеры./Под ред. Форсайта Ф. М.: Радио и связь, 1987.

138. Элти Дж., Кумбс М. Экспертные системы: концепции и примеры. Пер. с англ. М. : Финансы и статистика. 1987.

139. Эндрю А. Искусственный интеллект: Пер. с англ. М.: Мир. 1985.14 9. Янг С. Алгоритмические языки реального времени. Конструирование и разработка. Пер. с англ. М. : Мир. 1985.

140. Ясухара X., Нитадори К. ORBIT-параллельная модель выполнения Пролог-программ. // Язык Пролог в пятом поколении ЭВМ.- М.: Мир, 1988.-с.310-325.

141. А. с. 494768 СССР, МКИ G 11с 17/00. Постоянное запоминающее устройство / Балашов Е.П., Пузанков Д. В., Страбыкин Д.А. (СССР) . № 2045402/18-24; Заявл. 18.07.74; Опубл. 05.12.75, Бюл. № 45. - 2 с.

142. А. с. 511628 СССР, МКИ G 11С 11/00. Логическое запоминающее устройство / Балашов Е.П., Пузанков Д. В., Страбыкин Д.А. (СССР). № 2045407/24; Заявл. 18.07.74; Опубл. 25.04.7 6, Бюл. № 15. - 3 с.

143. А. с. 639019 СССР, МКИ G 11С 17/00. Постоянное запоминающее устройство / Страбыкин Д. А. (СССР) . № 2435329/18-24; Заявл. 29.12.76; Опубл. 25.12.78, Бюл. № 47. - 2 с.

144. А. с. 836681 СССР, МКИ G 11С 11/00. Постоянное запоминающее устройство / Матвеев В.Д., Прокашев Н.А., Страбыкин Д.А., Шибанов Э.И. (СССР). № 28138 69/18-24; Заявл. 17.08.7 9; Опубл. 30.04.81, Бюл. № 16. - 3 с.

145. А. с. 826418 СССР, МКИ G 11С 17/00. Запоминающее устройство / Матвеев В.Д., Соловьев А.Н., Страбыкин Д.А., Шибанов Э.И. (СССР). № 27 90950/18-24; Заявл. 05.07.79; Опубл. 07.06.81, Бюл. № 21. - 4 с.

146. А. с. 942141 СССР, МКИ G 11С 11/00. Запоминающее устройство / Прокашев Н.А., Соловьев А.Н., Страбыкин Д.А., Шибанов Э.И., Пестов А.Ю. (СССР). № 2966795/1824; Заявл. 22.07.80; Опубл. 07.07.82, Бюл. № 25. - 7 с.

147. А. с. 970463 СССР, МКИ G 11С 11/00. Запоминающее устройство / Страбыкин Д.А., Родионов Е.П. (СССР). -№ 3273471/18-24; Заявл. 14.04.81; Опубл. 30.10.82, Бюл. № 40. 3 с.

148. А. с. 1038965 СССР, МКИ G 09G 1/18. Устройство для отображения информации / Лукояничев В.Г., Носов А.А., Прокашев Н.А., Страбыкин Д.А. (СССР). № 3433944/18-24; Заявл. 05.05.82; Опубл. 30.08.83, Бюл. № 32. - 4 с.

149. А. с. 1108486 СССР, МКИ G 09G 1/16. Устройство для отображения информации на экране телевизионного приемника / Лукояничев В.Г., Матвеев В.Д., Прокашев Н.А., Страбыкин Д.А. (СССР). № 3449084/18-24; Заявл. 03.06.82; Опубл. 15.08.84, Бюл. № 30. - 4 с.

150. А. с. 1269180 СССР, МКИ G 09G 1/16. Устройство для отображения информации на экране электронно-лучевой трубки / Носов А.А., Пестов А.Ю., Прокашев Н.А., Страбыкин Д.А. (СССР). № 3757722/24-24; Заявл. 21.06.84; Опубл. 07.11.8 6, Бюл. № 41. - 5 с.

151. А. с. 1354242 СССР, МКИ G 09G 1/16. Устройство для отображения информации на экране электронно-лучевой трубки / Носов А.А., Пестов А.Ю., Родионов Е.П., Страбыкин Д.А. (СССР). № 3999168/24-24; Заявл. 27.12.85; Опубл. 23.11.87, Бюл. № 43. - 12 с.

152. А. с. 1251178 СССР, МКИ G 11С 15/00. Ассоциативное запоминающее устройство / Страбыкин Д.А., Родионов Е.П., Пестов А.Ю., Носов А.А. (СССР). № 3844270/24-24; Заявл. 16.01.85; Опубл. 15.08.8 6, Бюл. № 30. - 3 с.

153. Ackerman, W.B. and Dennis, J.B. VAL A value oriented algorithmic language // MIT Lab. For Computer Scince Tech. Rep. 218, June 1979.

154. Noakes M.D., Wallach D.A., Dally W.J. The J-Machine Multicomputer: An Architectural Evaluation // Proc. of the IEEE, 1993. P. 224-235.

155. Agha G. ,Hewitt C. Concurrent programming using actors: Exploiting large-scale parallelism // Lect Not. In Comput. Sci. 1990, № 206. P. 19-41.

156. Amamiya M., Nasegawa R., Takesue M., Mikami H. A data flow machine architecture for highly parallel symbol manipulations // Jour. Inform. Process. 1989, Vol 10, № 4. - p. 227-236.

157. Anderson, R.B., R.E. Thomas, C. J. Gatchel, and N.D. Bennett. 1993. Computerized technique for recording board defect data. Res. Pap. NE-671. Radnor, PA: U.S. Department of Agriculture, Forest Service, Northeastern Forest Experimrnt Station. 17 p.

158. Arvind A. Semantics of loops in ID // Note 11, March 1977, Univ. Of California.

159. Bertsekas D., Gallger R. Data Networks. Prentice Hall, 1992.

160. Bic L. A data-driven model for parallel interpretation of logic programs // Proc. Of the Int. Conf. On Fifth Gen. Comput. Systems, 1988. p. 517-523.

161. Chang J.H., Despain A.M., DeGroot D. AND-Parallelism of Logic Programs Based on a Static Data Dependency Analysis //Proc. COMPCON spring, IEEE, 1985.

162. Chassin de Kergommeaux. An Abstract Machine to Implement AND-OR-parallel Prolog Efficiently // J. Logic Programming, 1990. p. 249-264.

163. Chikayama Т., Kiyohara R. Parallel Inference System Research in the Japaese FGCS Project. /Lecture Notes in Computer Science. Vol 748. R.H. Halstead (Ed), Parallel Symbolic Computing Laguages, Systems and Aplica-tions. Proceedings. 1992.

164. Cho, Т.Н., R.W. Conners and P.A. Araman, A computer vision system for automatic grading of rough hardwood using a knowledge-based approach, Proc. IEEE Int. Conf. on Systems, Man, and Cybernetics, 4-7 November 1990, Los Angeles, CA, pp 345-350.

165. Ciepielewsky A., Haridi S. A Formal Model for OR-Parallel Execution of Logic Programs //Inf. Proces., 1983.

166. Clocksin W.F. Principles of the Delphi parallel inference machine // Computer J. 1987. - Vol. 30, № 5, - p. 392-396.

167. Conery J.S., Kibler D.F. AND-parallelism and nondeter- minism in logic programs // New Generation Computing. 1985.- Vol.3, N 1. - P. 43-70.

168. Dennis J.B. Data Flow Supercomputers // Computer. 1992 N 11, p. 48-56.

169. Despain A.M., Patt Y.N. The Aquarius Project // Digest of papers / COMPCON spring. 1984. - p.65-84.

170. Fagin B.S., Despain A.M. The Performance of Parallel Prolog Programs // IEEE Transactions on Computers. 1990/ - Vol 39, № 12, p. 1434-1445.

171. Flagship: A parallel architecture for declarative programming / Watson I., Woods V., Watson P., Banach R., at al.// Proc. 15-th Annu. Int. Symp. Computer Architecture, 1988.- P.124-130.

172. Fox R., Josephson J. A Tool for Abductive Inference. IEEE, 1994.

173. Frosini G., Corsini P., Rizzo L. Implementing a Parallel Prolog Interpreter by Using Occam and Transputers // Microprocessors and Microsistems. 1989. Vol 13, № 4, p. 271-279.

174. Goto A., Tanaka H., Moto-Oca T. Highly Parallel Infe- rence Engine PIE-Goal Rewriting Model and Machine Architecture // New Generation Computing.- 1984.- Vol. 2, N 1.- P. 37-58.

175. Guo-Jie, Wah B.W. Optimal granularity of parallel evaluation of AND trees // Proc. Fall Joint

176. Comput. conf., 1987,Oct. P. 297-306.

177. Habata S., Nakazaki R., Konagaya A., Atarashi A. Co- operatuve high perfomance sequential inference machine: CHI-II // NEC Research and Development.- 1988. N 88.- P. 92 101.

178. Hasegawa R., Amamiya M. Parallel execution of logic programms based on dataflow concept // Proc. Of Int. Conf. On Fifth Gen. Comput. Systems, 1984. p.507-516.

179. Hwang K. Advance computer architecture: parallelism, scalability, programmability. McGraw-Hill series in computer engineering. 1993, 772 p.

180. Irani K.B., Shih Y.F. Implementation of Very Large Prolog-Based Knowledge on Data Flow Architectures // Proc. 1st Conf. on Artificial Intelligence Applications / IEEE, Dec. 1988.- P.-454-459.

181. Ito N., Shimizu H., Kuno E. Et al. Data-Flow Based Execution Mechanism of Parallel Concurrent Prolog // New Generation Computing. 1986. - №3, p.15-41.

182. Kacsuk P. A Parallel Prolog Abstract Machine and its Multi-Transputer Implementation // The Computer J.- 1991. Vol. 34, №1.- P.52-63.

183. Kacsuk P., Bale A. DAP Prolog: A Set oriented approach to prolog // The Computer J.- 1987,- Vol. 30, №5.- P.261-275.

184. Kakas A.C., Kowalski R.A., Toni F. Abduction and logic programming. Draft. Imperial College of Science, Technology and Medicine, London.

185. Kaneda Y., Tamura N., Wada K., et al. Sequential Prolog machine РЕК // New Generation Computing. 1986. - Vol.4.- P.-51-66.

186. Komorowski H.J. An Abstract Prolog Machine // Integrated Interactive Computing Systems Proc./ Ed. by P. Degano, E. Sandewall. 1983. - 76 p.

187. McCarthy J. Recursive functions of symbolic ex-presions and their computation by machine // CACM, vol. 3, pp. 184-195.

188. Moto-Oka T. Overview to the Fifth Generation Computer System Project // Proc. 10th Annual Int' 1 Symp. on Computer Architecture / IEEE/ACM, June 1983.-P.417-422.

189. Murakami K., Kakuta Т., Onai R. Architectures and Hardware Systems: Parallel Inference Machine and Knowledge Base Machine // Proc. Int. Conf. 5th Generation Computer Systems. ICOT.-1984. P. 1836.

190. Naganuma J. , Ogura T. A Highli OR-Parallel Inference Machine (Multi-ASCA) and Its Load Balancing Algorithms // IEEE Trans, on Comput. 1994.- Vol. 43, N9.-P.-20-35

191. Nakazaki R. Design of a High-Speed Prolog Machine (HPM) // SIGARCH Newsletter. 1986. - Vol. 13, N 3. - P.191-197.

192. Ng K.W., Leung H.F. Competition: A model of AND-parallel execution of logic programa // The Comput. -1990.-Vol.33,No.3. P.215-218.

193. Nishikawa H. The personal sequential inference machine (PSI): its design philosophy and machine architecture // Proc. Logic programming workshop. 1983. P. 53-73.

194. Onai R. Et al. Architecture of a Reduction-Based Parallel Inference Machine: PIM-R // New Generation Computing. 1985, Vol.3, N2. - P.197-228.

195. Peirce C.S. Collected Papers of Charles Sanders Peirce. Vol. 2.1931-1958. Garvard Univercity Press.

196. Pereira L.M., NaSr R. Delta-Prolog, a Distributed Logic Programming Language // Proc. Int' 1 Conf. on Fifth Generation Computer Systems. ICOT.-1984.- P.283-291.

197. Researsh on Parallel Machine Architecture 5th Generation Computer Systems/ Murakami K., Kakuta Т., Onai R., Ito N. // IEEE Computer.- 1985.- Vol.18, N 6.-P.76-92.

198. Reynolds T.J. BRAVE a parallel logic languages for artifical intelligence // Future Generation Computer System.- 1988.-Vol.4,N 1.- P. 6975.

199. Rich E., Knight K. Artificial Inelligence. 2nd ed. McGrow-Hill Inc. New York. 1991.

200. Rich E., Knight K. Artificial Inelligence. 2nd ed. New York: McGrow-Hill Inc., 1991.

201. Shobotake Y.,Aiso H. Unification Processor Based on Uniformly Structured Cellular Hardware // Computer Archit.News 1986 Vol.14 N 2 pp 140-148.

202. Siekman J. Universal Unification // Lecture Notes Сотр. Sci. -1984. Vol 170. pp.1-43.

203. Trinker P.A. Performance of an OR-Parallel Logic Programming System // Journal of Programming. 1988. Vol 17, N1. p. 59-92.

204. Turner D.A. A new implementation technique for applicative languages // Software Pract. Exper., vol. 8, pp. 31-49.

205. Umeyama S., Tamura K. A Parallel Execution Model of logic Programs // Proc. 10th Annual Symp. On Computer Architecture, IEEE/ACM, 1983. N6, p. 349-355.

206. Warren D.H.D. An Abstract Prolog Instruction Set. Tech. Note 309. AI Research Center, 1983.

207. Warren D.H.D. OR-Parallel execution models of Prolog // Lect. Mot. In Comput. Sci., 1987. -N250. p. 234-259.

208. Wise M.J. EPILOG = PROLOG + data flow. Arguments for combining PROLOG with a data driven mechanism // ACM SIGPLAN notices. 1985. Vol 17, N12. p. 80-84.

209. Yasuura H. On Parallel Computational Complexity of Unification. Proceeding of the International Conference of Fifth Generation Computer Systems 1984. pp 325-243.

210. The UltraSPARC Architecture. The UltraSPARC Processor, Technology White Paper, Sun Microsystems, Inc., 1995.