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

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

9373

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

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

1

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

Целью изобретения является повышение производительности Vcтpoйcтвa за счет обработки двух множеств элементов.

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

Устройство содержит регистры 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.

На схеме устройства (фиг.З) изображена последовательность выполняемых микроопераций. В блоках схемы микропрограмьш числами справа от черты представлены выходы блока 19 под действием импульсов, на которых

выполняются соответствующие микрооперации. Числа слева от черты в обычных блоках и числа в логических блоках представляют элементы устройства. Если номер элемента заключен в круглые скобки, то это означает, что берется содержимое (выходы) элемента. Стрелка обозначает пересылку информации, а знак вопроса проверку условия. Элементы множества представляются кодами чисел и располагаются в последовательных ячейках блока 6 памяти. За последним элементом множества записан уникальный код, который будет свидетельствовать об окончании выборки множества. Пусть А и В - множества. Объеди7 нение множеств А и В - это множество С, составленное из элементов каждый из которых принадлежит, по крайней мере одному из множеств А или В.

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

После включения питания оно устанавливается в исходное состояние импульсом с входа 22 устройства. При этом генератор 41 переводится в запертое состояние, распределитель . 42 - в исходное (ни на одном из его выходов сигнал не появляется), а в регистр 16 записывается уникальный код заглушки. Затем в счетчик 9 и регистр 1 по входам 20 и 21 записываются адреса первых элементов множеств А и В соответственно. Устройство готово к работе.

3

Запуск устройства в работу осуществляется импульсом с входа 23 усТ ройства, вследствие чего в счетчик 38 заносится адрес первой микрокоманды микропрограммы. По этому адресу из узла 34 памяти выбирается ;первая микрокоманда. Код каждой микрокоманды состоит из кода микрооперации, который расшифровывается дешифратором 35, и кода адреса следующей микрокоманды. Код микрооперации первой микрокоманды приводит к появлению-сигнала на пбрвом выходе дешифратора 35. После этого появляется импульс на выходе элемента 43 задержки и генератор 41 начинает выдавать импульсы, которые.распределяются распределителем 42 по управляющим точкам блока 19. Первый импульс появляется на первом выходе распределителя 42. При этом адрес второй микрокоманды через открытую группу элементов И 36 записывается в регистр 39 и появляется импульс на выходе элемента И 45, который проходит через выход 26 блока 19 на управляющий вход группы 3 элементов И, в результате чего адрес первого элемента множества А через группы элементов И 3 и элементов ИЛИ 5 подается на адресный вход блока 6 памяти, а адрес первого элемента множества В через группу элементов И 11 - в счетчик 10. Второй импульс с выхода генератора 41 появляется на втором выходе распределителя 42, вcлeдcfвиe чего адрес следующей микрокоманды переписывается из .регистра 39 в счетчик 38. В дальнейшем блок 19 работает аналогично. В результате выборки второй микрокоманды появляется импульс на выходе 27 блока 19. При этом блок 6 памяти выдает первый элемент множества А (в дальнейшем - очередной элемент множества А или код конца множества) на свои выходы. По следующей микрокоманде осуществляется проверка выборки из блока 6 памяти кода конца множества. На этот код настроен.дешифратор 7. Он вцдает сигнал при обнаружении этого кода. Сигнал на входе 33 блока 19 анализируется импульсом с .выхода элемента И 52. Если на выходе дешифратора 7 единица, то он проходит через элемент И 54 с задержкой, необходимой для записи в счетчик 38 адреса микрокоманды.

793734

которая будет выполняться cлeдyюD eй при отсутствии сигнала на выходе дешифратора 7, увеличивает содержимое счетчика 38 на единицу, формируя ад. рее микрокоманды, которая будет выполняться следующей при наличии сигнала на выходе дешифратора 7. Таким образом осуществляется разветвление в микропрограмме.

Если из блока b считан не код конца множества, то при выполнении следующей микропрограммы появляется сигнал на выходе 28 блока 19, по которому содержимое счетчика 9 увеличи5 вается на единицу (формируется адрес следующего элемента множества А) и открывается группа элементов И 13. При этом элемент множества А принимается в регистр 2. По импульсу с выхода 29 блока 19 открывается группа элементов И 14 и содержимое регистра 2 проходит на В111ход 24 устройства в качестве первого (в дальнейшем очередного) элемента множества С.

5 После этого появляется сигнал на выходе блока 19, в результате чего открывается группа элементов И 4 и адрес первого элемента множества В подается на адресный вход блока 6 памяти. Затем вьщается импульс на выходе 27 блока 19, по которому блок 6 выставляет на своих выходах первый элемент множества В (в дальнейшем очередной элемент множества В или

3 код конца множества). Если выбран код конца множества, то осуществляется переход к первоймикрокоманде микропрограммы. При этом может использоваться микрокоманда безусловного перехода, код микрооперации которой дешифратором 35 не расшифровывается. В противном случае появляется сигнал на выходе 31 блока 19 и содержимое счетчика 10 увеличивается

5 на единицу (формируется, адрес следующего элемента множества В). Кроме того, на элементе И 15 анализируется сигнал с выхода узла 17 сравнения. Узел 17 осуществляет сравнение

0 содержимого регистра 2 (очередного элемента множества А) с кодом на выходах блока 6 (очередным элементом множества В) и вьщдет сигнал при их . совпадении. При этом появляется импульс на выходе элемента И 15 и заглущка из регистра 16 записывается по адресу очередного элемента множества В. Это необходимо для того.

чтобы исключить в последующем при просмотре множества В повторную выдачу на выход 24 элементов множества В, совпадающих с элементами множества А.

Если из блока 6 считан код конца множества (при выборке очередного элемента множества А), то появляется импульс на выходе 30 блока 19, открывающий группу элементов И 4, и адрес первого элемента множества В принимается в блок 6. По импульсу с выхода 27 блока 19 блок 6 вЪщает элемент множества В (первый а в дал нейшем - очередной или код конца мнжества) . После этого анализируется выход дешифратора 7, Если выбран не код конца множества, то появляется импульс на выходе 32 блока 19, по которому содержимое счетчика 10 увеличи- зется на единицу (формируется адрес следующего элемента множества В), Этот же импульс подается на второй управляющий вход группы, элементов И 12. Дешифратор 8 настроен на код заглушки. Следовательно, если из блока 6 выбран код заглушки. Следовательно, если из блока 6 выбран код заглушки, то группа элементов И 12 не открывается (дешифратор 8 не выдает сигнал при распознавании заглушки). В противном случае код очередного элемента множества С с выходов блока 6 проходит на выход 24 устройства. Если же из блока 6 выбран код конца множества, то выбирается микрокоманда, приводящая к появлению импульса на выходе элемента И 53, по которому устанавливается в исходное состояние. Этот же импульс проходит на выход 25 устройства, сигнализируя об окончании выполнения операции объединения двух заданных множеств.

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

2S 27 29 23 30 31 32 25

11

фиг. 2