Процессор для обработки семантических сетей Советский патент 1991 года по МПК G06F15/16 

w

Ё

Изобретение относится к вычислительной технике и предназначено для построения мультимикропроцессорных вычислительных систем распределенной обработки информации в системах искусственного интеллекта. Цель изобретения - расширение функциональных возможностей процессора за счет обеспечения формирования баз знаний. Процессор содержит блок 1 обработки, блок 2 памяти, контроллер 3 внешней памяти, линейные адаптеры 4 - 7, командный адаптер 8, информационный регистр 9, регистр 10 общих признаков. 7 ил.

О vj

Ю О

ю

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

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

На фиг.1-4 представлены структурные схемы соответственно предлагаемого процессора, командного адаптера, информационного регистра, регистра общих признаков; на фиг.5-7 - алго- ритмы функцичнирования процессора.

Процессор (фиг.1) включает в себя блок 1 обработки, блок 2 памяти, контроллер 3 внешней памяти, линейные адаптеры 4-7, командный адаптер 8, информационный регистр 9, регистр 10 признаков, общую шину 11.

Командный адаптер 8 (фиг.2) содержит дешифратор 12, узел 13 формирования сигнала ответа, узел 14 форми- рования сигнала готовности, последовательно-параллельный преобразователь 15, ключ 16, повторитель 17„

Информационный регистр 9 (фиг.З) содержит дешифратор 18 адреса и сдви- говый регистр 19.

Регистр 10 общих признаков содержит дешифратор 20 адреса и регистр 21.

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

Сигналы запроса от ведущей ЭВМ через повторитель 17 поступают к разрешающему входу узла 13 формирования сигнала ответа, который представляет собой D-триггер, а также на линию наивысшего приоритета запроса прерывания на общей шине. По этому запросу блок 1 прерывает свою работу и переходит на подпрограмму обработки прерывания по поступившему запросу. Командный адаптер в поле адресов блока 1 должен занимать старшие разряды адреса. При обращении к командному адаптеру со стороны блока 1 дешифра

п

5

5

5

тор 12 дешифрирует адрес адаптера. С выхода дешифратора сигнал поступает на вход снятия готовности узла 14 формирования сигнала готовности, представляющего собой D-триггер, и на установочный вход узла 13, с первого выхода которого к внешней ЭВМ посылается сигнал о готовности сетевого процессора к приему макрокоманды, а с второго выхода на ключ 16 подается сигнал разрешения его включения. Кроме того, узел 13 формирования сигнала ответа, узел 14 формирования сигнала готовности и ключ 16 обеспечивают защиту всей мультимикропроцессорной системы от неисправностей отдельных сетевых процессоров, так как при сбойной работе последних они автоматически отключаются от управляющих шин ведущей ЭВМ за счет снятия готовности сбойным блоком 1 обработки.

При нормальном функционировании макрокоманда в последовательном коде от ведущей ЭВМ через ключ 16 поступает на последовательно-параллельный преобразователь 15, представляющий собой сдвиговый регистр, при заполнении которого на вход сброса узла 13 и на вход восстановления готовности узла 14 поступает сигнал, последний сообщает внешней ЭВМ о завершении приема макрокоманды, а блоку 1 обработки разрешает прием на выполнение с выходов последовательно-параллельного преобразователя 15 кода операции. Ведущая ЭВМ может загружать в сдвиговый регистр 19 или считывать из него в последовательном коде данные, являющиеся исходными или результирующими для процессора. Прием и выдача внешних данных осуществляется по строби- рующему сигналу от ведущей ЭВМ. Внутри же процессора регистр 19 имеет параллельный выход на общую шину и адресуется блоком 1 обработки как порт ввода/вывода.

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

Функционирование процессора может быть проиллюстрировано на примере работы со знаниями, организованными в виде пирамидальной семантической сети (ПС).

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

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

Все перечисленные выше особенности ПС определяются следующими правилами их построения.

Правило 1. Если при вводе описания нового объекта в сети появляются ассоциативные элементы А, имеющие в своем подмножестве возбужденные элеКоманды управляющей ЭВМ

Ввод описании первого объекта 1 (правило 1 не работает)

