Устройство управления логическим выводом

 

Изобретение относится к вычислительной технике и может быть использовано при разработке устройства, выполняющего функции логического вывода. Цель изобретения - увеличение быстродействия устройства управления выводом за счет распараллеливания процесса унификации. Устройство содержит N блоков 1 обработки данных, блок 2 памяти, N блоков 3 управления, два блока 4 управления доступом и регистр 5„ Устройство имеет вход 6 данных, первый вход 7 синхронизации, N входов 8 аргумента, N входов 9 разрешения записи,N входов 10 установки в О, N информационных выходов 11, N выходов 12 констант, N выходов 13 переменных, второй вход 14 синхронизации. Блок 1 обработки данных имеет группу входов 15 микрокоманды , группу выходов 16 признаков, вход 17 аргумента, вход 18 разрешения записи, вход 19 установки в О, информационный выход 20, выход 21 констант, выход 22 переменных, первый выход 23 ссылки, вход 24 альтернативной ссылки, вход 25 ссылки на последующий элемент, вход 26 ссылки на предикат, вход 27 ссылки . на список предикатов-аргументов, второй выход 28 ссылки и вход 29 конечного состояния. Блок 4 управления доступом имеет 2N входов 30 запросов , тактовыь вход 31 и N+1 выходов 32 размещения доступа. 3 ил. (Л 35 Јь N3 -U О5 &

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

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

РЕСПУБЛИК (19) Ш) (1)5 G 06.F 9/44, 3/00

ОЛИСАНИЕ ИЗОБРЕТЕНИЯ

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

У

ГОСУДАРСТВЕННЫЙ НОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР (21) 4381332/24 (22} 22.02.88 (46) 15.04.91. Бюп. № 14

{71) Минский радиотехнический институт (72). В.А. Вишняков, В.И. Хведчук, А.3. Банцевич и Л.Д. Перельмутер (53) 681 325(088.8) (56) Заявка WO № 851057111, кл. Г, 06 F 15/46, 1986.

Заявка EP ¹ 0104487, кл. С 06 F 9/44, 1986. (54) УСТРОЙСТВО УПРАВЛЕНИЯ ЛОГИЧЕСКИМ

ВЬ 30 J1;0N (57) Изобретение относится к вычислительной технике и может быть ис пользовано при разработке устройства, выполняющего функции логического вывода. Пель изобретения — увеличение быстродействия устройства управ. ления выводом за счет распараллеливания процесса унификации. Устройство содержит N блоков 1 обработки данных, блок 2 памяти, N блоков

3 управления, два блока 4 управления доступом и регистр 5. Устройство имеет вход 6 данных, первый вход 7 синхронизации, N входов 8 аргумента, N входов 9 разрешения записи,N входов

10 установки в "0", N информационных выходов 11, N выходов 12 констант, N выходов 13 переменных, второй вход ! 14 синхронизации. Блок 1 обработки данных имеет группу входов 15 микро-. команды, группу выходов 16 признаков, вход 17 аргумента, вход 18 разрешения записи, вход 19 установки в

"0", информационный выход 20, выход

21 констант, выход 22 переменных, первый выход 23 ссылки, вход 24 альTPPHBTHBHoH b KH, xc 25 ccblTIKH на последующий элемент, вход 26 ссылки на предикат, вход 27 ссылки, на список предикатов-аргументов, второй выход 28 ссылки и вход 29 конечного состояния. Блок 4 управления доступом имеет 2N входов 30 запросов, тактовый вход 31 и 11+1 выходов

32 размещения доступа. 3 ил.

1642466

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

Цель изобретения — увеличение быстродействия устройства управления логическим выводом за счет распараллеливания процесса унификации. 10

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

Устройство управления логическим выводом содержит N блоков 1 обработки данных, блок 2 памяти, N блоков 3 управления, два блока 4 управления доступом, и регистр 5.и имеет вход 6 20 данных, первый вход 7 синхронизации, N входов 8 аргумента, N входов 9 разрешения записи, N входов 10 установки в "0", N информационных выходов 11, N выходов 12 констант, N выходов 25

13 переменных и второй вход 14 синхронизации.

Блок 1 обработки данных имеет группу входов 15 микрокоманды, группу выходов 16 признаков, вход 17 аргу- 30 мента, вход 18 разрешения. записи, вход 19 установки в "0", информационный выход 20, выход 21 констант, выход 22 переменных, первый выход 23 ссылки, вход 24 альтернативной ссылки, вход 25 ссылки на последующий элемент, вход 26 ссыпки на предикат, вход 27 ссылки .на список предикатов— аргументов, второй выход 28 ссылки. и вход 29 конечного состояния. 40

