Устройство управления логическим выводом Советский патент 1991 года по МПК G06F9/44 G06F3/00 

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

ВЫВОДЗо

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

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

Устройство управления логическим выводом содержит 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 разрешения доступа.

Блок 1 унификации (фиг„ 2) содер- жит два мультиплексора 33 и 34, одиннадцать регистров 35-45, четыре блока 46-49 стековой памяти, два триггера 50 и 51, схему 52 сравнения и четыре элемента И 53-56„

Блок 4 управления доступом (фиг.З) включает регистр 57, мультиплексор 58, элемент И 59, счетчик 60, дешифратор 61 и элемент ИЛИ 62.

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

Перед началом работы блока 1 обработки данных все его элементы с тристабильными выходами переведены

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

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

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

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

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

5

памяти и считывает оттуда информаци по адресу, находящемуся в первом регистре 35о Считывание производится одновременно в первый 35, второй 36 и третий 37 регистры. После этого содержимое первого регистра 35 пересыпается в четвертый регистр 38, а оттуда - в регистр 5. Содержимое третьего регистра 37 передается в одиннадцатый регистр 45, после чего анализируется сигнал на выходе третьего элемента И 55, Если он равен единице, то это означает, что в одиннадцатый регистр 45 передан код

Конец1

данный предикат не

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

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

0

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

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

Сначала из первого и второго блоков 46 и 47 стековой памяти считывается по одному аргументу. Эти аргументы пересылаются в девятый и десятый регистры 43 и 44 соответственно. Затем содержимое этих регистров сравнивается с помощью схемы 52 сравнения. Результат сравнения 1, если 5 есть равенство, и 0, если равенства нет) заносится во второй триггер 51 о

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

5

0

0

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

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

2)первый аргумент - константа, второй - переменная, В этом случае

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

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

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

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

71

4) оба аргумента - переменные. В этом случае, если они равны между собой, то выполняется переход к пятому этапу работы Если же нет, то возможны три случая:

а)обе переменные не содержатся в блоке 48 о Тогда сразу выполняется переход к пятому этапу работы блока 1;

б)обе переменные содержатся в блоке 48. Тогда, если соответствующие им константы из блока 49 равны между собой, выполняется переход к пятому этапу работы, а если нет,

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

в)если в блоке 48 стековой памяти содержится только одна из двух переменных, то вторая переменная так же заносится в блок 48, а в блок 49 заносится константа, соответствующая той переменной, которая содер- далась в блоке 48. После этого блок

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

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

пу работы . к обработке очередной пары аргументов

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

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

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

8

5

0

5

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-ro блока 3 управления (сигнал записи информации в регистр 5)„ После этого значения сигналов на j-м входе элемента ИЛИ 62 и на j-м входе регистра 57 устанавливаются в

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

0

5

0

0

5

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

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

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

,-

tg

щ 20 25 0 Q 5

5

ра, выход которого подключен к входам альтернативной ссылки всех блоков обработки данных, первый информационный выход блока памяти подключен к входам ссылки на последующий элемент всех блоков обработки данньк„ второй информационный выход блока памяти подключен к входам ссылки на предикат всех блоков обработки данных, третий информационный выход блока памяти подключен к входам ссыпки на список предикатов-аргументов всех блоков обработки данных, вторые выходы ссыпки всех блоков обработки данных подключены к адресному входу блока памяти, i-й выход разрешения доступа первого блока управления доступом (i 19 1ч7) подключен к первому входу разрешения доступа i-ro блока управления, i-и выход разрешения доступа второго блока управления доступом подключен к второму входу разрешения доступа i-ro блока управления, (N+1)-fr вьгход разрешения доступа первого блока управления доступом подключен к синхровходу регистра, (N+O-й выход разрешения доступа второго блока управления доступом подключен к входу разрешения записи блока памяти, выход управления ссылкой и выход управления установкой в О i-ro блока управления подключены соответственно к (21-1)- му и 21-му входам запросов первого блока управления доступом, выход управления разрешением записи и выход управления аргументом 1-го блока управления подключены соответственно к (21-1)-му и 21-му входам запросов второго блока управления доступом, тактовые входы блоков управления доступом подключены к второму входу синхронизации устройства, выход конечного состояния 1-го блока управления подключен к входу конечного состояния 1-го блока обработки данных о

Изобретение относится к вычислительной технике и может быть использовано при разработке устройства, выполняющего функции логического вывода. Цель изобретения - увеличение быстродействия устройства управления выводом за счет распараллеливания процесса унификации. Устройство содержит 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 &