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

 

Ассоциативная однородная вычислительная система относится к области вычислительной техники и может быть использована для решения задачи дедуктивного логического вывода в исчислении предикатов. Цель изобретения - повышение быстродействия . В системе осуществляется унификация термов одноименных и (или) контрарных предикатов и получение результата данной процедуры как в случае унифицируемости , так и не унифицируемости термов. Поставленная цель достигается тем, что ассоциативная однородная вычислительная система содержит матрицу РхК блоков обработки, блок управления и группу блоков управления. 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, что для связывающей переменной подстановкой является переменная. Данное сообщение является для узла микропрограммного управления 12 командой для запоминания символа связывающей пере17

1837310 м нной в узле памяти 13, чтобы в последующ м при выполнении поиска перекрестной связи не принимать во внимание эту уже проверенную переменную. При этом узел микропрограммного управления 12 получив от одного иэ блоков управления 10(aB) в реэу ьтате поиска переменных очередную пер менную для анализа сравнивает ее имя с и енами проверенных на перекрестную связь переменных из узла памяти 13, В случае совпадения узел микропрограммного уп авления 12 далее ее не анализирует и в бирает очередную переменную. Это буд равносильно выполнению вместо связ вающей переменной подстановки типа— п еменная. Далее выполняется очередной ц кл унификации, начинающийся с прове ки тождественности предикатов. Если результат дизьюнкции ответов дополните ьной проверки равен единице, то блок уп авления 10(Р) выполняет проверку наличи в Р-й строке символа с типом подстановки константа, 5

20 по н об

"1 ип ни по ь

„1 то уп ла ти ко чи ки вы ти си бу ат ус уп от та мо со

11, но ме

При поиске в P-й строке символа с ти- 25 подстановки — функция блок управлея 10(Р) производит опрос блоков аботки по коду опроса тип подстановки ункция и формирует дизьюнкцию отве; В случае единичного результата блок 30 авления 10(Р) проверяет наличие симвос типом подстановки — константа, в проном случае проверяет тождественность стант e P-й строке, Для проверки налив P-й строке символа с типом подста нов- 35 — константа блок управления 10(Р) тавляет на выходы группы 39 код опроса подстановки — константа, единичный нал на все выходы 33(1),...,33(К). При этом ут опрашиваться только те узлы ассоци- 40 аной памяти 43, для.которых триггеры 44 ановлены в единичное состояние. Блок авления 10(Р) формирует диэьюнкцию етов в узле коммутации 23, Если резульравен единице, то унификация невоз- 45 на и блок управления 10(Р) выдает бщение в центральный блок управления в противйом случае выполняется подстака функции вместо связывающей переной. 50

При проверке тождественности конт в P-й строке блок управления 10(Р) огично другим блокам управления 10(В) в=1,...,P-1) определяет наличие констанстроке на заданном уровне вхождения 55 инимает ее. При этом, при формировакода опроса в качестве признаков исзуются тип подстановки — константа и константы. В результате в регистре 20 г. 2) блока управления 10(Р) будет записана имя константы, которая проверялась на тождественность с другими константами, Если в результате выполнения обнаружится нетождественность констант, записанных в блоках обработки P-й строки (т.е. имеются константы с разными именами), то отсутствует общая подстановка для связывающей переменной и блок управления 10(Р) выдает в центральный блок упоавления 11 сообщение о невозможности унификации. Если константы окажутся тсждественными, TG блок управления 10(P) выполняет подстановку константь вместо связывающей переменной, Для этого блок управлечия 10(Р) обнуляет все триггеры 44, опрашивает Groки обработки по коду опроса тип подстановки — переменная и записывает ответ о наличии таких данных в триггеры 44, Далее блок управления 10(Р) выдает сигнал на все выходы 33(1),...,33(К), а на выходы группы 39 код опроса, соответствующий замене данных и имя константы. В результате этого в узлах ассоциативной памяти 43 тех блоков обработки, у которых триггер 44 находился в единичном состоянии, произойдет замена данн ых (дан н ые, которые выдавались по предыдущему коду опроса заменяются на те, которые поступили с новым), После чего блок управления 10(Р) информирует центральный блок управления 11 об окончании данной пересылки. Получив такой сигнал, центральный блок управления 11 инициирует выдачу из блоков обработки Р-й строки замещенных термов через блок управления

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

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

