Ассоциативная однородная вычислительная система Советский патент 1993 года по МПК G06F15/16 

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

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

Поставленная цель достигается тем, что в а:социативную однородную вычислительную систему, содержащую матрицу размером РхК блоков обработки (где Р - число аргументов унифицируемых предикатов, К- число предикатов) введены группа Р блоков управления, центральный блок управления, причем, первый, второй, третий и четвертый вхс ды кода операции, выходы признака го- ТОЕНОСТИ и признака наличия информации, информационные входы и информационные выходы блока обработки а-ro столбца в-й стр оки матрицы (где ) подключены соответственно к (4(а-1)+1)-му выходу, к (4(а-1)+2)-му. выходу, к (4(а-1)+3)-му выходу, к (4(а-1)+4)-му выходу, а-му и (к+а)--му входам режима, к выходам первой группы и ко входам режима первой группы в-го блока управления группы, выходы второй группы, входы режима второй группы, (4К+1)-й выход и (4К+2)-й выход которого подключены соответственно к входам режима первой группы, к выходам первой группы, к в-му и (Р+в)-му входам режима центрального блока управления, входы режима второй группы и выходы второй группы которого являются соответственно входами кода операции и информационными выходами системы, причем, центральный блок управления содержит узе/г микропрограммного управления, узел памяти, узел коммутации, регистр, группу элементов И и формирователь одиночного импульса, причем, входы режима первой группы и выходы первой группы узла микропрограммного управления являются соответственно входами режима первой

ы

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

которого являются соответственно выходами с первого по 4К-й блока управления группы, информационные входы, адресные входы, вход записи решения и выходы узла

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

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

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

5 узел ассоциативной памяти, триггер, два элемента И, элемент ИЛИ и группу элементов И, причем, в каждом блоке обработки выходы группы узла ассоциативной памяти являются информационными выходами бло0 ка обработки, информационные входы узла ассоциативной памяти подключены к выходам элементов И группы, выход узла ассоциативной памяти является выходом признака готовности блока обработки и

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

0 кода операции блока обработки, выход элемента ИЛ И подключен к первым входам элементов И группы, вторые входы которых являются соответственно информационными входами блока обработки.

5

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

те,

цу ун

дукатов) блоков обработки. 1(11),

1(5

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

Ассоциативная однородная вычислиьная система (фиг. 1, 2) содержит матриразмером РхК (где Р - число аргументов

лфицируемых предикатов, К- число пре1)1(К1)1(1Р)1(КР), каждый из ко1)10(Р) и центральный блок управледь10

нИя 11.

При этом, центральный блок управлений содержит узел микропрограммного уп- равления 12, узел памяти 13, узел коммутации 14, регистр 15, группу элементе з И 16 и формирователь одиночного им- пупьса 17, каждый блок управления из

гр

27 28 29

ппы блоков управления содержит узел

управления 18, узел памяти 19, первый и второй регистры 20, 21, счетчик 22, узел ко мутации 23 и элемент И 24, причем, центральный блок управления имеет входы режима первой группы 25, выходы первой группы 26, первые Р входов режима

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

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

управления имеет первые 4К выходов, соот- Befственно, 31 (а), 32(а), 33(а), 34(а) (где а К), первые К входов режима 35(1)

35 N

венно, выходы первой группы 39, входы режима первой группы 40, выходы второй

гр

К), вторые К входов режима 26(1)36(К),

+1)-й и (4К+2)-й выходы 37, 38, соответстппы 41, входы режима второй группы 42.

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

3) тр

одержит узел ассоциативной памяти 43, irrep 44, два элемента И 45, 46, элемент

.И/|И 47 и группу элементов И 48.

При этом, элементы, узлы и блоки ассо- ци тивной однородной вычислительной системы соединены следующим образом.

Входы кода операции 2-5, выходы при- знйка готовности и признака наличия ин- фо мации 6, 7. информационные входы и иноормационные выходы 8, 9 блока обра- бот ки а-ro столбца в-й строки матрицы 1(ав)

(rflija 1К; )(фиг. 1,2) подключены

