Ассоциативная однородная вычислительная система

Ассоциативная однородная вычислительная система

Иллюстрации

Показать все

Реферат

 

Ассоциативная однородная вычислительная система относится к области вычислительной техники и может быть использована для решения задачи дедуктивного логического вывода в исчислении предикатов. Цель изобретения - повышение быстродействия . В системе осуществляется унификация термов одноименных и (или) контрарных предикатов и получение результата данной процедуры как в случае унифицируемости , так и не унифицируемости термов. Поставленная цель достигается тем, что ассоциативная однородная вычислительная система содержит матрицу РхК блоков обработки, блок управления и группу блоков управления. 3 ил.

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

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

РЕСПУБЛИК (я)5 G 06 F 15/16

ГО

УДАРСТВЕННОЕ ПАТЕНТНОЕ

ОМСТВО СССР

СПАТЕНТ СССР) ПИСАНИЕ ИЗОБРЕТЕНИЯ

АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

1 (21 5007494/24 (2 01.07.91 (4 30.08.93. Бюл. М 32 (7 В,П, Прохоров, В,П, Кириллов, Г,П, Нико анко, Б.Б; Борисов и А.Г. Курчин (5 Авторское свидетельство СССР

N 18738, кл, G 06 F 15/16, .1978, Евреинов Е. В „Хорош евский В.Г. Одноро ные вычислительные системы, Новосиби ск: Наука, 1978, с. 111, рис, 4, 6. (5 АССОЦИАТИВНАЯ ОДНОРОДНАЯ ВЫ Ч СЛИТЕЛЬНАЯ СИСТЕМА (5 Ассоциативная однородная вычислите ьная система относится к области вычисПредлагаемое изобретение относится к об асти вычислительной техники и может бы ь использовано при построении специали ированных систем, предназначенных дл решения задач дедуктивного логического ывода в исчислении предикатов.

Целью предлагаемого изобретения явля тся повышение быстродействия.

Поставленная цель достигается тем, что в а социативную однородную вычислительн систему, содержащую матрицу размер РхК блоков обработки (где P — число а ментов унифицируемых предикатов, К— ч о предикатов) введены группа P блоков у авления, центральный блок управления, и чем, первый, второй, третий и четвертый в ды кода операции, выходы признака гот ности и признака наличия информации, и ормационные входы и информационные в оды блока обработки а-го столбца в-й с ки матрицы (где а=1,..., К; в=1,..., P) подк чены соответственно к (4(а-1)+1)-му вы Ы 1837310 Al лительной техники и может быть использована для решения задачи дедуктивного логического вывода в исчислении предикатов.

Цель изобретения — повышение быстродействия. В системе осуществляется унификация термов одноименных и (или) контрарных пр дикатов и получение результата данной процедуры как в случае унифицируемости, так и не унифицируемости термов. Поставленная цель достигается тем, что ассоциативная однородная вычислительная система содержит матрицу РхК блоков обработки, блок управления и группу блоков управления. 3 ил. ходу, к (4(а-1)+2)-му выходу, к (4(а-1)+3}-му выходу, к (4(а-1)+4)-му выходу, а-му и (k+a).ìó входам режима, к выходам первой группы и ко входам режима первой группы в-го блока управления группы, выходы второй группы, входы режима второй группы, (4К+1)-й выход и (4К+2)-й выход которого подключены соответственно к входам режима первой группы, к выходам первой группы, к в-му и (Р+в)-му входам режима центрального блока управления, входы режима второй группы и выходы второй группы которого являются соответственно входами кода операции и информационными выходами системы, причем, центральный блок управления содержит узел микропрограммного управления, узел памяти, узел коммутации, регистр, группу элементов И и формирователь одиночного импульса, причем, входы режима первой группы и выходы первой группы узла микропрограммного управления являются соответственно входами режима первой

1837310 группы и выходами первой группы центрального блока управления, входы режима

à îðoÀ группы и выходы второй группы узла микропрограммного управления являются соответственно входами режима второй 5 группы и выходами второй группы центрального блока управления, выходы третьей и четвертой группы, первый выход и входы режима третьей группы узла микроп рограммного управления подключены cooTBBTGTвенно к информационным входам, к адресным входам,.ко входу записи решения и.выходам узла памяти, выходы пятой группы и входы режима четвертой группы узла микропрограммного управления подключены соответственно к первым входам элементов И группы и к выходам элементов И группы, вторые входы которых подключены соответственно к выходам регистра, информационные входы которого являются соот- 20 ветственно входами режима с (P+1)-го по

2Р-й центрального блока управления, входы режима с первого по P-й которого подключены соответственно к информационным входам узла коммутации, выход которого подключен ко входу режима узла микропрограммного управления и ко входу запуска формирователя одиночного импульса, выход которого подключен к входу записи/чтения регистра, второй выход узла мик-. 30 ропрограммного управления подключен к управляющему входу узла коммутации, причем, каждый блок управления из группы блоков управления содержит узел управления, узел памяти, два регистра, счетчик, 35 узел коммутации и элемент И. причем, в каждом блоке управления группы входы режима первой группы и выходы первой группы узла управления являются входами режима первой группы и выходами первой 40 группы блока управления группы, входы режима с первого по К-й которого подключены соответственно к информационным входам узла коммутации, выход которого подключен к первому входу режима узла управле- "5 ния, к первому входу элемента И и является (4К+1)-м выходом блока управления группы, (4К+2)-м выходом которого является выход элемента И, выход режима узла управления подключен ко второму входу элемента И, б0 первый выход узла управления подключен к управляющему входу узла коммутации, выходы второй группы и входы режима второй группы узла управления являются соответственно выходами второй группы и входами 55 режима второй группы блока управления группы, входы режима с (К+1)-ro по 2К-й которого подключены соответственно ко входам режима со второго по (К+1)-й узла управления, выходы со второго по (4К+1)-й которого являются соответственно выходами с первого по 4К-й блока управления группы, информационные входы, адресные входы, вход записи решения и выходы узла памяти подключены соответственно к выходам третьей группы, выходам четвертой группы, (4К+2)-му выходу и ко входам режима третьей группы узла управления, выходы пятой группы, (4К+3)-й выход и входы режима четвертой группы которого подключены соответственно к информационным входам, ко входу записи/чтения и к выходам первого регистра, выходы шестой группы, (4K+4)-й, (4К+5)-й, (4К+6)-й выходы и входы режима пятой группы узла управления подключены соответственно к информационным входам, к счетному входу, к вычитающему входу, ко входу записи и к информационным выходам счетчика, выходы седьмой группы, (4К+7)-й выход и входы режима шестой группы узла управления подключены соответственно к информационным входам, ко входу записи/чтения и к выходам второго регистра, причем, каждый блок обработки содержит узел ассоциативной памяти, триггер, два элемента И, элемент ИЛИ и группу элементов И, причем, в каждом блоке обработки выходы группы узла ассоциативной памяти являются информационными выходами блока обработки, информационные входы узла ассоциативной памяти подключены к выходам элементов И группы, выход узла ассоциативной памяти является выходом признака готовности блока обработки и подключен к первому входу первого элемента И, второй вход которого является первым входом кода операции блока обработки, выход первого элемента И подключен ко входу установки в единицу триггера, входустановки в ноль которого является вторым входом кода операции блока обработки, прямой выход триггера является выходом признака наличия информации блока обработки и подклюявн к первому входу второго элемента И, второй вход которого является третьим входом кода операции блока обработки, выход второго элемента И подключен к первому входу элемента ИЛИ, второй вход элемента ИЛИ является четвертым входом кода операции блока обработки, выход элемента ИЛИ подключен к первым входам элементов И группы, вторые входы которых являются соответственно информационными входами блока обработки.

На фиг. 1, 2 представлена структурная схема ассоциативной однородной вычислительной системы; на фиг. 3 — структурная схема блока обработки ассоциативной однородной вычислительной системы, 1837310

Ассоциативная однородная вычислительная система (фиг. 1, 2) содержит матрицу размером РхК (где P — число аргументов у ифицируемых предикатов, К вЂ” число и ред катов) блоков обработки 1(11), 5

1(1),...,1(К1),...,1(1Р),...,1(КР), каждый из кото ых имеет, соответственно, первый 2, втор и 3, третий 4 и четвертый 5 входы кода о ерации, выходы признака готовности 6 и и изнака наличия информации 7, информа- 10 ц онные входы 8 и информационные выходы 9, группу P блоков управления

1 1),...,10(Р) и центральный блок управлен я11.

При этом, центральный блок управле- 15 н я содержит узел микропрограммного упр вления 12, узел памяти 13, узел ко мутации 14, регистр 15, группу элементо И 16 и формирователь одиночного импу ьса 17, каждый блок управления из 20 гр ппы блоков управления содержит узел уп авления 18, узел памяти 19, первый и вт рой регистры 20, 21, счетчик 22, узел ко мутации 23 и элемент И 24, причем, центр льный блок управления имеет входы ре- 25 ж ма первой группы 25, выходы первой гр ппы 26, первые P входов режима

27 1),...,27(Р) и вторые P входов режима

28 1),...,28(Р), входы режима второй группы

29 и выходы второй группы 30, каждый блок 30 уп авления имеет первые 4К выходов, соотве ственно, 31(a), 32(а), 33(а), 34(а) (где

a=I,...,Ê), первые К входов режима 35(1)„...

35 К), вторые К входов режима 26(1),....36(K}, (4 +1)-й и (4K+2)-й выходы 37, 38, соответст- 35 ве но, выходы первой группы 39, входы реж ма первой группы 40, выходы второй гр ппы 41, входы режима второй группы 42.

Каждый блок обработки ассоциативной од ородной вычислительной системы (фиг, 40

3) одержит узел ассоциативной памяти 43, тр ггер 44, два элемента И 45, 46, элемент .И И 47 и группу элементов И 48.

При этом, элементы, узлы и блоки ассоци тивной однородной вычислительной си- 45 ст мы соединены следующим образом, Входы кода операции 2 — 5, выходы и ризн ка готовности и признака наличия инфо мации 6, 7, информационные входы и ин ормационные выходы 8, 9 блока абра- 50 бо ки а-го столбца в-й строки матрицы 1(ав) (гд а=1,...,К; в=1,...,P) (фиг. 1, 2) подключены со тветственно к выходам 31(а), 32(а), 33(а), 34(), входам режима 35(а), 36(а), выходам пе вой группы 39 и входам режима первой 55 гр ппы 40 в-ro блока управления 10(в) группы 10, выходы второй группы 41, входы режи а второй группы 42, выходы 37, 38 ко орого подключены соответственно к входаь режима первой группы 25, к выходам первой группы 26, к входам режима 27(в), 28(в) центрального блока управления 11, входы режима второй группы 29 и выходы второй группы 30 которого являются соответственно входами кода операции и информационными выходами системы.

Входы режима первой группи и выходы первой группы узла микропрограммного управления 12 являются соответственно входами режима первой группы 25 и выходами первой группы 26 центрального блока управления 11, входы режима второй группы и выходы второй группы узла микропрограммного управления 11 являются соответственно входами режима второй группы 29 и выходами второй группы 30 центрального блока управления 11, выходы третьей и четвертой группы, первый выход и входы режима третьей группы узла микропрограммного управления 12 подключены соответственно к информационным входам, кадресным входам, ко входу записи решения к выходам узла памяти 13, выходы пятой группы и входы режима четвертой группы узла микропрограммного управления 12 подключены соответственно к первым входам элементов

И группы 16 и к выходам элементов И группы 16, вторые входы которых подключены соответственно к выходам регистра 15, информационные входы которого являются соответственно (Р+1)-м„,2Р-м входами режима 28(1)„„,28(Р) центрального блока управления 11, 1-й„...Р-й входы режима

27(1),...,27(Р) которого подключены соответственно к информационным входам узла коммутации 14, выход которого подключен ко входу режима узла микропрограммного управления и ко входу запуска формирователя одиночного импульса 17, выход которого подключен к входу записи/чтения регистра 15, второй выход узла микроп рограммного управления подключен к управляющему входу узла коммутации 14.

Входы режима первой группы и выходы первой группы узла управления 18 каждого блока обработки группы 10 являются входами режима первой группы 40 и выходами первой группы 39 блока управления группы

10, 1-й,...,К-й входы режима 35(1),.„,35(К) которого подключены соответственно к информационным входам узла коммутации 23, выход которого подключен к первому входу режима узла управления 18, к первому входу элемента И 24 и является (4К+1)-м выходом 37 блока управления группы 10, (4К+2)-м выходом 38 которого является выход элемента И 24, выход режима узла управления

18 подключен ко второму входу элемента И

24, первый выход узла управления 18 подключен к управляющему входу узла комму1837310 тации 23, выходы второй группы и входы режима второй группы узла управления 18 являются соответственно выходами второй группы 41 и входами режима второй группы

42 блока управления группы 10, (К+1)-й, „„

2К-й. входы режима 36(1)„...36(К) которого подключены соответственно ко входам режима со второго по (K+1)-й узла управления, выходы со второго по (4К+1)-й которого являются соответственно T-м,...,4К-м выходами 31(а), 32(а), 33(а), 34(а) (где а=1, ..., К) блока управления группы 10, информационные входы, адресные входы, вход записи решения и выходы узла памяти 19 подключены соответственно к выходам третьей группы, выходам четвертой группы, (4К+2)-му выходу и ко входам режима третьей группы узла управления 18, выходы пятой группы, (4K+3)-й выход и входы режима четвертой группы которого подключены соответственно к информационным входам, ко входу записи/чтения и к выходам первого регистра

20, выходы шестой группы, (4К+4)-й, (4К+5)й, (4К+6)-й выходы и входы режима пятой группы узла управления 18 подключены соответственно к информационным входам, к счетному входу, к вычитающему входу, ко входу записи и к информационным выходам счетчика 22, выходы седьмой группы, (4К+7)й выход и входы режима шестой группы узла управления 18 подключены соответственно к информационным входам, ко входу записи/чтения и к выходам второго регистра 21.

Выходы группы узла ассоциативной па. мяти 43 блока обработки 1(ав) (где а=1,.„,К, в=1, ..., P) (фиг. 3) являются информационными выходами 9 блока обработки, информационные входы узла ассоциативной памяти

43 подключены к выходам элементов И группы 48, выход узла ассоциативной памяти 43 является выходом признака готовности 6 блока обработки и подключен к первому входу первого элемента И 45, второй вход которого является первым входом кода операции 2 блока обработки, выход первого элемента И 45 подключен ко входу установ ки в единицу триггера 44, вход установки в ноль которого является вторым входом кода операции 3 блока обработки, прямой выход триггера 44 является выходом признака наличия информации 7 блока обработки и подключен к первому входу второго элемента И

46, второй вход которого является третьим входом кода операции 4 блока обработки, выход второго элемента И 46 подключен к первому входу элемента ИЛИ 47, второй вход элемента ИЛИ 47 являетвя четвертым входом кода операции 5 блока обработки, выход элемента ИЛИ 47 подключен к первым входам элементов И группы 48, вторые

10

35

40 висит от исходных данных (термов), но не может превышать количества разноименН blX ПЕРЕМЕН Н ЫХ.

55 входы которых являются соответственноинформационными входами 8 блока обработки.

Работа ассоциативной однородной вычислительной системы состоит в следующем.

Подлежащие унификации термы предикатов последовательно посимвольно, начиная с первого терма первого предиката, вводятся пользователем через входы кода операции 29 в центральный блок управления 11 (фиг, 2), откуда под управлением узла микропрограммного управления 12 поступают в блоки управления группы 10 с выходов группы 26 где записываются в узлы памяти 19. При этом, в узле управления 18 определяется максимальное значение уровня вхождения символа в аргумент предикатов для термов строки, которое записывается в отдельную ячейку узла памяти 19. Далее, под управлением блоков управления группы 10 термы предикатов заnNcblBBIoTcsI в узлы ассоциативной памяти

43 блоков обработки (фиг. 3). Перед записью предикаты должны иметь одинаковое количество аргументов, количество предикатов должно совпадать с К, что достигается добавлением предикатов, тождественных какому-либо из предикатов. Таким образом, в узле памяти 19 в-го блока управления 10(в) (где e-=1Ä,Р-1) хранятся все символы аргументов, находящихся на в-ом месте каждого предиката, а в узле ассоциативной памяти

43 блока обработки а-го столбца в-й строки

1(ав) (где а=1,...,К) хранятся символы, относящиеся к одному аргументу, расположенному на в-м месте а-го предиката.

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

1 (aP) (где а=1,..., К) под управлением блока управления 10(Р). При этом, центральный блок управления 11 осуществляет синхронизацию работы блоков управления 10(в) путем циклического последовательного опроса блоков управления 10(в) по выходам группы 26 с целью получения от них со входов режима 25 сигнала об окончании проверки тождественности термов в в-й строке.

1837310

Проверка тождественности предикатов в троках матрицы выполняется следующим о разом. Узлы управления 18 всех блоков управления 10(в) пересылают из узлов памяти 19 максимальное значение уровня вхож- 5 д ния в счетчик 22 для организации ц клического выполнения в пределах своей в- строки следующей последовательности д йствий.

Выбор иэ блока обработки символа с 10 за: анным уровнем вхождения. Производится поиск данных в блоках обработки в-й ст оки по ассоциативному признаку — урове ь вхождения, взятого из счетчика 22 (фиг.

2) передача слова, удовлетворяющего дан- 15 н у признаку в регистр 20. При этом, в на але поиска осуществляется обнуление тр ггеров 44 путем одновременной подачи бл ком управления 10(e) сигналов на входы

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

rp ппы 26 пересылает его на входы режима гр ппы 42 блоков управления группы 10 и, да ее, в узлы управления 18, Во втором слу- 30 ча код опроса формирует узел управления

18 Узел управления 18 с выходов 34(а) пасы ает на входы кода операции 5 блоков об аботки данной строки сигналы разрешени приема, а на информационные входы 8 35 ко опроса.

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

2 оков обработки (фиг. 1). После выполнени операции ассоциативного поиска на выхо ах признака готовности 6 тех бгоков об аботки, где имеются искомые данные, 45 бу ет сформирован сигнал ответа, который пе еведет в единичное состояние триггер

44 фиг. 3), а также поступи через выход 6 бл ка обработки а-го столбца в-й строки

1(а ) на вход режима 35(а) блока управления 50

10() и там на вход узла коммутации 23 (фиг.

2)., I

В процессе поиска на управляющий вход узла коммутации 23 поступит сигнал., 55 со ветствующий операции ИЛИ. Результат зт операции поступит в узел управления

18 Если результат операции равен единице это будет указывать на наличие данных в и еделах строки.

Если поиск производится по всей матрице, то узел управления 18 (фиг, 2) подает разрешающий сигнал на второй вход элемента И 24. Узел микропрограммного управления 12 (фиг. 2), посылает на управляющий вход узла коммутации 14 сигнал, соответствующий операции ИЛИ. При этом, сигналы, с выходов 38 блоков управления 10(в) поступают на входы режима 28(в} и, далее, на информационные входы регистра 15, а также с выходов 37 блоков управления 10(в) на информационные входы узла коммутации

14 центрального блока управления 11, где над ними выполняется операция ИЛИ. Если результат равен единице, что, означает в пределах матрицы имеются искомые данные, то данный сигнал запускает формирователь одиночного импульса 17, который вырабатывает сигнал разрешения записи информации с входов 28(в) в регистр 15, При этом, установление в-го разряда регистра

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

И группы 16.

Номер блока обработки в пределах в-й строки определяет узел управления 18 на основе анализа сигналов = выходов признака наличия информации 7, которые поступают на входы режима 36(а) блок- управления

10(в) и указывают на единичное состояние триггера 44 (фиг. 3), При атом, триггер 44 устанавливаешься в единичное состочние под воздействием сигналов, одновременно поступающих на входы кода операции 2 Gnoков обработки ",(ав) с выходов 31(а) блоков управления .О(в) только при наличии сигнала ответа с выхода узла ассоциативной памяти 43. Выбор данных из такого а-го блока обработки осуществляется подачей на вход кода операции 5 сигнала с выхода 34(а) блоKG управления 10(в) (фиг. 2), по которому код опроса проходит на информационные входы группы узла ассоциативной памяти 43 только а-ro блока обработки 1(ав), следовательно, на информационных выходах 9 появятся данные только этого блока обработки, которые и примет блок управления 10(в), Выявление наличия данных одновременно во всех блоках обработки строки или матрицы, удовлетворяющих заданному ассоциативному признаку, выполняется ана12

1837310

50 логично, описанным выше действиям с той лишь разницей, что узлы 12, 18 вырабатывают управляющие сигналы, соответствующие выполнению в узлах коммутации 14,23 операции И, Производится опрос блоков обработки в-й строки по коду опроса, равному содержимому регистра 20, с целью поиска одинаковых символов, Узел коммутации 23 выполняет операцию И. Результат поступает на первый вход режима узла управления

18 и с выхода 37 на вход 27(в) центрального блока управления 11 в узел коммутации 14, Производится анализ результата конъюнкции узлом управления 18. Если он равен нулю, то в пределах данной строки термы не унифицируемы. B этом случае узел управления 18 удерживает на выходах группы 39 код опроса, на выходах 34(а) (где а=1„...К) разрешающий сигнал и на первом выходе сигнал операции И узла коммутации 23 до .тех пор, пока центральный блок управления

11 не закончит проверку на тождественность предикатов. При этом, узел управления 18 готовит сигнал ответа об окончании проверки и при обращении к нему центрального блока управления 11 выдает его с выходов .груп п ы 41. Если результат конъюнкции равен единице, то выполняется следующее. Узел управления 18 уменьшает содержимое счетчика 22 на единицу и проверяет его содержимое. Если оно равно нулю, то, так же как при анализе результатов опроса блоков обработки, узел управления

18 удерживает на вышеперечисленных выходах сигналы и формирует сигнал об окончании проверки на тождественность термов в данной строке. Если содержимое счетчика

22 не равно нулю, то узел управления 18 выбирает из блока обработки символ с заданным уровнем вхождения, Как только все блоки управления 10(s) (где в=1,...,P-1) закончат свои проверки, узел микропрограммного управления 12 (фиг. 2) закончит проверку на тождественность всего мно>кества предикатов путем подачи со второго выхода управляющего сигнала операции И для узла коммутации 14, единичный результат которой означает, что унифицируемые предикаты тождественны, о чем на информационные выходы 30 системы выдается сигнал и производится последовательная выдача пользователю термов всех предикатов начиная с первой строки первого блока обработки и заканчивая (P-1)-строкой, На этом работа системы заканчивается. В случае нулевого результата операции И осуществляется проверка наличия переменных в множестве термов одновременно во всех строках матрицы под управлением центрального блока управления 11.

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

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

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

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

11, находящиеся в единичном состоянии, будут указывать строки, в которых присутствуют переменные. Узел микропрограммного управления 12 поочередно опрашивает разряды регистра 15 и если встречается единица, выдает сигнал на поиск данных в соответствующий блок управления 10(в) на входы группы 42. На этом начинается цикл анализа очередной переменной. По этому сигналу узел управления 18 (фиг. 2) производит поочередный опрос входов 36(а) (где а=1„.,К). Наличие сигнала на входе 36(с) (где с=1„.„К) указывает на присутствие переменной в с-ом блоке обработке 1(св), так как его триггер 44 операцией поиска переменных был переведен в единичное состояние. Узел управления 18 опрашивает блок обработки

1(св) по коду опроса, соответствующего ассоциативному признаку переменной, вызывает зту переменную на регистр 20, а затем обнуляет триггер 44 (фиг. 3) путем подачи сигнала на вход 3 блока обработки 1(св)(фиг.

3), Далее, для поиска перекрестных связей узел управления 18 пересылает содержимое регистра 20, в котором хранится переменная (символ аргумента) с выходов группы 41 на входы режима группы 25 в узел микропрограммного управления 12, который с выходов группы 26 (фиг. 2) пересылает код этой переменной в узлы управления 18 всех блоков управления.10(в) и, далее, на регистры

20 этих блоков. Узлы управления 18 производят опрос всех блоков обработки по коду опроса — содержимое регистра 20, при этом, выдают на второй вход элемента И 24 разрешающий сигнал. Узлы коммутации 23, 14 реализуют операцию ИЛИ. Если ее результат равен единице, это указывает на наличие перекрестной связи, при этом, номера разрядов регистра 15, установленные в еди13

1837310

55 ни ное состояние будут указывать мно>кество строк, связанных одной переменной (переменной, имя которой содержится в узлах ас оциативной памяти 43 блоков обработки эт х строк). В этом случае узел микропрогра много управления 12 прекращает перебо переменных и с выходов группы 26 вы ает команду о начале определения типа по становок и их выполнение для связываю ей переменной в блоки управления, для ко орых разряды регистра 15 установлены в ед ничное состояние. При нулевом значени дизьюнкции узел управления 18 строки, из оторой была извлечена предыдущая пере енная, продолжает анализ входов режима 6(а)(где а=1,...,К) блока управления 10(в), Есйи на всех входах 36(а) сигналы отсутствуют узел управления 18 выдает сигнал в узел ми ропрограммного управления 12 об исче пании всех переменных вданной строке.

В том случае узел микропрограммного упра пения 12 переходит к анализу содержимо о следующего разряда регистра 15, По ок нчании просмотра содержимого регистра 5, что означает отсутствие в множестве те мов переменных с перекрестными связя и, центральный блок управления 11 выда т команду в блоки управления 10(в) (где в= ...,Р-1) об окончании перебора переменны и о начале выполнения подстановок (ун фикации) одновременно во всех строках ма рицы.

Выполняются следующие типы подстано ок: переменная вместо других переменнь; константа вместо переменных; фу кция вместо переменных.

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

Эт аналогично поиску подстановки в одной стр ке при отсутствии перекрестных связей и ее выполняют блоки обработки, входя ие в Р-ю строку, и соответствующий бло управления 10(Р).

Далее, в,счетчик 22 узел управления 18 эап сывает значение уровня вхождения им ни связывающей переменной из регистра 0 только для тех блоков управления

10(), в строках которых содержится связыва щая переменная. Если перекрестных свя ей нет, то узлы управления 18 всех блоков управления 10(в) записывают в свои сче чики 22 уровень вхождения равный единице. Производится сравнение содержимо!

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

11, что он готов к проверке на тождественность предикатов. Если содержимое счетчика 22 меньше или равно, производится опрос блоков обработки в-й строки по коду опроcà одновременно по признаку переменной и уровню вхождения и формирование диэьюнкции ответов. Если в какой-либо строке не обнаружена переменная, то соответствующий блок управления 10(в) определяет тождественность символов в строке на заданном уровне вхождения. Блоки управления в строках которых имеются такие переменные, выполняют следующее. Блок управления 10(в) производит обнуление триггеров 44 всех блоков обработки в-й строки и осуществляет их опрос по коду опроса, соответствующему ассоциативным признакам — уровень вхождения и константа. Узел управления 18 формирует дизьюнкцию ответов в узле коммутации 23. При этом производится запоминание ответов в триггерах 44 (фиг. 3), Если результатдизьюнкции равен единице, то сигналы с входов

36(1),...,36(К) записываются в регистр 21 (фиг, 2), после чего блок управления 10(a) выполняет прием константы и опрос блоков обработки строки по ее имени и заданному уровню вхождения. В случае нулевого результата дизьюнкции проверяется наличие в строке функции на заданном уровне вхождения и обнуляются триггеры 44 блоков обработки. На основе анализа сигналов с информационных выходов 7 блоков обработки блок управления 10(в) путем подачи сигнала на вход 5 принимает символ константы на регистр 20. Далее блок управления 10(в) производит опрос блоков обработки по коду опроса соответствующего признакам уровень вхождения и имя константы из регистра 20 с записью результатов в триггеры 44, После этого блок управления 10(в) осуществляет поразрядное сравнение входов 36(1),...,36(K) и разрядов регистра 21, В случае их совпадения, что означает тождественность (равенство) констант между собой обнуляет триггеры 44, и определяет наличие функций в строке на заданном уровне вхождения. Если совпадения не произошло, то константы в-й строки не тождественны, что означает невозможность унификации термов в в-й строке. блок

1837310

10

20

35

55 управления 10(в) (где в=1,...,Р-1) выдает сообщение о невозможности унификации.

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

10(в) в центральный блок управления 11, который с выходов группы 26 пересылает в блок управления 10(P). который отправляет их в узлы ассоциативной памяти 43 блоков обработки 1(вР).

Далее, блоки управления 10(в) тех строк, которые содержат связывающие переменные, с помощью блоков обработки P-й строки и блока управления 10(Р) выполняют подстановки вместо связывающей переменной. Далее определяется наличие в строке матрицы функции путем опгоса в-й строки по коду опроса, включающему уровень вхождения и признак функции, с запоминанием ответов на триггерах 44 (фиг, 3) и выполнением операции ИЛИ в узле коммутации 23 блока управления 10(в). Если результат дизъюнкции равен нулю, это означает, что в строке, содержащей переменную на уровне ее вхождения, нет ни функций, ни констант, то блок управления

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

При установлении для переменной подстановки типа переменная в случае отсутствия перекрестной связи блок управления

10(в) производит опрос блоков обработки по коду опроса, включающему признак переменной и уровень вхождения, взятого иэ счетчика 22, с запоминанием сигналов ответов в триггерах 44, Осуществляет прием символа переменной из одного иэ ответивших блоков обработки в регистр 21 и обнуляет триггер 44 данного блока обработки, Посылает на место данных, удовлетворяющих указанному коду опроса, содержимое регистра 21. В случае наличия перекрестной связи тип подстановки вместо связывающей переменной вместе с именем переменной из регистра 20 поступает от блока управления 10(в) под управлением центрального блока управления 11 с выходов группы 41 в узел микропрограммногоуправления 12, который с выходов группы 26 пересылает их в блок управления 10(Р), который, в свою очередь, записывает в узлы ассоциативной памяти 43 блоков обработки

P-й строки.

Далее, блок управления 10(в) ожидает команд от центрального блока управления

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

10(Р) символ с признаком подстановки. Для этого блок управления 10(Р) опрашивает блоки обработки по коду опроса — тип подстановки переменная, а в узле коммутации

23 формирует дизъюнкцию .ответов, Если дизъюнкция равна единице т,е. есть терм с данным признаком подстановки, то блок управления 10(Р) выполняет поиск в Р-й строке символа с типом подстановки константа, в противном случае повторно определяет наличие в Р-й строке символа с типом подстановки константа.

Для поиска в P-й строке символа с типом подстановки константа блок управления 10(Р) производит опрос блоков обработки P-й строки по коду опроса тип подстановки — константа, выполняет дизь- . юнкцию ответов и запись их в триггеры 44 (фиг. 3). При равенстве результата дизъюнкции единице блок управления 10(Р) выполняет поиск e P-й строке символа с типом подстановки функция. При равенстве результата дизъюнкции нулю, блок управления 10(Р) проверяет наличие в блоках обработки термов с типом подстановки— функция, аналогично для переменной, только по коду опроса тип подстановки - функция. Если дизъюнкция ответов этой проверки равна нулю, то блок управление

10(Р) сообщает в центральный блок управления 11, что для связывающей переменной подстановкой яв