44, посылает на место данных, удовлетворяющих этому коду опроса, содержимое регистра 21. Далее блок упр" âëåíèÿ 10(в) сравнивает содержимое счетчика 22 (фиг, 2) с единицей. Если оно равно единице или данный блок управления 10(в) выполняет действия для устранения перекрестной связи; то он выдаегс выходов группы 41 сигнал о своей готовности к проведению проверки предикатов на тождественность. B противном случае узел управления 18 данного блока управления уменьшает содержимое счетчика 22 на единицу и переходит к опре1837310

20 делению наличия переменной в строке на заданном уровне вхождения, В процессе работы системы возникает необходимость выявления тождественности символов в строке на заданном уровне вхождения, Для этого блок управления 10(в) осуществляет прием символа с информационных выходов 9 первого блока обработки в-й строки по коду опроса — уровень вхождения и запись символа в регистр 20. После чего данный блок управления 10(в) производит поиск данных в блоках обработки строки по коду опроса — уровень вхождения и имя символа и выполняет операцию И в узле коммутации 23 над сигналами ответа. В случае нулевого результата блок управления

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

При подстановке функции вместо связывающей переменной блок управления

10(Р) производит действия аналогичные действиям, производимыми блоками управления 10(в) (где в=1„.,Р-1) при сравнении имен функций в строке на заданном уровне вхождения, определении тождественности функций, проверке наличия переменных внутри функции и проверке переменных на нижних уровнях вхождения. При этом, в качестве кода опроса используется только признак тип подстановки — функция, в качестве значения уровня вхождения используется значение уровня вхождения символа функции, полученные при выдаче данных из блоков обработки и записанное в счетчик 22 блока управления 10(Р). Если функции не одноименны, то унификация невозможна и блок управления 10(Р) извещает об этом центральный блок управления 11, Если функции окажутся тождественными, то осуществляется попытка унификации в Р-й строке, при этом, выполняются аналогичные действия, которые опроизводятся блоками управления 10(в) (где в=1,...,P-1) в своих строках при отсутствии перекрестных связей, В случае тождественности функций в P-й строке или после проведения унификации в данной строке осуществляется пересылка функции с аргументами вместо связывающей переменной в строки, содержащие, связывающую переменную. Данная пересылка выполняется под управлением центрального блока управления 11 по команде, которую он посылает с выходов группы 26 в блок

55 управления 10(Р). Блок управления 10(P) осуществляет выбор символа функции в регистр 20 и, далее, следует пересылка его из регистра 20 в регистры 21 блоков управления 10(в), содержащих связывающую переменную, Далее, под управлением блоков управления 10(в), содержащих связывающую переменную, осуществляется выполнение подстановки функции вместо связывающей переменной, При этом, узел управления 18 каждого блока .управления

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

10(Р) сохраняет предыдущее значение счетчика 22 в регистре 21 и осуществляет циклическое выполнение следующей последовательности действий, Увеличивает значение счетчика 22 на единицу.

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

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

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

Просмотр входов 36(1),.„,36(К) с целью опре22 входов с целью определения первого блока обработки, содержащего искомые данные.

Далее, производится запись символа константы из ответившего блока обработки в регистр 20, обнуление триггеров 44. Производится опрос блоков обработки по коду опроса — уровень вхождения и имя константы из регистра 20 и запись ответов в триггеры 44. Узел управления 18 осуществляет поразрядное сравнение входов 36(1)„.„36(К) с разрядами регистра 21. Если они совпадают, то константы данного уровня вхождения одноименны, и соответствующий блок управления 10(в) переходит к выполнению проверки наличия переменных внутри функции. В противном случае термы данной строки не унифицируемы и блок управления

