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

(ц)5 С 06 Г 15/16 ИСАНИЕ ИЗОБРЕТЕНИЯ я ма 60 в Со апврцег Рагс 72,рога 1;1 ор, 32.(54) ПРТИЧЕСКИХ ССОР ДЛЯ ОБРАБОТКИЕТЕЙ ЕИАНОСУДАРСТВЕННЫЙ НОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР Н АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(57) Изобретение относится к вычис лительной технике и предназначено цля построения мультимикропроцессорных вычислительных систем распределенной обработки информации в системах искусственного интеллекта. Цель изобретения - расширение функциональных возможностей процессора за счет обеспечения формирования баз знанийПроцессор содержит блок 1 обработки, блок 2 памяти, контроллер 3 внешней памяти, линейные адаптеры 4-, командный адаптер 8, информационный регистр 9, регистр 10 общих признаков, 7 ил.Изобретение относится к вычислительной технике и предназначено дляпостроения мультимикропроцессорнь 1 хвычислительных систем распределеннойобработки инФормации в системах искусственного интеллекта.Цель изобретения - расширениефункциональных возможностей эа счетобеспечения Формирования баз знаний.На фиг.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 адреса и сдвиговый регистр 19.Регистр 10 общих признаков содержит дешифратор 20 адреса и регистр21.Командный адаптер выполняет функ 35ции по приему по сигналам запроса отведущей ЭВМ макрокоманд управленияв последовательном коде, преобразованию их в параллельный внутренний кодопераций, выдаче этого кода на вьг 40полнение блоку обработки, а такжепо передаче внешней ЭВМ сигналовподтверждения для синхронизации работы блока 1 с другими сетевыми процессорами.45Сигналы запроса от ведущей ЭВМчерез повторитель 17 поступают к разрешающему входу узла 13 формированиясигнала ответа, который представляетсобой Э-триггер, а также на линиюнаивысшего приоритета запроса прерывания на общей шине. По этому запросу блок 1 прерывает свою работу и переходит на подпрограмму обработкипрерывания по поступившему запросу,Командный адаптер в поле адресов бло 55ка 1 должен занимать старшие разрядыадреса. При обращении к командномуадаптеру со стороны блока 1 дешифратор 12 дешифрирует адрес адаптера, С выхода дешифратора сигнал поступает на вход снятия готовности узла 14 формирования сигнала готовности, представляющего собой П-триггер, и на установочный вход узла 13, с первого выхода которого к внешней ЭВМ посылается сигнал о готовности сетевого процессора к приему макрокоманды, а с второго выхода на ключ 16 подается сигнал разрешения его включения. Кроме того, узел 13 формирования сигнала ответа, узел 14 формирования сигнала готовности н ключ 16 обеспечивают защиту всей мультимикропроцессорной системы от неисправностей отдельных сетевых процессоров, так как при сбойной работе последних они автоматически отключаются от управляющих шин ведущей ЭВМ за счет снятия готовности сбойным блоком 1 обработки.При нормальном функционировании макрокоманда в последовательном коде от ведущей ЭВМ через ключ 16 поступает на последовательно-параллельный преобразователь 15, представляющий собой сдвиговый регистр, при заполнении которого на вход сброса узла 13 и на вход восстановления готовности узла 14 поступает сигнал, последний сообщает внешней ЭВМ о завершении приема макрокоманды, а блоку 1 обработки разрешает прием на выполнение с выходов последовательно-параллельного преобразователя 15 кода операции. Ведущая ЭВМ может загружать в сдвиговый регистр 19 или считывать иэ него в последовательном коде данные, являющиеся исходными или результирующими для процессора, Прием и выдача внешних данных осуществляется по стробирующему сигналу от ведущей ЭВМ, Внутри же процессора регистр 19 имеет параллельный выход на общую шину и адресуется блоком 1 обработки как порт ввода/вывода.В регистр 21 блок обработки может независимо записывать два бита внутреннего состояния процессора, С выхода регистра 21 эти биты поступают на линии признаков мультимикропроцессорной системы и анализируются ведущей ЭВМ в ходе вычислений.функционирование процессора может быть проиллюстрировано на примере работы со знаниями, организованными в виде пирамидальной семантической сети (ПС).16 Команды управляющей ЭВМ Работа сетевых процессоров Ввод описания первого объекта(правило 1 не работает)Вызвать свободные ячейки- Прием команды выхода и запроцессоры для рецепторов грузка н сдвиговый регистр и их номера записать в ввода/вывода признака затаблицу имен рецепторов. нятости из внутреннего ОЗУ. Прочитать информацию с регистра ввода/вывода и поместить ее в соответствующую область внутреннегоОЗУ, что соответствуетвозбуждению процессороврецепторов. Перевести рецепторы в соответствии с описаниемобъекта в возбужденноесостояние путем загрузкив сдвИговый регистр ввода/вывода функции возбуждения. Пирамидальной сетью называетсяориентированный граф, н котором нетнершин со степенью захода 1. Вершиныэтого графа называются элементами, адуги - связями. Элементы со степеньюзахода ) 1 называются ассоциативнымиэлементами, Элементы со степенью захода, равной О, называются рецептор-.ными элементами. Входы ассоциативныхэлементов называются активными, еслиони связаны с выходами других ассоциативных или рецепторных элементов,и пассивными - в противном случаеПС обеспечивают экономное, иерархическое и ассоциативное хранениезнаний о задачах и средах. При построении ПС автоматически устанавливаются связи между объектами путемвыделения пересечений описаний объек,тов и ввода в сеть элементов, соответствующих этим пересечениям. На ПСопределены процессы формирования понятий, в основе которых лежат методыиндуктивного обучения. ПС удобны длявыполнения операций ассоциативногопоиска, а также таких процедур семантического анализа,как выделение информации, относящейся к конкретнойзадаче, распознавания применимостимоделей действий к моделям ситуаций,преобразование модели одной ситуациив модель другой ситуации и др. (Гладун В.П. Планирование решений, Киев:Наукова думка, 1987).Все перечисленные выше особенностиПС определяются следующими правиламиих построения,Правило 1. Если при вводе описаниянового объекта в сети появляются ассоциативные элементы А , имеющие вУсвоем подмножестве возбужденные эле 724626меты Б 1) 1), то связи, соединяющие Ь с А ликвидируются и несеть ннодятся новые элементы С, Ь(1),входы каждого из которых соединяютсяс выходами В а выход - с одним изУпассивных входов. Новые ассоциативные Элементы находятся в возбужденном состоянии. После введения новых элементов во все участки сети, гденыполняется условие правила 1, выполняется правило 2.Правило 2. Если в сети имеетсяболее одного возбужденного элемента(рецепторного или ассоциативного), 15не имеющего других возбужденных элементов в своем супермножестве, то ксети присоединяется ноный ассоциативный элемент, входы которого соеди О няются с выходами возбужденных элементов. Новый ассоциативный элементнаходится в возбужденном состоянии.Другими словами, в процессе выполнения правила 1 производится пе рестройка структуры сети путем изменения связей между элементами и вводавершинных элементов пирамид, соответствующих пересечениям множеств,а в процессе выполнения правила 2сеть достраивается путем объединенияв пирамиду объекта возбужденныхэлементов. Функционирование процессоров в составе мультипроцессорной однородной вычислительной системы при построении ПС н соответствии с приведенными правилами происходит следующим образом, Причем считается, что каждый процессор представляет собой один элемент сети (рецепторный или ассоциативный) со всеми его связями,1672462 Применение правила 2 Ввод описаний последующих объектов Применение правила 1 Вызвать через сдвиговыйрегистр ввода/выводасвободный процессор подописание нового объекта и занести его номерв таблицу имен элементов. Возбудить процессоробъект. Уст апов ить с в я з и междувозбужд нныки элементами. Пополнить таблицу именрецепторов для новогоописания объекта, выполнив процедуру поискасвободных ячеек-процессоров под рецепторы.Возбудить рецепторы. Распространить возбуждение по логическим связямот возбужденных эементовПрием команды вызова и загрузка в сдвиговый регистрввода/вывода признака занятости иэ внутреннего ОЗУ. Прочитать информацию с регистра ввода/вывода и поместить ее в соответствуюшую область внутреннего ОЗУ,что соответствует возбуждению процессора-объекта,Возбужденному процессоруобъекту выслать по каналамсвязи сообщения с командойна установление с ним логических связей другим возбужденным элементам сети,которые по получении сообщений создают в своих РЗУ "короткие" списки связей спроцессором-объектом, высылают ему свои физическиеадреса и гасят собственноевозбуждение. По полученииответных сообщений процессоробъек г в ОЗУ создает спискисвязей с элементами своего подмножества, оставаясь приэтом возбужденным. Выполнить команды ведущейЭВИ по определению и возбуждению рецепторных элементов,Воз бужденным процессорам-рецепторам выслать сообщениявсем логически связанным сними элементам сети.Каждому процессору"объектупо получении сообщенийпроанализировать условиясвоей возбудимости, при выполнении которых обратнымисообщениями с командой погасить возбужденные элементы в своих подмножествах,10 1672462 после чего выслать сообщения о возбуждении по всемвыходным логическим связямили, если их нет, остатьсяз возбужденном Состоянии.Частично возбужденнымпроцессорам-объектам в поле меток входных связей зафиксировать, что эти связиидут от возбужденных элементов. Процессорам-объектам с частично возбужденными связями( 1) выслать сообщения с командой на поиск свободных процессоров-ячеек и по получении от них ответов с адресами послать к ним сообщениясо списками возбужденных связей и свой адрес.Этим новым процессорам по полученным спискам связей разослать сообщения с командой нагашение возбужденных элементови с командой коррекции указателей связей на вновь образованные элементы. Новые элементы находятся в состояниивозбуждения,Как видно из рассмотренного примера, процессоры при работе с семантическими сетями сильно взаимодействуют как друг с другом, так и с ведущей ЭВМ, получая и выполняя коман 50 ды и обмениваясь данными в параллельном режиме. Гибкость управления вычислительным процессом достигается за счет получения процессора через командные адаптеры макрокоманд от управляющей ЭВМ и дальнейшей автономной работы сети процессоров. Причем ход вычислений зависит от данных, загружаемых через сдвиговый регистр ввоПроанализировать условиеокончания выполнения предыдущей команды путемопроса регистра общихпризнаков сети.Выделить пересечениеописаний объектов Проанализировать условиеокончания выполненияпредыдущей команды путемопроса регистра общихпризнаков сети.Перейти к выполнению правила 2. да/вывода. Об окончании выполнениямакрокоманды или о невозможности завершения вычислений сигнализируетинформация на выходе регистра общихпризнаков,В известных устройствах (например, в транспьютерах) такое взаимодействие может быть организовано либоэа счет выделения отдельного канала,что существенно снижает коммуникационные возможности сети, либо засчет организации обмена через общееполе памяти. В последнем случае неизбежна потеря производительности, 1672462 1225 50 так как потребуется постоянный опроспамяти с целью определения моментовпоступления управляющей информацииили данных для обработки. Синхроннаяже обработка массивов данных в такойсети становится проблематичной.Работа процессора заключается ввыполнении программ, хранящихся вовнешнем запоминающем устройстве (накаждый сетевой процессор отводитсясвое ЗУ), в обработке запросов прерывания от ведущей ЭВМ или в функционировании под ее упранлением, а также в обмане сообщениями с близлежащими соседями через линейные адаптеры.Поэтому целесообразно алгоритм работысетевого процессора рассмотреть втрех аспектах:1) обработка информации,2) работа с ведущей ЭВМ,3) обмен сообщениями с соседями.Обработка информации включает всебя интерпретацию полученных сообщений и коканд волнового языка, атакже организацию собственно вычислительного процесса, Словесное описание одного иэ алгоритмов работысо знаниями приведено выше.На фиг.4 дана схема алгоритма работы процессора с ведущей ЭВМ, нафиг,5,6 - алгоритмы обмена сообщениями с соседями, а также протоколобмена.Протокол обмена сообщениями:1. Проверить работоспособность канала.352, установить канал,3. Передать служебное сообщение, определяющее основное.4. Принять ответ;40а) готов принять сообщение,б) входной буфер заполнен,в) есть копия сообщения.5. Передать основное сообщение в случае 4, а.456. Ожидать или работать с другим каналом в случае 4, б,7. Аннулировать сообщение в этом направлении в случае 4, в,8. Получить подтверждение приема сообщения в случае 5.9. Разобрать канал.С целью уменьшения числа внешнихвыводов в процессоре обмен информацией с ведущей ЭВМ осуществляется впоследовательном коде. Средстнамипреобразования последовательностейбитов во внутренний параллельный кодслужат последовательно-параллельный преобразователь в командном адаптере и сдвиговый регистр ввода/вывода,Загрузка информации в последовательно-параллельный преобразователь происходит в старт-стопном режиме. Сдвиги тактируются импульсами с частотой, равной или кратной частоте синхронизации процессора (СС 1 К). Кроме командного адаптера СС 1,К поступает также в блок обработки и в линейные адаптеры, СС 1 К может вырабатываться как внутри процессора, так и подаваться извне.При работе сетевого процессора в составе мультипроцессорных вычислительных систем, состоящих из десятков тысяч процессоров,в виду значительных искажений и задержек при передаче сообщений на высоких скоростях (свьппе 1 О Мбит/с) вместо старт-стопной синхронизации более предпочтительным может оказаться применение самосинхронизирующихся кодов.Фо рмула изо бре тенияПроцессор для обработки семантических сетей, содержащий блок обработки, контроллер ннешней памяти, блок памяти и группу линейных адаптерон, системные входы и выходы которых объединены через общую шину, причем входы и выходы внешнего устройства контроллера внешней памяти соединены с входами и выходами первой группы процессора, входы и выходы внешних устройств линейных адаптеров группы соединены с входами и выходами второй группы процессора, о т л и - ч а ю щ и й с я тем, что, с целью расширения функциональных возможностей за счет обеспечения формирования баз знаний, в него введены командный адаптер, информационный регистр и регистр общих признаков, причем их системные входы и выходы введенных блоков объединены между собой через общую шину и подключены к системным входам и выходам блока обработки, блока памяти, контроллера внешней памяти и группы линейных адаптеров, входы и выходы внешних устройств командного адаптера, информационного регистра и регистра общих признаков соединены с входами и ныходами соответственно третьей, четвертой и пятой групп процессора.1672462 Составитель АЧекановТехред Л.Сердюкова Корректор М.Демчик Редактор Г.Бельская Заказ 2841 Тираж 393 ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва, Ж, Раушская наб., д. 4/5 Производственно-издательский комбинат "Патент", г, Ужгород, ул. Гагарина, 101