Содержание к диссертации
Перечень сокращений и специальных терминов 5
Введение , б
1 Обзор архитектур и средств аппаратной поддержки ИА 12
1.1 Продукционная модель представления знаний 12
Общие сведения 12
RETE-сеть и ее модификации 16
Представление и обработка неопределенных знаний в ПС 21
1.2 Интеллектуальные агенты 25
Понятие ИА реального времени 25
Архитектуры интеллектуальных агентов 28
Место ПС в ИА РВ 45
1.3 Анализ подходов к аппаратной поддержке ПС 50
Процессоры срасширенной системой команд 50
Многопроцессорные архитектуры 51
Мультипроцессорные архитектуры с программируемой структурой 56
Функционально-ориентированные сопроцессоры 57
Нейросетевые (коннекционистские) реализации 59
Универсальный интерпретатор ПС 60
Выводы 62
2 Организация МЛВ на основе RETE-сети 63
2.1 Виртуальная машина вывода для обработки продукционных систем
на базе RETE-сети 63
2.2 Анализ способов представления RETE-сети в памяти ФОП 71
Статические структуры данных в классическом способе представления RETE-сети 71
Модифицированная структура RETE-сети 79
RETE-сеть в ПС с объектами одного класса 85
2.2.4 Разработка форматов внутреннего представления RETE-сети 88
2,3 Выводы 95
3 Проектирование ФОП аппаратной поддержки ПС на основе RETE-сети 96
Анализ архитектурных решений ФОП 96
Методы оптимизации RETE-сети 105
Обоснование подхода к оптимизации 105
Постановка задачи оптимизации RETE-сети 112
Метод оптимизации на основе склеивания и алгоритм компиляции RETE-сети 115
Уточнение алгоритма интерпретатора 119
Методика проектирования ФОП 122
Выводы 126
4 Реализация ФОП на БИС программируемой логики и экспериментальное
исследование . 127
ПЛИС как элементная база для реализации ФОП аппаратной поддержки РТА РВ 127
Проектирование процессора на языке VHDL 130
Реализация ФОП на основе макетной платы 134
Методика проведения эксперимента 136
Программное обеспечение экспериментального образца ФОП 140
Проведение и результаты эксперимента 143
Выводы 154
Заключение , 156
Список литературы 159
Список иллюстраций 177
Приложение А 180
VHDL-проект базовой архитектуры ФОП на базе графического пакета
Renoir 180
Приложение Б 185
Схемы вспомогательной аппаратуры для связи ядра ФОП с базовой
платформой 185
Приложение В 186
Листинги модулей программного обеспечения 186
Листинг 1. Модуль RETEJNT.H 186
Листинг 2. Модуль RETEJNT.CPP 188
Листинг 3. Модуль RTN2FOP.CPP 191
Листинг 4. Модуль TKN2FPT.CPP 191
Листинг 5. Модуль KBG2CLP.CPP 192
Листинг 6. Модуль RETE_FOP 196
Листинг 7. Модуль ROPT_GEN 199
Листинг 8. Модуль ROPT_PRT 200
Листинг 9. Модуль RETE_OPT 202
Перечень сокращений и специальных терминов
ASIC — Application-Specific Integrated Circuit
CPLD — Complex Programmable Logic Device
FPGA — Field programmable array
PLD — Programmable logic device (БИС программируемой логики, ПЛИС)
SOPC — System-on-programm able-chip
БД — База данных
БЗ — База знаний
БФА — Блок формирования адреса
ИА — Интеллектуальный агент
ИИ — Искусственный интеллект
MAC — Многоагентная система
МЛВ — Машина логического вывода
ПБЗ — Продукционная база знаний
ПЛИС — Программируемая логическая интегральная схема
ПЛМ — Программируемая логическая матрица
ПМЛ — Программируемая матричная логика
гггтд — Пара «Проверка-действие»
ПС — Продукционная система
РВ — Реальное время
СБИС — Сверхбольшая интегральная схема
СИИ — Система искусственного интеллекта
СНК — Система на кристалле
УЭ — Условный элемент
УИ — Универсальный интерпретатор
ФОП — Функционально-ориентированный процессор
ЭВМ — Электронно-вычислительная машина
Введение к работе
Актуальность темы. Системы искусственного интеллекта (СИИ) находят в последние годы все более широкое применение в самых различных областях: медицина, авиационная и космическая техника, бытовая техника, робототехника, системы управления предприятиями, социально-аналитические системы, интернет-приложения и так далее [I, 2]. Современный этап развития СИИ связан с разработкой теории, методов и средств построения интеллектуальных агентов (ИА) — нового класса СИИ, способных к автономному целенаправленному функционированию в открытых, динамических и неопределенных средах [57, 59]. В частности, концепция ИА все шире используется в приложениях реального времени (РВ), включая бортовые и встраиваемые системы [95,104,106].
В теории ИИ агенты рассматриваются как системы «ограниченной эффективности» [7], которые не могут в общем случае решать за отведенное время все стоящие перед ними задачи оптимально вследствие открытости и динамичности среды, а должны максимально эффективно использовать все имеющееся у них время и ресурсы для принятия решений. В соответствии с этим, производительность работы подсистем агента влияет на качество принимаемых им решений в рамках интервала времени, вычисляемого динамически в соответствии с текущей ситуацией в среде.
ИА в целом представляют собой гибридные СИИ, так как строятся с использованием различных моделей представления и обработки знаний, а также традиционных вычислительных алгоритмов. Вместе с тем, эффективность их функционирования в приложениях жесткого РВ может быть существенно повышена за счет использования средств аппаратной поддержки алгоритмов, составляющих значительный удельный вес в архитектуре ИА.
Как показывает анализ, важное место при построении ИА играют продукционные системы (ПС), задаваемые совокупностью правил «Если ..., то...». ПС используются в разных подсистемах агента для задания как предметных, так и управляющих знаний. Таким образом, эффективность функционирования ИА РВ может быть повышена за счет средств аппаратной поддержки ПС.
Существующие подходы к аппаратной поддержке ПС, такие как системы массового параллелизма [125-153], расширения набора команд стандартных микрокои-
троллеров [167-169] и процессоры поддержки высокоуровневых языков [172-177] по разным причинам не применимы или не обеспечивают требуемой эффективности в бортовых и встраиваемых приложениях ИА РВ [170, 178]. Наиболее важными из этих причин являются недостаточная гибкость и функциональность, а также существенные аппаратные затраты при увеличении объемов баз знаний. Эффективным подходом к реализации средств аппаратной поддержки для таких приложений являются ФОП обработки продукционных знаний, построенные по принципу универсального интерпретатора продукционных систем (УИ ПС) [68, 170, 171]. Данный принцип позволяет обрабатывать любые ПС в рамках заданных ограничений на форму представления знаний. Таким образом, ФОП может использоваться для обработки ПБЗ разных подсистем агента. Концепция УИ ПС была предложена и доказана ее эффективность для списочной формы представления продукционных знаний и деревьев решений.
Эффективной, с точки зрения вычислительных затрат, формой представления продукционных баз знаний является RETE-сеть [16] и ее модификации [18—20, 32, 35, 40-42], представляющие собой графы потока данных специального вида, позволяющие исключить из процесса логического вывода алгоритмическую избыточность. RETE-сеть уже более 20 лет активно используется в большинстве программных платформ с продукционным выводом. В том числе, такие широко известные платформы построения ИА, как CLIPS [21-23] и JESS [24] также используют RETE-сеть для внутреннего представления знаний. При этом CLIPS специально разработан и позиционируется NASA как платформа для бортовых систем реального времени.
Прогресс технологии ПЛИС создал предпосылки к реализации высокопроизводительных ФОП обработки знаний в габаритах типовых плат расширения, подключаемых к стандартным магистралям современных бортовых или настольных ЭВМ. Как показывает анализ, такой подход наиболее целесообразен для бортовых и встраиваемых систем [188-199]. Таким образом, разработка подобных ФОП аппаратной поддержки RETE-сетей является актуальной на сегодняшний день научной задачей. Стремительное развитие систем на кристалле в настоящее время обуславливает перспективность данного подхода для встроенных систем, создавая дополнительные возможности повышения функциональности и производительности ФОП за счет уменьшения затрат на взаимодействие с ядром основного процессора и возможности оперативной реконфигурации.
Цель и задачи исследования. Целью диссертационной работы является разработка принципов организации, архитектур и методов проектирования функционально-ориентированных процессоров обработки продукционных баз знаний на основе RETE-сети.
В соответствии с поставленной целью, в работе формулируются и решаются следующие основные задачи:
Анализ известных подходов к построению средств аппаратной поддержки ПС на основе RETE-сетей с точки зрения эффективности их использования при построении ИА РВ.
Разработка виртуальной машины логического вывода для продукционных баз знаний на основе RETE-сети.
Анализ и разработка эффективных с точки зрения аппаратной реализации способов внутреннего представления и методов оптимизации RETE-сети;
Разработка базовых архитектур и методики проектирования ФОП аппаратной поддержки ПС на основе RETE-сети;
Разработка методов и алгоритмов эффективной компиляции исходных ПБЗ в форматы внутреннего представления оптимизированной RETE-сети;
Разработка методики и экспериментальная оценка производительности ФОП с использованием макетного образца.
Предмет и методы исследования
Предметом исследования являются способы представления и обработки ПБЗ на основе RETE-сети и принципы организации ФОП аппаратной поддержки алгоритмов логического вывода для ПС на базе RETE-сетей. Методами исследования являются целочисленное линейное программирование; методы оптимизации; элементы теории автоматов; методы алгоритмизации и программирования на языках C++, Fortran; методы проектирования аппаратуры на базе БИС программируемой логики с использованием языков описания дискретных устройств (VHDL).
Научную новизну работы составляют:
1. Модификации RETE-сети, ориентированные на аппаратную реализацию продукционных систем и отличающиеся от известных использованием статических структур данных, что позволяет при незначительном росте объема памяти базы знаний существенно упростить архитектуру и повысить производительность ФОП.
Базовая архитектура и ряд вариантов структурной организации ФОП, ориентированные на предложенный способ представления RETE-сети и учитывающие представление и обработку в продукционных БЗ неопределенной информации.
Постановка и решение задачи определения оптимальной структуры подсетей р-узлов RETE-сети по критерию минимального времени логического вывода в терминах целочисленного линейного программирования.
Метод и алгоритм быстрой компиляции БЗ в модифицированную RETE-сеть с оптимизацией по склеиванию р-узлов, отличающийся использованием матричных и побитовых преобразований над антецедентами правил. Метод позволяет исключить комбинаторный перебор конфигураций сети и обеспечивает предсказуемое время ее построения.
Практическая значимость работы заключается в следующем:
Разработан пакет VHDL-модулей масштабируемого ядра ФОП обработки продукционных БЗ на основе RETE-сети, позволяющий проектировать подобные устройства с учетом различных форм неопределенности и требований по параметрам обрабатываемых баз знаний, таких как максимальное число объектов, глубина RETE-сети, ширина входного токена, и т.п.
Разработан и реализован экспериментальный образец ФОП обработки продукционных баз знаний на основе СБИС программируемой логики, позволяющий оценить эффективность предложенного подхода к построению средств аппаратной поддержки ПС. Показано, что ФОП на основе предложенной архитектуры, позволяет получить предсказуемое время обработки БЗ, что имеет существенное значение при построении ИА реального времени.
Реализован алгоритм быстрой компиляции исходной БЗ в оптимизированную RETE-сеть с предсказуемым временем обработки, позволяющий использовать ФОП в системах реального времени с динамическим формированием баз знаний. Экспериментально подтверждена квадратичная сложность данного алгоритма.
Написан ряд программных модулей для взаимодействия ФОП с базовой машиной и проведения экспериментальной оценки его производительности. Разработанные модули могут в дальнейшем использоваться в составе инструментальной среды проектирования устройств подобного класса.
5. На основе созданного аппаратно-программного комплекса проведено экспериментальное исследование и установлено, что выигрыш ФОП в производительности по сравнению с процессорами общего назначения составляет от 10 до 40 раз в зависимости от характеристик БЗ и БД. При оценке использовалось два разных подхода к организации программных интерпретаторов: стандартная платформа CLIPS, используемая для построения ИА, и низкоуровневый программный интерпретатор.
Достоверность результатов исследования.
Достоверность полученных в диссертации выводов подтверждается результатами теоретических расчетов, результатами экспериментального сравнения с существующими программными интерпретаторами ПС, а также результатами практического использования, что подтверждается актом о внедрении.
Для экспериментальной оценки производительности ФОП в качестве основного сравниваемого варианта выбрана реализация в среде CLIPS, так как она наиболее широко используется для построения ИА РВ. С целью повышения достоверности экспериментальных оценок был также написан программный интерпретатор RETE-сети на C++, функционально аналогичный ФОП. В CLIPS был введен ряд средств, позволяющих точно измерить время этапа сопоставления фактов. Оценка программных платформ производилась дважды с использованием разных базовых вычислительных платформ (Pentium Ш-700МГц и Pentium IV-ЗГТц). Результаты сравнения производительности получены на основании измерений по 400 сгенерированным БЗ различного объема. Предложенная в работе методика оценки производительности включает ряд способов минимизации влияния побочных эффектов на точность измерений. Достоверность результатов измерений времени обработки БЗ программными интерпретаторами подтверждается приблизительным равенством результатов для БЗ большого объема. Измерения времени обработки тестовых БЗ в ФОП проводились с использованием счетчика тактов, специально введенного для этой цели в его структуру.
Внедрение результатов.
Теоретические и практические результаты диссертационной работы, полученные в ходе выполнения НИР 5937/ВТ-210, внедрены на предприятии ФГУП НПП «Рубин» при разработке принципов построения экспертных систем реального времени и средств их аппаратной поддержки для автоматизированных систем оценки и прогнозирования воздушной обстановки.
Работа также поддержана:
Грантом Министерства образования — "Организация и проектирование процессоров аппаратной поддержки объектно-продукционных моделей представления и обработки знаний для интеллектуальных агентов реального времени"/ НИР ВТ-39/ГТАТ, проект ТОО-3.3-2672, научный руководитель Пантелеев М.Г.
Персональным грантом СП6ТЭТУ для студентов и аспирантов ЭТУ за 2001г.
Персональным грантом - «Разработка архитектур и методов проектирования функционально-ориентированных процессоров логического вывода для продукционных баз знаний на основе RETE-сети» по конкурсу проектов аспирантов и докторантов по разделу III Темплана Минобразования 2002г.
Апробация результатов исследования. Основные положения и результаты работы докладывались и обсуждались на научно-технических конференциях СПбТЭ-ТУ в 2001—2003 гг., а также на следующих конференциях: седьмая национальная конференция по искусственному интеллекту с международным участием «КИИ'2000», Переславль-Залесский, 2000 г.; четвертый и пятый международные симпозиумы «Интеллектуальные системы» ИНТЕЛС, Москва, 2000г., Калуга, 2002 г.; четвертая международная конференция по мягким вычислениям и измерениям SCM'2001, Санкт-Петербург, 2001 г.; международный конгресс «Искусственный интеллект в XXI веке» ІСАГ2001, Двиноморское, 2001 г.; международная научно-техническая конференция «СуперЭВМ и многопроцессорные вычислительные системы» MCS'2002, Таганрог, 2002 г.; международная конференция «Искусственные интеллектуальные системы» IEEE ICAIS'2002, Двиноморское, 2002 г.; четвертая и пятая международные научно-техническая конференция «Искусственный интеллект. Интеллектуальные и многопроцессорные системы» ИМС, Двиноморское, 2003 и 2004 г.
Публикации. По теме диссертации опубликовано 15 научных работ, в том числе 4 статьи в журналах, 10 тезисов докладов на международных научно-технических конференциях, 1 авторское свидетельство на полезную модель.
Структура и объем работы.
Диссертация состоит из введения, четырех глав, заключения, трех приложений и списка литературы, включающего 202 наименования. Основная часть работы изложена на 146 страницах машинописного текста и содержит 68 рисунков, 2 таблицы.