Блок 4 управления доступом имеет

2N входов 30 запросов, тактовый вход

31 и И+1 выходов 32 разрешения доступа.

Блок 1 унификации (фиг. 2) содер- 45 жит два мультиплексора 33 и 34, одиннадцать регистров 35-45, четыре блока

46-49 стековой памяти, два триггера

50 и 51, схему 52 сравнения и четыре элемента И 53-56. 50

Блок 4 управления доступом (фиг.3) включает регистр 57, мультиплексор

58, элемент И 59, счетчик 60, дешифратор 6 1 и элемент ИЛИ 62.

Устройство. работает следующим образом.

Перед началом работы блока 1 обработки данных все его элементы с тристабильными выходами переведены в отключенное состояние, Первый триггер 50 установлен в единичное состояние, и блок 1 находится в состоянии "Стоп".

На первом этапе работы блока 1 первый триггер 50 переводится в нулевое состояние„ Далее первый блок

46 стековой памяти переводится в активное состояние, указатель первого блока 46 стековой памяти устанавливается в полажение "0", после чего в блок 46 заносится первая половина множества рассогласования. Это множество состоит из аргументов того предиката, который все блоки 1 будет использовать на данном шаге доказательства в качестве первого элемента из пары предложений, над которой выполняется попытка унификации. Затем блок 46 стековой памяти переводится в отключенное состояние.

На втором этапе работы блока 1 выполняется формирование во втором блоке 47 стековой памяти второй половины множества рассогласования.

Сначала блок 1 обращается к регистру 5 с помощью своего блока 3 управления. Содержимое регистра 5 через второй вход первого мультиплексора 33 заносится в первый регистр 35. Сигнал на выходе первого элемента И 53 определяет, является ли занесенное в первый регистр 35 значение кодом "Конец". Если да (уровень "1" на выходе элемента И 53), то это означает, что новых предложений с нужным именем предиката в базе знаний больше нет. В этом случае блок 1 с помощью своего блока 3 управления освобождает регистр 5, затем устанавливает первый триггер 50 ,в единичное состояние и переходит в

1 состояние, в котором он находился перед началом работы, т.е. первый триггер 50 переводится в состояние

"1", а все тристабильные элементы— в отключенное состояние. После этого блок 1 переходит к выполнению первого этапа работы. Если же занесенное в первый регистр 35 значение не является кодом "Конец" ("0" на выходе первого элемента И 53), то блок 1 переходит непосредственно к формированию второй половины множества рассогласования. Это происходит следующим образом.

С помощью своего блока 3 управления блок 1 получает доступ к блоку 2

5 i6 памяти и считывает оттуда информацию по адресу, находящемуся в первом ре— гистре 35„Считывание производится одновременно в первый 35, второй 36 и третий 37 регистры, После этого содержимое первого регистра 35 пересылается в четвертый регистр 38, а оттуда — в регистр 5. Содержимое третьего регистра 3? передается в одиннадцатый регистр 45, после чего анализируется сигнал на выходе третьего элемента И 55, Гсли он равен единице, то это означает, что в одиннадцатый регистр 45 передан код Конец 1, т.е. данный предикат не содержит аргументов. В этом случае блок 1 сразу переходит к выполнению шестого этапа работы. Если же сигнал на выходе третьего элемента И 55 равен нулю, то это означает, что список аргументов предиката не пуст.

В этом случае блок 1, получив доступ к блоку 2 памяти, считывает информацию по адресу, содержащемуся во втором регистре 36. Считанная информация заносится в первый 35, второй 36 и третий 37 регистры. Затем содержимое второго регистра 36 загружается во второй блок 47 стековой памяти и выполняется инкремент указателей первого и второго блоков 46 и 47 стековой памяти„ Далее анализируется сигнал на выходе первого элемента

И 53. Если он равен единице, то в первом регистре 35 находится код

1 Конец", т„е, список аргументов исчерпан, и блок 1 переходит к выполнению третьего этапа работы,„ Если же сигнал на выходе первого элемента И 53 равен нулю, то блок 1 считы— вает информацию по адресу, содержа— щемуся в первом регистре 35. Информация заносится в первый 35, второй 36 и третий 37 регистры. Затем блок 1 выполняет загрузку во второй блок 47 .стековой памяти и инкремент указателей первого и второго блоков 46 и 47 стековой памяти. Цикл продолжается до тех пор, пока в первом регистре

35 не окажется код "Конец", формирующий уровень "l" на выходе первого элемента И 53.

