Устройство для сравнения чисел

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскикСоциалистическихРеспублик(61) Дополнительное к авт. свид-ву(22) Заявлено 110381 (21) 3287797/18-24с присоединением заявки М- (23) Приоритет(1 М Кп 3 6 06 Г 7/06 Государственный комитет СССР ио делам. изобретений и открытийУЧУДИТ 681.325 (088.8) Опубликовано 07.1132 Бюллетень М 41 Дата опубликования опксания 071132(72) Авторы изобретения Сапрыки ран, О.Б,Макаревич,П.В.ЙЕмиденко 71) Заявител 54) УСТРОЙСТВО ДЛЯ СРАВНЕНИЯ 1 ИСЕЛ 25 м свторо первым 0 соеди Изобретение относится к вычислительной технике и может быть кспользовано при разработке многопроцессорных вычислительных систем.При решении ряда задач в многопроцессорных вычислительных системах возникает необходимость нахождения суммы результатов, получаемых в раз" личных решающих блоках системы. При решении обыкновейных дифференциальных уравнений; представленнйх в форме Шеннона, решающие блоки работают по программе интегрирования и в результате получаются приращения которые складываются между собой по группам. Количество слагаемых в группе колеблется от одного до десятков. Существуют эффективные методы решения дифференциальных уравнений в частных производных, в процессе которых возникает необходимость анализа сумьы результатов, получаемых в различных решающих блоках. В этом случае в сложении могут участвовать все.блоки системы. Для организации сложения чисел с плавающей запятой необходимо определить и записать во все блоки, участвующие в получении данной суммы, порядок наибольшего из слагаемых. Операции нахождения максимального и минимального числа из массива результатовимеют достаточно широкую областьприменения.Известно устройство для сравнения а,п-разрядных чисел, содержащееи узлов анализа 111.Недостаток этого устройстваего сложность. необходимость инвертировать сравниваетые числа при нахождении минимума. Кроме того, устройство не позволяет обрабатыватьнесколько массивов циФр.Наиболее близким к изобретениюявляется .устройство для сравнениячисел, содержащее матрицу ячеек,каждая из которых состоит из триггера с входными элементами И, инвертора, элементов И и ИЛИ, причемвходы элементов И каждой ячейки соединены с первым логическим входомэтой ячейки, выход первого элемента Н соединен с входами элемЕнтов ИЛИ,вторые входы первого и второго элеента ИЛН соединены соответственновторым логическим входом ячейкии выходом второго эЛемента и, выходго элемента ИЛИ соединен слогическим выходом ячейки, 3 ненным с первым логическим вхо 972501дом первой смежной ячейки матрицы,выход второго элемента ИЛИ соединенс вторым логическим выходом ячейки,соединенным с вторым логическим входом второй смежной ячейки матрицы,вход второго элемента И соединен 5через инвертор с третьим логическим выходом тай же ячейки, соединенным с третьим логическим входом смежной ячейки матрицы, первые входы вход.ных элементов И триггера соединеныс управляющей шиной соответствующейстроки матрицы, а вторые входы соединены соответственно свторым логическим входом ячейки и выходом инвертора выход триггера соединен с инфор 15мационным входои ячейки, соединеннымс входом первого элемента И 2.Недостатком этого устройства является невозможность обработки нескольких массивов чисел при организации параллельных вычислений алгорит"мов,и программ,Цель изобретения - расширениефункциональных возможностей за счеттого, что поле процессоров, участвующих в нахождении максимального илиминимального из чисел, может бытьразбито на произвольные группы процессоров, в которых параллельно происходит нахождение максимальногоили минимального из группы чисел, ЗфПоставленная цель достигаетсятем, что в устройстве для сравнениячисел, содержащем группу ячеек, каждая из которых состоит из схемы сравнения кодов двух чисел, каждая ячейка содержит узел коммутации и узелсинхронизации, причем информационныевходы устройства соецинены с первыми входамн соответствующих схемсравнения, вторые входы которых сое Одинены с первыми выходами соответствующих узлов синхронизации, третьивходы схем сравнения соединены свходом установки в нольустройства,первый выходузла коммутации 1-й ячейки (1 = 1о,где и -максимальноечисло сравниваемыхчисел) соединен спервым входом узлакоьмутации (1-1)-йячейки, а второй - с вторым входомузла коммутации (1+1)-й ячейки,третьи выходы узлов комиутации соединены с четвертым входом соответствующихсхем сравнения, пятые входы схем сравнения соединены с входом, задающимрежим сравнения, третьи выходыузлов коммутации являются выходамиустройства кода экстремального числа,третьи входы узлов коммутации соединены с выходами соответствующих схемсравнения, четвертые входы узловкоычутации соединены с первьми входами узлов синхронизации и входом,задающим количество чисел сравнения,первый выход узла синхронизации1-й ячейки соединен с вторым входом,а второй - с третьим входом узлов 65 синхронизации (1-1) -й и (1+1) -й ячеек соответственно, первые выходы узлов синхронизации являются выходами синхронизации устройства.Схема сравнения каждой ячейки содержит элементы И, ИЛИ, триггер, полусумматор, причем первый вход схемы сравнения каждой ячейки соединен с первым и вторым входами полу" сумматора, второй вход схемы сравнения соединен с первым входом первого элемента И, выход которого соединен с единичным входом триггера, второй вход первого элемента И соединен с выходом полусумматора и первым входом второго элемента И, третий вход - с четвертым входом схемы сравнения, третий и четвертый входы полусумматора соединены с пятым входом схемы сравнения, инверсный выход триггера соединен с вторым входом второго элемента И, выход которого является выходом схемы сравнения.Узел коммутации каждой ячейки содержит элементы И, ИЛИ, при этом первые входы первого и второго элементов И соединены с четвертым входом узла коммутации, вторые входы соединены с выходами соответственно первого,и второго элементов ИЛИ, первые входы которых соединены с третьим входом узла коммутации, а вторые входы - соответственно с вторым и первым входами узла коммутации, выход первого элемента ИЛИ соединен с первым входом третьего элемента ИЛИ, выход которого соединен с третьим выходом узла комиутации, выход пер" вого элемента И является вторым выходом узла коммутации, выход второго элемента И соединен с вторым входом третьего элемента ИЛИ и является первым выходои узла коммутации.Узел синхронизации каждой ячейки содержит элементы И и ИЛИ, причем первые входы первого, второго, третьего и четвертого элементов И соединены с первым входом узла синхронизации, второй вход первого элемента И соединен с вторым входом третьего элемента И и является вторым входом узла синхронизации, а выход соединен с вторым входом второго элемента И и первым входом первого элемента ИЛИ, третий вход второго элемента И соединен с вторым входом четвертого элемента И и является третьим входом узла синхронизации, выход второго элемента И соединен с первым входом второго элемента ИЛИ, втОрой вход которого соединен с выходом третьего элемента И, выход четвертого элемента И соединен с вторым входом первого элеиента ИЛИ, выход которого является первым выходом узла синхронизации, выход второго элемента ИЛИ является вторымвыходом узла синхронизации.На фиг1 представлена структурная схема устройства для сравнения чисел; на фиг. 2 - структурная схема одной ячейки устройства.Структурная схема устройства для сравнения чисел состоит из произвольного числа ячеек фиг. 1). Каждая ячейка 1 содержит схему 2 сравнения двух чисел, узел 3 коммутации, узел 4 синхронизации. Схема 2 сравнения двух чисел имеет два информа О ционных входа 5 и б, три управляющих входа 7-9. Узел 3 коммутации имеет информационный вход, который одновременно является и выходом схемы. 10 сравнения двух чисел, информационные входы 11 и 12, Узел 4 синхронизации имеет два информационных входа 13 и 14 и один управляющий вход 15, который является одновременно и управляющим входом узла 3 коммутации. 20 Выходом устройства нахождения максимального и минимального из произвольного количества чисел служит выход б, Выходами узла 3 коммутации являются выходы 19 и 17, а узла 4 синхронизации - выходы 18 и 19. Алгоритм нахождения минимального или максимального из произвольногоколичества чисел заключается в следующем.ЗОУправляющий сигнал 15 задает то количество чисел, которое участвует в нахождении максимального и минимального числа, другими словами, управ- ляющий сигнал 15 разбивает поле 35 процессоров на группы, т.е. определяет последний процессор в группе.Управляющий сигнал 9 служит для задания режимов сравнения кодов чисел.На вход 7 поступает сигнал началь ной установки триггера устройства.Сигнал 8 синхронизирует поступление разрядов сравниваемых чисел.Сравниваемые числа поступают на соответствующие ячейки на информа ционный вход 5, и, проходя черезсхему 2 сравнения двух чисел, поступают на узел 3 коммутации, который собирает по ИЛИ все приходящие разряды сравниваемых чисел и результат, 50 т,е. максимальный разряд из поступи-.вших, выдает на выход 8 в схему 2 нахождения максимального или минимального из двух чисел для сравнения с разрядом собственного сравниваемого числа. Результат сравнения, т.е. максимальное число из группы чисел, поступает на выход б. Для упрощения понимания работы устройства на фиг. 2 приведена структурная схема ячейки нахождения мак,симального или минимального из произвольного количества чисел, содержащая схему 2 сравнения, состоящую из полу- сумматора 20, триггера 21, элемен тов И 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 коммутации по выводу б. Узел 4 синхронизации начинает свою работу с поступлением на вход 15 управляющего потенциала. Если процессор в группе процессоров не последний, то на управляющий вход 15 подается единичный потенциал, длительность которого определяется количеством сравниваемых разрядов. В том случае, когда процессор в группе процессоров является последним, то на управляющий вход 15 подается нулевой потенциал, который, проходя через элемент И 29, вырабатывает единичный сигнал, поступающий на элемент ИЛИ 33 и далее на выход 18 и поступает на вход 13 следУющей ячейки,. Проходя через элемент И 30 и эле 1972501 35 Формула изобретения мент ИЛИ 33, единичный сигнал поступает на последнюю ячейку в группе,элемент И 32 открыт по нулевому сигналу на входе В 5 и единичный сигналпроходит через элементы И 32, ИЛИ 34и далее выдается на выходы В и В 9 ипоступает на следующую ячейку навход В 4.Поиск наиболыаего числа заканчивается через и тактов, где и - раз-рядность сравниваемых чисел. цля поиска наименьшего числа достаточнона вход 9 подать нулевой потенциал,далее поиск экстремального числа.происходит аналогично,.15При использовании предложенного устройства нахождения максимального или минимального из пройзвольного количества чисел в многопроцессорных системах или в однородных вычислительных структурах массив процессоров разбивается на произвольные груйпы, в которых одновременно происходит поиск наибольыей или наименьшей величины из .данной группы процессоров, что расширяет функциональные возможности устройства, в то время как прииспользовании ранее известных устройств нахождения максимальных или минимального из чисел массив, среди которых происходит поиск, заранее задан числом входов и его нельзя изменить при переходе к решению других задач. В. Устройство для сравнения чисел,: содержащее. группу ячеек, каждая из которых состоит из схемы .сравне; 40 ния кодов двух чисел. о т л и ч а ющ е е с ятем, что, с целью расширения функциональных возможностей за счет обеспечения возможности обработки нескольких массивов цифр, 45 каждая ячейка. содержит узел коммутации и .узел синхронизации, причем информационные входы устройства соединены с первыми входами соответст-, вующих схем, сравнения вторые вхо" дц которых соединены с первыми выходами соатветствующих узлов.синхронизации, третьи входы схем сравнения соединены с.входом установки в ноль устройства, первый выход узла коммутации 1-.й ячейки (1 155 и,:где и .- максимальное число сравниваемых чисел) соединен с первым входом узла коммутации (1-1)-й ячейки, а второй - с вторым. входом узла коммутации (1+1)-йячейки, третьи бО выходы узлов коммутации соединены с четвертым входом соответствующих схем сравнения,пятые входы схем сравнения соединены свходом, задающим режим сравнения, третьи выходы б 5 узлов коммутации являются выходамиустройства кода экстремального числа, третьи входы узлов коммутации соединены с выходами соответствующихсхем сравнения, четвертые входы узлов коммутации соединены с первыми входами узла синхронизации и входом,задающим количество чисел сравнения,первый выход узла синхронизации 1-й ячейки соединен с вторым входом,а второй - с третьим входом узлов синхронизации(1-1)-й и (1+1)-й ячеек соответственно, первые выходы узлов синхронизации являются выходами синхронизации устройства.2, Устройство по п. В, о т л и ч аю щ е е с я тем, что схема сравнения каждой ячейки содержит элементы И, ИЛИ, триггер, полусумматор,причем первый вход схемы сравнениякаждой ячейки соединен с первым ивторым входами полусуькатора, второйвход схемы сравнения соединен с первым входом первого элемента И,.выходкоторого соединен с единичным входоМтриггера, второй вход первого элемента И соединен с выходом полусумматора и первым входом второго элемента И, третий вход - с четвертым входом схемысравнения, третий и четвертый входы полусумматора соединены с пятым входом схемы сравнения инверсный выход триггера соединен с вторым входом второго элемента И, выход которого является выходом схе-. мы сравнения.3. Устройство по п. В, о т л ич а ю щ е е с я тем, что узел коммутации каждой ячейки содержит элемент И, ИЛИ, при этом первые входыпервого и второго элементов И соединены с четвертым входом узла коммутации, вторые входы соединены с выходами соответственно первого и второго элементовИЛИ, первые входыкоторых соединены с третьим входомузла коммутации, а вторые входы -соответственно с вторым и первымвходами узла коммутации, выход первого элемента ИЛИ соединей с первымвходом третьего элемента ИЛИ, выходкоторого соединен с третьим выходомузла коммутации, выход первого элемента И является. вторым выходом узлакоммутации, выход второго элемента И соединен с вторым входом третьего элемента ИЛИ и является первым,выходом узла коммутации. 4. Устройство по и. В, о т л ич а ю щ е е с я тем, что узел синхронизации каждой ячейки содержит элементы И и ИЛИ, причем первые входы первого, второго, третьего и четвертого элементов И соединены с первым входом узла синхронизации, второй вход первого элемента И соединен с вторым входом третьего элемента Ии является вторым входом узла синхро-низации, а выход соединен с вторымвходом второго элемента И и первымвходом первого элемента ИЛИ, третийвход второго элемента И соединен свторым входом четвертого элемента И 5и является третьим входом узла синхронизации, выход второго элемента Исоединен с первым входом второго элемента ИЛИ, второй вход которого соединен с выходом третьего элемента И, 30выход четвертого элемента И соединенс вторым входом первого элемента ИЛИ,выход которого является первым выходом узла синхронизации, выход второгоэлемента ИЛИ является вторым выходомузла синхронизации. Источники инРормации,принятые во внимание нри экспертизе1, Авторское свидетельство СССР9 б 41443, кл, С Об Г 7/04, 19792. Авторское свидетельство СССРР 424141, кл. С 06 Г 7/06, 1974972501 фи Составитель А.Суздалеведактор А.Козориз Техред А.Бабинец Корректор В.Бутяга каз 85 илиал ППП "Патент", г.ужгород, ул.Проектная,1 Тираж 731 НИИПИ Государственного по делам изобретений 13035, Москва, Ж, Р