Вызвать свободные ячейки- Прием команды выхода и за- процессоры для рецепторов грузка в сдвиговый регистр и их номера записать в ввода/вывода признака за- таблицу имен рецепторов,, нятости из внутреннего ОЗУ.

Перевести рецепторы в соответствии с описанием объекта в возбужденное состояние путем загрузки в сдвиговый регистр ввода/вывода функции возбуждения.

72462

10

20

25

30

35

40

менты Bj (j 1), то связи, соедиА.

Л то

няющие

bi

ликвидируются и в

Ск (kЈl),

сеть вводятся новые элементы входы каждого из которых соединяются с выходами Bj, а выход - с одним из пассивных входов. Новые ассоциативные элементы находятся в возбужденном состоянии. После введения новых элементов во все участки сети, где выполняется условие правила 1, выполняется правило 2.

Правило 2. Если в сети имеется более одного возбужденного элемента (рецепторного или ассоциативного), не имеющего других возбужденных элементов в своем супермножестве, то к сети присоединяется новый ассоциативный элемент, вхдды которого соединяются с выходами возбужденных элементов. Новый ассоциативный элемент находится в возбужденном состоянии.

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

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

I

Работа сетевых процессоров

Прочитать информацию с регистра ввода/вывода и поместить ее в соответствующую область внутреннего ОЗУ, что соответствует возбуждению процессоров- рецепторов.

Применение правила 2

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

Возбудить процессор- объект.

Установить связи между возбужденными элементами.

Ввод описаний последующих объектов Применение правила 1

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

Распространить возбуждение по логическим связям

т возбужденных элементов, всем логически связанным с

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

Прием команды вызова и загрузка в сдвиговый регистр ввода/вывода признака занятости из внутреннего ОЗУ.

Прочитать информацию с регистра ввода/вывода и поместить ее в соответствующую область внутреннего ОЗУ, что соответствует возбуждению процессора-объекта.

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

Выполнить команды ведущей ЭВМ по определению и возбуждению рецепторных элементов.

Возбужденным процессорам-рецепторам выслать сообщения

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

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

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

Процессорам-объектам с частично возбужденными связями ( 1) выслать сообщения с командой на поиск свободных процессоров-ячеек и по получении от них ответов с адресами послать к ним сообщения со списками возбужденных связей и свой адрес. Этим новым процессорам по полученным спискам связей разослать сообщения с командой на гашение возбужденных элементо и с командой коррекции указателей связей на вновь образованные элементы. Новые элементы находятся в состоянии возбуждения.

0

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

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

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

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

1)обработка информации,

2)работа с ведущей ЭВМ,

3)обмен сообщениями с соседями. Обработка информации включает в

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

На фиг.4 дана схема алгоритма работы процессора с ведущей ЭВМ, на фиг.5,6 - алгоритмы обмена сообщениями с соседями, а также протокол обмена

Протокол обмена сообщениями:

а)готов принять сообщение,

б)входной буфер заполнен,

в)есть копия сообщения.

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

0

5

0

5

0

5

0

5

0

5

преобразователь в командном адаптере и сдвиговый регистр ввода/вывода.

Загрузка информации в последовательно-параллельный преобразователь происходит в старт-стопном режиме. Сдвиги тактируются импульсами с частотой, равной или кратной частоте синхронизации процессора (CCLK). Кроме командного адаптера CCLK поступает также в блок обработки и в линейные адаптеры. CCLK может вырабатываться как внутри процессора, так и подаваться извне.

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

Формула изобретения

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

Линия запроса прерывания Фиг. 2

Фиг.З

Фиг. It

Ре хин oipofo/лки

есть запрос от у №т ЗВМ /

Ш.

Обработка хлроса

Лриен команды I

onaffda

Bbino HtfWf команды I

Запрос снят

I Выбор канала

/Канал работоспособен рнастройки канала на передачу

Канал Jom08f y L.

Ло

Передача сообщения

i Реа8орка канала.

, .i

/имею/лея eu& CffoffutfМУД 7 /

нет конец

Hem

ды

Не/л

S

Нет

Мстя

Mff

L.

8рс/№ настроили. сл еклог/

Есть запросы 8 X е/77 каналах /

Выбор и яастройна каяа/ia /лг ярмем

Лрием информации

№м/ все запросы Ч Да

о с/1уже#б/

О

Фиг. 7

Ч

О