Устройство для сравнения чисел Советский патент 1982 года по МПК G06F7/06 

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

При решении ряда задач в многопроцессорных вычислительных системах возникает необходимость нахождения суммы результатов, пoлyчae вix в различных решакяцих блоках систеьсл. При решении обыкновейных дифференциаль- ных уравнений, представленных в форме Шеннона, решгиоцие блоки работают по прогршиме интегрирования и в результате получаются приращения, которые складываются менду собой по группам. Количество слагаемых в группе колеблется от одного до десятков. Существуют эффективные методы решения дифференциальных уравнений в частных производных, в процессе которых возникает необходимость анализа суммы результатов, получа- емых в различных решающих блоках. В этом случае в сложении могут участвовать все .блоки системы. Для организации сложения чисел с плавающей запятой необходимо определить и записать во все блоки, участвукяцие в получении данной суммы, порядок наибольшего из слагае1иих. Операции

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

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

Наиболее близким к изобретению

15 является устройство для сравнения чисел, содержащее матрицу ячеек, каждая из которых состоит из триггера с входными элементами И, инвертора, элементов И и ИЛИ, причем

20 входы элементов И каждой ячейки соединены с первым логическим входом этой ячейки, выход первого элемента И соединен с входами элементов ИЛИ, вторые входы первого и второго эле25мента ИЛИ соединены соответственно с вторым логическим входом ячейки и выходом второго элемента И, выхрд второго элемента ИЛИ соединен с первым логическим выходом ячейки,

