Введение к работе
Актуальность проблемы. Актуальной проблемой теории и практики вычислительных систем является создание высокопроизводительных машин логического вывода. Актуальность этой проблемы обусловлена тем, что одно из основных направлений развития современных вычислительных систем заключается в переходе от архитектуры, ориентированной на обработку данных, к архитектуре, ориентированной на обработку знаний. Важнейшую роль в обработке знаний играет логический вывод. Машина логического вывода (МЛВ) является основным компонентом вычислительных систем, ориентированных на обработку знаний, и во многом определяет их характеристики. Создание высокопроизводительных вычислительных систем обработки знаний диктуется потребностью практики, поскольку использование методов искусственного интеллекта при решении задач в таких областях, как обработка изображений, машинное зрение, семантический анализ речи, обработка радиолокационных, сейсмических, метеорологических, медицинских и других данных позволяет перейти на качественно новый уровень.
Проблема создания высокопроизводительных МЛВ имеет три составляющие.
Первая составляющая связана с разработкой методов логического вывода. Здесь, вероятно, отправным методом следует считать разработанный Дж. Робинсоном (1965 г.) метод резолюций. Существуют и другие не менее сильные методы логического вывода: метод Маслова, вывод на основе интерпретаций Бета, сравнений по образцу (pattern matching) и др. Тем не менее, именно для метода резолюций была разработана Р. Ковальским идея процедурной интерпретации логического вывода, которая дала начало собственно логическому программированию как языку, технологии и парадигме. Несомненно, что среди языков логического программирования ведущее место в этом отношении занимает язык ПРОЛОГ и его многочисленные версии. Создание программного обеспечения для описания задачи и реализации логического вывода образуют вторую составляющую проблемы.
Наконец, третья важнейшая составляющая проблемы создания высокопроизводительных МЛВ - это аппаратная поддержка логического вывода, необходимость которой обусловлена следующими причинами:
переборным характером процедур вывода;
использованием сложных нетрадиционных структур данных;
наличием специфических операций, не имеющих аналогов в других вычислениях.
Весьма продуктивным здесь оказался подход, основанный на использовании абстрактных ПРОЛОГ-машин, и, прежде всего, широко известной абстрактной машины Д. Уоррена.
Большинство современных машин логического вывода реализовано на базе ПРОЛОГ-процессоров, основным недостатком которых является низкая производительность. Чтобы повысить быстродействие ПРОЛОГ-машин, были
предприняты попытки модифицировать "чистый" ПРОЛОГ в его параллельные версии. Однако должного эффекта не было достигнуто, поскольку в основе языка ПРОЛОГ лежит последовательный принцип SLD-резолюции. Производительность созданных ПРОЛОГ-машин не превышает уровня 10 MLIPS, в то время как для масштабных задач требуется производительность порядка 1 GLIPS.
Таким образом, перед разработчиками перспективных средств вычислительной техники встала важная научно-техническая проблема создания высокопроизводительных машин логического вывода на основе новых методов логического вывода и нетрадиционных архитектурно-структурных решений.
Основная часть исследований, посвященных теории и методам логического вывода, проводится в России под эгидой Ассоциации искусственного интеллекта. Большое влияние на развитие исследований в этой области искусственного интеллекта оказали работы Д.А. Поспелова, Г.С. Осипова, В.Н. Вагина, В.К. Финна, В.Ф. Хорошевского, Е.А. Сидоренко и др. Теоретические основы построения высокопроизводительных проблемно-ориентированных вычислительных систем были заложены в работах Э.В. Евреинова, Ю.Т. Косарева, И.В. Прангишвили, В.Б. Смолова, Е.П. Балашова, Д.В. Пузанкона, А.В. Каляева, В.В. Корнеева и др. Важные результаты на пути создания высокопроизводительных ПРОЛОГ-машин получили В.А. Вишняков, Д.Ю. Буландже, О.В. Герман, B.C. Фомичев, А.И. Водяхо, А.А. Власов и др. В предлагаемой работе решение данной проблемы рассматривается в рамках научного направления "Высокопроизводительные системы обработки данных и знаний".
Предметом исследования являются высокопроизводительные машины логического вывода: формы представления знаний, виды и методы логического вывода, вычислительные модели, архитектура, программирование, организация и применение.
Целью работы является разработка методов и средств повышения производительности машин дедуктивного и абдуктивного вывода на знаниях за счет организации параллельных логических вычислений.
В соответствии с поставленной целью в работе формулируются и решаются следующие основные задачи.
1. Разработка основ теории параллельных дедуктивных и абдуктивных
вычислений, в том числе:
построение формальных систем для представления знаний, позволяющих проводить параллельный логический вывод;
разработка методов параллельного дедуктивного вывода;
разработка методов параллельного абдуктивного вывода.
2. Разработка и исследование модели вычислений и абстрактной машины
логического вывода, в том числе:
разработка основ языка декларативного логического программирования;
разработка модели параллельных логических вычислений для дедуктивного и абдуктивного вывода;
разработка архитектуры абстрактной машины параллельного логического вывода и интерпретатора языка декларативного логического программирования;
исследование подходов к реализации абстрактной машины логического вывода.
3. Разработка и исследование принципов организации, функционирования и реализации высокопроизводительных машин логического вывода, в том числе:
разработка структур и алгоритмов функционирования многопроцессорных машин логического вывода;
разработка базовых архитектурно-структурных решений для создания быстродействующих процессоров логического вывода;
исследование вопросов оценки эффективности и применения машин логического вывода.
Методы исследования основаны на использовании теории множеств и теории графов, математической логике, теории моделирования, теории вычислительных систем и логического программирования, методов научного анализа и синтеза.
Научная новизна. В результате проведенных исследований получены следующие научные результаты.
-
Для представления знаний в машинах логического вывода предложена формальная система - исчисление высказываний I, отличающаяся от известных составом аксиом и правил доказательства, а также нетрадиционной экспликацией логического следования. На основе исчисления I разработано исчисление предикатов первого порядка IP, в котором доказаны необходимые теоремы и производные правила вывода, позволяющие применять известные способы преобразования произвольных выражений исчисления IP в дизъюнкты и проводить логический вывод.
-
Разработаны методы параллельного дедуктивного и абдуктивного логического вывода на знаниях, представленных выражениями исчисления высказываний I, названые методами деления дизъюнктов, которые отличаются от известных содержанием выполняемых преобразований и широкими возможностями по распараллеливанию вычислений.
-
Разработаны методы параллельного дедуктивного и абдуктивного логического вывода на знаниях, представленных выражениями исчисления предикатов IP. Методы отличаются от известных содержанием выполняемых преобразований и широкими возможностями по распараллеливанию вычислений. Кроме того, в отличие от известных методов разработанный метод абдуктивного вывода способен порождать не только однолитеральные, но и многолитеральные дополнительные посылки.
4. Разработаны основы языка декларативного программирования -
АЛОГ. Семантика языка АЛОГ базируется на методах параллельного дедуктив
ного и абдуктивного вывода, разработанных в рамках исчисления предикатов
IP. Отличительными особенностями языка являются: использование дизъюнк-
тов общего вида, возможность представления заключения конъюнкцией дизъюнктов, ориентация на получение множества решений, полная декларативность.
-
Разработана многоуровневая модель параллельных логических вычислений для дедуктивного и абдуктивного вывода методом деления дизъюнктов, отличающаяся от известных наличием четырех типов параллелизма, присущих методу деления дизъюнктов.
-
Разработана абстрактная машина параллельного логического вывода и интерпретатор языка декларативного логического программирования, позволяющие уменьшить семантический разрыв между архитектурой машины логического вывода и средой, в которую ее помещают при реализации. Исследованы возможности реализации абстрактной машины параллельного логического вывода в системах с директивным, потоковым и запросным механизмом управления.
-
Сформулирован принцип (принцип концентрации ресурсов) и разработан способ организации вычислительных процессов в многопроцессорной машине (логического вывода), позволяющие избежать резкого возрастания числа активизируемых процессов и объема промежуточных результатов в машинах с моделями вычислений, представляемыми набором деревьев. Определено множество вариантов построения многопроцессорных машин логического вывода в зависимости от числа уровней и распределения основных вычислительных процессов по уровням кластерной организации.
Практическая ценность. Практическую ценность представляют: программы решения логических задач, многоуровневые структуры многопроцессорных машин, архитектура н структура процессора логического вывода с быстрым переключением контекста, система моделирования многопроцессорных машин логического вывода на базе локальной вычислительной сети, организация диалоговых систем управления процессами и приборами. Совокупность полученных в диссертации результатов позволяет ставить и решать разнообразные задачи проектирования и применения высокопроизводительных машин логического вывода, однако разработанные методы и архитектурно-структурные решения могут быть также использованы при построении машин и диалоговых систем управления умеренной и средней производительности.
Достоверность н эффективность. Достоверность полученных в диссертации выводов подтверждается: строгими математическими доказательствами, результатами теоретических расчетов, результатами имитационного моделирования выполненных разработок, а также результатами практического использования. Эффективность предложенных методов, методик и структурных решений доказана при разработке диалоговых систем управления различного назначения, выполненных по заказам научно-исследовательских и промышленных организаций, что подтверждается актами о внедрении научно-исследовательских работ.
Внедрение результатов. Диссертационная работа является обобщением результатов, полученных автором в Ленинградском электротехническом институте им. В. И. Ульянова /Ленина/ и в Вятском государственном техническом
университете в процессе выполнения в 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 таблиц.
