Процессор для обработки семантических сетей

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

РЦS G 06 Г 15/16, 15/18

ГОСУДАРСТВЕННЫЙ НОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ . Н ABTOPCHOMY СВИДЕТЕЛЬСТВУ

Фиг 1 (21) 4675441/24 (22) 11. 04. 89 (46) 23. 08 ° 91 ° Бюл. 9 31 (71) Институт кибернетики им. В.М. Глушкова (72) Е.И,Ершов и В.k.Áoãoëåïoâ (53) 681.32(088.8) (56) Хиллис У.Д. Коммутационная машина. В мире науки, 8, 1987, с. 6069.

The Transputer Fami1ó, Inmos Cor»

poration, Part 72, TR М 05601, 1987, р, 32. (54) ПРОЦЕССОР ДЛЯ ОБРАБОТКИ СЕМАНТИЧЕСКИХ СЕТЕЙ.. Ж 1672462 А1

2 (57) Изобретение относится к вычисI лительной технике и предназначено цля построения мультимикропроцессорных вычислительных систем распределенной обработки информации в системах искусственного интеллекта. Цель изобретения — расширение функциональных возможностей процессора за счет обеспечения формирования баз знаний °

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

1672462

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

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

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

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

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

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

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

21.

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

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

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

ЭВМ в ходе вычислений.

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

Команды управляющей ЭВМ Работа сетевых процессоров

Ввод описания первого объекта

1 (правило 1 не работает)

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

Прочитать информацию с регистра ввода/вывода и поместить ее н соответствующую область внутреннего

ОЗУ, что соответствует возбуждению процессороврецепторов.

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

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

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

Наукова думка, 1987).

Все перечисленные выше особенности

ПС определяются следующими правилами их построения, Правило 1. Если при вводе описания нового объекта в сети появляются ассоциативные элементы А, имеющие в

У своем подмножестве возбужденные эле72462

6 менты Б1 (j ) 1), то связи, соединяющиее Ь c А ли кв идируются H B у сеть ннодятся новые элементы С, (1c(1), входы каждого из которых соединяются с выходами В а выход — с одним из

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

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

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

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

1672462

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

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

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

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

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

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

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

Возбудить рецепторы.

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

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

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

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

Выполнить команды ведущей

ЭВИ по определению и возбуждению рецепторных элементов.

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

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

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

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

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

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

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

Выделить пересечение описаний объектов

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

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

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

25

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

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

Поэтому целесообразно алгоритм работы сетевого процессора рассмотреть в трех аспектах:

1) обработка информации, 2) работа с ведущей ЭВМ, 3) обмен сообщениями с соседями.

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

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

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

1. Проверить работоспособность канала.

2. Установить канал.

3. Передать служебное сообщение, определяющее основное.

4. Принять ответ;

40 а) готов принять сообщение, б) входной буфер заполнен, в) есть копия сообщения.

5. Передать основное сообщение в случае 4, а.

6. Ожидать или работать с другим каналом в случае 4, б.

7. Аннулировать сообщение в этом направлении в случае 4, в, 8. Получить подтверждение приема сообщения в случае 5.

9. Разобрать канал.

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

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

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

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

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

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

l672462

Harms преры8ания

Фаг. 2

1672462

Фиг. б

1672462

Составитель А Чеканов

Техред Л. Сердюкова Корректор М.Демчик

Редактор Г.Бельская

Заказ 2841 Тираж 393 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101