42466

Третий этап работы блока 1 заключается в подготовке блоков 48 и 49 стековой памяти к очередному циклу унификации. Для этого указатели

5 обоих стеков устанавливаются в положение "О", затем седьмой регистр 41 переводится.в активное состояние и в него заносится код Конец". После этого код "Конец" с выхода седьмого регистра 4 1 записывается в блоки 48 и 49. Затем производится инкремент указателей обоих блоков 48 и 49.

Четвертый этап работы блока 1 является основным. На этом этапе и выполняется собственно унификация.

Сначала из первого и второго блоков 46 и 47 стековой памяти считывается по одному аргументу. Зти аргу20 менты пересылаются в девятый и десятый регистры 43 и 44 соответственно.

Затем содержимое этих регистров сравнивается с помощью схемы 52 сравнения. Результат сравнения " 1", если есть равенстго, и 0", если равенства нет) заносится во второй триггер 51.

При выборке текущей пары аргументов возможны четыре случая в зависимости от того, является ли каждый из аргументов переменной или константой:

1) оба аргумента — константы. Тогда, если они равны, тс блок 1 сразу

35 переходит к пятому этапу работы, а если они не равны, то унификация невозможна и блок 1 осуществляет переход к второму этапу работы;

2) первый аргумент — константа, 40 второй — переменная, В этом случае блок выполняет проверку, содержится ли данная переменная в блоке 48 стековой памяти. Если нет, то второй аргумент заносится в блок 48, а

45 первый аргумент — в блок 49. Гсли да, то выполняется проверка, равны ли между собой первый аргумент и константа из блока 49, соответствующая переменной из блока 48. Если

50 равны, то блок 1 переходит к пятому этапу работь., а если не равны, то унификация невозможна и блок 1 переходит к второму этапу работы;

Таким образом, по окончании второго этапа работы блока 1 во втором блоке 47 стековой памяти сформирована вторая половина множества рассогласования„

3) первый аргумент — переменная, второй — константа. В том случае выполняются аналогичные действия, только первый аргумент используется вместо второго и наоборот;

7 1642466

Содерхымое одиннадцатого регистра 45 и блоков 48 и 49 запоминается на внешних элементах памяти и передается впоследствии на блок 1 для

55 обработки.

После передачи на соответствующие выходы содержимого одиннадцатого регистра 45 и блоков 48 и 49 блок

4) оба аргумента †. переменные.

В этом случае, если они равны между собой, то выполняется переход к пятому этапу работы. Если же нет, то возможны три случая: а) обе переменные не содержатся в блоке 48. Тогда сразу выполняется переход к пятому этапу работы блока 1; 10 б) обе переменные содержатся в блоке 48. Тогда, если соответствующие им константы из блока 49 равны межцу собой, выполняется переход к пятому этапу работы, а если нет, 15 то унификация невозможна, и блок 1 переходит к второму этапу работы; в) если в блоке 48 стековой памяти содержится только одна из двух переменных, то вторая переменная так- 20 же заносится в блок 48, а в блок 49 заносится константа, соответствующая той переменной, которая содердалась в блоке 48. После этого блок

1 переходит к пятому этапу работы. 25

На пятом этапе работы блока 1 выполняется анализ сигнала на первом выходе первого блока 46 стековой памяти. Если этот сигнал равен "1", то блок

46 пуст, т.е. список аргументов исчерпан. В этом случае блок 1 переходит к выполнению шестого этапа работы. Если же сигнал на первом выходе- блока 46 равен "0", то блок 1 осуществляет переход к четвертому этапу работы, т.е. к обработке очередной пары аргументов„

На шестом этапе работы блока 1 вначале анализируется сигнал на выходе третьего элемента И 55. Если этот сигнал равен ."1", то это означает., что в одиннадцатом регистре 45 находится код Конец, т. е. унификация завершена успешно и получено пустое предложение„ После этого блок 1 45 переходит к выполнению второго этапа работы. Если же сигнал на выходе третьего элемента И 55 равен "0", то это означает, что при проведении унификации возникла подцель.

1 переходит к выполнению второго этапа работы.

Блок 4 управления доступом работает следующим образом.

В исходном состоянии все разряды регистра 57 обйулены. На входах элемента ИЛИ 62 находятся сигналы низкого логического уровня. На вход 31 блока 4 поступают тактовые импульсы.

Счетчик 60 циклически изменяет свое состояние под воздействием тактовых импульсов на своем счетном входе„

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

58 на его выход.

