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

,У ИДЕТЕЛЬСТВУ ОСУДАРСТВЕННЫЙ КОМИТЕТО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМРИ ГКЙТ СССР ОПИСАН И К АВТОРСКОМУ СВ(71) Таганрогский радиотехнический институт им. В.Д.Калмыкова(56) Авторское свидетельство СССР М 666545, кл. С 06 Е 15/38. 1978.Авторское свидетельство СССР 1 Ф 1176346, кл, 6 06 Р 15/38, 1984. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ПЕРЕСЕЧЕНИЯ МНОЖЕСТВ (57) Изобретенйе относится к вычислительной технике и может быть использованов Я 2 17569 ОЗ А 2средствах аппаратной поддержки процессора реляционной алгебрысистем управления базами данных и базами знаний интеллектуальной системы автоматизированного проектирования РЭА и ЭВА, Целью изобретения является повышение быстродействия. Устройство содержит счетчики 1 и 2, блок 3 постоянной памяти; регистр 4, триггер 5, элементы И 6-13, элемент ЗАПРЕТ 14, элементы ИЛИ 15-17, элемент И 18, элемент 19 задержки, формирователь 20 ймпульсов, элемейт 21 задержки, дешифратор 22, узел 23 сравнения, элемент ИЛИ 24, триггер 25. 1 ил,Г оЛ =2,27 Тогда Тпр = 2 ТБп+ 362 Тлэ:Тз = 2 ТБп + 17 Тлэ Изобретение относится к вычислительной технике и может быть использовано в средствах аппаратной поддержки процессора реляционной алгебры систем управле-ния базами данных и базами знаний 5 интеллектуальной системы автоматизированного проектирования РЭА иЭВА.Известно устройство для преобразования кодов с одного языка на другой, содер жащее регистр приема, два дешифратора, 10 блок памяти, регистр выдачи, регистр управления, две группы элементов И, группу элементов ИЛИ и элемент НЕ.Наиболее близким по технической сущности к предлагаемому является устройство 15 . для определения пересечения множеств, содержащее два регистра, пять групп элементов И; группу элементов ИЛИ, дешифратор, блок памяти, два счетчика, элемент ИЛИ, триггер, узел сравнения, блок микро: программного управления, содержащий узел памяти, счетчик, две группы элементов И, дешифратор; генератортактовых импульсов, распределитель импульсов, два элемента задержки, регистр, два элемента 25 ИЛИ, триггер и два элемента И.Недостатком известного устройства является низкое быстродействие.- Цель изобретения - повышение быстродействия за счет перехода от программно аппаратной архитектуры к аппараткой, позволяющей распараллелить часть операций алгоритма пересечения множеств.Оценивают среднее быстродействие известного и предлагаемого решений по ме тоду суммирования средней задержки сра-батывания основных функциональных элементов устройства: . Тпр =. 7 ТБУ + 2 ТБП + 2 ТСТ + Тйб + ТОС + 40Тср+ ЗТи+ Тили,где Тьу = Тгти + Тяо + Твом + Тст + Тос ++ Ти)+ Тзд,где Тф = Тздпрет = Тлэ; Тзд = 5 Тлэ. Относительный коэффициент увеличения быстродействия Лсоставляет д Тпр 2 ТБп + 362 Тлэ Тз 2 ТБп + 17 Тлэ При использовании в качестве блока памяти, например ОЗУ ЕС, собранного на ИС ОЗУ КР 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 - к 8-входу триггера 25, й-вход которого вместе с С-входом счетчика 1 и Н-входом регистра 4, вход которого подключен к выходу блока 3, подключены к выходу элемента И 18, первый вход которого соединен с,1756903вторым входом элемента И 13. выход кото- элемент И 11, открытый единичным потенрого является выходом 29, и подключен кциалом с инверсного.выхода триггера 5, напрямому вйходу триггера 25, а второй вход вход "+1" сложения и через элемент ИЛИ 16 подключен через формирователь 20 к Я-вй- на С-вход счета счетчика 2, увелйчивая его ходу блока 3, а также к прямому входу"эле содержимое на "1", Задерживаясь на элемента ЗАПРЕТ 14 и второму входу элемента менте 21 на время изменения содержимого И 12, выход которого соединен с первыми счетчика 2 (Тээ 5 Тдэ), импульс поступает входами элементов ИЛИ 17 и 24 и с Т-вхо на входы опроса элементов И 7, разрешая дом триггера 5, вход 26 соединен через эле- поступление кода адреСа первого элемента мент 19 и элементИЛИ 17 с входами опроса 10 множества В с выхода счетчика 2 через эле. элементов И 6, выходы элементов И 8 под- менты И 7 и ИЛИ 15 в блок 3. При рассмотключены к вторым входам узла 23, выходренной ситуацйи импульс" с выхода которой соединен с опросными входами формирователя 20 проходит через элемент элементов И 9. ЗАПРЕТ 14 и открывает элементы И 8. разУстройство работает следующим обра решая в узле 23.анализ на совпадение кодов зом., : .: .: первых элемейтов множеств А(с выхода реУстройство запускается импульсом; по- гистра 4) и В (с выхода блока 3),даваемым на вход 26, При этом в счетчики 1 .: Функциональная надежность устройсти 2 зайисываются адресные коды первых ва гарантируется при"одновременном по- элементов множеств А и В (в счетчик 2 запи ступлении импульсов на информационные . сывается код на единицу меньше), подавае- входы и входы опроса элементов И 8, что мые на входы 27 и 28 соответственно, обеспечивается подбором импульсных хатриггер 5 по В-входу обнуления устанавли- рактеристик формирователя 20 и согласовавается в нулевое состояние, а триггер 25 по нием задержек цепей управления при Я-входуустанавливается в единичноесосто расчете асинхронной принципиальной схеяние, Задержанный на элементе 19 на вре- мы устройства, Далее импульс поступает на мязаписиисходнойинформации всчетчикисчетчик 2 и процесс повторяется. Если из 1 и 2 импульс поступает через элемейт ИЛИ блока 3 считан уникальйый код (метка, сле на входы опроса элементов И 6. Код ад- дующая после последнего элемента множереса первого элемента множества А посту ства В), то на выходе дешифратора 22 пает через элементы И 6 и ИЛИ 15 в блок 3,появляется единичный сигнал,и импульс с После окончания переходных процессов выхода формирователя 20 проходит через при выборке кода первого элемента мноЖе- элементы И 12 и ИЛИ 17 на адресные входы ства А(в дальнейшем код А) на асинхроннбм элементов И 6, открывая их; на счетный ТЯ-выходе окончания переходных процессов 35 вход триггера 5, переводя его в инверсное блока.З появляется положительный порог (единичное) состояние, и через элемент (перепад уровней 0 -1 1), преобразуемый ИЛИ 24 на Т-вход триггера 25, устанавливая формирователь 20 в импульс стандартной его в единичное состояние. При этом код длительности ТиЗТлэ, который проходит адреса второго элемента мйожества А с вычерез элемент И 18, открытый единичным 40 хода счетчика 1 поступает через элементы И потенциаломс прямого выхода триггера 25 6 и ИЛИ 15 в блок 3, а импульсом с выхода на Ч-вход записи регистра 4, записывая в формирователя 20 в регистр 4 записывается него код А, на С-вход счета счетчика 1, уве- код второго элемента множества А, счетчик личивая его содержимое на "1", и на В-вход1 производит увелйчение содержимого на двухступенчатого триггера 25, переводя его 45 "1" (формируется код адреса третьего алев нулевое состояние, "мента множества А), а триггер 25 обнуляетОдновременно с этим, если на вйходе ся. Далее функционирование устройства дешифратора 22 присутствует нулевой сиг- протекает аналогично описанной ситуации, нал (на входах отсутствует уникальный код, но с той разницей, что реверсивный счетчик свидетельствующий о просмотревсехэле 2 работает уже в режиме вычитания.ментов множества В), то импульс с.выхода Таким образом, при каждом новом элеформирователя 20 проходит через откры- менте множестваА счетчик 2 изменяет ретый нулевым сигналом с выхода дешифрато- жим работы. чем обеспечивается принцип ра 22 элемент ЗАПРЕТ 14 и поступает на перебора "Каждый элемент множества А с входы опросаэлементов И 8. При этом в 55 каждым элементом множества В", Если в узле 23 анализируется на совпадение код результате сравнения в узле 23 коды А и В элемента множества А(с выхода регистра 4) совпадают, то сигнал с выхода узла 23 отс нулевым кодом (с выхода блока 3), Одно- крывает элементы И 9, и код С = Аг 1 В провременно с этим импульс проходит через ходит с выхода регистра 4 через элементы И9 на выход 30 устройства, Если в результатеГ1756903 считывания кода очередного элемента множества А дешифратор 22 идентифицирует уникальный код, то сигнал с его выхода проходит черезз элемент И 13, открытый единичным потенциалом с прямого выхода триггера 25, на выход 29 устройства, сигнализируя о завершении перебора элементов множеств.с пы узла сравнения, выход которого подключен к вторым входам элементов И третьей группы, выходы группы блока постоянной памяти подключены соответственно к информационным входам регистра, выход блока постоянной памяти подключен к входу формирователя импульсов, выход кото-,рого подключен к первым входам первого,второго и третьего элементов И, выход первого элемента И подключен к входу записи считывания регистра, к счетному входу счетчика и к входу установки в "О" первого триггера, выход которого подключен к второму входу первого элемента И и к первому входу ключен к вторым входам элементов И второй группы, к входу первого элемента того элементов И, выход которого подключен к первому входу режима реверсивного счетчика и к первому входу первого элемента ИЛИ, выход которого подключен к счетному входу реверсивного счетчика, выход третьего элемента И подключен к первым входам второго и третьего элементов ИЛИ и к информационному входу второго триггера, прямой выход которого подключен к вто 30 рому входу пятого элемента И, выход которого подключен к второму входу первого элемента ИЛИ и к второму входу режима реверсивного счетчика, инверсный выход второго триггера подключен к второму вхомента задержки подключен к вторым входам элементов И четвертой группы, выход дешифратора подключен к второму(инверсному) входу второго элемента И и к вторым входам третьего и четвертого элементов И, вход запуска устройства подключен к вхбду Режима счетчика, к третьему входу режима реверсивного счетчика, к вхо 40 ду установки в "О" второго триггера, к второму входу третьего элемента ИЛИ и к входу второго элемента задержки, выход которого подключен к второму входу второго элемента ИЛИ, выход которого подключен к вторым входам элементов И первой группы, выход третьего элемента ИЛИ подключен к входу установки в "1" первого триггера,45 50 Составитель А.Пришибской:Редактор И.ДербакТехред М.Моргентал Корректор Л,Лукач Заказ ЗО 89Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб 4/5 Производственно-издательский комбинат "Патент", г. ужгород, ул.Гагарина, 101 Формула изобретения .Устройство для определения пересече-. ния множеств, содержащее счетчик, блок постоянной памяти, регистр, дешифратор, узел сравнения, с первой по четвертую группы элементов И игруппу элементов ИЛИ, при этом входы кода элементов множеств первой группы устройства подключены соответственно к информационным входам первого счетчика; выходы которого подключены соответственно к первым входам элементов И первой группы, выходы которых подключены соответственно к первым входам элементов ИЛИ группы, выходы которых подключены соответственно к адресным входам блока постоянной памяти, выходы группы которого подключены соответственно к информационным входам дешифратора и к первым входам элементов И второй группы, выходы регистра подключены соответственно к первым входам элементов И третьей группы и к входам первой группы узла сравнения, выходы элементов И третьей группы подключены соответственйо к выходу пересечения множеств устройства, выходы элементов И четвертой группы подключены соответственно к вторйм входам элементов ИЛИ, о т л и ч а ющ е еся тем, что, с целью повышения быстродействия,оно содержит первый. и второй триггеры, реверсивный счетчик, первый и второй элементы задержки, формирователь импульсов, с первого по третий элементы ИЛИ и с первого по шестой элементы И, при этом входы кода элементов множеств второй руппы устройства подключены соответственно к информационным входам реверсивного счетчика, выходы которого подключены соответственно к вторым входам элементов И четвертой группы, выходы элементов И второй группы подключены соответственно к входам второй груп 15 четвертого элемента И, выход которогоподключен к выходу признака готовности устройства, выход второго элемента И под 20 задержки и к первым входам пятого и шес 35:ду шестого элемента И, выход первого эле