Введение к работе
Актуальность проблемы Развитие методов, возникших в области искусственного интеллекта, их применение в более широких областях, таких, как понимание текстов на естественных языках, экспертные системы, банки данных, происходила посредством специализации языков программирования, которые содержали необходимые средства для аксиоматизации и решения поставленных задач.
Интерес к Прологу за рубежом значительно возрос после его принятия .в качестве базового языка японским проектом создания машин пятого поколения . В настоящее время популярность языка увеличивается, однако более широкому распространению препятствует практическая непригодносгь его реализаций на современных однопроцессорных универсальных машинах для решения больших задач в области искусственного интеллекта( ИИ) и экспертных систем <ЭС).
На современных ЭЕЫ один шаг логического вывода в силу большого семантического разрыва требует исполнения порядка 100. .1000 машинных команд. Производительность универсальных ЭВМ составляет. 1..20 млн. кошанд/с . Следовательно, реализация Пролога на таких' универсальных ЭЕЫ обеспечит производительность порядка 1.. 20Q KLIPS, что недостаточно для решения в реальном масштабе времени больших, требующих десятков и сотен миллионов логических выводов, задач Ш и 30.
Поэтому задача разработки высокоэффективных Пролог-систем является актуальной.
Усилия разработчиков Пролог систем, направленные на повышение производительности, распределены по следующим, относительно ортогональным уровням :
уровень языка : создание новых, параллельных языков логического программирования, в состав которых вводятся специальные синтаксические и семантические конструкции,обеспечивающие "видимость" внутреннего параллелизма Пролога, и/или развитие последовательных версий языка путем добавления подобных конструкций с целью его адаптации к уже существующим мультип-роцеесарньгм и мультимашинным архитектурам;
уровень компилятора : применение методов выделения параллелизма в исполняемом коде на этапе компиляции с испольво-
-' 2 -ванием статического анализа вависимости по данным?'
уровень процессора : повышение тактовой частоты, уменьшение количества тактов на логическом выводе путем сокращения семантического разрыва, микропрограммная интерпретация W-кода, RISC;
системный (межпроцессорный) уровень і . мультипроцессор-, ная или мультимашинная конфигурация системы с целью увеличения вычислительной мощности при помощи увеличения числа процессоров или ЭВМ.
Целью данной работы является разработка высокоэффективной Пролог-системы, реализующая внутренний, присущий Прологу параллелизм преимуществено на системном уровне. Со стороны интерфейса программиста система должна удовлетворять следующими требованиями:
- Получение и выдача всех возможных решений исходного^це
левого утверждения. Это требование посвяарно предотвращению
аномалии ускорения, наличие которой' не является корректным
критерием оценки эффективности системы;
. - Обнаружение и реализация параллелизма прозрачны для программиста и не требуют применения дополнительных синтаксических конструкций языка Пролог. Шжно считать, что противопо- лойшая концепция противоречит идее полного разграничения семантики от управления, заложенной е основе рассматриваемого языка программирования.
Достижение вышеприведенной цели предполагает решение следующих задач: . '"
Выбор прототипов модели параллельного логического вывода и параллельной архитектуры для ее реализации;
Разработка модели параллельного логического вывода, позволяющая эффективно реализовать внутренний параллелизм Пролога;' .
-Разработка- архитектуры -параллельной Пролог-системы, поддеживагощяя реализацию модели параллельного логического выгода;
- Разработка системы моделирования, и ее применение с
целью качественной и количественной оценки,результатов решения
предидуших трех задач.
Методы исследования базируются на теорию вычислительные систем, а также на накопленный к настоящему времени, опыт и ре-
- d -
вультату в области логического программирования, организации вычислительных процессов, проектирования и программного моделирования мультипроцессорных вычислительных систем. Научная новизна состоит в следующем
Равработана модель параллельного логического вывода нз базе взаимодействующих через сообщения И- и ИЛИ-процессов, которая отличается от аналогичных эффективным механизмом передачи сообщений и реализацией нескольких типов параллелизма и конвейеризацией активации процессов.
Разработана архитектура параллельной Пролог-системы, обеспечньаюшдя поддержку разработанной модели и реализующая на данном уровне несколько типов параллелизма. Архитектура отличается от аналогичных использованием аппаратных узлов подделки межпроцессорных взаимодействий,
Получены количественные оценки эффективности системы, которые позволяют сделать заключение о максимальной производительности порядка 1.05 ML IPS при длительности цикла синхронизации С0не, что соответствует выполнению одного логического вывода за 5 тактов.
Практическая ценность заключается в следующем:
Разработано (в системе команд последовательного RISC-процессора с минимальным ее расширением командам! поддержки параллелизма) ядро системного програшного обеспечения параллельной Пролог-системы;
Предложена гетерогенная, мультипроцессорная, скльносаа-аанная структура параллельной Пролог-системы с иепольэованем в качестве вычислительных узлов последовательных RISC-Про-лог-процессоров с минимальным (ориентированным на параллелизм) расширением функциональных возможностей;
Разработана система моделирования параллельной Пролог-системы, исполняемая в монопрограммной, однопроцессорной среде ЫЗ-П05 и обладающая хорошо развитым интерактивным, дру-даественным интерфейсом польЕОвателя.
"Внедрение результатов работы осуществляется в рамках курса "Специализированные процессоры ЗИЛ".
Апробация работы. Основные положения и результаты диссертационной рабяты докладывались на научно-практических конференциях ЛЭТИ им. R И. Ульянова /Ленина/ в 1991-1993 гг. и на местной, российско-германском научно-техническом семинаре "Вы-
- 4 -числительные системы с массовый параллелизмом", г. Санкт-Петера бург 1992 г.
Публикации- По материалам работы опубликованы 2 статьи.
Структура м обьем работы Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы, включающего 68' наименований, и 27 приложений. Основная часть работы изложена на 145 страницах машинописного теглта.- Работа содержит 27 рисунков и 15 таблиц.