В таком режиме блок 4 работает до тех пор, пока на одном из входов регистра 57 не появится сигнал уровня "1" (например, íà j-ом входе).

Этот сигнал, являющийся запросом от j-ro блока 3 управления, передается на j-й вход мультиплексора 58.

Когда мультиплексор 58, управляемый счетчиком 60, передаст этот сигнал (с инверсией) на второй вход элемента И 59, поступление тактовых импульсов на вход счетчика 60 блокируется.

В результате возбуждается j-й выход дешифратора 61 разрешения доступа и удерживается в возбужденном состоянии. Затем íà j-й вход элемента

ИЛИ 62 поступает сигнал уровня "1" от j-го блока 3 управления (сигнал записи информации в регистр 5). После этого значения сигналов на j-м входе элемента ИЛИ 62 и на j ì входе регистра 57 устанавливаются в "0".

При установке j-ro разряда регистра 57 в состояние "0" на выходе мультиплексора 58 появляется значение

"1", так как счетчик 60 находится в состоянии, обеспечивающем передачу информации с j-ro входа мультиплексора

58 на выход мультиплексора 58. В результате открывается элемент И 59 и тактовые импульсы, поступающие на его первый вход, проходят на ход счетчика 60. Счетчик 60 снова начинает с проходом каждого тактового импульса изменять свое соСтояние, осуществляя последовательный перебор двоичных комбинаций на (п+1)-м входе мультиплексора 58 и на входе дешифратора 61. Если теперь i-й разряд (i+j} регистра 57 находится в состоянии

1642466

"1", то при передаче информации с

j-го входа мультиплексора 58 на его выход элемент И 59 снова закрывается и в возбужденном состоянии оказывается i-й выход дешифратора 61 до тех пор, пока i-й разряд регистра 57 не установится в состояние 1 0 .

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

Устройство управления .логическим выводом, содержащее блок обработки данных, блок памяти, блок управления, причем вход данных блока памяти явля-15 ется входом данных устройства, синхровход блока управления является первым входом синхронизации устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия 20 устройства за счет распараллеливания процесса обработки информации в блоке обработки данных, в устройство введены N — 1 блоков обработки данных, N-1 блоков управления (где N — число од- 25 новременно выполняемых действий над информацией), два блока управления доступом и регистр, причем синхровходы всех блоков управления объединены, группы выходов микрокоманды и входов признаков i-ro блока управления (i = 1, N) подключены к соответствующим группам входов микрокоманды и выходов признаков 1.-го блока обработки данных, входы аргумента, разрешения записи и установки в

"0" i-го блока обработки данных являются соответственно 1-ми входами аргумента, разрешения записи и установки в 0 . устройства, информацион- 40 ный выход, выход констант и выход переменных i-го блока обработки данных являются соответственно -м информационным выходом, i-м выходом констант и 1.-м выходом перем «ных .устройства, первые выходы ссылки всех блоков обработки данных подключены к информационному входу регистра, выход которого подключен к входам альтерHàòèâíeé ссылки всех блоков обработки данных, первый информационный выход блока памяти подключен к входам ccblTIKH на последующий элемент всех блоков обработки pBHHbDc второй информационный выход блока памяти подключен к входам ссыпки на предикат всех блоков обработки данных, третий информационный выход блока памяти подключен к входам ccbUI ки на список предикатов-аргументов всех блоков обработки данных, вторые выхопы ссыпки всех блоков обработки данных: подключены к адресному входу блока памяти i-й выход разрешения доступа первого блока управления доступом (i = 1, N) подключен к первому входу разрешения доступа z-го блока управления, i-й выход разрешения доступа второго блока управления доступом подключен к второму входу разрешения доступа i-ro блока управления, (N+1) é выход разрешения доступа первого блока управления доступом подключен к синхровходу регистра, (N+1) é выход разрешения доступа второго блока управления доступом подключен к входу разрешения записи блока памяти, выход управления ссылкой и выход управления установкой в "0" i-го блока управления подключены соответственно к (2i-1)му и 2i-му входам запросов первого блока управления доступом, выход управления разрешением записи и выход ,управления аргументом i-го блока управления подключены соответственно к (2i — 1) -му и 2i-му входам запросов второго блока управления доступом, тактовые входы бпоков управления доступом подключены к второму входу синхронизации устройства, выход конечного состояния i-го блока управления подключен к входу конечного состояния i-ro блока обработки данных„

1642466

32

Составитель С. Авервянова

Техред С,Мигунова Корректор Л. Пилипенко

Редактор А. Лежнина

Заказ 1148 . Тираж 414 Подписное

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

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

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