10(в) извещает об этом центральный блок управления 11.

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

ИЛИ с сигналами ответов в узле коммутации

23 и записывает сигналы ответов в триггеры

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

Далее, при отсутствии перекрестной связи блок управления 10(в) выполняет подстановку функции вместо переменной. В случае если перекрестная связь присутствует, то выполняется следующая последовательность действий. Узел управления 18 блока управления 10(в) выполняет опрос блоков обработки в-й строки по коду опроса — уровень вхождения и признак функции, пересылает обнаруженный терм в регистр 20, Тип подстановки вместо связывающей переменной — функция вместе с именем и уровнем вхождения функции из регистра 21 поступает от блока управления 10(в) под управлением центрального блока управления

11 в узел микропрограммного управления

12, который пересылает их в блок управления 10(Р). который, в свою очередь, записывает в узел ассоциативной памяти 43 блока обработки 1(аР) (где а=1,...,К). Далее узел управления 18 (фиг. 2) сохраняет предыдущее содержимое счетчика 22 в регистре 21 и осуществляет циклическое выполнение следующей последовательности действий, Увеличивает значение счетчика 22 на единицу. Обнуляет триггеры 44 в блоках обработки, производит их опрос по коду опроса— уровень вхождения, формирует дизьюнк21 1837310 д ления первого блока обработки, содержащ го искомые данные, Запись сигналов с в одов 36(1),...,36(К) в регистр 21 (фиг. 2).

В эов имени функции из ответившего блока о работки в регистр 20. Обнуление тригге- 5 р в 44 (фиг. 3). Опрос блоков обработки по к ду опроса — уровень вхождения и имя функ ии из регистра 20. Запись ответов в тригг ры 44. Поразрядное сравнение входов

3 (1),...,36(К) с разрядами регистра 21. Если 10 о и совпадают, то функции данного уровня а ождения одноименны, и соответствующ и блок управления 10(в) переходит к onр делению тождественности функцией, Е ли они не совпадают, то термы в данной 15 ст оке не унифицируемы и блок управления

1 в) извещает об этом центральный блок у равления 11. Для определения тождественности функций блок управления 10(в) зась лает значение счетчика 22 в ячейку узла 20 па мяти 19 для временного хранения. Содержимое счетчика 22 узел управления 18 увел чивает на единицу. Далее производит ср внение полученного значения с максим ьным уровнем вхождения для данной 25 ст оки. Если оно не превышено, то блок уп веления 10(в) производит сравнение и ен функций в строке на заданном уровне вх ждения, Если очередные имена функций не совпадают, то на этом проверка на тож- 30 де твенность прерывается, из ячейки узла па яти 19 восстанавливается в счетчике 22

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

10 в) переходит на выполнение проверки 35 ок нчания цикла по уровню вхождения. Если они совпали, узел управления 18 снова ув личивает значение в счетчике 22 на едини у и проверки продолжаются.

Если при выполнении проверок функ- 40 ци не обнаружено, т.е. результат дизъюнкци в узле коммутации 23 равен нулю, то ос ществляется дополнительная проверка на тождественность аргументов функций в сл чае если они константы. Для реализации 45 эт и проверки блок управления 10(в) обнуля т триггеры 44.блоков обработки и осущест яет их опрос по коду опроса — уровень вх ждения и признак константы. Выполняет запоминание ответов на триггерах 44 и 50 фо мирование дизьюнкции ответов в узле ко мутации 23, Если результат равен нулю, то, эел управления 18 восстанавливает из яч йки узла памяти 19 в счетчике 22 прежне значение, к нему добавляет единицу и 55 пе еходит к выполнению проверки окончани цикла по уровню вхождения, Если резул тат равен единице, то узел управления

18 существляет запись сигналов с входов

36(;)...„36(К) в регистр 21, просмотр этих

1837310

15

