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

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

РГ6 од

У Жуковская Марина Витальевна

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

Специальность: 05.13.17 - Теоретические основы информатики

АВТОРЕФЕРАТ

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

Таганрог - 1998

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

НАУЧНЫЙ РУКОВОДИТЕЛЬ:

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

ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ:

1. Доктор технических наук, профессор

Вптиска П.И.

2. Кандидат технических наук, с.н.с.

Жила В.В.

ВЕДУЩАЯ ОРГАНИЗАЦИЯ:

НИИ Связи (г.Таганрог)

Защита состоится " июня 1998 г. в /у часов на заседании специализированного совета Д 063.13.01 по защите диссертаций при Таганрогском государственном радиотехническом университете по адресу: 347915, г.Таганрог, пер.Некрасовский, 44, ауд. Д-406.

С диссертацией можно ознакомиться в библиотеке университета. Автореферат разослан " ¡¡.¿¿¿¿¿Я— 1998 г.

Ученый секретарь специализированного совета к.т.н., доцент

А.Г. Чефранов.

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

Актуальность темы. В настоящее время появилось значительное число коммерческих ЭВМ, ориентированных на параллельную обработку данных. Большинство параллельных машин, объединяющих сотни и тысячи микропроцессоров (Connection Machine, iPSC/2, NCUBE/ten, Caltecli/JPL Mark III, System 14/n и др.), имеют сеть обмена типа гиперкуб.

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

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

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

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

В связи с поставленной целыо в диссертации решаются следующие основные задачи:

— анализ подходов и разработка методов реализации систем обработки знаний в гиперкубовых процессорных структурах;

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

— разработка методов создания на основе таких структур толерантных систем для обработки знаний.

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

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

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

— предложен способ хранения системы продукций в процессорных структурах, который учитывает особенности распределенной обработки знаний;

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

связность этих структур при поиске доказательства;

— разработан способ представления графа поиска доказательства, который позволяет осуществлять децентрализованный параллельный логический вывод в процессорных структурах;

— разработан метод извлечения решения из графа поиска доказательства, который основан на параллельной идентификации всех возможных решений, найденных в ходе доказательства;

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

В работе получены и выносятся на защиту следующие новые основные результаты:

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

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

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

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

Апробация работы и публикации. По теме диссертации опубликовано 4 работы [1-4]. Основные результаты докладывались на 5 научно-технических конференциях.

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

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

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

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

Обобщенный гиперкуб размерности п (N — m, х т: X... т„) - это структура, где для всех 1—1,..л, нг,>1 каждая вершина v задана числом со

