Устройство для определения пересечения множеств Советский патент 1992 года по МПК G06F15/38 

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

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

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

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

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

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

ТПр 7Тву + 2Твп + 2Тст + TRG + TDC +

TCP + ЗТи + Тили,

где ТБУ Тгти + TRQ + TROM + Тст + Тос + 4Ти+ + 2Тили + 2Тзд 49Тлэ;

Тгти TRG Тст TDC ЗТлэ; Ти Тили Тлэ;

Тром (8-10)Тлэ;

Тз - Тст + 2Твп + 2Тф + ТЗАПРБТ + ЗГГили + Ти) + Тзд.

где То ТЗАПРЕТ Тлэ; Тзд 5Тлэ. Тогда

ТПР 2Твп + 362Тлэ: Тз 2Твп + 17Тлэ.

0

5 0 5

0

5

0

5

0

5

Относительный коэффициент увеличения быстродействия А составляет

л ТпР 2 ТБП + 362 ТЛЭ Тз 2 ТБП+ 17 Тлэ

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

А 2,27.

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

На чертеже приведена структурная схема устройства.

Устройство содержит счетчики 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 подключен к V-входам счетчиков 1 и 2, к R-входу триггера 5, а через элемент ИЛИ 24 - к S-входу триггера 25, R-вход которого вместе с С-входом счетчика 1 и V-входом регистра 4. вход которого подключен к выходу блока 3, подключены к выходу элемента И 18, первый вход которого соединен с

вторым входом элемента И 13. выход которого является выходом 29, и подключен к прямому выходу триггера 25, а второй вход подключен через формирователь 20 к S-вы- ходу блока 3, а также к прямому входу элемента ЗАПРЕТ 14 и второму входу элемента И 12, выход которого соединен с первыми входами элементов ИЛИ 17 и 24 и с Т-вхо- дом триггера 5, вход 26 соединен через элемент 19 и элемент ИЛИ 17с входами опроса элементов И 6, выходы элементов И 8 подключены к вторым входам узла 23, выход которой соединен с опросными входами элементов И 9,

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

Устройство запускается импульсом, подаваемым на вход 26. При этом в счетчики 1 и 2 записываются адресные коды первых элементов множеств А и В (в счетчик 2 записывается код на единицу меньше), подаваемые на входы 27 и 28 соответственно, триггер 5 по R-входу обнуления устанавливается в нулевое состояние, а триггер 25 по S-входу устанавливается в единичное состояние. Задержанный на элементе 19 на время записи исходной информации в счетчики 1 и 2 импульс поступает через элемент ИЛИ 17 на входы опроса элементов И 6. Код адреса первого элемента множества А поступает через элементы И 6 и ИЛИ 15 в блок 3. После окончания переходных процессов при выборке кода первого элемента множества А (в дальнейшем код А) на асинхронном S-выходе окончания переходных процессов блока 3 появляется положительный порог (перепад уровней 0 - 1), преобразуемый формирователь 20 в импульс стандартной длительности Ти ЗТлэ, который проходит через элемент И 18, открытый единичным потенциалом с прямого выхода триггера 25 на V-вход записи регистра 4, записывая в него код А, на С-вход счета счетчика 1, увеличивая его содержимое на 1, и на R-вход двухступенчатого триггера 25, переводя его в нулевое состояние.

Одновременно с этим, если на выходе дешифратора 22 присутствует нулевой сигнал (на входах отсутствует уникальный код, свидетельствующий о просмотре всех элементов множества В), то импульс с выхода формирователя 20 проходит через открытый нулевым сигналом с выхода дешифратора 22 элемент ЗАПРЕТ 14 и поступает на входы опроса элементов И 8. При этом в узле 23 анализируется на совпадение код элемента множества А (с выхода регистра 4) с нулевым кодом (с выхода блока 3). Одновременно с этим импульс проходит через

элемент И 11, открытый единичным потенциалом с инверсного выхода триггера 5, на вход +1 сложения и через элемент ИЛИ 16 на С-вход счета счетчика 2, увеличивая его 5 содержимое на 1. Задерживаясь на элементе 21 на время изменения содержимого счетчика 2 (Тэз 2:5Тлэ). импульс поступает на входы опроса элементов И 7, разрешая поступление кода адреса первого элемента

0 множества В с выхода счетчика 2 через элементы И 7 и ИЛИ 15 в блок 3. При рассмотренной ситуации импульс с выхода формирователя 20 проходит через элемент ЗАПРЕТ 14 и открывает элементы И 8, раз5 решая в узле 23 анализ на совпадение кодов первых элементов множеств А (с выхода регистра 4) и В (с выхода блока 3)

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

5 расчете асинхронной принципиальной схемы устройства. Далее импульс поступает на счетчик 2 и процесс повторяется. Если из блока 3 считан уникальный код (метка, следующая после последнего элемента множе0 ства В), то на выходе дешифратора 22 появляется единичный сигнал, и импульс с выхода формирователя 20 проходит через элементы И 12 и ИЛИ 17 на адресные входы элементов И 6, открывая их, на счетный Т5 вход триггера 5, переводя его в инверсное (единичное) состояние, и через элемент ИЛИ 24 на Т-входтриггера 25, устанавливая его в единичное состояние. При этом код адреса второго элемента множества А с вы0 хода счетчика 1 поступает через элементы И 6 и ИЛИ 15 в блок 3, а импульсом с выхода формирователя 20 в регистр 4 записывается код второго элемента множества А, счетчик 1 производит увеличение содержимого на

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

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

Таким образом, при каждом новом элементе множества А счетчик 2 изменяет режим работы, чем обеспечивается принцип перебора Каждый элемент множества А с

5 каждым элементом множества В. Если в результате сравнения в узле 23 коды А и В совпадают, то сигнал с выхода узла 23 открывает элементы И 9, и код С An В проходит с выхода регистра 4 через элементы И 9 на выход 30 устройства. Если в результате

считывания кода очередного элемента множества А дешифратор 22 идентифицирует уникальный код, то сигнал с его выхода проходит через элемент И 13, открытый единмч- ным потенциалом с прямого выхода триггера 25, на выход 29 устройства, сигнализируя о завершении перебора элементов множеств.

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

группы, выходы группы блока постоянной

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

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

0 задержки и к первым входам пятого и шестого элементов И. выход которого подключен к первому входу режима реверсивного счетчика и к первому входу первого элемента ИЛИ, выход которого подключен к счет5 ному входу реверсивного счетчика, выход третьего элемента И подключен к первым входам второго и третьего элементов ИЛИ и к информационному входу второго триггера, прямой выход которого подключен к вто0 рому входу пятого элемента И, выход которого подключен к второму входу первого элемента ИЛИ и к второму входу режима реверсивного счетчика, инверсный выход второго триггера подключен к второму вхо5 ду шестого элемента И, выход первого элемента задержки подключен к вторым входам элементов И четвертой группы, выход дешифратора подключен к второму (инверсному) входу второго элемента И и к

0 вторым входам третьего и четвертого элементов И, вход запуска устройства подключен к входу режима счетчика, к третьему входу режима реверсивного счетчика, к входу установки в О второго триггера, к второ5 му входу третьего элемента ИЛИ и к входу второго элемента задержки, выход которого подключен к второму входу второго элемента ИЛИ, выход которого подключен к вторым входам элементов И первой группы.

0 выход третьего элемента ИЛИ подключен к входу установки в 1 первого триггера.

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