25 текущего уровня вхождения в регистр 21 для 30 временного хранения и уменьшает содер-обнаружены и производит ее проверку ана- 50 логично рассмотренной выше. После того, как все переменные будут проанализирова55 цию сигналов ответа и записывает их в триггеры 44, Если результат равен единице, то под управлением центрального блока управления 11 аргумент, как и имя функции, записывается в узел ассоциативной памяти

43 блока обработки 1(аР) и, далее, процесс повторяется. При этом, узел управления 18 в блоке управления 10(Р) записывает максимальное значение уровня вхождения в отдельную ячейку узла памяти 19. Как только результат дизъюнкции станет равным нулю, узел управления 18 восстанавливает прежнее значение счетчика 22 иэ регистра 21, извещает центральный блок управления 11 и ожидает от него дальнейших команд на подстановку вместо связывающей переменной терма, При проверке переменных на нижних уровнях вхождения организуется цикл по переменным, обнаруженным при выполнении проверки наличия переменных внутри функции, при этом блоки обработки. в которых эти переменные присутствуют имеют сигнал на выходе 7, Узел управления 18 анализирует входы 36(1)„...36(К) и выбирает поочередно блоки обработки для выбора очередной переменной. Узел управления 18 пересылает на регистр 20 очередную переменную, засылает содержимое счетчика 22 жимое счетчика 22 на единицу, Далее, блок управления 10(в) производит циклический опрос блоков обработки строки по коду onроса — имя переменной из регистра 20 и уровень вхождения из счетчика 22, при этом в каждом цикле узел управления 18 уменьшает. содержимое счетчика 22 на единицу, выполняет дизъюнкцию сигналов ответов в узле коммутации 23 (фиг. 2). Наличие единичного значения дизъюнкции делает унификацию невозможной, Блок управления

10(в) в этом случае выдает сообщение в центральный блок управления 11. Как только содержимое счетчика 22 станет равным нулю, узел управления 18 восстанавливает прежнее содержимое счетчика 22 из регистра 21, осуществляет выбор следующей переменной, из числа тех, которые были ны, узел управления 18 восстанавливает из ячейки узла памяти 19 старое содержимое счетчика 22.

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

45 пы 10 выполняются те же действия, что и при проверке наличия переменных внутри функции, Для подстановки функции вместо переменной узел управления 18 блока управления 10(в) выполняет опрос блоков обработки по коду опроса — уровень вхождения и признак функции, а затем пересылает обнаруженный таким образом терм иэ блока обработки в регистр 21 (фиг, 2). Далее, производится подстановка символа функции из регистра 21 вместо переменной. Узел управления 18 сохраняет предыдущее содержимое счетчика 22 в регистре 21, записывает сигналы с входов 36(1),...,36(К) в регистр 20 и осуществляет циклическое выполнение следующих действий, Увеличивает значение счетчика 22 на единицу, Обнуляет триггеры

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

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

Работа системы заканчивается в одном из двух случаях.

Первый. Центральный блок управления

11 получает от одного из блоков управления

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

43, в узлы памяти 19 и по запросу от центрального блока управления 11 выдают эти данные иэ узла памятИ 19 в узел памяти 13 центрального блока управления 11. После приема данных от всех блоков управления

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

