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

 

Изобретение относится к вычислительной технике и может быть использовано в средствах аппаратной поддержки процессора реляционной алгебры систем управления базами данных и базами знаний интеллектуальной системы автоматизированного проектирования РЭА и ЭВА Целью изобретения является повышение быстродействия Устройство содержит счетчики 1и 2, блок 3 постоянной памяти, регистр 4, триггер 5, элементы И 6-13, элемент ЗАПРЕТ 14, элементы ИЛИ 15-17, элемент И 18, элемент 19 задержки, формирователь 20 импульсов, элемент 21 задержки, дешифратор 22, узел 23 сравнения, элемент ИЛИ 24 триггер 25. 1 ил.

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

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

РЕСПУБЛИК

Cst)s G 06 F 15/38

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКЙТ СССР ч

ОПИСАНИЕ ИЗОБРЕТЕНИЯ (л ! О

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

f (21) 4813560/24 * (22) 11.04.90 (46) 23.08.92, Бюл. N 31 (71) Таганрогский радиотехнический институт им. В.Д.Калмыкова (72) А.В.Пришибской, В.М.глушань и

В.М.Курейчик (56) Авторское свидетельство СССР

N 666545, кл. G 06 F 15/38. 1978.

Авторское свидетельство СССР

bh 1176346, кл. G 06 F 15/38, 1984. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ

ПЕРЕСЕЧЕНИЯ МНОЖЕСТВ (57) Изобретенйе относится к вычислительной технике и может быть использовано в

АЛЫХ 17569ОЗ A1l

2 средствах аппаратной поддержки процессора реляционной алгебры систем управления базами данных :и базами знаний интеллектуальной системы автоматизированного проектирования РЭА и ЭВА, Целью изобретения является повышение быстродействия. Устройство: содержит счетчики 1и

2, блок 3 постоянной памяти, регистр 4, триггер 5, элементы И 6-13, элемент ЗАПРЕТ 14, элементы ИЛИ 15-17, элемент И

18, элемент 19 задержки, формирователь 20 ймпульсов, элемейт 21 задержки, дешифратор 22, узел 23 сравнения, элемент ИЛИ 24, триггер 25. 1 ил, 1756903

Л =2,27

Тогда

Тпр = 2ТБп+ 362Тлэ;

Тз = 2ТБп + 17Тлэ

Изобретение относится к вычислительной технике и может быть использовано в средствах аппаратной поддержки процессора реляционной алгебры систем управле- i ния базами данных и базами знаний 5 интеллектуальной системы автоматизированного проектирования РЭА и ЭВА.

Известно устройство для преобразования кодов с одного языка на другой, содер жащее регистр приема, два дешифратора, 10 блок памяти, регистр выдачи, регистр управления, две группы элементов И, группу элементов ИЛИ и элемент НЕ.

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

ИЛИ, триггер, узел сравнения, блок микро- 20: программного управления, содержащий узел памяти, счетчик, две группы элементов

И, дешифратор; генератортактовых импульсов, распределитель импульсов, два элемента задержки, регистр, два элемента 25

ИЛИ, триггер и два элемента И.

Недостатком известного устройства является низкое быстродействие.

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

Оценивают среднее быстродействие известного и предлагаемого решений по ме- 35 тоду суммирования средней задержки сра- батывания основных функциональных элементов устройства: .

Тлр = 7ТБУ + 2T6n + 2Тст + ТР6 + TDc + 40

Тср+ ЗТи+ Тили, где Ти = Тгти + TRG + Твом + Тст + Тос +

+4Ти+ + 2Тили + 2Тзд = 49Тлэ, 45

TrTä = TRa = Тст = Toc =3Тлэ: Ти = Тили=

= Тлэ:

TRoM = (8-10) Тлэ:

Тз = Тст+ 2ТБп+ 2Тф + Тздп рот+ 3(Тили

+ Ти)+ Тзд, где Тэ = Тздпрет = Тлэ; Тзд = 5Тлэ.

Относительный коэффициент увеличения быстродействия Лсоставляет д Тпр 2 Т п + 362 Тлэ

Тз 2 ТБп + 17 Тлэ

При использовании в качестве блока памяти, например ОЗУ ЕС-1045, собранного на ИС ОЗУ КР565РУЗ (время выборки 18-24 машинных такта длительностью 120 нс), выигрыш составляет

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

Устройство содержит счетчики 1 и 2, блок 3 постоянной памяти, регистр 4, триггер5, элементы И 6 — 13, элемент ЗАПРЕТ 14, элементы ИЛИ 15-17, элемент И 18, элемент И 19 задержки, формирователь 20 импульсов, элемент 21 задержки, дешйфратор

22, узел 23 сравнения, элемент ИЛИ 24, триггер 25, вход 26 запуска, адресные входы

27 и 28 устройства, сигнальный выход 29 и информационный выход 30 устройства.

Причем выходы счетчика 1, вход которого является входом 27, подключены через элементы И 6 к.входам элементов ИЛИ 15, элементы И 7 выходами подключены через элементы ИЛИ 15 к блоку 3, выход которого подключен к входу дешифратора 22 и входам элементов И 8, разрядные выходы реги- . стра 4 подключены к первым входам узла 23 и элементов И 9, выходы которых являются выходами 30. Выход дешифратора 22 соедикен с первыми входами элементов И 12 и 13 и инверскым входом элемента ЗАПРЕТ 14, выход которого подключен к опросным входам элементов И 8, а через элемент 21 — к входам опроса элементов И 7, к первым входам элементов И 10 и 11, вторые входы которйх подключены к прямому и инверсному выходам триггера 5 соответственно, а выходы соединены с соответствующими входами "-1" и "+1" счетчика 2 и подключены через элемент ИЛИ 16 к С-входу счетчика 2, вход которого является входом 28, а выходы йодключены к входу элементов И 7, вход 26 подключен к Ч-входам счетчиков 1 и 2, к

Я-входу триггера 5, а через элемент ИЛИ 24 — к S-входу триггера 25, R-вход которого вместе с С-входом счетчика 1 и Н-входом регистра 4, вход которого подключен к выходу блока 3, подключены к выходу элемента И 18, первый вход которого соединен с,1756903 вторым входом элемента И 13, выход которого является выходом 29, и подключен к прямому вйходу триггера 25, а второй вход подключен через формирователь 20 к S-вйходу блока 3, а также к прямому входу эле- 5 мента ЗАП РЕТ 14 и второму входу элемента

И 12, выход которого соединен с первыми входами элементов ИЛИ 17 и 24 и с Т-вхо-дом триггера 5, вход 26 соединен через элемент 19 и элемент ИЛИ 17 с входами опроса 10 элементов И 6, выходы элементов И 8 подключены к вторым входам узла 23, выход которой соединен с опросными входами элементов И 9.

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

Устройство запускается импульсом; подаваемым на вход 26. При этом в счетчики 1 и 2 зайисываются адресные коды перйых элементов множеств А и В (в счетчик 2 запи- 20 сывается код на единицу меньше), подаваемые на входы 27 и 28 соответственно, триггер 5 no R-входу обнуления устанавливается в нулевое состояние, а триггер 25 rio

S-входуустанавливается в единичное состб- 25 яние. Задержанный на элементе 19 на время записи исходной информации в счетчики

1 и 2 импульс поступает через элемейт ИЛИ

17 на входы опроса элементов И 6. Код адреса первого элемента множества А посту- 30 пает через элементы И 6 и ИЛИ 15 в блок 3, После окончания переходных процессов при выборке кода первого элемента мнбжества А (в дальнейшем код А) на асинхроннбм

S-выходе окончания переходных процессов 35 блока.3 появляется положительный порог (перепад уровней 0 — 1), преобразуемый формирователь 20 в импульс стандартной длительности Ти > ЗТлэ, который проходит через элемент И 18, открытый единичным 40 потенциалом с прямого выхода триггера 25 на V-вход записи регистра 4, записывая в него код А, на С-вход счета счетчика 1, увеличивая его содержимое на "1", и íà R-вход двухступенчатого триггера 25, переводя его 45 в нулевое состояние.

Одновременно с этим, если на вйходе дешифратора 22 присутствует нулевой сигнал.(на входах отсутствует уникальный код, свидетельствующий о просмотре всех эле- 50 ментов множества В), то импульс с.выхода формирователя 20 проходит через открытый нулевым сигналом с выхода дешифратора 22 элемент ЗАПРЕТ 14 и поступает на входы опроса элементов И 8. При этом в 55 узле 23 анализируется на совпадение код элемента множества А (с выхода регистра 4) с нулевым кодом (с выхода блока 3). Одновременно с этим импульс проходит через элемент И 11, открытый единичным потен циалом с инверсного выхода триггера 5, на.. вход "+1" сложения и через элемент ИЛИ 16 на С-вход счета счетчика 2, увелйчивая его содержимое на "1". Задерживаясь на элементе 21 на время изменения содержимого счетчика 2 (Тээ 5Тдэ1, импульс поступает на входы опроса элементов И 7, разрешая поступление кода адреСа первого элемента множества В с выхода счетчика 2 через элементы И 7 и ИЛИ 15 в блок 3. При рассмотренной ситуацйи импульс с выхода формирователя 20 проходит через элемент

ЗАПРЕТ 14 и открывает элементы И 8. разрешая в узле 23 анализ на совпадение кодов первых элемейтов множеств А(с выхода регистра 4) и В (с выхода блока 3), Функциональная надежность устройства гарантируется при"одновременном поступлении импульсов .на информационные входь. и входы опроса элементов И 8, что обеспечивается подбором импульсных характеристик формирователя 20 и согласованием задержек цепей управления при расчете асинхронной принципиальной схемы устройства. Далее импульс поступает на счетчик 2 и процесс повторяется. Гсли из блока 3 считан уникальный код (метка, следующая после последнего элемента множества В), то на выходе дешифратора 22 появляется единичный сигнал, и импульс с выхода формирователя 20 проходит через элементы И 12 и ИЛИ 17 на адресные входы элементов И 6, открывая их; на счетный Твход триггера 5, переводя его в инверсное (единичное) состояние, и через элемент

ИЛИ 24 на Т-вход триггера 25, устанавливая

его в единичное состояние. При этом код адреса второго элемента мйожества А с выхода счетчика 1 поступает через элементы И

6 и ИЛИ 15 в блок 3, а импульсом с выхода формирователя 20 в регистр 4 записывается код второго элемента множества А, счетчик

1 производит увелйчение содержимого на

"1" (формируется код адреса третьего элемента множества А), а триггер 25 обнуляется. Далее функционирование устройства протекает аналогично опиСанной ситуации, но с той разницей, что реверсивный счетчик

2 работает уже в режиме вычитания.

Таким образом, при каждом новом элементе множества А счетчик 2 изменяет режим работы. чем обеспечивается принцип перебора "Каждый элемент множества А с каждым элементом множества В", Если в результате сравнения в узле 23 коды А и В совпадают, то сигнал с выхода узла 23 открывает элементы И 9, и код С = Ай В проходит с выхода регистра 4 через элементы И

9 на выход 30 устРойства, Если в результате

1756903 считывания кода очередного элемента множества А дешифратор 22 идентифицирует уникальный код, то сигнал с его выхода проходит черезз элемент И 13, открытый единичным потенциалом с прямого выхода триггера 25, на выход 29 устройства, сигнализируя о завершении перебора элементов множеств. с пы узла сравнения, выход которого подключен к вторым входам элементов И третьей группы, выходы группы блока постоянной памяти подключены соответственно к информационным входам регистра, выход блока постоянной памяти подключен к входу формирователя импульсов, выход кото-, рого подключен к первым входам первого, второго и третьего элементов И, выход первого элемента И подключен к входу записи считывания регистра, к счетному входу счетчика и к входу установки в "0" первого триггера, выход которого подключен к второму входу первого элемента И и к первому входу ключен к вторым входам элементов И второй группы, к входу первого элемента того элементов И, выход которого подключен к первому входу режима реверсивного счетчика и к первому входу первого элемента ИЛИ, выход которого подключен к счетному входу реверсивного счетчика, выход третьего элемента И подключен к первым входам второго и третьего элементов ИЛИ и к информационному входу второго триггера, прямой выход которого подключен к вто30 рому входу пятого элемента И, выход которого подключен к второму входу первого элемента ИЛИ и к второму входу режима реверсивного счетчика, инверсный выход второго триггера подключен к второму вхомента задержки подключен к вторым входам элементов И четвертой группы, выход дешифратора подключен к второму(инверсному) входу второго элемента И и к вторым входам третьего и четвертого элементов И, вход запуска устройства подключен к вхбду режима счетчика, к третьему входу режима реверсивного счетчика, к вхо40 ду установки в "0" второго триггера, к второму входу третьего элемента ИЛИ и к входу второго элемента задержки, выход которого подключен к второму входу второго элемента ИЛИ, выход которого подключен к вторым входам элементов И первой группы, выход третьего элемента ИЛИ подключен к входу установки в "1" первого триггера, 45

Составитель А.ПришибскойРедактор И.Дербак Техред М.Моргентал Корректор Л.Лукач

Заказ 3Î89 Тираж Подписное

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

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

Производственно-издательский комбинат "Патент", г. ужгород, ул.Гагарина, 101

Формула изобретения .

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

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

И третьей группы подключены соответственйо к выходу пересечения множеств устройства, выходы элементов И четвертой группы подключены соответственно к вторйм входам элементов ИЛИ, отл и,ч а ющ е е-c я тем, что, с целью повышения быстродействия, оно содержит первый, и второй триггеры, реверсивный счетчик, первый и второй элементы задержки, формирователь импульсов, с первого по третий элементы ИЛИ и с первого по шестой элементы И, при этом входы кода элементов множеств второй руппы устройства подключены соответственно к информационным входам реверсивного счетчика, выходы которого подключены соответственно к вторым входам элементов И четвертой группы, выходы элементов И второй группы подклю-чены соответственно к входам второй груп15 четвертого элемента И, выход которого подключен к выходу признака готовности устройства, выход второго элемента И под20 задержки и к первым входам пятого и шес35:ду шестого элемента И, выход первого эле