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

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

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

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

Устройство (фиг.) содержит счетчики 1 и 2, группы 3-6 элементов И, группы .7 и 8 элементов ШШ, блок 10 памяти, регистры П и 12, дешифраторы 13 и 14, схему 15 сравнения, выходы которой обозначены позиция1«ш 16 и 17, блок 18 управления выходы к о- торого обозначены позициями 19-24, а входы - 25-28, группы 29 и 30 адресных входов 5 группу 31 информаци- oHMiJx выходов, установочный вход 32, вход 33 запуска и сигнальный выход 34 устройства.

Блок 18 управления (фиг.2) выполнен но микропрограммному припцину. Он содержит счетчик 35, узел 36 памяти команд, дешифратор 37, группу 38 элементов И, генератор 39 импульсов, элементы ИЛИ 40 и 41, элементы 42-44 задержки, элементы И 45-61 и регистр 62. Выход элемента ИЛИ 40 соединен с входом останову генератора и№1уль- сов, вход запуска которого соединен с входом 33, выход, элемента 42 задержки соединен с управляющим входом

. группы 38, выход элемента 43 задерж- ки соединен с установочшлм входом

счетчика 35, счетный вход которого соединен с выходом элемента 44 задержки, выход генератора 39 соединен с управляющим входом регистра 62, остальные связи ясны из чертежа.

В каждом блоке cxeMisi микропрограммы работы устройства (фиг.З) изображены выполняемые микроонерадии. УЗЛЫ устройства представлены пози- днями на фиг.1 и 2. Справа от черты в прямоугольном блоке отмечается выход блока 18, под действием импульса на котором выполняется соответствующая микрооперация. Позидии,. заклю- ченршш в скобки, определяют содержимое соответствующих узлов устройства либо, состояние выходов соответствую- пщх узлов устройства.

0

5

Стрелка внутри блока схемы обозначает пересылку информадии.

Пусть А и В - множества. Тогда объединение двух множеств А и В - это множество С AUB, составленное из элементов, каждый из которых принадлежит, по крайней мере, одному из множеств А или В. Каждое множество хранится в блоке 10 памяти, причем элементы г-шожества представлены кодами чисел, отсортированы по возрастанию и находятся в смежных ячейках. За носитедним элементом множества следует уникальный ко д (например, нулевой), расшифровываемый дешифраторами 3 и 14. Этот код называется кодом конца множества.

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

При включении нитания устройство устанавливается в исходное состояние импульсом с входа 32, по которому (через элемент Hnii 40) генератор 39 импульсов переводится в запертое состояние, и с задержкой, необходимой д,ля окончания переходных процессов в блоке 18, в счетчике 35 формируется а,чрес первой микрокоманды микропрограммы работы устройства, записанной в узле 36 памяти команд. При этом из него выбирается первая микрокоманда, состоящая из кода микрооперации, который подается на входы дешифратора 37, и кода адреса следующей шкpoкoмaнды, он появляется на второй группе выходов узла 36, соединенной с входам;и регистра 62. Код первой микрооперации расшифровывается дешифратором 37 и появляется CHI- нал на его первом выходе (слева по схеме). По группам 29 и 30 входов в счетчики 1 и 2 записываются адреса первых элементов множеств А и В. Устройство готово к работе.

SarsycK устройства в работу производится импульсом с входа 33. По этому импульсу запускается генератор 39, который начинает вьщавать импульсы тактовой частоты. Первый импульс с выхода генератора 39 проходит через открытый элемент И 45 на выход 19 блока 18, При этом содержимое счетчика 1 через группы 3 элементов И и 7 элементов ИЛИ подается в блок 10 памяти, из которого выбирается первый элемент множества А, Кроме того, адрес следующей микрокоманды принимается в регистр 62. После это0

5

0

5

0

5

,1278890

появляется in-шульс на выходе элесяду пу

мента 42 задержки, который открывает группу 38 элементов И, разрешая запись в счетчик 35 адреса следа-гащеи микрокоманды, который из регистра 62 переписывается в счетчик 35. В даль- нейБгем выборка микрокоманд из узла 36 памяти команд и их расшифровка производятся аналогично. Код второй микрооперации приводит к появлению импз льса па выходе 20 блока 18. в

