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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК О А 1 1)5 6 06 гас УДАРСТВЕННОЕ ПАТЕНТНОЕ ОМСТВО СССРСПАТЕНТ СССР) г ПИСАНИЕ ИЗОБРЕТЕН ВТОР У СВИДЕТЕЛЬСТВ. Одно- НовосиЯ ВЫх пу однэя вычислик области вычис(4(а) д го ч Ч(46 30.08,93. Бюл, М 32 (72 В,П, Прохоров, В,П, К ко енко, Б.Б. Борисов и А. (5 Авторское свидетельст Ит 18738, кл, 6 06 Р 15/16Евреинов Е.ВХараше ро ные вычислительные с би ск: Наука, 1978, с. 111, (54 АСС О ЦИАТИ В НАЯ ОД Ч СЛИТЕЛЬНАЯ СИСТЕМ (5 Ассоциативная однор те ьная система относится Предлагаемое изобретение относится к асти вычислительной техники и может ь использовано при построении специаированных систем, предназначенных решения задач дедуктивного логическоывода в исчислении предикатов. Целью предлагаемого изобретения явся повышение быстродействия. Поставленная цель достигается тем, что социативную однородную вычислитель- систему, содержащую матрицу разме- РхК блоков обработки (где Р - число ментов унифицируемых предикатов, К - о предикатов) введены группа Р блоков авления, центральный блок управления, чем, первый, второй, третий и четвертый ды кода операции, выходы признака гоости и признака наличия информации, ормационные входы и информационные оды блока обработки а-го столбца в-йки матрицы (где а=1 К; в=1 Р) подчены соответственно к (4(а)+1)-му вылительной техники и может быть использована для решения задачи дедуктивного логического вывода в исчислении предикатов. Цель изобретения - повышение быстродействия, В системе осуществляется унификация термов одноименных и (или) контрарных пр,.дикатов и получение результата данной процедуры как в случае унифицируемости, так и не унифицируемости термов, Поставленная цель достигается тем, что ассоциативная однородная вычислительная система содержит матрицу Р " блоков обработки, блок управления и груп блоков управления. 3 ил,ходу, к +2)-му выходу, к (4(а)+3)-му выходу, к (4(а)+4)-му выходу, а-му и (1+а) му входам режима, к выходам первой группы и ко входам режима первой группы в-го блока управления группы, выходы второй группы, входы режима второй группы, (4 К+1)-й выход и (4 К+2)-й выход которого подключены соответственно к входам режима первой группы, к выходам первой группы, к в-му и (Р+в)-му входам режима центрального блока управления, входы режима второй группы и выходы второй группы которого являются соответственно входами кода операции и информационными выходами системы, причем, центральный блок управления содержит узел микропрограммного управления, узел памяти, узел коммутации, регистр, группу элементов И и формирователь одиночного импульса, причем, входы режима первой группы и выходы первой группы узла микропрограммного управления являются соответственно входами режима первойделению наличия переменной в строке на заданном уровне вхождения,В процессе работы системы возникает необходимость выявления тождественности символов в строке на заданном уровне вхождения, Для этого блок управления 10(в) осуществляет прием символа с информационных выходов 9 первого блока обработки в-й строки по коду опроса - уровень вхождения и запись символа в регистр 20. После чего данный блок управления 10(в) производит поиск данных в блоках обработки строки по коду опроса - уровень вхождения и имя символа и выполняет операцию И в узле коммутации 23 над сигналами ответа. В случае нулевого результата блок управления 10(в) сообщает центральному блоку управления 11 с выходов группы 41, что унификация в данной строке невозможна, Если результат операции И равен единице, то блок управления 10(в) начинает следующий цикл проверок и с этой целью увеличивает содержимое своего счетчика 22 на единицу и переходит к выполнению проверки окончания цикла по уровню вхождения,При подстановке функции вместо связывающей переменной блок управления 10(Р) производит действия аналогичные действиям, производимыми блоками управления 10(в) (где в=1.,Р) при сравнении имен функций в строке на заданном уровне вхождения, определении тождественности функций, проверке наличия переменных внутри функции и проверке переменных на нижних уровнях вхождения. При этом, в качестве кода опроса используется только признак тип подстановки - функция, в качестве значения уровня вхождения используется значение уровня вхождения символа функции, полученные при выдаче данных из блоков обработки и записанное в счетчик 22 блока управления 10(Р). Если функции не одноименны, то унификация невозможна и блок управления 10(Р) извещает об этом центральный блок управления 11, Если функции окажутся тождественными, то осуществляется попытка унификации в Р-й строке, при этом, выполняются аналогичные действия, которые опроизводятся блоками управления 10(в) (где в=1,Р) в своих строках при отсутствии перекрестных связей, В случае тождественности функций в Р-й строке или после проведения унификации в данной строке осуществляется пересылка функции с аргументами вместо связывающей переменной в строки, содержащие, связывающую переменную, Данная пересылка выполняется под управлением центрального блока управления 11 по команде, которую он посылает с выходов группы 26 в блок 5 10 15 20 25 30 35 40 45 50 55 управления 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(К) с целью опре21 1837310 д ления первого блока обработки, содержащ го искомые данные, Запись сигналов с в одов 36(1).36(К) в регистр 21 (фиг. 2).В зов имени функции изответившего блока о работки в регистр 20. Обнуление тригге р в 44 (фиг. 3). Опрос блоков обработки по к ду опроса - уровень вхождения и имя функ ии из регистра 20. Запись ответов в тригг ры 44. Поразрядное сравнение входов 3 (1)36(К) с разрядами регистра 21. Если 10 о и совпадают, то функции данного уровня в ождения одноименны, и соответствующ й блок управления 10(в) переходит к опр делению тождественности функцией, Е ли они не совпадают, то термы в данной 15 ст оке не унифицируемы и блок управления 1 в) извещает об этом центральный блок у равления 11. Для определения тождественности функций блок управления 10(в) засьлает значение счетчика 22 в ячейку узла 20 пачяти 19 для временного хранения. Содержимое счетчика 22 узел управления 18 увел чивает на единицу. Далее производит ср внение полученного значения с максим ьным уровнем вхождения для данной 25 ст оки. Если оно не превышено, то блок уп веления 10(в) производит сравнение и ен функций в строке на заданном уровне вх ждения, Если очередные имена функций не совпадают, то на этом проверка на тож де твенность прерывается, из ячейки узла па яти 19 восстанавливается в счетчике 22 ег прежнее значение, к его содержимому до авляется единица и блок управления 10 в) переходит на выполнение проверки 35 ок нчания цикла по уровню вхождения. Если они совпали, узел управления 18 снова ув личивает значение в счетчике 22 на едини у и проверки продолжаются.Если при выполнении проверок функ ци не обнаружено, т.е. результат дизъюнкци в узле коммутации 23 равен нулю, то ос ществляется дополнительная проверка на тождественность аргументов функций в сл чае если они константы. Для реализации 45 эт й проверки блок управления 10(в) обнуля т триггеры 44 блоков обработки и осущест яет их опрос по коду опроса - уровень вх ждения и признак константы. Выполняет запоминание ответов на триггерах 44 и 50 фо мирование дизьюнкции ответов в узле ко мутации 23, Если результат равен нулю, то, эел управления 18 восстанавливает из яч йки узла памяти 19 в счетчике 22 прежне значение, к нему добавляет единицу и 55 пе еходит к выполнению проверки окончани цикла по уровню вхождения, Если резул тат равен единице, то узел управления 18 существляет запись сигналов с входов 36(,)36(К) в регистр 21, просмотр этих 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 в блоках обработки, производит их опрос по коду опроса - уровень вхождения, формирует дизъюнк 1837310 24цию сигналов ответа и записывает их в триггеры 44, Если результат равен единице, то под управлением центрального блока управления 11 аргумент, как и имя функции, записывается в узел ассоциативной памяти 43 блока обработки 1(аР) и, далее, процесс повторяется. При этом, узел управления 18 в блоке управления 10(Р) записывает максимальное значение уровня вхождения в отдельную ячейку узла памяти 19. Как только результат дизъюнкции станет равным нулю, узел управления 18 восстанавливает прежнее значение счетчика 22 иэ регистра 21, извещает центральный блок управления 11 и ожидает от него дальнейших команд на подстановку вместо связывающей переменной терма,При проверке переменных на нижних 15 уровнях вхождения организуется цикл по переменным, обнаруженным при выполнении проверки наличия переменных внутри функции, при этом блоки обработки. в которых эти переменные присутствуют имеют 20 сигнал на выходе 7, Узел управления 18 анализирует входы 36(1).36(К) и выбирает поочередно блоки обработки для выбора 25 очередной переменной, Узел управления 18 пересылает на регистр 20 очередную переменную, засылает содержимое счетчика 22 жимое счетчика 22 на единицу, Далее, блок управления 10(в) производит циклический опрос блоков обработки строки по коду опроса - имя переменной из регистра 20 и уровень вхождения из счетчика 22, при этом в каждом цикле узел управления 18 уменьшает. содержимое счетчика 22 на единицу, выполняет дизъюнкцию сигналов ответов в узле коммутации 23 (фиг, 2). Наличие единичного значения дизъюнкции делает унификацию невозможной, Блок управления 10(в) в этом случае выдает сообщение в центральный блок управления 11. Как только содержимое счетчика 22 станет равным ну 35 40 45 лю, узел управления 18 восстанавливает прежнее содержимое счетчика 22 из регистра 21, осуществляет выбор следующей переменной, из числа тех, которые были обнаружены и производит ее проверку аналогично рассмотренной выше. После того,как все переменные будут проанализированы, узел управления 18 восстанавливает из ячейки узла памяти 19 старое содержимое счетчика 22.Если перекрестная связь отсутствует, то блок управления 10(в) переходит к выполнению подстановки функции вместо переменной. В случае если перекрестная связь присутствует, то блоками управления груп 55 текущего уровня вхождения в регистр 21 для 30временного хранения и уменьшает содер-. пы 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Р) центральный блок управления 11 выдает команду об. окончании унификации и выдачи из узлов ассоциативной памяти 43 всех блоков обработки аргументов предикатов. По этой команде блоки управления независимо друг от друга организуют передачу от всех блоков обработки строки данных (аргументов), хранящихся в их узлах ассоциативной памяти 43, в узлы памяти 19 и по запросу от центрального блока управления 11 выдают эти данные иэ узла памятй 19 в узел памяти 13 центрального блока управления 11. После приема данных от всех блоков управления 10(с) (где с=1Р) центральный блок управления 11 выдает пользователю с информационных выходов системы 30 сообщение, что унификация невозможна и далее данные (аргументы неунифицируемых предикатов) из узла памяти 13.11 (г ст ра ка да с= Щ ус гу уз 5 10 15 20 ти оц гд ди нь КТ ви ни пр 25 30 те ме ар чи чт он це в 35 40 с 1 1 вы пе пы вт хо вх пе ре вх ро ст ин 45 50 55 че Второй. Центральный блок управления получил от всех блоков управления 10(с) е с=1,Р) сообщение, что аргументы их ок тождественны, В этом случае центьный блок управления 11, аналогично, и в первом случае управляет приемом ных от блоков управления 10(с) (где Р), но пользователю выдает сообние о том, что унификация закончилась ешно, и далее передает ему данные (аренты унифицированных предикатов) из а памяти 13.Выигрыш в быстродействии ассоцианой однородной вычислительной систев сравнении с прототипом может быть нен по формуле 2 (10 КТ + КР + 20)КТ - общее число переменных в К преатах; КР - общее число связанных перемене К предикатах; КХ - число контрарных пар предикатов. Так, в случае когда КХ=24, Р, 816, КР=24, выигрыш в быстродейстсоставит В=4,8 - 24,6 и растет с увеличем числа Р аргументов унифицируемых дикатов. Формула изобретения 1. Ассоциативная однородная вычислиьная система, содержащая матрицу разом РхК блоков обработки (где Р - число ументов унифицируемых предикатов, К - ло предикатов), о т л и ч а ю щ а я с я тем, , с целью повышения быстродействия,содержит группу Р блоков управления, тральный блок управления, причем пер, второй, третий и четвертый входы кода рации, выходы признака готовности и знака наличия информации. информанные входы и информационные выходы ка обработки а-го столбца в-й строки рицы (где а=1,.,К; в=1Р) подключены тветственно к (4(а)+1)-му выходу, к (4(а)-му выходу, к (4(а)+3)-му выходу, к (4(а)-му выходу, а-му и (К+а)-му входам, к одам первой группы и к входам режима вой группы в-го блока управления групвыходы второй группы, входы режима рой группы, (4 К+1)-й выход и (4 К+2)-й выкоторого подключены соотетственно к дам режима первой группы, к выходам вой группы, к в-му и к (Р+в)-му входам има центрального блока управления, ды режима второй группы и выходы втогруппы которого подключены соответенно к входам кода операции и к ормационным выходам системы, прицентральный блок управления содерузел микропрограммного управления,узел памяти, узел коммутации, регистр, группу элементов И и формирователь одиночного импульса, причем входы режима первой группы и выходы первой группы узла микропрограммного управления подключены соответственно к входам режима первой группы и к выходам первой группы центрального блока управления, входы режима второй группы и выходы второй группы узла микропрограммного управления подключены соответственно к входам режима второй группы и к выходам второй группы центрального блока управления, выходы третьей и четвертой группы, пеовый выход и входы режима третьей группы узла микропрограммного управления подключены соответственно к информационным входам, к адресным входам, к входу записи решения и выходам узла памяти, выходы пятой группы и входы режима четвертой группы узла микропрограммного управления подключены соответственно к первым входам элементов И группы и к выходам элементов И группы, вторые входы которых подключены соответственно к выходам регистра, информационные входы которого подключены соответственно к входам режима с (Р+1)-го по 2 Р-й центрального блока управления, входы режима с первого по Р-й которого подключены соответственно к информационным входам узла коммутации, выход которого подключен к входу режима узла микропрограммного управления и к входу запуска формирователя одиночного импульса, выход которого подключен к входу записи/чтения регистра, второй выход узла микропрограммного управления подключен к управляющему входу узла коммутации, причем каждый блок управления из группы блоков управления содержит узел микропрограммного управления, узел памяти, два регистра, счетчик, узел коммутации и элемент И, причем в каждом блоке управления группы входы режима первой группы и выходы первой группы узла управления являются входами режима первой группы и выходами первой группы блока управления группы, входы режима с первого по К-й которого подключены соответственно к информационным входам узла коммутации, выход которого подключен к первому входу режима блок управления. группы, (4 К+2)-м выходом которого является выход элемента И, первый выход узла управления подключен к второму входу элемента И, второй выход которого подключен к управляющему входу узла коммутации, выходы второй группы и входы режима второй группы узла управления являются соответственно выходами второй группы и входами режима второй группы блока уп 1837310 28равления группы, входы режима с (К+1)-го по 2 К-й которого подключены соответственно к входам режима с второго по К+1)-й узла управления, выходы с второго по (К 4+1)-й которого подключены соответственно к вы ходам с первого по 4 К-й блока управления группы, информационные входы и выходы узла памяти поключены соответственно к входам режима третьей группы и к выходам третьей группы узла управления, выходы 10 четвертой группы, (4 К+2)-й выход и входы режима четвертой группы которого подключены соответственно к информационным входам, к входу записи/чтения и к выходам первого регистра, выходы пятой группы, 15 (4 К+3)-й выход и входы режима пятой группы узла управления подключены соответственно к информационным входам, к счетному входу и к информационным выходам счетчика. 20 2. Система. по и. 1, о т л и ч а ю щ а яс я тем, что блок обработки содержит узел ассоциативной памяти;триггер, два элемента И, элемент ИЛИ и группу элементов И, 25 причем в каждом блоке обработки информационные входы и выходы группы узла ассоциативной памяти подключены соответственно к информационным выходам блока обработки и к выходам элементов И группы, выход узла ассоциативной памяти является выходом признака готовности блока обработки, подключен к первому входу первого элемента И, второй вход которого является первым входом кода операции блока обработки, выход первого элемента И подклю" чен к входу установки в единицу триггера, вход установки в ноль которого подключен к второму входу кода операции блока обработки, прямой выход триггера является выходом признака наличия информации блока обработки и подключен к первому входу второго элемента И, второй вход которого является третьим входом кода операции блока обработки, выход второго элемента И подключен к первому входу элемента ИЛИ, второй вход элемента ИЛИ является четвертым входом кода операции блока обработки, выход элемента ИЛИ подключен к первым входам элементов И группы, вторые входы которых подключены соответственно к информационным входам блока обработки.1837310 ффмВ актор Н.Коляд оизводственно-издательский комбинат "Патент", г. Ужгород, ул,Гагарина, 10 аказ 2867 ВНИИПИ Гос Составитель Б.БорисовТехред М.Моргентал Корректор М.Куль Тираж Подписноерственного комитета по изобретениям и открытиям при ГКНТ ССС 113035, Москва, Ж, Рауушская наб 4/5группы и выходами первой группы центрального блока управления, входы режима второй группы и выходы второй группы узла микропрограммного управления являются соответственно входами режима второй 5 группы и выходами второй группы центрального блока управления, выходы третьей и четвертой группы, первый выход и входы режима третьей группы узла микроп рограммного управления подключены соответст венно к информационным входам, к адресным входам,.ко входу записи решения и.выходам узла памяти, выходы пятой группы и входы режима четвертой группы узла микропрограммного управления подключе ны соответственно к первым входам элементов И группы и к выходам элементов И группы, вторые входы которых подключены соответственно к выходам регистра, информационные входы которого являются соот ветственно входами режима с (Р+1)-го по 2 Р-й центрального блока управления, входы режима с первого по Р-й которого подключены соответственно к информационным входам узла коммутации, выход которого 25 подключен ко входу режима узла микропрограммного управления и ко входу запуска формирователя одиночного импульса, выход которого подключен к входу записи/чтения регистра, второй выход узла мик-. 30 ропрограммного управления подключен к управляющему входу узла коммутации, причем, каждый блок управления из группы блоков управления содержит узел управления, узел памяти, два регистра, счетчик, 35 узел коммутации и элемент И. причем, в каждом блоке управления группы входы режима первой группы и выходы первой группы узла управления являются входами режима первой группы и выходами первой 40 группы блока управления группы, входы режима с первого по К-й которого подключены соответственно к информационным входам узла коммутации, выход которого подключен к первому входу режима узла управле ния, к первому входу элемента И и является (4 К+1)-м выходом блока управления группы, (4 К+2)-м выходом которого является выход элемента И, выход режима узла управления подключен ко второму входу элемента И, 50 первый выход узла управления подключен к управляющему входу узла коммутации, выходы второй группы и входы режима второй группы узла управления являются соответственно выходами второй группы и входами 55 режима второй группы блока управления группы, входы режима с (К+1)-го по 2 К-й которого подключены соответственно ко входам режима со второго по (К+1)-й узла управления, выходы со второго по (4 К+1)-й которого являются соответственно выходами с первого по 4 К-й блока управления группы, информационные входы, адресные входы, вход записи решения и выходы узла памяти подключены соответственно к выходам третьей группы, выходам четвертой группы, (4 К+2)-му выходу и ко входам режима третьей группы узла управления, выходы пятой группы, (4 К+3)-й выход и входы режима четвертой группы которого подключены соответственно к информационным входам, ко входу записи/чтения и к выходам первого регистра, выходы шестой группы, (4 К+4)-й, (4 К+5)-й, (4 К+6)-й выходы и входы режима пятой группы узла управления подключены соответственно к информационным входам, к счетному входу, к вычитающему входу, ко входу записи и к информационным выходам счетчика, выходы седьмой гоуппы, (4 К+7)-й выход и входы режима шестой группы узла управления подключены соответственно к информационным входам, ко входу записи/чтения и к выходам второго регистра, причем, каждый блок обработки содержит узел ассоциативной памяти, триггер, два элемента И, элемент ИЛИ и группу элементов И, причем, в каждом блоке обработки выходы группы узла ассоциативной памяти являются информационными выходами блока обработки, информационные входы узла ассоциативной памяти подключены к выходам элементов И группы, выход узла ассоциативной памяти является выходом признака готовности блока обработки и подключен к первому входу первого элемента И, второй вход которого является первым входом кода операции блока обработки, выход первого элемента И подключен ко входу установки в единицу триггера, входустановки в ноль которого является вторым входом кода операции блока обработки, прямой выход триггера является выходом признака наличия информации блока обработки и подклюявн к первому входу второго элемента И, второй вход которого является третьим входом кода операции блока обработки, выход второго элемента И подключен к первому входу элемента ИЛИ, второй вход элемента ИЛИ является четвертым входом кода операции блока обработки, выход элемента ИЛИ подключен к первым входам элементов И группы, вторые входы которых являются соответственно информационными входами блока обработки. На фиг. 1, 2 представлена структурная схема ассоциативной однородной вычислительной системы; на фиг. 3 - структурная схема блока обработки ассоциативной однородной вычислительной системы, 1837310При этом, центральный блок управлен содержит узел микропрограммного упр вления 12, узел памяти 13, узел ко мутации 14, регистр 15, группу элементо И 16 и формирователь одиночного ими ьса 17, каждый блок управления из гр ппы блоков управления содержит узел уп авления 18, узел памяти 19, первый и вт рой регистры 20, 21, счетчик 22, узел ко мутации 23 и элемент И 24, причем, центр льный блок управления имеет входы реж ма первой группы 25, выходы первой гр ппы 26, первые Р входов режима 271)27(Р) и вторые Р входов режима 28 1)28(Р), входы режима второй группы 29 и выходы второй группы 30, каждый блок уп авления имеет первые 4 К выходов, соотве ственно, 31(а), 32(а), 33(а), 34(а) (где а=1 К), первые К входов режима 35(1)35 К), вторые К входов режима 26(1)36(К), (4 +1)-й и (4 К+2)-й выходы 37, 38, соответстве но, выходы первой группы 39, входы реж ма первой группы 40, выходы второй гр ппы 41, входы режима второй группы 42,Каждый блок обработки ассоциативной од ородной вычислительной системы (фиг, 3) одержит узел ассоциативной памяти 43, тр ггер 44, два элемента И 45, 46, элемент И И 47 и группу элементов И 48.При этом, элементы, узлы и блоки ассоци тивной однородной вычислительной си ст мы соединены следующим образом,Входы кода операции 2 - 5, выходы и ризн ка готовности и признака наличия инфо мации 6, 7, информационные входы и ин ормационные выходы 8, 9 блока абра бо ки а-го столбца в-й строки матрицы 1(ав) (гд а=1,.,К; в=1Р)(фиг. 1,2) подключены со тветственно к выходам 31(а), 32(а), 33(а), 34( ), входам режима 35(а), 36(а), выходам пе вой группы 39 и входам режима первой 5 гр ппы 40 в-го блока управления 10(в) группы 10, выходы второй группы 41, входы режи а второй группы 42, выходы 37, 38 ко орого подключены соответственно к входаь режима первой группы 25, к выходам Ассоциативная однородная вычислительная система (фиг. 1, 2) содержит матриц размером РхК (где Р - число аргументов уифицируемых предикатов, К - число и ред катов) блоков обработки. 1(11), 1( 1), 1(К 1)1(1 Р), 1(КР), каждый из кото ых имеет, соответственно, первый 2, втор й 3, третий 4 и четвертый 5 входы кода о ерации, выходы признака готовности 6 и и изнака наличия информации 7, информац онные входы 8 и информационные выход 9, группу Р блоков управления 1 1)10(Р) и центральный блок управлен 11. первой группы 26, к входам режима 27(в), 28(в) центрального блока управления 11, входы режима второй группы 29 и выходы второй группы 30 которого являются соот ветственно входами кода операции и информационными выходами системы.Входы режима первой группи и выходыпервой группы узла микропрограммного управления 12 являются соответственно вхо дами режима первой группы 25 и выходамипервой группы 26 центрального блока управления 11, входы режима второй группы и выходы второй группы узла микропрограммного управления 11 являются соответ ственно входами режима второй группы 29и выходами второй группы 30 центрального блока управления 11, выходы третьей и четвертой группы, первый выход и входы режима третьей группы узла микропрограммного 20 управления 12 подключены соответственнок информационным входам, кадресным входам, ко входу записи решения к выходам узла памяти 13, выходы пятой группы и входы режима четвертой группы узла микро программного управления 12 подключенысоответственно к первым входам элементов И группы 16 и к выходам элементов И группы 16, вторые входы которых подключены соответственно к выходам регистра 15, ин формационные входы которого являютсясоответственно (Р+1)-м,2 Р-м входами режима 28(1),28(Р) центрального блока управления 11, 1-йР-й входы режима 27(1)27(Р) которого подключены соответ ственно к информационным входам узлакоммутации 14, выход которого подключен ко входу режима узла микропрограммного управления и ко входу запуска формирователя одиночного импульса 17, выход которо го подключен к входу записи/чтениярегистра 15, второй выход узла микроп рограммного управления подключен к управляющему входу узла коммутации 14.Входы режима первой группы и выходы 5 первой группы узла управления 18 каждогоблока обработки группы 10 являются входами режима первой группы 40 и выходами первой группы 39 блока управления группы 10, 1-й,К-й входы режима 35(1),.,35(К) ко торого подключены соответственно к информационным входам узла коммутации 23, выход которого подключен к первому входу режима узла управления 18, к первому входу элемента И 24 и является (4 К+1)-м выхо дом 37 блока управления группы 10, (4 К+2)-мвыходом 38 которого является выход элемента И 24, выход режима узла управления 18 подключен ко второму входу элемента И 24, первый выход узла управления 18 подключен к управляющему входу узла комму 1837310510 15 20 25 30 35 45 50 55 тации 23, выходы второй группы и входы режима второй группы узла управления 18 являются соответственно выходами второй группы 41 и входами режима второй группы 42 блока управления группы 10, (К+1)-й,2 К-й. входы режима 36(1),36(К) которого подключены соответственно ко входам режима со второго по (К+1)-й узла управления, выходы со второго по (4 К+1)-й которого являются соответственно 1-м 4 К-м выходами 31(а), 32(а), 33(а), 34(а) (где а=1, , К) блока управления группы 10, информационные входы, адресные входы, вход записи решения и выходы узла памяти 19 подключены соответственно к выходам третьей группы, всчходам четвертой группы, (4 К+2)-му выходу и ко входам режима третьей группы узла управления 18, выходы пятой группы, (4 К+3)-й выход и входы режима четвертой группы которого подключены соответственно к информационным входам, ко входу записи/чтения и к выходам первого регистра 20, выходы шестой группы, (4 К+4)-й, (4 К+5)- й, (4 К+6)-й выходы и входы режима пятой группы узла управления 18 подключены соответственно к информационным входам, к счетному входу, к вычитающему входу, ко входу записи и к информационным выходам счетчика 22, выходы седьмой группы, (4 К+7)- й выход и входы режима шестой группы узла управления 18 подключены соответственно к информационным входам, ко входу записи/чтения и к выходам второго регистра 21,Выходы группы узла ассоциативной па. мяти 43 блока обработки 1(ав) (где а=1,.,К,в=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 блока обработки а-го столбца в-й строки 1(ав) (где а=1 К) хранятся символы, относящиеся к одному аргументу, расположенному на в-м месте а-го предиката.Далее, унификация термов выполняется циклически, причем, количество циклов за 40 висит от исходных данных (термов), но не может превышать количества разноименных переменных,Цикл начинается с проверки тождественности предикатов, заключающийся в сравнении всего множества аргументов по строкам, которое выполняется во всех строках одновременно под управлением блоков управления 10(в). В Р-й строке матрицы выполняется операция обнуления ячеек узлов ассоциативной памяти 43 блоков обработки 1 (аР) (где а=1 К) под управлением блока управления 10(Р). При этом, центральный блок управления 11 осуществляет синхронизацию работы блоков управления 10(в) путем циклического последовательного опроса блоков управления 10(в) по выходам группы 26 с целью получения от них со входов режима 25 сигнала об окончании проверки тождественности термов в в-й строке.Проверка тождественности предикатов в троках матрицы выполняется следующим о разом. Узлы управления 18 всех блоков управления 10(в) пересылают из узлов памяти 19 максимальное значение уровня вхож д ния в счетчик 22 для организации ц клического выполнения в пределах своей в- строки следующей последовательности д йствий.Выбор из блока обработки символа с 10 за анным уровнем вхождения. Производится поиск данных в блоках обработки в-й ст оки по ассоциативному признаку - ураве ьвхождения, взятого из счетчика 22 (фиг. 2) передача слова, удовлетворяющего дан н у признаку в регистр 20. При этом, в на але поиска осуществляется обнуление тр ггеров 44 путем одновременной подачи бл ком управления 10(в) сигналов на входы 3 лаков обработки в-й строки (фиг, 3), По ис и выдача из блока обработки слова, уд влетворяющему заданному ассоциативно у признаку, состоит из следующем. Паис может производиться в пределах всей м рицы или только одной строки. В первом 25 сл чае код опроса вырабатывает централь.нь й блок управления 11, который с выходов гр ппы 26 пересылает его на входы режима гр ппы 42 блоков управления группы 10 и, да ее, в узлы управления 18, Во втором слу ча код опроса формирует узел управления 18 Узел управления 18 с выходов 34(а) пасы ает на входы кода операции 5 блоков об аботки данной строки сигналы разрешени приема, а на информационные входы 8 35 ко опроса.Если требуется не только обнаружить на ичие данных, но и установить номера бй ков обработки где они хранятся, то блок уп авления .группы 10 подает разрешаю щ й сигнал также на входы кода операции 2 оков обработки (фиг. 1). После выполнени операции ассоциативного поиска на выхо ах признака готовности 6 тех блоков об аботки, где имеются искомые данньи, 45 бу ет сформирован сигнал ответа, который пе еведет в единичное состояние триггер 44 фиг. 3), а также поступи через выход 6 бл ка обработки а-го столбца в-й строки 1(а ) на вход режима 35(а) блока управления 50 10( ) и там на вход узла коммутации 23 (фиг. 2).,В процессе поиска на управляющий вход узла коммутации 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 блоков обработки 1(ав) с выходов 31(а) блоков управления О(в) только при наличии сигнаЛа ОтВЕта С ВЫХОДа УЗЛа аССОЦИатИВНОй Памяти 43. Выбор данных из такого а-го блока обработки Осуществляется подачей на вход кода операции 5 сигнала с выхода 34(а) блока управления 10(в) (фиг. 2), па которому код опроса проходит на информационные входы группь; узла ассоциативной памяти 43 только а-го блока обработки 1(ав), следовательно, на информационных выходах 9 появятся данные только зтога блока обработки, которые и примет блок управления 10(в),Выявление наличия данных одновременно ВО всех блоках обработки строки или матрицы, удовлетворяющих заданному ассоциативному признаку, выполняется ана12 1837310 10 20 25 30 35 40 45 50 логично, описанным выше действиям с той лишь разницей, что узлы 12, 18 вырабатывают управляющие сигналы, соответствующие выполнению в узлах коммутации 14,23 операции И,Производится опрос блоков обработки в-й строки по коду опроса, равному содержимому регистра 20, с целью поиска одинаковых символов, Узел коммутации 23 выполняет операцию И. Результат поступает на первый вход режима узла управления 18 и с выхода 37 на вход 27(в) центрального блока управления 11 в узел коммутации 14, Производится анализ результата конъюнкции узлом управления 18, Если он равен нулю, то в пределах данной строки термы не унифицируемы. В этом случае узел управления 18 удерживает на выходах группы 39 код опроса, на выходах 34(а) (где а=1 К) разрешающий сигнал и на первом выходе сигнал операции И узла коммутации 23 до .тех пор, пока центральный блок управления 11 не закончит проверку на тождественность предикатов. При этом, узел управления 18 готовит сигнал ответа об окончании проверки и при обращении к нему центрального блока управления 11 выдает его с выходов .группы 41. Если результат конъюнкции равен единице, то выполняется следующее. Узел управления 18 уменьшает содержимое счетчика 22 на единицу и проверяет его содержимое. Если оно равно нулю, то, так же как при анализе результатов опроса блоков обработки, узел управления 18 удерживает на вышеперечисленных выходах сигналы и формирует сигнал об окончании проверки на тождественность термов в данной строке. Если содержимое счетчика 22 не равно нулю, то узел управления 18 выбирает из блока обработки символ с заданным уровнем вхождения, Как только все блоки управления 10(в) (где в=1Р) закончат свои проверки, узел микропрограммного управления 12 (фиг. 2) закончит проверку на тождественность всего мнокества предикатов путем подачи со второго выхода управляющего сигнала операции И для узла коммутации 14, единичный результат которой означает, что унифицируемые предикаты тождественны, о чем на информационные выходы 30 системы выдается сигнал и производится последовательная выдача пользователю термов всех предикатов начиная с первой строки первого блока обработки и заканчивая (Р)-строкой, На этом работа системы заканчивается, В случае нулевого результата операции И осуществляется проверка наличия переменных в множестве термов одновременно во всех строках матрицы под управлением центрального блока управления 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ни ное состояние будут указывать мнокество строк, связанных одной переменной (переменной, имя которой содержится в узлах ас оциативной памяти 43 блоков обработки зт х строк). В этом случае узел микропрог ра много управления 12 прекращает перебо переменных и с выходов группы 26 вы ает команду о начале определения типа по становок и их выполнение для связываю ей переменной в блоки управления, для 10 ко орых разряды регистра 15 установлены в ед ничное состояние. При нулевом значени дизъюнкции узел управления 18 строки, из оторой была извлечена предыдущая пере енная, продолжает анализ входов режи ма 6(а)(где а=1 К) блока управления 10(в), Если на всех входах 36(а) сигналы отсутствуют узел управления 18 выдает сигнал в узел ми ропрограммного управления 12 об исче пании всех переменных вданной строке. 20 В том случае узел микропрограммного упра ления 12 переходит к анализу содержимо о следующего разряда регистра 15, По ок нчании просмотра содержимого регистра 5, что означает отсутствие в множестве 25 те мов переменных с перекрестными связя и, центральный блок управления 11 выда т команду в блоки управления 10(в) (где в= ,Р) об окончании перебора переменны и о начале выполнения подстановок 30 (ун фикации) одновременно во всех строках ма рицы. Выполняются следующие типы подстано ок: переменная вместо других перемен нь; константа вместо переменных; фу кция вместо переменных,Если при наличии перекрестных связей не бходимо выполнять подстановку после него типа, то системой анализируется 40 стр ктура аргументов функции, которые выбр ны в качестве кандидатов для подстано и вместо связывающей переменной в различных строках, а затем определяется сре и этих подстановок наиболее общая, 45 Эт аналогично поиску подстановки в одной стр ке при отсутствии перекрестных свяй и ее выполняют блоки обработки, вхоие в Р-ю строку, и соответствующийо управления 10(Р). 50Далее, в,счетчик 22 узел управления 18 зап сывает значение уровня вхождения им ни связывающей переменной из регистра 0 только для тех блоков управления 10( ), в строках которых содержится связы ва щая переменная. Если перекрестных свя ей нет, то узлы управления 18 всех блоков управления 10(в) записывают в свои сче чики 22 уровень вхождения равный единице. Производится сравнение содержимо зе дя бл го счетчика 22 с максимальным уровнем вхождения символа для данной строки, хранящимся в узле памяти 19, Если содержимое счетчика 22 в каком-либо блокеравления окажется больше максимального значения уровня вхождения, что означает данный блок управления закончил просмотр возможных подстановок, то он информирует центральный блок управления 11, что он готов к проверке на тождественность предикатов. Если содержимое счетчика 22 меньше или равно, производится опрос блоков обработки в-й строки по коду опроса одновременно по признаку переменной и уровню вхождения и формирование диэьюнкции ответов, Если в какой-либо строке не обнаружена переменная, то соответствующий блок управления 10(в) определяет тождественность символов в строке на заданном уровне вхождения, Блоки управления в строках которых имеются такие переменные, выполняют следующее. Блок управления 10(в) производит обнуление триггеров 44 всех блоков обработки в-й строки и осуществляет их опрос по коду опроса, соответствующему ассоциативным признакам - уровень вхождения и константа. Узел управления 18 формирует дизьюнкцию ответов в узле коммутации 23. При этом производится запоминание ответов в триггерах 44 (фиг. 3), Если результатдизьюнкции равен единице, то сигналы с входов 36(1)36(К) записываются в регистр 21 (фиг, 2), после чего блок управления 10(в) выполняет прием константы и опрос блоков обработки строки по ее имени и заданному уровню вхождения. В случае нулевого результата дизьюнкции проверяется наличие в строке функции на заданном уровне вхождения и обнуляются триггеры 44 блоков обработки. На основе анализа сигналов с информационных выходов 7 блоков обработки блок управления 10(в) путем подачи сигнала на вход 5 принимает символ константы на регистр 20. Далее блок управления 10(в) производит опрос блоков обработки по коду опроса соответствующего признакам уровень вхождения и имя константы из регистра 20 с записью результатов в триггеры 44, После этого блок управления 10(в) осуществляет поразрядное сравнение входов 36(1).,36(К) и разрядов регистра 21, В случае их совпадения, что означает тождественность (равенство) констант между собой обнуляет триггеры 44, и определяет наличие функций в строке на заданном уровне вхождения. Если совпадения не произошло, то константы в-йстроки не тождественны, что означает невозможность унификации термов в в-й строке. блок10 15 20 2530 35 4550 управления 10(в) (где в=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. 8 случае наличия перекрестной связи тип подстановки вместо связывающей переменной вместе с именем переменной из регистра 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 командой для запоминания символа связывающей пере 17 1837310м нной в узле памяти 13, чтобы в последующ м при выполнении поиска перекрестной связи не принимать во внимание эту уже проверенную переменную. При этом узел микропрограммного управления 12 получив отодного иэ блоков управления 10(ав) в реэу ьтате поиска переменных очередную пер менную для анализа сравнивает ее имя с и енами проверенных на перекрестную связь переменных из узла памяти 13, В случае совпадения узел микропрограммного у авления 12 далее ее не анализирует и 5 10 бирает очередную переменную. Это буравносильно выполнению вместо свяающей переменной подстановки типа - 15 еменная. Далее выполняется очередной л унификации, начинающийся с проки тождественности предикатов. Если аультат дизьюнкции ответов дополниьной проверки равен единице, то блок 20 авления 10(Р) выполняет проверку налив Р-й строке символа с типом подстановконстанта,При поиске в Р-й строке символа с ти подстановки - функция блок управлея 10(Р) производит опрос блоков аботки по коду опроса тип подстановки ункция и формирует дизьюнкцию отве; В случае единичного результата блок 30 авления 10(Р) проверяет наличие симвос типом подстановки - константа, в проном случае проверяет тождественность стант в Р-й строке, Для проверки налив Р-й строке символа с типом подста нов - константа блок управления 10(Р) тавляет на выходы группы 39 код опросаподстановки - константа, единичный нал на все выходы 33(1)33(К). При этом ут опрашиваться только те узлы ассоци аной памяти 43, для.которых триггеры 44 ановлены в единичное состояние, Блок авления 10(Р) формирует диэьюнкцию етов в узле коммутации 23, Если резульравен единице, то унификация невоз на и блок управления 10(Р) выдает бщение в центральный блок управления в противйом случае выполняется подстака функции вместо связывающей переной. 50 При проверке тождественности конт в Р-й строке блок управления 10(Р) логично другим блокам управления 10(В) в=1 Р) определяет наличие констанстроке на заданном уровне вхождения 55 инимает ее. При этом, при формировакода опроса в качестве признаков исьзуются тип подстановки - константа иконстанты, В результате в регистре 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, Далее блок управления 10(в) сравнивает содержимое счетчика 22 (фиг, 2) с единицей, Если ано равно единице или данный блок управления 10(в) выполняет действия для устранения перекрестной связи, та он выдаетс выходов группы 41 сигнал о своей готовности к проведению проверки предикатов на тождественность. В противном случае узел управления 18 даннога блока управления уменьшает содержимое счетчика 22 на единицу и переходит к опре