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

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