Устройство для сравнения чисел
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ
Союз Советскик
Социалистических
Республик (1)972501 (6t) Дополнительное к авт. свид-ву(22) Заявлено 110381 (21) 3287797/18-24 с присоединением заявки М? (23) Г)риоритетР М g+ з
G 06 F 7/06
Государственный комитет
СССР ио делам изобретений и открытий (53) УДК 681. 325 (088.8) Опубликовано 071182Бюллетень М 41
Дата опубликования опксания 071182 (72) Авторы изобретения
В.А.Сапрыкин, Е.Ю.Шафран, О.Б.Макаревич, и П.В.цемиденко с! (71) Заявитель с с (54) УСТРОЙСТВО ДЛЯ СРАВНЕНИЯ с1ИСЕЛ
Изобретение относится к вычислительной технике и может быть кспользовано при разработке многопроцессорных вычислительных систем.
При решении ряда задач в многопроцессорных вычислительных системах возникает необходимость нахождения суммы результатов, получаемых в различных решающих блоках системы. При решении обыкновейиых дифференциальных уравнений; представленнйх в форме Шеннона, решающие блоки работают по программе интегрирования и в результате получаются приращения, которые складываются между собой по группам. Количество слагаемых в группе колеблется от одного до деcHTI В этом случае в сложении могут участвовать все.блоки системы. Для организации сложения чисел с плавающей запятой необходимо определить и записать во все блоки, участвующие в получении данной суммы, порядок наибольшего из слагаемых. Операции нахождения максимального и минимального числа из массива результатов имеют достаточно широкую область Известно устройство для сравнения m,n-разрядных чисел, содержащее и узлов анализа 1 . Недостаток этого устройства 10 его сложность. необходимость инвертировать сравниваетые числа при нахождении минимума. Кроме того, устройство не позволяет обрабатывать - несколько массивов цифр. Наиболее близким к изобретению является устройство для сравнения чисел, содержащее матрицу ячеек, каждая из которых состоит из триггера с входными элементами И, инвертора, элементов И и ИЛИ, причем входы элементов И каждой ячейки соединены с первым логическим входом этой ячейки, выход первого элемента П соединен с входами элемЕнтов ИЛИ, вторые входы первого и второго эле25.мента ИЛН соединены соответственно с вторым логическим входом ячейки и выходом второго эЛемента И, выход второго элемента ИЛИ соединен с первым логическим выходом ячейки, 30 соединенным с первым логическим вхоЭ 25О дом первой смежной ячейки матрицы, выход второго элемента ИЛИ соединен с вторым логическим выходом ячейки, соединенным с вторым логическим входом второй смежной ячейки матрицы, вход второго элемента И соединен 5 через инвертор с третьим логическим выходом тай же ячейки, соединенным с третьим логическим входом смежной ячейки матрицы, первые входы входных элементов И триггера соединены с управляющей шиной соответствующей строки матрицы, а вторые входы соединены соответственно свторым логическим входом ячейки и выходом инверто15 мационным входои ячейки, соединенным с входом первого элемента N (2). Недостатком этого устройства является невозможность обработки нескольких массивов чисел при организации параллельных вычислений алгоритмов,и программ. Цель изобретения — расширение функциональных возможностей за счет того, что поле процессоров, участвующих в нахождении максимального или минимального из чисел, может быть разбито на произвольные группы процессоров, в которых параллельно происходит нахождение максимального или минимального из группы чисел. Поставленная цель достигается тем, что в устройстве для сравнения чисел, содержащем группу ячеек, каждая из которых состоит из схемы сравнения кодов двух чисел, каждая ячей- 35 ка содержит узел коммутации и узел синхронизации, причем информационные входы устройства соецинены с первыми входамн соответствующих схем сравнения, вторые входы которых сое- д() динены с первыми выходами соответствующих узлов синхронизации, третьи входы схем сравнения соединены с входом установки в нольустройства, первый выходузла коммутации i -йячейки (i = I,...,n,где и -максимальное число сравниваемыхчисел) соединен с первым входом узлакоьмутации (i-1)-й ячейки, а второй — с вторым входом узла коммутации (i+1)-й ячейки,третьи выходы узлов комиутации соединены с четвертым входо л соответствующих схем сравнения, пятые входы схем сравнения соединены с входом, задающим режим сравнения, третьи выходы узлов коммутации являются выходами устройства кода экстремального числа, третьи входы узлов коммутации соединены с выходами соответствующих схем сравнения, четвертые входы узлов коычутации соединены с первыли вхо- 60 дами узлов синхронизации и входом, задающим количество чисел сравнения, первый выход узла синхронизации i-й ячейки соединен с вторым входом, а второй — с третьим входом узлов синхронизации (i-I) -й и (i+1) -й ячеек соответственно, первые выходы узлов синхронизации являются выходами синхронизации устройства. Схема сравнения каждой ячейки содержит элементы И, ИЛИ, триггер, полусумматор, причем первый вход схемы сравнения каждой ячейки соединен с первым и вторым входами полусумматора, второй вход схемы сравнения соединен с первым входом первого элемента И, выход которого соединен с единичным входом триггера, второй вход первого элемента И соединен с выходом полусумматора и первым входом второго элемента И, третий вход — с четвертым входом схемы сравнения, третий и четвертый входы полусумматора соединены с пятым входом схемы сравнения, инверсный выход триггера соединен с вторым входом второго элемента И, выход которого является выходом схемы сравнения. Узел коммутации каждой ячейки содержит элементы И, ИЛИ, при этом первые входы первого и второго элементов И соединены с четвертым входом узла коммутации, вторые входы соединены с выходами соответственно первого.и второго элементов ИЛИ, первые входы которых соединены с третьим входом узла коммутации, а вторые входы — соответственно с вторым и первым входами узла коммутации, выход первого элемента ИЛИ соединен с первым входом третьего элемента ИЛИ, выход которого соединен с третьим выходом узла комиутации, выход первого элемента И является вторым выходом узла коммутации, выход второго элемента И соединен с вторым входом третьего элемента ИЛИ и является первым выходои узла коммутации. Узел синхронизации каждой ячейки содержит элементы И и ИЛИ, причем первые входы первого, второго, третьего и четвертого элементов И соединены с первым входом узла синхронизации, второй вход первого элемента И соединен с вторым входом третьего элемента И и является вторым входом узла синхронизации, а выход соединен с вторым входом второго элемента И и первым входом первого элемента ИЛИ, третий вход второго элемента И соединен с вторым входом четвертого элемента И и является третьим входом узла синхронизации, выход второго элемента И соединен с первым входом второго элемента ИЛИ, второй вход которого соединен с выходом третьего элемента И, выход четвертого элемента И соединен с вторым входом первого элеиента ИЛИ, выход которого является первым выходом узла синхронизации, выход второго элемента ИЛИ является вторым выходом узла синхронизации. 972501 На фиг. 1 представлена структурная схема устройства для сравнения чисел; на фиг. 2 — структурная схема одной ячейки устройства. Структурная схема устройства для сравнения чисел состоит из произвольного числа ячеек (фиг. 1). Каждая ячейка 1 содержит схеглу 2 сравнения двух чисел, узел 3 коммутации, узел 4 синхронизации. Схегла 2 сравнения двух чисел имеет два информа- I0 ционных входа 5 и б, три управляющих входа 7-9. Узел 3 коммутации имеет информационный вход, который одновременно является и выходом схемы. 10 сравнения двух чисел, информаци-15 онные входы 11 и 12. Узел 4 синхронизации имеет два информационных входа 13 и 14 и один управлянщий вход 15, который является одновременно и управляющим входом узла 3 коммутации. 20 Выходогл устройства нахождения максимального и минимального из произвольного количества чисел служит выход б, Выходами узла 3 коммутации являются выходы 19 и 17, а узла 4 синхронизации — выходы 18 и 19. Алгоритм нахождения минимального или максимального из произвольного I количества чисел заключается в следующем. ЗО Управляющий сигнал 15 задает то количество чисел, которое участвует в нахождении максимального и минимального числа, другими словами, управ- ляющий сигнал 15 разбивает поле 35 процессоров на группы, т.е. определяет последний процессор в группе. Управляющий сигнал 9 служит для задания режимов сравнения кодов чисел. На вход 7 поступает. сигнал началь- 40 ной установки триггера устройства. Сигнал 8 синхронизирует поступление разрядов сравниваемых чисел. Сравниваемые числа поступают на соответствующие ячейки на информа- 45 ционный вход 5, и, проходя через схему 2 сравнения двух чисел, поступают на узел 3 коммутации, который собирает по ИЛИ все приходящие разряды сравниваемых чисел и результат, т.е. максиглальный разряд из поступи-. вших, выдает на выход 8 в схеглу 2 нахождения максимального или минимального из двух чисел для сравнения с разрядом собственного сравниваемого числа. Результат сравнения, т.е. максимальное число из группы чисел, поступает на выход 6. Для упрощения пониглания работы устройства на фиг. 2 приведена структурная схема ячейки нахождения мак,симального или глиннмального из произвольного количества чисел, содержащая схему 2 сравнения, состоящую из полусумматора 20, триггера 21, элемен- 65 тов И 22 и 23, узел 3 коммутации, состоящий из элементов ИЛИ 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 коммутации. Если сигнал, поступающий с выхода 6, равен сигналу, поступившему на вход 5, то триггер 21 остается в том же состоянии, и следующий сравниваемый разряд проходит на узел 3 коммутации. Если сигнал, поступающий с выхода б, равен единице, в то время как на вход 5 поступил нуль, то единица, поступившая с выхода элеглента И 23, подается на триггер 21, который переходит в единичное сосР тояние и своигл сигналом запрещает прохождение сравниваемого разряда на узел 3 коммутации, и в дальнейшем данное число в сравнении не участвует. Узел 4 синхронизации управляет работой всего устройства, выраба- тывает сигнал синхронизации, выдаваемый на выход 8, который синхронизирует момент сравнения разряда сравниваемого числа данной ячейки и разряда, поступающего с узла 3 коммутации по выводу 6. Узел 4 синхронизации начинает свою работу с поступлением на вход 15 управляющего потенциала. Если процессор в группе процессоров не последний, то на управляющий вход 15 подается единичный потенциал, длительность которого определяется количествогл сравниваемых разрядов. В тогл случае, когда процессор в группе процессоров является последним, то на управляющий вход 15 подается нулевой потенциал, который, проходя через элемент И 29, вырабатывает единичный сигнал, поступающий на элемент ИЛИ 33 и далее на выход 18 и поступает на вход 13 следУющей ячейки.. Проходя через элемент И 30 и эле1 972501 лент ИЛИ 33, единичный сигнал поступает на последнюю ячейку в группе, элемент И 32 открыт по нулевому сигналу на входе 15 и единичный сигнал проходит через элементы И 32, ИЛИ 34 и далее выдается на выходы 8 и 19 и поступает на следующую ячейку на вход 14. Поиск наибольшего числа заканчивается через и тактов, где n — раз- рядность сравниваемых чисел. для по- 10 иска наименьшего числа достаточно на вход 9 подать нулевой потенциал, далее поиск экстремального числа.происходит аналогично. При использовании предложенного устройства нахождения максимального или минимального из пройзвольного количества чисел в многопроцессорныХ системах или в однородных вычислительных структурах массив процессоров разбивается на произвольные груйпы, в которых одновременно происходит поиск наибольшей или наимень,шей величины из данной группы процессоров, что расширяет функциональные возможности устройства, в то время как при использовании ранее известных устройств нахождения максимальных или минимального из чисел массив, среди которых происходит поиск, заранее задан числом входов и eIo нельзя изменить при переходе к решению других задач. Формула изобретения 1. Устройство для сравнения чи1 сел,: содержащее. группу ячеек, каждая из которых состоит из схемы .сравне; 4р ния кодов двух чисел. о т л и ч а ющ е е с я тем, что, с целью расширения функциональных возможностей за счет обеспечения возможности обработки нескольких массивов цифр, 45 каждая ячейка. содержит узел коммутации и .узел синхронизации, причем информационные входы устройства соединены с первыми входами соответст-, вующих схем, сравнения вторые входы которых сОединены с первыми выходами соатветствующих узлов.синхронизации, третьи входы схем сравнения соединены с входом установки в ноль устройства, первый выход узла коммутации i-.é ячейки (1 1,..., 55 n,:ãäå и - rnarrcHMairI,Hoe число сравниваемых чисел) соединен с первым входом узла коюфтации (i -1) -й ячейки, а второй — с вторым .входом узла коммутации (i+1) -й..ячейки, третьи бО выходы узлов коммутации соединены с четвертым входом соответствующих схем сравнения, пятые входы схем сравнения соединены с входом, задающим режим сравнения, третьи выходы б5 узлов коммутации являются выходами устройства кода экстремального числа, третьи входы узлов коммутации соединены с выходами соответствующих схем сравнения, четвертые входы узлов коммутации соединены с первыми входами узла синхронизации и входном, задающим количество чисел сравнения, первый выход узла синхронизации i-й ячейки соединен с вторым входом, а второй - с третьим входом узлов синхронизации (i-1)-й и (1+1)-й ячеек соответственно, первые выходы узлов синхронизации являются выходами синхронизации устройства. 2. Устройство по п. 1, о т л и ч аю щ е е с я тем, что схема сравнения каждой ячейки содержит элементы И, ИЛИ, триггер, полусумматор, причем первый вход схемы сравнения каждой ячейки соединен с первым и вторым входами полусумчатора, второй вход схемы сравнения соединен с первым входом первого элемента И,.выход которого соединен с единичным входом триггера, второй вход первого элемента И соединен с выходом полусумматора и первым входом второго элемента И, третий вход - с четвертым входом схемы сравнения, третий и четвертый входы полусумматора соединены с пятым входом схемы сравнения> инверсный выход триггера соединен с вторым входом второго элемента И, выход которого является выходом схе-. мы сравнения. 3. Устройство по II ° 1, о т л ич а ю щ е е с я тем, что узел коммутации каждой ячейки содержит элемент И, ИЛИ, при этом первые входы первого и второго элементов И соединены с четвертым входом узла коммутации, вторые входы соединены с выходами соответственно первого и вто рого элементов ИЛИ, первые входы которых соединены с третьим входом узла коммутации, а вторые входы— соответственно с вторым и первым входами узла коммутации, выход первого элемента ИЛИ соединей с первым входом третьего элемента ИЛИ, выход которого соединен с- третьим выходом узла коммутации, выход первого элемента И является. вторым выходом узла коммутации, выход второго элемента И соединен с вторым входом третьего элемента NJIH и является первым ,выходом узла коммутации. 4 Устройство rro и 1, о т л ич а ю щ е е с я тем, что узел синхронизации каждой ячейки содержит элементы И и ИЛИ, причем первые входы первого, второго, третьего и четвертого элементов И соединены с первым входом узла синхронизации, второй вход первого элемента И соединен с вторым входом третьего элемента И 972501 10 и является вторым входом узла синхро- низации, а выход соединен с вторым входом второго элемента И и первым входом первого элемента ИЛИ, третий вход второго элемента И соединен с вторым входом четвертого элемента И 5 и является третьим входом узла синхронизации, выход второго элемента И соединен с первым входом второго элемента ИЛИ, второй вход которого соединен с выходом третьего элемента И, 3Q выход четвертого элемента И соединен с вторым входом первого элемента ИЛИ, выход которого является первым выходом узла синхронизации, выход второго элемента ИЛИ является вторым выходом узла синхронизации. Источники инФормации, принятые во внимание нри экспертизе 1. Авторское свидетельство СССР Р 641443, кл. G 06 F 7/04, 1979 ° 2. Авторское свидетельство СССР 9 424141, кл. С 06 F 7/06, 1974 (прототип). 972501 Составитель A.Ñóçäàëåâ Техред A.Áàáèíåö Корректор В.Бутяга Редактор A.Êîçoðèý Филиал ППП "Патент", г.ужгород, ул.Проектная, 4 Заказ 8518/41 Тираж 731 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5