11 (r ст ра ка да

c-Щ ус гу уз

20 ти оц гд ди нь

КТ ви ни пр

30 те ме ар чи чт он це в

40 с

1 вы пе пы вт хо вх пе ре вх ро ст ин

55 че

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

Выигрыш в быстродействии ассоцианой однородной вычислительной систев сравнении с прототипом может быть нен по формуле

2 (1ОКТ + КР + 20)

КТ вЂ” общее число переменных в К преатах;

KP — общее число связанных переменв К предикатах;

КХ вЂ” число контрарных пар предикатов.

Так, в случае когда KX=2...4, P-4...8, 8...16, КР=2...4, выигрыш в быстродейстсоставит В=4.8 — 24,6 и растет с увеличем числа P аргументов унифицируемых ди катав.

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

1. Ассоциативная однородная вычислиьная система, содержащая матрицу разом РхК блоков обработки (где P — число ументов унифицируемых предикатов, К— ло предикатов), отличающаяся тем,, с целью повышения быстродействия, содержит группу P блоков управления, тральный блок управления, причем пер, второй, третий и четвертый входы кода рации, выходы признака готовности и знака наличия информации. информанные входы и информационные выходы ка обработки à-ro столбца в-й строки рицы (где а=1,.„,К; в=1,...,Р) подключены тветственно к (4(а-1)+1)-му выходу, к (4(а)-му выходу, к (4(а-1)+3)-му выходу, к (4(а)-му выходу, а-му и (К+а)-му входам, к одам первой группы и к входам режима вой группы в-ro блока управления групвыходы второй группы, входы режима рой группы, (4К+1)-й выход и (4К+2)-й выкоторого подключены соотетственно к дам режима первой группы, к выходам вой группы, к в-му и к (Р+в)-Му входам има центрального блока управления, ды режима второй группы и выходы втогруппы которого подключены соответенно к входам кода операции и к ормационным выходам системы, прицентральный блок управления содерузел микропрограммного управления, узел памяти, узел коммутации, регистр, группу элементов И и формирователь одиночного импульса, причем входы режима первой группы и выходы первой группы узла микропрограммного управления подключены соответственно к входам режима первой группы и к выходам первой группы центрального блока управления, входы режима второй группы и выходы второй группы узла микропрограммного управления подключены соответственно к входам режима второй группы и к выходам второй группы центрального блока управления, выходы третьей и четвертой группы, гервый выход и входы режима третьей группы узла микропрограммного управления подключены соответственно к информационным входам, к адресным входам, к входу записи решения и выходам узла памяти, выходы пятой группы и входы режима четвертой группы узла микропрограммного управления подключены соответственно к первым входам элементов И группы и к выходам элементов И группы, вторые входы которых подключены соответственно к выходам регистра, информационные входы которого подключены соответственно к входам режима с (Р+1)-го по

2Р-й центрального блока управления, входы режима с первого по Р-й которого подключены соответственно к информационным входам узла коммутации, выход которого подключен к входу режима узла микропрограммного управления и к входу запуска формирователя одиночного импульса, выход которого подключен к входу записи/чтения регистра, второй выход узла микропрограммного управления подключен к управляющему входу узла коммутации, причем каждый блок управления из группы блоков управления содержит узел микропрограммного управления, узел памяти, два регистра, счетчик, узел коммутации и элемент И, причем в каждом блоке управления группы входы режима первой группы и выходы первой группы узла управления являются входами режима первой группы и выходами первой группы блока управления группы, входы режима с первого по К-й которого подключены соответственно к информационным входам узла коммутации, выход которого подключен к первому входу режима блок управления. группы, (4К+2)-м выходом которого является выход элемента И, первый выход узла управления подключен к второму входу элемента И, второй выход которого подключен к управляющему входу узла коммутации, выходы второй группы и входы режима второй группы узла управления являются соответственно выходами второй группы и входами режима второй группы блока уп27

1837310

28 равления группы, входы режима с (К+1)-го по 2К-й которого подключены соответственно к входам режима с второго по К+1)-й узла управления, выходы с второго по (К4+1)-й которого подключены соответственно к вы- 5 ходам с первого по 4К-й блока управления группы, информационные входы и выходы узла памяти поключены соответственно к входам режима третьей группы и к выходам третьей группы узла управления, выходы 10 четвертой группы, (4К+2)-й выход и входы режима четвертой группы которого подключены соответственно к информационным входам, к входу записи/чтения и к выходам первого регистра, выходы пятой группы, 15 (4K+3)-й выход и входы режима пятой группы узла управления подключены соответственно к информационным входам, к счетному входу и к информационным выходам счетчика. 20

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

1837310

1837310 ф фоФ

Составитель Б.Борисов

Техред M.Ìoðãåíòàë Корректор М.Куль

Редактор Н.Коляда

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

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

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

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