Устройство для определения пересечения множеств

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 4 С 06 Р 15/38 ОПИСАНИЕ ИЗОБРЕТЕНИ ИДЕТЕЛЬСТВ К РСКОМУ(46)72 входами элементов ИЛИкоторых соединены сблока памяти, втовыход которого сое группы, выхо ресным входо рои ипформационныи динен с первым информационным входом у с информационными вхо И второй группы, выхо динены с информационн го регистра, выходы р соединены с вторым ин а сравнения и элементов которых сое щ входом первозрядов которогоормационным УДАРСТВЕННЫЙ КОМИТЕТ СССРДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ 3711901/24-246.03.8430.08.85. Бюл. В 32(54)(57) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯПЕРЕСЕЧЕНИЯ МНОЖЕСТВ, содержащеедва регистра, группы элементов И,группу элементов ИЛИ, дешифратор иблок памяти, первый информационныйвыход которого соединен с входомдешифратора, о т л и ч а ю щ е е с ятем, что, с целью повышения производительности устройства эа счет обработки двух множеств элементов,в него введены два счетчика, элементИЛИ, триггер, узел сравнения и блокмикропрограммного управления, причем первый адресный вход устройствасоединен с информационным входом пер.вого счетчика, выходы разрядов которого соединены с информационными вхо.дами элементов И первой группы, выходы которых соединены с первыми ЯО 1176346 А входом узла сравнения и с информационными входами элементов И третьейгруппы, выходы которых соединены синформационным выходом устройства,второй адресный вход устройства соединен с информационньм входом второгорегистра, выходы разрядов которогосоединены с информационными входамиэлементов И четвертой группы, выходыкоторых соединены с информационнымвходом второго счетчика, выходы разрядов которого соединены с информационными входами элементов И пятойгруппы, выходы которых соединены свторыми входами элементов,ИЛИ группы,выход узла сравнения соединен с единичным входом триггера, .единичныйвыход которого соединен с первымиуправляющими входами элементов Итретьей группы, первый выход блокамикропрограммного управления соединен с управляющими входами элементов И первой группы, второй выходсоединен со счетным входом первогосчетчика и с управляющими входамиэлементов И второй группы, третий,четвертый, пятый и шестой выходыблока микропрограммного управленийсоединены соответственно с управляющими входами элементов И четвертойгруппы, пятой группы, узла сравненияи с вторыми управляющими входамиэлементов И третьей группы, седьмойвыход соединен со счетным входомвторого счетчика и с первым входомэлемента ИЛИ, выход которого соединен с нулевым входом триггера, нулевой выход которог 6 соединен с первымвходом блока микропрограммного управления, восьмой выход которого сое176346 динен с сигнализирующим выходом устройства и свторым входом элементаИЛИ, выход дешифратора соединен свторым входом блока микропрограммного управления, третий вход кото Изобретение относится к вычислительной технике и может быть использовано в системах управления банками данных,Цель изобретения - повышение 5 производительности устройства за счет обработки двух множеств элемен" тов.На фиг. 1 приведена схема устройства; на фиг, 2 - схема блока. микропрограммного управления, на фиг, Э - схема микропрограммы работы устройства,Схема содержит регистры 1 и 2, группы 3-7 элементов И, группу 5 элементов ИЛИ, дешифратор 9, блок 10 памяти, счетчики 11 и 12, элемент ИЛИ 13, триггер 14, узел 15 сравнения, блок 16 микропрограммного управления, адресные входы 17 и 18 2 О устройства, установочный вход 19 устройства, вход 20 запуска устройства, информационный выход 21 устройства,сигнализирующий выход 22 устройства, выходы 23 - 29 блока 16 и входы 30 и 31 блока 16 узел 32 памяти, счетчик 33, группы 3435 элементов И, дешифратор 36, генератор 37 импульсов, распредеитель 38 импульсов, элементы ЗО 39 и 40 задержки, регистр 41, элементы ИЛИ 42, 43; триггер 44 и эле" менты И 45-58.В каждом блоке схемы микропро-, граммы работы устройства (фиг. 3) . 35 изображены выполняемые микрооперации, Элементы устройства отмечены их позициями на фиг. 1 и 2. Справа от черты в прямоугольном блоке отмечается выход блока 16, под дейст вием импульса на котором выполняется соответствующая микрооперация. Позиции, заключенные в скобки, определяют выходы (содержимое рого соединен с установочншм входол,устройства и с третьим входом элемента ИЛИ, вход запуска устройствасоединен с четвертым входом блокамикропрограммного управления. соответствующих элементов устройства. Стрелка обозначает пересылкуинформации, а знак вопроса - проверку условия,Пусть А и В - множества элементов. Тогда пересечение двух множествявляется множеством С элементов,принадлежащих как множеству А, так имножеству В. Каждое множество хранится в блоке 10 памяти, причемэлементы множества представленыкодами чисел и находятся в последовательных ячейках. Последний элементмножества отмечается в блоке 10специфическим содержимым дополнительных разрядов, выходы которыхсоединены с входами дешифратора 9.Если группа дополнительных разрядовиспользуется только для этой цели,то она может быть заменена однимразрядом, а дешифратор 9 может бытьисключен из схемы устройства. Устройство работает следующим образом.При включении питания устройство устанавливается в исходное состояние импульсов с входа 19, по которому обнуляются триггеры 14 (через элемент ИЛИ 1 Э) и 44 (через элемент ИЛИ 42); распределитель 38 переводится в исходное состояние (ни на одном из его вьходов сигнал не появляется), а генератор 37 - в запертое состояние. В счетчике 11 по входу 17 записывается адрес первого элемента множества А, а в регистр 1 по входу 18 - адрес первого элемента множества В. Устройство готово к работе.Запуск устройства в работу производится импульсом с входа 20. По этому импульсу в счетчике 33 форми" руется адрес первой микрокоманды микропрограммы работы устройства,з 1 записанной в узле 32 памяти. При этом из него выбирается первая микро команда на входы дешифратора 36, и кода адреса следующей микрокоманды. Этот же импульс с задержкой, необходимой для выборки первой микро- команды, подается на вход запуска генератора 37, который начинает выдавать импульсы тактовой частоты, Они распределяются распределителем 38 по управляющим точкам блока 16. Первый импульс появляется на первом выходе распределителя 38 и проходит через. элемент И 45 (код микроопера-. ции первой микрокоманды должен приводить к появлению сигнала на первом выходе дешифратора 36). При этом содержимое счетчика 1 подается чере группы 3 элементов И и 8 элементов ИЛИ в блок 10 памяти, из которого выбирается первый элемент множества А. Кроме того, адрес следующей микро команды принимается в регистр 41, Второй импульс с выхода распределителя 38 открывает группы 35 элементов И и адрес следующей микрокоманды приниМается в счетчик 33. В даль нейшем выборка микрокоманд из узла 32 памяти и их расшифровка производится аналогично. Код второй микро- операции приводит к появлению импульса на входе 24 блока 16, в результате чего содержимое счетчика 11 увеличивается на единицу (формируется адрес следующего элемента множества А), а первый элемент множества А с блока 10 памяти принимает ся в регистр 2 (так как открывается группа 4 элементов И). Кроме того, этот же импульс подается на элемент И 55. Дешифратор 9 настроен.на содержимое дополнительных разрядов блока 10 памяти, соответствующее последнему элементу множества, Следовательно, если из блока 10 на предыдущем такте выбран последний элемент множества А, то появляется импульс на выходе элемента И 55, который устанавливает триггер 44 в единичное состояние. При выполнении следующей микрокоманды появляется импульс на выходе 25 блока 16 и содержимое регистра 1 переписы вается в счетчик 12. Далее появляет. ся импульс на выходе 26 блока 16, который открывает группу 7 элементов И и содержимое счетчика 12 подается в блок 10 памяти. При этом176346 4 30 55 О 5 20 25 40 50 из него выбирается первый элемент множетсва В. По импульсу на цыходе 27 блока 16 осуществляется сравнение в узле 15 содержимого на выходе блока 10 памяти с содержимым регистра 2. При совпадении этих кодов появляется импульс на выходе узла 15 сравнения и триггер 14 устанавливается в единичное состояние, подготавливая к отрытию группу 5 элементов И. По импульсу с выхода 28 блока 16 осуществляется выдача первого элемента множества С из регистра 2 на 21, если триггер 14 находится в единичном состоянии.Если же он в нулевом состоянии, то выдача не производится. При выполне. нии следующей микрокоманды появляется импульс на выходе элемента И 52. Здесь микропрограммаразветвляется в зависимости от состояния триггера 14Если триггер 14 находится в нулевом состоянии, то появляется импульс на выходе элемента И 57, который проходит через элемент ИЛИ 43 и с задержкой, необходимой для принятия в счетчик 33 адреса следующей . микрокоманды, подается на счетный вход счетчика 33, увеличивая его содержимое на единицу. При этом иэ блока 32 выбирается микрокоманда. в результате выполнения которой появляется импульс на выходе 29 блока 16, вследствйе чего содержимое счетчика 12 увеличивается на единицу (формируется адрес следующего элемента множества В), а триггер 14 устанавливается в нулевое состояние. Затем появляется импульс на выходе элемента И 53 и происходит анализ потенциала на выходе дешифратора 9. Если он нулевой, то элемент И 58 не открывается и следующей выбирается микрокоманда безусловного перехода. Код этой микрокоманды дешифратором 36 не расшифровывается, но в результате ее выполнения в счетчик 33 записывается адрес четвертой микрокоманды микропрограммы. Если на выходе дешифратора 9 присутствует сигнал, то появляется импульс на выходе элемента И 58 и в счетчике 33 формируется адрес микрокоманды, в результате выполнения которой появляется импульс на выходе элемента И 54.Если триггер 14 находится в единичном состоянии, то содержимое счеП 117634 бса 33 не изменяется, вследствие чего из узла 2 выбирается микрокоманда безусловного перехода к микрокоманде, по которой выдается импульс на выходе элемента И 54.По импульсу с выхода элемента И 54 производится анализ состояния триггера 44. Если он находится в нулевом состоянии, то следующей выбирается микрокоманда безусловного пе- рехода к первой микрокоманде микропрограммы. Если же триггер 44 находится в единичном состоянии, то появляется импульс на выходе 22 уст:ройства, сигнализирующий об окончанииработы устройства. Этим же импульсомустройство переводится в исходное состояние. После записи в счетчик 11 и ре О гистр 1 адресов первых элементовдвух других множеств и подачи импульса на выход 20 устройство снова запус.кается в работу.1176346 ставитель А, Жеренохред З.ПалийКовальч дак орректор Л. Бескодпис каз 49 Тираж 710 П НИИПИ Государственного комитета СССРпо делам изобретений и открытий13035, Москва, Ж, Раушская наб., д. 4Филиал ППП "Патент", г, Ужгород, ул, Проектн