Введение к работе
Актуальность темы. В настоящее время появилось значительное число коммерческих ЭВМ, ориентированных на параллельную обработку данных. Большинство параллельных машин, объединяющих сотни и тысячи микропроцессоров (Connection Machine, iPSC/2, NCUBE/ten, Caltecli/JPL Mark III, System 14/n и др.), имеют сеть обмена типа гиперкуб.
Традиционно гиперкубовые структуры используют для решения таких задач, которые характеризуются большим числом входных данных и высоким уровнем параллелизма их обработки: в вычислительной геометрии, при сортировке, поиске, моделировании химических реакции и явлений, моделировании схем, обработке изображений и сейсмических данных, размещении ресурсов и других. Поскольку большинство реальных задач по своей природе являются последовательно-параллельными, то в процессе их решения возникает потребность в обмене результатами между отдельными подзадачами. Гиперкубовые структуры обеспечивают решение этой проблемы за счет наличия эффективной сети связи процессорных элементов. Фактически, пользователь может рассматривать гиперкубовую систему как полносвязное множество процессоров, благодаря небольшому расстоянию между всеми парами процессорных элементов.
Использование гиперкубовых структур не ограничивается задачами со статическим параллелизмом, т.е. таким параллелизмом, уро-вень которого можно определить на этапе компиляции и вследствие этого можно обеспечить равномерную нагрузку процессоров в процессе работы. Особый интерес такие структуры представляют для решения задач искусственного интеллекта, в частности, обработки баз знаний большой размерности. Наличие сильносвязной коммутационной сети позволяет эффективно решить проблему поиска. Однако нахождение
4 нужной информации в реальных системах требует не только просмотра имеющихся знаний, но и организации процедур логического вывода. Исследованию возможности организации систем обработки знаний, реализующих, прежде всего, функции логического вывода, в гиперкубовых процессорных структурах, посвящена данная диссертационная работа.
Целью работы является разработка способов реализации баз знаний в спльносвязных процессорных структурах с гиперкубнческой архитектурой.
В связи с поставленной целью в диссертации решаются следующие основные задачи:
анализ подходов и разработка методов реализации систем обработки знаний в гиперкубовых процессорных структурах;
разработка методов параллельного логического вывода в таких структурах;
разработка методов создания на основе таких структур толерантных систем для обработки знаний.
Предметом исследования является параллельный логический вывод на знаниях в гпперкубовых процессорных структурах.
Методы исследования базируются на аппарате математической логики, теории множеств, теории графов, теории дедуктивного вывода.
Научная новизна. В результате проведенных в диссертации исследований:
предложен способ хранения системы продукций в процессорных структурах, который учитывает особенности распределенной обработки знаний;
разработан метод параллельного логического вывода в гиперку-бовьгх процессорных структурах, который позволяет использовать
5 связность этих структур при поиске доказательства;
разработан способ представления графа поиска доказательства, который позволяет осуществлять децентрализованный параллельный логический вывод в процессорных структурах;
разработан метод извлечения решения из графа поиска доказательства, который основан па параллельной идентификации всех возможных решений, найденных в ходе доказательства;
разработаны методы повышения живучести гиперкубических структур для систем обработки знании.
В работе получены и выносятся на защиту следующие новые основные результаты:
-
способ представления и метод реализации параллельного логического вывода в гиперкубовых структурах;
-
методы повышения живучести снльносвязных гиперкубовых структур, учитывающие нарушение связности графа поиска доказательства.
Достоверность основных положений работы подтверждается моделированием на ЭВМ процедур логического вывода в пшеркубиче-скнх структурах различной модификации.
Практическая ценность работы заключается в том, что был предложен эффективный метод параллельного логического вывода на продукциях в коммерческих процессорных структурах. Это позволяет использовать гиперкубовые структуры с большим числом процессорных элементов для построения систем обработки знаний большой размерности.
Апробация работы и публикации. По теме диссертации опубликовано 4 работы [1-4]. Основные результаты докладывались на 5 научно-технических конференциях.
Структура и объем диссертационной работы. Диссертация состоит из введения, трех глав и заключения, изложена на 134 страницах машинописного текста. Имеется список литературы (80 наименований) и приложения на 26 страницах.
