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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК (! 9) (11) (51)4 С 06 F 15/38

ОПИСАНИЕ ИЗОБРЕТЕНИЯ 3

1 Б " РТ(((д

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫИ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3711906/24-24 (22) 16.03.84 (46) 15.09.85. Бюл. № 34 (72) Б.С.Богумирский, В.Я.Яцук и С.В.Сычев (53) 681.325(088.8) (56) Заявка Великобритании № 1448211, кл. G 06 F 15/38, 1976.

Авторское свидетельство СССР № 666545, кл. G 06 F 15/38, 1977. (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 под действием импульсов, на которых

S !

О .15

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

С, составленное из элементов, каждый из которых принадлежит, по крайней мере одному иэ множеств А или В.

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

После включения питания оно устанавливается в исходное состояние импульсом с входа 22 устройства. При этом генератор 41 переводится в запертое состояние, распределитель

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

3 11793

Запуск устройства в работу осу.ществляется импульсом с входа 23 уст1 ройства, вследствие чего в счетчик

38 заносится адрес первой микрокоманды микропрограммы. По этому адресу из узла 34 памяти выбирается. .первая микрокоманда. Код каждой микрокоманды состоит из кода микрооперации, который расшифровывается дешифратором 35, и кода адреса сле- 10 дующей микрокоманды. Код микрооперации первой микрокоманды приводит к появлению .сигнала на первом выходе дешифратора 35. После этого появляется импульс на выходе элемента 43 15 задержки и генератор 41 начинает выдавать импульсы, которые .распределяются распределителем 42 по управляющим точкам блока 19. Первый импульс появляется на первом выходе 20 . распределителя 42. При этом адрес второй микрокоманды через открытую группу элементов И 36 записывается в регистр 39 и появляется импульс на выходе элемента И 45, который . 2$ проходит через выход 26 блока 19 на управляющий вход группы 3 элементов И, в результате чего адрес первого элемента множества А через группы элементов И 3 и элементов ИЛИ З0

5 подается на адресный вход блока 6, памяти, а адрес первого элемента множества В через группу элементов И

11 - в счетчик 10. Второй импульс с выхода генератора 41 появляется на З втором выходе распределителя 42, вследствие чего адрес следующей микрокоманды переписывается из .регистра 39 в счетчик 38. В дальнейшем блок 19 работает аналогично. В результате выборки второй микрокоманды появляется импульс на выходе 27 блока 19. При этом блок 6 памяти выдает первый элемент множества А (в дальнейшем - очередной элемент мно- 4З жества А или код конца множества) на свои выходы. По следующей микрокоманде осуществляется проверка выборки иэ блока 6 памяти кода конца множества. На этот код настроен .де- SO шифратор 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 записывается по адресу очередного элемента множества В. Это необходимо для того, 1179373 чтобы исключить в последующем при просмотре множества В повторную выдачу на выход 24 элементов множества В, совпадающих с элементами множества А.

Если из блока 6 считан код конца множества (при выборке очередного элемента множества А), то появляется импульс на выходе 30 блока 19, 10 открывающий группу элементов И 4, и адрес первого элемента множества

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

24 устройства. Если же из блока 6 выбран код конца множества, то выбирается микрокоманда, приводящая к появлению импульса на выходе элемента И 53, по которому устанавливается в исходное состояние. Этот же импульс проходит на выход 25 устройства, сигнализируя об окончании выполнения операции объединения двух заданных множеств.

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

1179373

1179373

Составитель А.Жеренов

ТехРед З.Палий Корректор В. Вутяга

Редактор И.Ковальчук

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4

Заказ 5678/52 Тираж 710 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5