Устройство для определения пересечения множеств Советский патент 1985 года по МПК G06F17/27 

динен с сигнализирующим выходом уст ройства и с /.вторым входом элемента ИЛИ, выход денюфратора соединен с вторым входом блока микропрограмм много управления, третий вход кото1176346

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

УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ПЕРЕСЕЧЕНИЯ МНОЖЕСТВ, содержащее два регистра, группы элементов И, группу элементов ИЛИ, дешифратор и блок памяти, первый информационный выход которого соединен с входом дешифратора, отличающееся тем, что, с целью повьппения производительности устройства за счет обработки двух множеств элементов, в него введены два счетчика, элемент ИЛИ, триггер, узел сравнения и блок микропрограммного управления, причем первый адресный вход устройства соединен с информационным входом первого счетчика, выходы разрядов которого соединены с информационными входами элементов И первой группы, выходы которых соединены с первыми входами элементов ИЛИ группы, выходы которых соединены с адресным входом блока памяти, второй информационньш выход которого соединен с первым информационным входом узла сравнения и с информационными входами элементов И второй группы, выходы которых соединены с информационным входом первого регистра, выходы разрядов которого соединены с вторым информационным входом узла сравнения и с информационными входами элементов И третьей группы, выходы которых соединены с информационным выходом устройства, второй адресный вход устройства соединен с информационным входом второго регистра, выходы разрядов которого соединены с информационными входами элементов И четвертой группы, выходы которых соединены с информационным входом второго счетчика, выходы разрядов которого соединены с информационными входами элементов И пятой группы, выходы которых соединены с вторыми входами элементов. ИЛИ группы, выход узла сравнения соединен с единичным вхоДом триггераJ .единичный (0 выход которого соединен с первыми С управляющими входами элементов И третьей группы, первый выход блока микропрограммного управления соединен с управляющими входами элементов И первой группы, второй выход соединен со счетным входом первого счетчика и с управляющими входами о элементов И второй группы, третий, Од 4 Од четвертый, пятый и шестой выходы блока микропрограммного управления соединены соответственно с управляютщими входами элементов И четвертой группы, пятой группы, узла сравнения и с вторыми управляющими входами элементов И третьей группы, седьмой выход соединен со счетным входом второго счетчика и.с первым входом элемента ИЛИ, выход которого соединен с нулевым входом триггера, нулевой выход которогб соединен с первым входом блока микропрограммного управления , восьмой выход которого сое

1

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

Цель изобретения - повьшение производительности устройства за счет обработки двух множеств элементов.

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

Схема содержит регистры 1 и 2, группы 3-7 элементов И, группу элементов ИЛИ, дешифратор 9, блок 10 памяти, счетчики 11 и 12, элемен ИЛИ 13, триггер 14, узел 15 сравнения, блок 16 Микропрограммного управления, адресные входы 17 и 18 устройства, установочный вход 19 устройства, вход 20 запуска устройства, информационньш выход 21 устройства,сигнализирующий выход 22 устройства, выходы 23 - 29 блока 16 и входы 30 и 31 блока 16, узел 32 памяти, счетчик 33, группы 34 и 35 элементов И, дешифратор 36, генератор 37 импульсов, -распреде- питель 38 импульсов, элементы 39 и 40 задержки, регистр 41, элементы ИЛИ 42, 43; триггер 44 и элементы И 45-58.

В кажд.ом блоке схемы микропро-. граммы работы устройства (фиг. 3) изображены вьшолняемые микрооперации. Элементы устройства отмечеиъ их позициями на фиг. 1 и 2. Справа от черты в прямоугольном блоке отмечается выход блока 16, под действием импульса на котором выполняется соответствующая микрооперация. Позиции, заключенные в скобки, определяют выходы (содержимО181

соответствующих элементов устройства. Стрелка обозначает пересылку информации, а знак вопроса - про- BiepKy условия,

5 Пусть А и В - множества элементов. Тогда пересечение двух множеств является множеством С элементов, принадлежащих как множеству А, так и множеству В. Каждое множество хра-.

О нится в блоке 10 памяти, причем элементы множества представлены кодами чисел и находятся в последовательных ячейках. Последний элемент множества отмечается в блоке 10

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

0 то она может быть заменена одним разрядом, а дешифратор 9 может быть исключен из схемы устройства.

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

При включении питания устройство устанавливается в исходное состояние импульсов с входа 19, по которому обнуляются триггеры 14 (через элемент ИЛИ 13) и 44 (через элемент ИЛИ 42); распределитель 38 переводится в исходное состояние (ни на одном из его вь-ходов сигнал не появляется), а генератор 37 - в запертое состояние. В счетчике 11 по входу

17 записывается адрес первого элемента множества А, а в регистр 1 по входу 18 - адрес первого элемента множества В. Устройство готово к работе.

Запуск устройства в работу производится импульсом с входа 20. По этому импульсу в счетчике 33 формируется адрес первой микрокоманды микропрограммы работы устройства. 3 записанной в узле 32 памяти. При этом из него выбирается первая микр команда на входы дешифратора 36, и кода адреса следующей микрокоманды.. Этот же импульс с задержкой, необходимой для выборки первой микрокоманды, подается на вход запуска генератора 37, который начинает выдавать импульсы тактовой частоты. Они распределяются распределителем 38 по управляющим точкам блока 16. Первый импульс появляется на первом выходе распределителя S8 и проходит через, элемент И 45 (код микрооперации первой микрокоманды должен приводить к появлению сигнала на первом выходе дешифратора 36). При это содержимое счетчика 11 подается чер группы 3 элементов И и 8 элементов ИЛИ в блок 10 памяти, из которого выбирается первый элемент множества А. Кроме того, адрес следующей микр команды принимается в регистр 41. Второй импульс с выхода распределителя 38 открывает группы 35 элементен И и адрес следующей микрокоманды прини14ается в счетчик 33. В даль нейшем выборка микрокоманд из узла 32 памяти и их расшифровка производится аналогично. Код второй микрооперации приводит к появлению импульса на входе 24 блока 16, в результате чего содержимое счетчика 11 увеличивается на единицу (формируется адрес следующего элемента множества А), а первый элемент множества А с блока 10 памяти принимае ся в регистр 2 (так как открывается группа 4 элементов И). Кроме того, этот же импульс подается на, эле мент И 55. Дешифратор 9 настроен.на содержимое дополнительных разрядов блока 10 памяти, соответствующее последнему элементу множества. Следовательно, если из блока 10 на пре дыдущем такте выбран последний элемент множества А, то появляется импульс на выходе элемента И 55, который устанавливает триггер 44 в единичное состояние. При выполнении следующей микрокоманды появляется импульс на выходе 25 блока 16 и содержимое регистра 1 переписы вается в счетчик 12. Далее появляет ся импульс на выходе 26 блока 16, который открывает группу 7 элементов И и содержимое счетчика 12 подается в блок 10 памяти. При этом 464 из него выбирается первый элемент множетсва В. По импульсу на цыходе 27блока 16 осуществляетсясравнение в узле 15 содержимого на выходе блока 10 памяти с содержимым регистра 2. При совпадении этих кодов появляется импульс на выходе узла 15 сравнения и триггер 14 устанавливается в единичное состояние, подготавливая к отрытию группу 5 элементов И. По импульсу с выхода 28блока 16 осуществляется выдача первого элемента множества С из регистра 2 на 21, если триггер 14 находится в единичном состоянии. Если же он в нулевом состоянии, то выдача не производится. При выполнении следующей микрокоманды появляется импульс на выходе элемента И 52. Здесь микропрограмма разветвляется в зависимости от состояния триггера 14. Если триггер 14 находится в нулевом состоянии, то появляется импульс на выходе элемента И 57, который проходит через элемент ИЖ 43 и с задержкой, необходимой для принятия в счетчик 33 адресаследующей . микрокоманды, подается на счетный вход счетчика 33, увеличивая его содержимое на единицу. При этом из блока 32 выбирается микрокоманда, в результате выполнения которой появляется импульс на выходе 29 блока 16, вследствие чего содержимое счетчика 1-2 увеличивается на единицу (формируется адрес следующего элемента множества В), а триггер 14 устанавливается в нулевое состояние . Затем появляется импульс на выходе элемента И 53 и происходит анализ потенциала на выходе дешифратора 9. Если он нулевой, то элемент И 58 не открывается и следующей выбирается микрокоманда безусловного перехода. Код этой микрокоманды дешифратором 36 не расшифровывается, но в результате ее выполнения в счетчик 33 записывается адрес четвертой микрокоманды микропрограммы. Если на выходе дешифратора 9 присутствует сигнал , то. появляется импульс на выходе элемента И 58 и в счетчике 33 формируется адрес микрокоманды, в результате выполнения которой появляется импульс на выходе элемента И 54. у Если триггер 14 находится в единичном состоянии, то содержимое C4eiv

sa 33 не изменяется, вследствие чего из узла 32 выбирается микрокоманда безусловного перехода к микрокоманде, по которой в1адается импульс на выходе элемента И 54. .

По импульсу с выхода элемента И 54 производится анализ состояния триггера 44. Если он находится в нулевом состоянии, то следукнцей выбирается микрокоманда безусловного перехода к первой микрокоманде микропрограммы. Если же триггер 44 находится в единичном состоянии, то появляется импульс на выходе 22 уст:ройства, сигнализирукнций об окончании работы устройства. Этим :же импульсом устройство переводится в исходное состояние.

После записи в счетчик 11 и регистр 1 адресов первых элементов двух других множеств и подачи импульса на выход 20 устройство снова запускается в работу.

J9 20

риг. 1

23 24 25 26 27 28 29

Фие. Z

(1)J2 2S

i

(гг) 2в