30 соединенным с первым fiorK4ecKHM входом первой смежной -ячейки матрицы, выход второго элемента ИЛИ соединен с вторым логическим выходом ячейки, соединенным с вторым логическим входом второй смежной ячейки матрицы, вход второго элемента И соединен через инвертор с третьим логическим выходом той же ячейки, соединенным с третьим логическим входом смезх ной ячейки матрицы, первые входы вхо ных элементов И триггера соединены с управлякадей шиной соответствующей строки матрища, а вторые входы соеди нены соответственно cвтopы логическим входе ячейки и выходом инвертора, выход триггера соединен с информационным входет нчейки, соединенньпл с входом первого элемента И 2. Недостатком этого устройства является невозможность обработки нескольк их массивов чисел при организа ции параллельных вычислений алгоритмов .и пpoгpa м, Цель изобретения расширение функцнональнык возможностей за счет того, что поле процессоров, участвукиих в нахойаден1Ш максимального или минимального и.з чисел, монет быть разбито на произвольные группы процессоров, в которых параллельно происходит нахождение максимального или минимального из группы чисел. Поставленная цель достигается тем что в устройстве для сравн ения чисел, содержащем группу ячеек, каждая из которых состоит из схемы срав нения кодов двух чисел, каждая ячейка содержит узел ко1Ф1утации и узел синхронизации, причем информационные входам устройства соединены с первыми входами соответствующих схем сравнения, вторые входы которых соединены с первыми выходами соответствующих узлов синхронизации, третьи входы схем сравнения соединены с входом установки в ноль устройства, первый выход у зла ког-с утащш -и ячейкй (i 1J...5.где п-максимсшьное число сравниваемыхчисел) соединен с перВБ - входом узла коглглутацрш (i -1) -и ячейки, а второй - с вторым входом узла коммутации (+1)-й ячейки,третьи выходы узлов коммутации соединены с четвертым входом соответствующи схем сравнения,пятые входы схем срав нения соединены с входом, задакяцим режим сравнения, третьи выходы узлов коммутации являются выходами устройства кода экстремального числа третьи входы узлов коммутации соединены с выходами соответствукяцих схем сравнения, четвертые входы узлов кo lyтaции соединены с первыми входами узлов синхронизации и входом, задакхдим количество чисел сравнения, первый вы(од узла синхронизации i -и ячейки соединен с вторым входом, а второй - с третьим входом узлов синхронизации { i - 1 j-и и { + 1)-.й ячеек соответственно, первые выходы узлов синхронизации являются выходами синхронизации устройства. Схема сравнения каждой ячейки содержит злементы И, ИЛИ, триггер, полусумматор, причем первый вход схемы сравнения каждой ячейки соединен с первым и вторыт.1 входами полусумматора, второй вход схемы сравнения соединен с первым входом первого элемента И, выход которого соединен с единичным входом триггера, второй вход первого элемента И соединен с выходом полусумматора и первым входом второго элемента И, третий вход - с четвертым входом схемы сравнения, третий и четвертый входы полycy 1 1aтopa соединены с пятым входом схемы сравнения, инверсный выход триггера соединен с вторым входом второго элемента И, выход которого является выходом схемы сравнения. Узел комглутации каждой ячейки содержит злементы И, ИЛИ, при зтом первые входы первого и второго элементов И соединены с четвертым входом узла комглутации, вторые входы соединены с выходами соответственно первого.и второго элементов ИЛИ, первые входы которых соединены с третыл входом узла коммутации, а вторые входы - соответственно с вторым и первым входами узла коммутации, выход первого элемента ИЛИ соединен с первым входом третьего элемента ИЛИ, выход которого соединен с третьим выходом узла коммутации, выход первого элемента И является вторым выходом узла коммутации, выход второго элемента И соединен с вторым входом третьего элемента ИЛИ и является первым выходом узла комглутации. Узел синхронизации каждой ячейки содержит элементы И и ИЛИ, причем первые входы первого, второго, третьего и четвертого элементов И соединены с первым входом узла синхронизации, второй вход первого элемента И соединен с вторыг/i входом третьего элемента И и является вторым входом узла синхронизации, а выход соединен с вторым входом второго элемента И и первым входом первого элемента ИЛИ, третий вход второго элемента И соединен с вторым входом четвертого элемента И и является третьи входом узла синхронизации, выход второго элемента И соединен с первыгл входом второго элемента ИЛИ, второй вход которого соединен с выходом третьего элемента И, выход четвертого элемента И соединен с вторым входом первого элемента ИЛИ, выход которого является первым выходом узла синхронизации, выход второго элемента ИЛИ является вторым выходом узла синхронизации. На фиг. 1 представлена структур ная схема устройства для сравнения чисел;- на фиг. 2 - структурная схема одной ячейки устройства. Структурная схема устройства для сравнения чисел состоит из произвольного числа ячеек фиг. 1). Ка дая ячейка 1 содержит cxeiiy 2 сравнения двух чисел, узел 3 коммутации узел 4 синхронизации. Схема 2 сравнения двух чисел имеет два информационных входа 5 и 6, три управляющи входа 7-9. Узел 3 коммутации имеет информационный вход, который одновременно является и выходом схемы. 10 сравнения двух чисел, информа онные входы 11 и 12. Узел 4 синхрон имеет два информационных входа 13 и 14 и один управляющий который является одновременно и управляющим входом узла 3 кем/мутации, Выходом устройства нахождения максимального и минимального из произвольного количества чисел служит вы ход 6. Выходами узла 3 когл гутации являются выходы IS и 17, а узла 4 синхронизации - выходы 18 и 19. Алгоритм нахождения тлинимального или максимального из произвольного количества чисел заключается в следующем. Управляющий сигнсШ 15 задает то количество чисел, которое участвует в нахождении максимального и минима ного числа, другими слова, управляющий сигнал 15 разбивает поле процессоров на группвл, т.е. определяет последний процессор в группе. Управляющий сигнал 9 служит для задания режи11ов сравнения кодов чисел На вход 7 поступает сигнал начальной установки триггера устройства. СигнсШ 8 синхронизирует поступление разрядов сравниваемых чисел. Сравниваемые числа поступают на соответствующие ячейки на информационный вход 5, и, проходя через схему 2 сравнения двух чисел, посту пают на узел 3 коммутации, который собирает по ИЛИ все приходящие разр ды сравниваемых чисел и результат, т.е. макс шкальный разряд из поступи вших, выдает на выход 8 в 2 нахождения максимального или минимального из двух чисел для сравнения с разрядом собственного сравниваемого числа. Результат сравнения, т.е. максимальное число из группы чисел, поступает на выход 6. Для упрощения понтлания работы устройства на фиг. 2 приведена стру турная схема ячейки нахолодения мак,симального или минимального из произ вольного количества чисел, содержаща схему 2 сравнения, состоящую из полу сумматора 20, триггера 21, элементов и 22 и 23, узел 3 комг.1утации, состоящий из элементов ИЛИ 24-26, элементов И 27 и 28, узел 4 синхронизации содержащий элементы И 29-32, элементы ИЛИ 33 и 34. Устройство работает следующим образом. Триггер 21 сигналом 7 устанавливается в нулевое состояние. Сигнал 9, равный единице, устанавливает режим определения максимального числа. В каждую ячейку на вход 5 поступают разряды сравниваемых чисел старшими разрядами вперед, которые проходят через полусумматор 20 и элемент И 22, поступают на узел 3 коммутации, в котором происходит сравнение значения сравниваемого разряда данной ячейки и значений сравниваемых разрядов, поступающих на входы 11 и 12. Данные сигналы 10-12 собираются на элементы ИЛИ 25 и 26 к результат сравнения поступает на элемент ИЛИ 24 и на выход 6, кото{ядй является выходом устройства и входом элемента И 23. Элемент И 23 и триггер 21 управляют прохождением сравниваемого разряда данной ячейки в узел 3 ког 1мутации. Если сигнал, поступаюгций с выхода 6, равен сигналу, поступившему на вход 5, то триггер 21 остается в том же состоянии, и следующий сравнивае1ИЫЙ разряд проходит на узел 3 коммутации. Если сигнал, поступающий с 6, равен единице, в то время как на вход 5 поступил нуль, то единица, поступившая с выхода элемента И 23, подается на триггер 21, который переходит в единичное состояние и своим сигналом запрещает прохождение сравниваемого разряда на узел 3 коммутации, и в дальнейшем данное число в сравнении не участвует. Узел 4 синхронизации управляет работой всего устройства, вырабатывает сигнал синхронизации, вьадаваемый на выход 8, который синхронизирует момент сравнения разряда сравниваемого числа данной ячейки и разряда, поступающего с узла 3 коммутации по выводу 6. Узел 4 синхронизации начинает свою работу с поступлением на вход 15 управляющего потенциала. Если процессор в группе процессоров не последний, то на управлякядий вход 15 подается единичный потенциал, длительность которого определяется количеством сравниваемых разрядов. В том случае, когда процессор в группе процессоров является последним, то на управляклдий вход 15 подается нулевой потенциал, который, проходя через И 29, вырабатывает единичный сигнал, поступающий на элемент ИЛИ 33 и далее на выход 18 и поступает на вход 13 следующей ячейки. Проходя через элемент И 30 и элеент ИЛИ 33, единичный сигнал посупает на последнюю ячейку в группе, лемент И 32 открыт по нулевому аигналу на входе 15 и единичный сигнал роходит через элементы И 32, ИЛИ 34 далее выдается на выходы 8 и 19 и поступает на следующую ячейку на вход 14.

Поиск наибольшего числа заканчивается через п тактов, где п - разрядность сравниваемых чисел. Для поиска наименьшего числа достаточно на вход 9 подать нулевой потенциал, далее поиск экстремального числа происходит аналогично.

При использовании предложенного устройства нахождения максимального ийи минимального из произвольного количества чисел в многопроцессорных системах или в однородных вычислигтельных структурах массив процессоров разбивается на -произвольные груАпы, в которых одновременно происходит поиск наибольшей или наименьшей величины из .данной группы процессоров, .что расширяет функциональные возможности устройства, в то время как прииспользовании ранее известных устройств нахождения максимальных или минимального из чисел массив/ среди которых происходит поиск, заранее задан входов и его нельзя изменить при переходе к решении) других задач.

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

1. Устройство дЛя сравнения чисел,. содержащее группу ячеек, каждая из которых, состоит из схемы .сравнегния кодов двух чисел, о т л и ч а юе е с я тем, что, с целью расширения функциональных возможностей за счет обеспечения возможности обработки нескольких массивов ц-ифр, каадая ячейка, содержит узел коммутации и узел синхронизации, причем информационные входы устройства соейинены с первыми входами соответст-; вующих схем . сравнения вторые входа которых соединены с первыми выходами .соо-тветствующих узлов синхрЬнизацйи/ третьи входы схем сравнения соединены с.йходом установки в ноль .устройства, первый выход узла коммутации i-и ячейки (Т 1 , .... п, Где .п - гчаксимальное число сравниваемых чисел) соедине.н с первым входом .у.зЛа кoм 5 тaции ( i -1) -и ячейки, а второй - с вторым.-взсрдом узла коммутации (1 + 1)-и. ячейки, третьи выходы узлов коммутации соединены . с четвертым входом сортветствуюцих схем сравнения,пятые, входы схем сравн.ениясоединены с входом, задающим режим сравнения, третьи выходы

узлов коммутации являются выходами устройства кода экстремального числа, третьи входы узлов ко лутации соединены с выходами соответствующих схем сравнения, четвертые входы узлов коммутации соединены с первыми входами узла синхронизации и вхоДом, задающи1л количество чисел сравнения, первый выход узла синхронизации i-и ячейки соединен с вторым входом,

0 а второй - с третьим входом узлов

синхронизации (-1)-и и (1+1)-й ячеек оответственно, первые выходы узлов синхронизации являются выходами синхронизации устройства.

5 2. Устройство по п. 1, о т л и ч аю щ е е с я тем, что схема сравнения каждой ячейки содержит элементы И, ИЛИ, триггер, полусумматор, причем первый вход схемы сравнения

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

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

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

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

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

5 узла коммутации, а вторые входы соответственно.с вторым и первым входами узла коммутации, выход первого элемента ИЛИ соединен с первым входом третьего элемента ИЛИ, выход

Q которого соединен с-третьим выходом узла коммутации, выход первого элемента И является - вторым выходом узла коммутации, выход второго элемента И соединен с вторым входом третьего Элемента ИЛИ и является первым

.выходом узла коммутации.

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

55 вторым входом третьего элемента И

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

выход которого является первым выходом узла синхронизации, выход второг элемента ИЛИ является вторым выходом узла синхронизации.

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР 641443, кл. G Об F 7/04, 1979.

2. Авторское свидетельство СССР 424141, кл. G 06 F 7/06, 1974 ( прототип).

4fj-,

/«

& J/

5 2/

3

r

«

Z2

фиг. 2