сое тветственно к выходам 31(а), 32(а), 33(а), 34(0, входам режима 35(а), 36(а), выходам первой группы 39 и входам режима первой группы 40 в-ro блока управления 10(в) группы 10, выходы второй группы 41, входы ре- жииа второй группы 42, выходы 37, 38 которого подкпючены соответственно к входам режима первой группы 25, к выходам

первой группы 26, к входам режима 27(в), 28(в) центрального блока управления 11, входы режима второй группы 29 и выходы второй группы 30 которого являются соот5 ветственно входами кода операции и информационными выходами системы.

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

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

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

Входы режима первой группы и выходы

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

42блоха управления группы 10, (К+1)-й, .,.., 2К-й входы режима 36(1),,..,36(К) которого подключены соответственно ко входам режима со второго по (К+1)-й узла управления, выходы со второго по (4К+1)-й которого являются соответственно Т-м4К-м выходами 31(а), 32(а), 33(а), 34(а)(где ) блока

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

Выходы группы узла ассоциативной памяти 43 блока обработки 1(ав)(где ,

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

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

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

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

Подлежащие унификации термы предикатов последовательно посимвольно, начиная с первого терма первого предиката,

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

записывается в отдельную ячейку узла памяти 19. Далее, под управлением блоков управления группы 10 термы предикатов записываются в узлы ассоциативной памяти 43 блоков обработки (фиг. 3). Перед записью

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

узле памяти 19 в-го блока управления 10(в) (где ,...,Р-1) хранятся все символы аргументов, находящихся на в-ом месте каждого предиката, а в узле ассоциативной памяти 43 блока обработки а-ro столбца в-й строки

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

Далее, унификация термов выполняется циклически, причем, количество циклов зависит от исходных данных (термов), но не может превышать количества разноименных переменных.

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

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

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

але поиска осуществляется обнуление

на fti уп щи

ггеров 44 путем одновременной подачи ком управления 10(в) сигналов на входы

на TPI бл

3 Олоков обработки в-й строки (фиг. 3). По- исс и выдача из блока обработки слова, уд эвлетворяющему заданному ассоциативному признаку, состоит из следующем. По- исс может производиться в пределах всей матрицы или только одной строки. В первом случае код опроса вырабатывает центральный блок управления 11, который с выходов группы 26 пересылает его на входы режима группы 42 блоков управления группы 10 и, да. iee, в узлы управления 18. Во втором случаи код опр.оса формирует узел управления 18, Узел управления 18 с выходов 34(а) по- сы тает на входы кода операции 5 блоков обработки данной строки сигналы разрешение приема, а на информационные входы 8 код опроса.

Если требуется не только обнаружить ичие данных, но и установить номера

ков обработки где они хранятся, то блок авления группы 10 подает разрешаю- й сигнал также на входы кода операции 2 б|локов обработки (фиг. 1). После выполнении операции ассоциативного поиска на вы- признака готовности б тех блоков обработки, где имеются искомые данные, будет сформирован сигнал ответа, который переведет в единичное состояние триггер 44 фиг. 3), а также поступит через выход 6 блс ка обработки а-го столбца в-й строки 1(а 0 на вход режима 35(а) блока управления 10(з) и там на вход узла коммутации 23 (фиг. 2). Г |

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

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

0 информационные входы регистра 15, а также с выходов 37 блоков управления 10(в) на информационные входы узла коммутации

14центрального блока управления 11, где над ними выполняется операция ИЛИ. Если

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

0 информации с входов 28(в) в регистр 15. При этом, установление в-го разряда регистра

15в единичное состояние означает наличие искомых данных в одном или нескольких блоках обработки в-й строки. Номера таких

5 строк поступают в узел микропрограммного управления 12 с выходов элементов И группы 16 путем подачи на первые входы элементов И группы 16 сигналов опроса, по которым информация с выходов регистра 15

0 при наличии сигнала разрешения чтения с выхода формирователя одиночного импульса 17 проходит на вторые входы элементов И группы 16.

Номер блока обработки в пределах в-й

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

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

5 управления 10(в) только при наличии сигнала ответа с выхода узла ассоциативной памяти 43. Выбор данных из такого а-го блока обработки осуществляется подачей ка вход кода операции 5 сигнала с выхода 34(а) бло0 ка управления 10(в}(фиг„ 2), по которому кед опроса проходит на информационные входы группы узла ассоциативной памяти 43 только а-го блока обработки 1(ав), следовательно, на информационных выходах 9 пся5 вятсй данные только этого блока обработки, . которые и примет блок управления 10(в),

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

Производится опрос блоков обработки в-й строки по коду опроса, равному содержимому регистра 20, с целью поиска одинаковых символов. Узел коммутации 23 выполняет операцию И. Результат поступает на первый вход режима узла управления 18 и с выхода 37 на вход 27(в) центрального блока управления 11 в узел коммутации 14. Производится анализ результата конъюнкции узлом управления 18. Если он равен нулю, то в пределах данной строки термы не унифицируемы. В этом случае узел управления 18 удерживает на выходах группы 39

код опроса, на выходах 34(а) (где )

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

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

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

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

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

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

5 был переведен в единичное состояние. Узел управления 18 опрашивает блок обработки 1(св) по коду опроса, соответствующего ассоциативному признаку переменной, вызывает эту переменную на регистр 20, а затем

0 обнуляет триггер 44 (фиг. 3) путем подачи сигнала на вход 3 блока обработки 1(св)(фиг. 3).

Далее, для поиска перекрестных связей узел управления 18 пересылает содержимое

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

0 переменной в узлы управления 18 всех блоков управления. 10(в) и, далее, на регистры 20 этих блоков. Узлы управления 18 производят опрос всех блоков обработки по коду опроса - содержимое регистра 20, при этом,

5 выдают на второй вход элемента И 24 разрешающий сигнал. Узлы коммутации 23, 14 реализуют операцию ИЛИ. Если ее результат равен единице, это указывает на наличие перекрестной связи, при этом, номера разрядов регистра 15, установленные в единижнее состояние будут указывать множество строк, связанных одной переменной (переменной, имя которой содержится в узлах асе оциативной памяти 43 блоков обработки зп х строк). В этом случае узел микропрограммного управления 12 прекращает пере- бо) переменных и с выходов группы 26 выдает команду о начале определения типа подстановок и их выполнение для связывающей переменной в блоки управления, для кот орых разряды регистра 15 установлены в единичное состояние. При нулевом значении дизъюнкции узел управления 18 строки, из которой была извлечена предыдущая перепенная, продолжает анализ входов режима 36(а)(,...,К) блока управления 10(в). Если на всех входах Зб(а) сигналы отсутствуют, узел управления 18 выдает сигнал в узел микропрограммного управления 12 об ис- чер пании всех переменных в данной строке.

В з

ра

МО

окончании просмотра содержимого регисттом случае узел микропрограммного уп- ления 12 переходит к анализу содержи- о следующего разряда регистра 15. По

pa

15, что означает отсутствие в множестве

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

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

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

стр бра

ктура аргументов функции, которые вы- ны в качестве кандидатов для подстазей

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

дящие в Р-ю строку, и соответствующий

управления 10(Р).

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

ра

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

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

0 11, что он готов к проверке на тождественность предикатов. Если содержимое счетчика 22 меньше или равно, производится опрос блоков обработки в-й строки по коду опроса одновременно по признаку пере5 менной и уровню вхождения и формирование дизъюнкции ответов. Если Б какой-либо строке не обнаружена переменная, то соответствующий блок управления 10(в) определяет тождественность символов в строке на

0 заданном уровне вхождения. Блоки управления в строках которых имеются такие переменные, выполняют следующее. Блок управления 10(в) производит обнуление триггеров 44 всех блоков обработки в-й

5 строки и осуществляет их опрос по коду опроса, соответствующему ассоциативным признакам - уровень вхождения и константа. Узел управления Сформирует дизъюнкцию ответов в узле коммутации 23. При этом

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

36(1)36(К) записываются в регистр 21

(фиг, 2), после чего блок управления 10(в)

5 выполняет прием константы и опрос блоков обработки строки по ее имени и заданному уровню вхождения. В случае нулевого результата дизъюнкции проверяется наличие в строке функции на заданном уровне вхож0 дения и обнуляются триггеры 44 блоков обработки. На основе анализа сигналов с информационных выходов 7 блоков обработки блок управления 10(в) путем подачи сигнала на вход 5 принимает символ кон5 станты на регистр 20. Далее блок управления 10(в) производит опрос блоков обработки по коду опроса соответствующего признакам уровень вхождения и имя константы из регистра 20 с записью

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

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

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

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

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

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

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

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

кой ста нта.

При поиске в Р-й строке символа с ти- поМ подстановки - функция блок управления 10(Р) производит опрос блоков обработки по коду опроса тип подстановки ункция и формирует дизъюнкцию отве- TOII; В случае единичного результата блок управления 10(Р) проверяет наличие символа

стипом подстановки - константа, в про(Фи

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

CHI нал на все выходы 33(1)33(К). При этом

будут опрашиваться только те узлы ассоци- ат1 вной памяти 43, для.которых триггеры 44 установлены в единичное состояние. Блок управления 10(Р) формирует дизъюнкцию OTJ етов в узле коммутации 23. Если результат равен единице, то унификация невоз- мо.кна и блок управления 10(Р) выдает сое бщение в центральный блок управления 11, в противном случае выполняется подста- но ка функции вместо связывающей переменной.

При проверке тождественности констант в Р-й строке блок управления 10(Р) анЈ логично другим блокам управления 10(В) (гд« ,..,,Р-1) определяет наличие константы j строке на заданном уровне вхождения и принимает ее. При этом, при формирование кода опроса в качестве признаков ис- по/ьзуются тип подстановки - константа и имя константы. В результате в регистре 20

. 2) блока управления 10(Р) будет записано имя константы, которая проверялась на тождественность с другими константами. Если в результате выполнения обнаружится нетождественность констант, записанных в блоках обработки Р-й строки (т.е. имеются константы с разными именами), то отсутствует общая подстановка для связывающей переменной и блок управления 10(Р) выдает в центральный блок управления 11 сообщение о невозможности унификации. Еслм константы окажутся тождественными, то блок управления 10(Р) выполняет подстановку константы вместо связывающей переменной. Для этого блок управления 10(Р) обнуляет все триггеры 44, опрашивает блоки обработки по коду опроса тип подстановки - переменная и записывает ответ о наличии таких данных в триггеры 44, Далее блок управления 10(Р) выдает сигнал на все выходы 33(1),...,33(К), а на выходы группы 39 код опроса, соответствующий замене данных и имя константы. В результате этого в узлах ассоциативной памяти 43 тех блоков обработки, у которых триггер 44 находился в единичном состоянии, произойдет замена данных (данные, которые выдавались по предыдущему коду опроса заменяются на те. которые поступили с новым). После чего блок управления 10(Р) информирует центральный блок управления 11 об окончании данной пересылки. Получив такой сигнал, центральный блок управления 11 инициирует выдачу из блоков обработки Р-й строки замещенных термов через блок управления 10(Р) и запись их в регистры 21 тех блоков управления 10(в), разряды которых в регистре 15 в единичном состоянии. После этого центральный блок управления 11 выдает блокам управления 10(в), содержащим связывающую переменную с выходов группы 26 команду на выполнение подстановка. По этой команде блок управления 10(в) осуществляет обнуление триггеров 44 блоков обработки и их опрос по коду опроса, включающем признак переменной и номер уровня вхождения, взятого из счетчика 22, с запоминанием сигналов ответа Б триггерах 44, посылает на место данных, удовлетворяющих этому коду опроса, содержимое регистра 21. Далее блок управления SO(s) сравнивает содержимое счетчика 22 (фмг, 2) с единицей. Если оно равно единице или данный блок управления 10(в) выполняет действия для устранения перекрестной связи, то он выдаете выходов группы 41 сигнал о своей готовности к проведению проверки предикатов к а тождественность. В противном случае узел управления 18 данного блока управлений уменьшает содержимое счетчика 22 на единицу и переходит к определению наличия переменной в строке на заданном уровне вхождения.

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

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

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

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

управления 10(Р). Блок управления 10(Р) осуществляет выбор символа функции в регистр 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(К) с целью определения первого блока обработки, содержа- щвго искомые данные, Запись сигналов с

36(1)36(К) в регистр 21 (фиг. 2).

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

3Ј(1)36(К) с разрядами регистра 21. Если

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

Если при выполнении проверок функ-

i не обнаружено, т.е. результат дизъ юн к- 1 в узле коммутации 23 равен нулю, то ществляется дополнительная проверка тождественность аргументов функций в чае если они константы. Для реализации и проверки блок управления 10(в) обну- ттриггеры 44 блоков обработки и осущецици

ОС

на

ел

эт

ля

ств(ляет их опрос по коду опроса - уровень

вх

ет

ждения и признак константы. Выполня- я запоминание ответов на триггерах 44 и

формирование дизъюнкции ответов в узле коммутации 23, Если результат равен нулю, то /зел управления 18 восстанавливает из ячейки узла памяти 19 в счетчике 22 прежнее значение, к нему добавляет единицу и nef еходит к выполнению проверки оконча- ни$ цикла по уровню вхождения. Если результат равен единице, то узел управления 18 осуществляет запись сигналов с входов 36(jl)36(К) в регистр 21, просмотр этих

входов с целью определения первого блока обработки, содержащего искомые данные. Далее, производится запись символа константы из ответившего блока обработки в регистр 20, обнуление триггеров 44. Производится опрос блоков обработки по коду опроса - уровень вхождения и имя константы из регистра 20 и запись ответов в триггеры 44. Узел управления 18 осуществляет

поразрядное сравнение входов 36(1)36(К)

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

При проверке наличия переменных внутри функции блок управления 10(в) обнуляет триггеры 44 и опрашивает блоки обработки по коду опроса - признак переменной и уровень вхождения, формирует операцию ИЛИ с сигналами ответов в узле коммутации 23 и записывает сигналы ответов в триггеры 44 (фиг, 3). Если значение дизъюнкции равно единице, то блок управления 10(в) выполняет проверку переменных на нижнихуровнях вхождения, в противном случае узел управления 18 восстанавливает из ячейки узла памяти 19 прежнее значение счетчика 22. Далее, при отсутствии перекрестной связи блок управления 10(в) выполняет подстановку функции вместо переменной. В случае если перекрестная связь присутствует, то выполняется следующая последовательность действий. Узел управления 18 блока управления 10(в) выполняет опрос блоков обработки в-й строки по коду опроса - уровень вхождения и признак функции, пересылает обнаруженный терм в регистр 20, Тип подстановки вместо связывающей переменной - функция вместе с именем и уровнем вхождения функции из регистра 21 поступает от блока управления 10(в) под управлением центрального блока управления 11 в узел микропрограммного управления 12, который пересылает их в блок управления 10(Р), который, в свою очередь, записывает в узел ассоциативной памяти 43 блока

обработки 1(аР) (где ). Далее узел

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

При проверке переменных на нижних уровнях вхождения организуется цикл по переменным, обнаруженным при выполне- нии проверки наличия переменных внутри функции, при этом блоки обработки, в которых эти переменные присутствуют имеют сигнал на выходе 7. Узел управления 18 анализирует входы 36(1)36(К) и выбирает по-

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

Если перекрестная связь отсутствует, то блок управления 10(в) переходит к выполнению подстановки функции вместо переменной. В случае если перекрестная связь присутствует, то блоками управления группы 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(в) (где ,...,Р) сообщение о невозможности унификации. В этом случае в блоки управления 10(с) (где с 1Р-1) центральный блок управления 11 выдает команду об окончании унификации и выдачи из узлов ассоциатибной памяти 43 всех блоков обработки аргументов предикатов. По этой команде блоки управления независимо друг от друга организуют передачу от всех блоков обработки строки данных (аргументов), хранящихся в их узлах ассоциативной памяти 43, в узлы памяти 19 и по запросу от центрального блока управления 11 выдают эти данные из узла памяти 19 в узел памяти 13 центрального блока управления 11. После приема данных от всех блоков управления 10(с) (где с 1Р-1) центральный блок управления 11 выдает пользователю с информационных выходов системы 30 сообщение, что унификация невозможна и далее данные (аргументы неунифицируемых предикатов) из узла памяти 13.

Второй. Центральный блок управления олучил от всех блоков управления 10(с)

,...,Р-1) сообщение, что аргументы их ок тождественны. В этом случае цент- ьный блок управления 11, аналогично, 5

и в первом случае управляет приемом

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

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

в

(Р-1) + КТ 2(10КТ + КР +20)

0)

20

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

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

КХ- число контрарных пар предикатов. Так, в случае когда ...4, ...8, 8... 16, ...4, выигрыш в быстродейст- 25 составит .8-24.6 и растет с увеличе- м числа Р аргументов унифицируемых дикатов.

Формула изобретения 1. Ассоциативная однородная вычисли30

)-му выходу, к (4(а-1)+3)-му выходу, к (4(а- )-му выходу, а-му и (К+а)-му входам, к

ьная система, содержащая матрицу разом РхК блоков обработки (где Р - число ментов унифицируемых предикатов, К - ло предикатов), отличающаяся тем, , с целью повышения быстродействия, 35 содержит группу Р блоков управления, тральный блок управления, причем пер- , второй, третий и-четвертый входы кода рации, выходы признака готовности и знака наличия информации, информа- 40 иные входы и информационные выходы ка обработки а-го столбца в-й строки

рицы (где ) подключены

тветственно к(4(а-1)+1)-му выходу, к(4(а45

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

5

10

5

0

5

0

5 0

5

0 5

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

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

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

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

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

Фиг. 1

F

Б

Ј

W

f t Ц

J7

rt

9Об

И

-

U

ьз.

63

Й/.3

О

Л

ov

Ь5

08