смешанным основанием r(v) =■ (x,...xi...xj, где 0<\{<тГ1, и вершина с

номером (х, ... -Г,.,л',л7+, ... х„) соединена ребром с теми и только теми вершинами, номера которых (х, ... х,_, х /Хц-/ ■■■ *„) ДОЯ всех 1< I <//, где X /Пробегает все целые значения между 0 и тг1, за исключением х,.

Модифицированный обобщенный гиперкуб размерности пХт (Л/ : п*т) - это структура, где каждая вершина задана декартовыми координатами г (у) = (х,у), где 1<х<п, 1<у<т, и вершина с номером соединена ребром с теми и только теми вершинами, номера которых

(х/,ук), где 1<х/<х„, х,^х1, ук = (1+1 )тос1 т.

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

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

Представим все связи вершины ОГК в виде вектора

-V---V-' -V-

а-п а«н-1 а=1

где для 1 / = \ Т.тг\-

Пусгь две вершины г, и имеют номераг(у,) - 11

>'(уг) = (Х1'Хз'-'-'Х^)' кот°рые отличаются в 1-й координате. Определим соответствие между номером связи / из вектора Ь вершины V, и /-и координатой х, вершины у2 :

ИЦЛпи~') + х,"-X. XI > X,

V V,: 1(х~) =

иначе

иначе

+х)1,10(1 т

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

размерности и (АТ = гп, хт2х... т„) имеет нижнюю оценку числа критических отказов 5 = (тк-1), где тк - минимальное из /и, Для оценки вероятности восстановления связности структуры при использовании процедур обхода неисправных связей был использован метод Монте-Карло. Результаты моделирования достоверно показали, что для лучшей из предложенных процедур отказоустойчивой трансляции в случае

равномерного распределения неисправностей вероятность совершения полного обмена информацией между всеми узлами структуры равна 1 при числе неисправных связей до 8% от общего количества ребер гиперкуба. Кроме этого, для данного количества неисправных связен вероятность нахождения пути обхода минимальной длины равна 0.9.

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

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

ах 1 л> 1 1 А' Г>'

А,Ш 1 Л;Й7 ш ,ИГ1 13 '

А[ Ш \ А'г Ш г- Ш А'пи~* В' '

где ^ - условия вывода, - заключения вывода, ХхУ ' е {& /у} ■

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

М = {{Ц, {К), {Р}, {О}, {К}, {В}},

где ¿-множество всех отрицательных литералов дизъюнктов, включая целевые; К-множество положительных литералов дизъюнктов; /•-множество фактов (аксиом); б-положительные литералы целевых дизъюнктов; /С,£)-соответственно операции конъюнкции п дизъюнкции.

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

Метод параллельного доказательства, предлагаемый в работе, заключается в следующем. После размещения лексем те{М} базы знаний и целевых выражений, в гиперкубовой структуре (ГКС) с учетом струк-

туры графов типа И/ИЛИ, процесс вывода берет начало в терминальных вершинах целевых выражений. Все терминальные вершины одновременно распространяют свою копию во все остальные вершины ГКС в режиме трансляции (Рис.1). Вершины ГКС, содержащие лексемы 1)1 с {{[7}и{Я}}, сравнивают свою лексему с лексемами терминальных вершин. Если предикатные символы совпадают, и существует набор подстановок, унифицирующий данные лексемы, то правило (факт) считается примененным. Они включаются в граф поиска доказательства (граф решения) 1! процесс вывода повторяется уже для терминальных вершин примененных правил. Вершины ГКС, с лексемами те{Р). по определению считаются концевыми в графе решения, а значит, они не продолжают процесс доказательства.

Pic. 1. Первый шаг доказательства долевого выражения Pi(x)vP2(x):

-- связь в гра<}е тшп И/ИЛИ;

-------> _ распространите сообщения с литералом Pi(x);

- распространение сообщения с литералом Pi(x).

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

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

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

Пусть граф решения цели С содержит множество вершин {vi.V2.-Vn}, »3 них {у1,у2,..л'т}с{Р}, т<п. Если (п=0)уСт^О), то цель О не имеет решения. Распределенное извлечение ответа предполагает перемещение множества подстановок, характеризующее конкретный граф-кандидат, от вершин вверх по дереву решения до достижения

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

при последовательном просмотре дерева решения от корня.

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

В третьей главе рассмотрены вопросы функционирования системы обработки знаний в гпперкубовых процессорных структурах как

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

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

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

Таблица 1.

Вклад вершин графа типа И/ИЛИ в процесс доказательства.

Этап доказа-Роль вершинь1~\. Построение дерева решения Сокращение дерева решения Извлечение ответа

инициируют Цель Литерал Факт

активно участвуют Цель, Правило, Литерал, Факт Операцня_&, Операция.^/, Литерал Операция_&, Цель

пассивно участвуют Опера цня_&, Операция^ Цель, Правило, Факт Литерал, Правило, Факт, Операция^,

наибольшая нагрузка Правило, Факт - Операция_&, Цель

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

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

а) хранение и обновление системы продукций;

б) поиск доказательства с использованием параллелизма типов И и ИЛИ;

в) одновременный поиск доказательства нескольких налей;

г) построения полного дерева решения (возможно,- на заданную г лубину);

д) реализация поиска доказательства "в глубину";

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

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

В заключении изложены выводы по диссертационной работе.

В приложениях приводятся разработанные алгоритмы и примеры работы программного эмулятора гиперкубовой системы обработки заннпй.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

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

1) Жуковская М.В., Кодачигов В.И. "О повышении живучести гиперкубовых структур"// "Компьютерные технологии в инженерной и управленческой деятельности", сб. трудов ТРТУ, Таганрог,

. 1998 г., ч.2

2) Жуковская М.В. "К проблеме обработки знаний, представленных в виде сети фреймов, в гпперкубовой многопроцессорной системе" // "Известия ТРТУ", сб. трудов ТРТУ, 1997 г., №3

3) Жуковская М.В. "Разработка библиотеки объектов для работы с базами данных" II тез. докл. II Всероссийской научно-технической конференции "Техническая кибернетика, радиоэлектроника и системы управления", ТРТУ, г. Таганрог, 1994 г.

4) Жуковская М.В. "Параллельный логический вывод на семантических сетях" И тез. докл. III Всероссийской научно-технической конференции "Техническая кибернетика, радиоэлектроника и

Тип. ТРТУ. Заказ № 186. Тир. 120 экз. 1998 г.