результате чего первьш элемент множества А принимается в регистр а содержимое счетчика 1 увеличивается на единицу (}.1Орг-п руется адрес еле дующего элемента множества А). При выпс;и1ении следующей Ш1кроконандг4 появляется импульс па ,е 21 с..-о- ка 18 и адрес первого элемента жества В через групггы 4 элементов И и 7 элементов ИЛИ поступает в (1т. от, 10 памяги, в результач е чего па ei o выходак появляется первый зл.смеит мпожества В, По следующей микрокоманде возн1гкает импульс на вьп-:оде 22 блока 18 и первый элемент множества В принимается в регистр 12, а содержимое счетчика 2 увеличивается на единицу (формируется адрес следующего элемента множества В).

Если на регистр 11 и/или регистр 12 принят код конца множества, то де иифратор 13 и/или l- i выдает сигнал. Схема 15 сравнения сравнивает содержимое регистров П и 12. Если, содер- Ж1шое регистра меньше содерлчнмого регистра 12 (т,е, код первого та мпожества А меньше кода первого элемента множества В), то появляется

сигнал на выходе 16, если же oini рав ны, ТО появляется сигнал на выхо- де 17.

По сл шдующей микрокоманде ПОЯБЛЯ- ется импульс на элемента И 5 i .

,Если в регистрах II и 12 находятся кодь конца множества, то этот импуль

:Проходит через элемент И 57, элеме1гг

.Ш1И 41 и с задержкой, необходимой

для принятия в счетчик 35 адреса с.ле-50 по которой появляется импульс иа выдующей м.икрокоманды, подается на счетньш вход счетчика 35, увеличивая его содержимое на единицу. В противном случае адрес следующей микрокоманды не изменяется. Таким образом, осуществляется разветвление в микропрограмме в зависимости от вьтолке- ния каких-либо условий.

5

15 1.;остп

5

Если в регистрах II и 12 нахо/дят- ся коды конца множества, то по следующей микрокоманде появляется импульс на выходе элемента И 56, кото5 рый проходит на сигнальный выход 34, свидетельствуя об окопчапии выполнения операции объединения множеств А и В. Этим же импульсом устройство переводится в исход ное состояние.

fO В противном случае выбирается №1крокоманда, по которой появляется иьшульс на выходе элемента И 52. По этому импульсу осуществляется разветвление в Ш1кропрограмме в зависнет сигнала на выходе дс.тщфра- гора 13, Если в регистре 11 находится код конца множества, то необходиМО U-.i)e;.i,aTb на выходы устр ойства все оставшиеся эле. множества В.

0 Поэтому по следующей микрокоманде появляется п.мпульс на выходе 24 блока IB, но которому очередной элемент г-нюжества В и,з регистра 12 через от- 1срытзпо грунну 6 элементов И и группу 8 элементов ИЛИ проходит на группу 31 выходов в качестве очередного множества С, Затем выбирается третья М1псрокоманда. Если в регистре 11 не находится код конца мно- жесч ва, то по аледующей юткрокоманде появляется и.мпульс на выходе элемента И 53, по которому анализируется сигнал на выходе дешифратора 14,

0

эле:.елта И

Если в регистре 12 не код конца мно. кества, то на : ыходе дешифратора 14 нулепой сигнал. В этом еле- дуюи;е; выби15ается микрокоманда, по KOTOpoii появляется импульс иа выходе

При этом осуществляется разветвление в микропрограмме в зависимости от сигнала на выходе 16 схемы 15 сравнения. Если иа этом выходе единичный сигнал (т.е. очередной элемент множества А меньше очередного элемента множества В), то необходимо передать очередной элемент IIoжecтвa А на выход устройства. Для этого, выбирается Ш1крокоманда,

ходе 23 блока 18. По этому импульсу открывается группа 5 элементов И и очередно множества А из регистра 11 проходит па группу 31 вы- ХОДО13 в качестве очередного элемента множества С. Эта же мпкрокоманда выполняется в случае, когда в регистре 2 находится код нoжecтвa

По двум следуюп1,им микрокомандам в регистр 11 из блока 10 принимается код следующего элемента множества А, а содержимое счетчика 1 увеличивается на единицу. После этого Бновь осуществляется анализ сигналов на выходах дешифраторов 4 и 13,

Если на выходе 16 cxeMiii 15 сравнения нулевой сигналJ то выбирается г шкрокоманда. по которой появляется ттупъс на выходе элемента И 55. Этим имиульсом анализируется сигнал на выходе 17 схемы 15 сравнения. Если на этом выходе присутствует единица (очередные элементы множеств А и Б равны) то на группу 31 выходов выдается очередной элемент множества АЗ а затем осуществляется переход к Ч 1 епи о следующих элементов множеств А и В, Б противном случае осуществляется выдача очередного элемента множества В,.

Ф о р м у л а и 3 о б р е т е и и я

