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

(19) Ш) 51)5 С 06.Р 9/44, 3/00 ОЛИСА Е ИЗОБРЕ ДЕТЕЛЬСТВУ ТЕНИЯ ле ий инс ведчуьмутейГОСУДАРСТВЕННЫЙ НОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИПРИ ГКНТ СССР К АВТОРСКОМУ СВИ(54) УСТРОЙСТВО УПРАВЛЕНИЯ ЛОГИЧЕСКИМВЬВОЛОМ(57) Изобретение относится к вычислительной технике и может быть ис:пользовано при разработке устройствавыполняющего функции логическоговывода, Пель изобретения - увеличение быстродействия устройства управления выводом за счет распараллеливания процесса унификации, Устройство содержит И блоков 1 обработкиданных, блок 2 памяти, 11 блоков 3 управления, два блока 4 управ ниядоступом и регистр 5, Устройствоимеет вход 6 данных, первый вход 7синхронизации, У входов 8 аргумента,И входов 9 разрешения записи,И входов10 установки в "0", М информационныхвыходов 11, И выходов 12 констант,И выходов 13 переменных, второй вход14 синхронизации, Блок 1 обработкиданных имеет группу входов 15 микро-.команды, группу выходов 16 признаков,вход 17 аргумента, вход 18 разрешения записи, вход 19 установки вИзобретение относится к вычислительной технике и может быть использовано при разработке устройства, выполняющего функции логического вывода.1 ель изобретения - увеличение быстродействия устройства управления логическим выводом за счет распараллеливания процесса унификации, . 1 ОНа фиг, 1 приведена схема устройства управления логическим выводом; на фиг, 2 - схема блока обработки данных; на фиг. 3 - схема блока уп,равления доступом. 15Устройство управления логическим выводом содержит 1 блоков 1 обработки данных, блок 2 памяти, И блоков 3 управления, два блока 4 управления доступом, и регистр 5.и имеет вход 6 20 данных, первый вход 7 синхронизации, И входов 8 аргумента, И входов 9 разрешения записи, М входов 10 установки в "0", И информационных выходов 11, И выходов 12 констант, И выходов 25 13 переменных и второй вход 14 синхронизации.Блок 1 обработки данных имеет группу входов 15 микрокоманды, группу выходов 16 признаков, вход 17 аргу мента, вход 18 разрешения. записи, вход 19 установки в "0", информационный выход 20, выход 21 констант, выход 22 переменных, первый выход 23 ссылки, вход 24 альтернативной ссылки, вход 25 ссылки на последующий элемент, вход 26 ссыпки на предикат, вход 27 ссылки .на список предикатов - аргументов, второй выход 28 ссылки. и вход 29 конечного состояния. 40Блок 4 управления доступом имеет 21 входов 30 запросов, тактовый вход 31 и И+1 выходов 32 разрешения доступа.ФБлок 1 унификации (фиг, 2) содер жит два мультиплексора 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 стековой памяти устанавливается в полажение "О", после чегов блок 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 получает доступ к блоку 25 16 памяти и считывает оттуда инФормацию по адресу, находящемуся в первом ре - гистре 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 Конец", те, список аргументов исчерпан, и блок 1 переходит к выполнению третьего этапа работы, Если же сигнал на выходе первого элемента И 53 равен нулю, то блок 1 считы - вает инФормацию по адресу, содержа - щемуся в первом регистре 35. ИнФормация заносится в первый 35, второй 36 и третий 37 регистры. Затем блок 1 выполняет загрузку во второй блок 47 .стековой памяти и инкремент указателей первого и второго блоков 46 и 47 стековой памяти, Цикл продолжается до тех пор, пока в первом регистре 35 не окажется код "Конец", Формирующий уровень "1" на выходе первого элемента И 53. 42466Третий этап работы блока 1 заключается в подготовке блоков 48 и 49стековой памяти к очередному циклууниФикации, Для этого указатели 5обоих стеков устанавливаются в положение "О", затем седьмой регистр 41переводится.в активное состояние ив него заносится код Конец . Послеэтого код "Конец" с выхода седьмогорегистра 4 1 записывается в блоки 48и 49, Затем производится инкрементуказателей обоих блоков 48 и 49.Четвертый этап работы блока 1 является основным. На этом этапе и выполняется собственно униФикация.Сначала из первого и второго блоков 46 и 47 стековой памяти считывается по одному аргументу. Зти аргу менты пересылаются в девятый и десятый регистры 43 и 44 соответственно,Затем содержимое этих регистров сравнивается с помощью схемы 52 сравнения. Результат сравнения " 1", еслиесть равенстго иО", если равенства нет) заносится во второй триггер 51.При выборке текущей пары аргументов возможны четыре случая в зависимости от того, является ли каждый из аргументов переменной или константой:1) оба аргумента - константы, Тогда, если они равны, тс блок 1 сразу 35 переходит к пятому этапу работы, аесли они не равны, то унпФпкация невозможна и блок 1 осуществляет переход к второму этапу работы;2) первый аргумент - константа, 40 второй - переменная., В этом случаеблок выполняет проверку, содержитсяли данная переменная в блоке 48 стековой памяти. Если нет, то второйаргумент заносится в блок 48, а 45 первый аргумент - в блок 49, Гслида, то выполняется проверка, равны ли между собой первый аргументи константа из блока 49, соответствующая переменной из блока 48, Если 50 равны, то блок 1 переходит к пятомуэтапу работь., а если не равны, тоуниФикация невозможна и блок 1 переходит к второму этапу работы;Таким образом, по окончании второго этапа работы блока 1 во втором блоке 47 стековой памяти сФормирована вторая половина множества рассогласования 3) первый аргумент - переменная, второй - константа, В том случае выполняются аналогичные действия, только первый аргумент используется вместо второго и наоборот;40 Содерхимое одиннадцатого регистра 45 и блоков 48 и 49 запоминается на внешних элементах памяти и передается впоследствии на блок 1 для55 обработки,После передачи на соответствующие выходы содержимого одиннадцатого регистра 45 и блоков 48 и 49 блок 4) оба аргумента в . переменные,В этом случае, если они равны междусобой, то выполняется переход кпятому этапу работы, Если же нет,то возможны три случая:а) обе переменные не содержатсяв блоке 48, Тогда сразу выполняетсяпереход к пятому этапу работы блока 1; 10б) обе переменные содержатся вблоке 48. Тогда, если соответствующие им константы из блока 49 равнымежду собой, выполняется переход кпятому этапу работы, а если нет, 15то унификация невозможна, и блок 1переходит к второму этапу работы.в) если в блоке 48 стековой памяти содержится только одна из двухпеременных, то вторая переменная также заносится в блок 48, а в блок 49заносится константа, соответствующая той переменной, которая содердалась в блоке 48. После этого блок1 переходит к пятому этапу работы, 25На пятом этапе работы блока 1 выполняется анализ сигнала на первом выходепервого блока 46 стековой памяти. Если этот сигнал равен "1", то блок46 пуст, т,е. список аргументов исчерпан. В этом случае блок 1 переходит к выполнению шестого этапа рабо"ты. Если же сигнал на первом выходе блока 46 равен "О", то блок 1 осуществляет переход к четвертому этапу работы, т,е, к обработке очередной пары аргументовНа шестом этапе работы блока 1вначале анализируется сигнал на выходе третьего элемента И 55. Еслиэтот сигнал равен ."1", то это означает., что в одиннадцатом регистре 45находится код Конец , т,е, унификация завершена успешно и получено пустое предложение После этого блок 1 45переходит к выполнению второго этапаработы, Если же сигнал на выходетретьего элемента И 55 равен "0",то это означает, что при проведенииунификации возникла подцель.50 1 переходит к выполнению второгоэтапа работы,Блок 4 управления доступом работает следующим образом.В исходном состоянии все разрядырегистра 57 обйулены. На входах элемента ИЛИ 62 находятся сигналы низкогологического уровня. На вход 31 блока 4 поступают тактовые импульсы.Счетчик 60 циклически изменяет своесостояние под воздействием тактовыхимпульсов на своем счетном входеПри этом осуществляется поочередноевозбуждение выходов дешифратора 61,а также поочередная передача информации (с инверсией) с одного из информационных входов мультиплексора58 на его выход.В таком режиме блок 4 работаетдо тех пор, пока на одном из входоврегистра 57 не появится сигнал уровня "1" (например, на 3-ом входе),Этот сигнал, являющийся запросомот 3-го блока 3 управления, передается на 1-й вход мультиплексора 58.Когда мультиплексор 58, управляемыйсчетчиком 60, передаст этот сигнал(с инверсией) на второй вход элемента И 59, поступление тактовых импульсов на вход счетчика 60 блокируется.В результате возбуждается 1-й выходдешифратора 61 разрешения доступаи удерживается в возбужденном состоянии. Затем на 1-й вход элементаИЛИ 62 поступает сигнал уровня "1"от 1-го блока 3 управления (сигналзаписи информации в регистр 5), После этого значения сигналов на 1-мвходе элемента ИЛИ 62 и на 1-м входерегистра 57 устанавливаются в "0".При установке -го разряда регистра 57 в состояние "0" на выходе мультиплексора 58 появляется значение"1", так как счетчик 60 находитсяв состоянии, обеспечивающем передачуинформации с 1"го входа мультиплексора58 на выход мультиплексора 58 В результате открывается элемент И 59 итактовые импульсы, поступающие на егопервый вход, проходят на ход счетчика 60. Счетчик 60 снова начинаетс проходом каждого тактового импульса изменять свое соСтояние, осуществляя последовательный перебор двоичных комбинаций на (п+1)-м входе мультиплексора 58 и на входе дешифратора 61, Если теперь -й разряд (+1)регистра 57 находится в состоянии"1", то при передаче информации с1-го входа мультиплексора 58 на еговыход элемент И 59 снова закрываетсяи в возбужденном состоянии оказывается 1-й выход дешифратора 61 до техпор, пока ь-й разряд регистра 51 неустановится в состояние 0,1Формула изобретения Устройство управления,логическим выводом, содержащее блок обработки данных, блок памяти, блок управления, причем вход данных блока памяти явля ется входом данных устройства, синхровход блока управления является первым входом синхронизации устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия 2 О устройства за счет распараллеливания процесса обработки информации в блоке обработки данных, в устройство введены Мблоков обработки данных, Иблоков управления (где Н - число од новременно выполняемых действий над информацией), два блока управления доступом и регистр, причем синхровходы всех блоков управления объединены, группы выходов микрокоманды и входов признаков 1-го блока управления (1 = 1, И) подключены к соответствующим группам входов микрокоманды и выходов признаков -го блока обработки данных, входы аргумента, разрешения записи и установки в "О" д-го блока обработки данных являются соответственно 1-ми входами аргумента, разрешения записи и установки в 0 устройства, информацион ный выход, выход констант и выход переменных 1-го блока обработки данных являются соответственно ь-м информационным выходом, 3.-м выходом констант и 1.-м выходом перем ных устройства, первые выходы ссылки всех блоков обработки данных подключены к информационному. входу регистра, вьход которого подключен к входам альтернативной ссылки всех блоков обработки данньп, первый информационный выход блока памяти подключен к входам ссылки на последующий элемент всех блоков обработки данньк, второй информационный выход блока памяти подключен к входам ссыпки на предикат всех блоков обработки данных, третий информационный выход блока памяти подключен к входам ссыпки на список предикатов-аргументов всех блоков обработки данных, вторые выхопы ссыпки всех блоков обработки данных подключены к адресному входу блока памяти, -й выход разрешения доступа первого блока управления доступом (1 = 1, М) подключен к первому входу разрешения доступа -го блока управления, 1-й выход разрешения доступа второго блока управления доступом подключен к второму входу разрешения доступа -го блока управления, (К+1) -й выход разрешения доступа первого блока управления доступом подключен к синхровходу регистра, (И+1)-й выход разрешения доступа второго блока управления доступом подключен к входу разрешения записи блока памяти, выход управления ссылкой и выход управления установкой в "О" 1-го блока управления подключены соответственно к (2-1)- му и 2-му входам запросов первого блока управления доступом, выход управления разрешением записи и выход ,управления аргументом -го блока управления подключены соответственно к (2-1) -му и 21-му входам запросов второго блока управления доступом, тактовые входы бпоков управлениядоступом подключены к второму входу синхронизации устройства, выход конечного состояния -го блока управления подключен к входу конечного состояния 1-го блока обработки данных1642466 15 оставитель С. Авервяноваехред С,Мигунова Корректор Л е Редакто Лежнина 1148 Тираж 414 ПодписноеИ Государственного комитета по изобретениям и открытиям при ГКНТ ССС 113035, Москва, Ж, Рауцская наб д. 4/5 Зак 11 ттПроизводственно-издательский комбинат Патент , г, Ужгород, ул. Гага