Устройство для объединения множеств,, содерлсащее первый, второй C4eT4V KHj перзыйд второйэ третий, четвертый блоки -элементон И, первый .и второй блоки элементов ИЖ1, блок памятн, первый и второй регистры, первый и второй дешифраторы, схему сравнения и блок управления, прячем вход адреса элементов первого множества устройства соединен с информационным входом nepBoi o счетчика, выходы первого и второго счетчиков соединены соответственно с первыми входами первого и второго блоков злемептов И, выходы которых соединены соответственно с первым и вторым входами первого блока элементов ИЛИ выход которого соединен с е гдресныь; входом блогса памяти, выход которого соединен с информационным входом первого регистра, выход которого соединен с первым входом схемы сравнения и первым входом третьего блока элементов И, выходы третьего и четвертого блоков элеме1ггов К соединены соот ветствеино с первьп-i и вторым вхо даш-1 второго блока элемен.тов Ш Ш, выход которого яБ.гшется информационным выходом устройства, установочный вход и вход запуска устройства соеди пены соответственно с первым и вторым входами блока управления, первый выход которого соединен с выходом

о12788906

сигнала окончания работы устройства, второй, третий, четвертьй, пятый, шестой выхода блоке управления соединены соответственно с вторым вхо- 5 дом первого блока элементов И, вторым входом второго блока элементов И, со счетным входом второго счетчи

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

причем блок управления содергкит счет- -шк команд, узел памяти команд, регистр, дешифратор команд, первую группу из двенадцати элементов И, вторую и третью группы элементов И, первый, второй, третий элементы задержки, генератор имтульсов, первый, второй и третий элементы ИШ, первьй вход первого элемента ИЛИ соединен с первым входом блока управления, выход первого элемента ИПИ соединен с входом останова генератора импульсов, второй вход блока управления соединен с входом запуска генератора, выход которого соединен с первыми вхо- даГ Ш ггервой группы элементов И блока управления, вторые входы первой группы элементов И блока управления соединены с выходами дешифратора команд, причем выход1 1 первого, второго, третьего, четвертого, пятого, шестого элементов И первой группы блока управления соединены соответствен:но с вторым, седьмым, третьим, четвертым.

712

пятым и шестым выходами блока управления, выходы с седьмого, по одиннад- цатьй элементов И первой группы блока управления соедннены с первьми входами элементов И второй группы блока управленихТ, выход двенадцатого элемента И первой группы блока управления соединен с первым выходом блока управления и вторым входом первого элемента ИЛИ, вторые входы первого и второго элементов И второй группы блока управления соединены с третьим входом блока управления, вторые входы третьего, четвертого, пятого элементов И второй группы блока управления соединеигл соответствепно с четвертым, пятым п шестым входам-i блока управления, четвер 1Ъ й вход блока управления соедпне с третьим входом первого элемента И второй группы блока управления, выходы элементов И второй группы блока управ- леш;я соединены с входами второго элемента HJM, выход которого соединен с вхс-дом первого элемента задерж88908

ки, выход которого соединен со счетным входом счетчика команд, установочный вход которого соединен с выходом зторого элемента задержки,

5 вход которого соединен с выходом первого элемента ИЛИ, вход третьего элемента эадержки соединен с установочным входом регистра и выходом генератора импульсов, входы дешифратоO pa команд соединены с группой выходов поля микрокоманды узла памяти команд, группа выходов поля местного управления которого присоединена к информационным входам регистра, выход, которого соединен с первыми входами элементов И третьей группы блока управления, вторые входы элемен- тов И которой соединены с выходом третьего элемента задержки, выходы

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

5

5

памяти команд. I -

г;

Z 7 Л 5 Б 19 20 21 22 23i 24

1 З Ч

-ч

Oi

Изобретение относится к вычислительной технике. Цель изобретения- повышение быстродействия устройства. Устройство содержит два счетчика, четыре группы элементов И, две группы элементов ИЛИ, блок памяти, два регистра, два дешифратора, компаратор и блок управления. В устройстве для объединения множеств каждый зпе- мент множеств А и В выбирается только один раз. При этом коды элемеитоп каждого множества должны быть отсортированы по возрастанию. 3 ил. ю N3 00 00 ЧаЕ

Фмг.2

С

Начало

()- Ю

(WJ- 11 1-7 /

IQ

(ij- 10

Сигнал 00 окончании

3

Конец J

Составитель В.Коряковцев Редактор В.Иванова Техред А.Кравчук,

Заказ 6841/49 Тираж 67 Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

(Троизводственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

.д

Корректор С.Шекмар