Устройство для выделения экстремального числа

СОЮЗ СОВЕТСКИХСОРИА ЛИСТИЧЕСНИХРЕСПУБЛИК 1), С 06 Р ОПИСАНИЕ ИЗОБРЕТЕНИ(46) 30,03.90. Бюл. Ь" (71) Харьковский авиа им. Н.Е.Жуковского (72) Ю.И.Ялинич, В.Ю. В.И.Хлесткое и М.Ф.Хо (53) 681.325 (088,8) (56) Авторское свидет И 894702, кл. С 06 РАвторское свидетел Ю 964643, кл. С 06 Р ионны титут Ларчен лодный ельство СССР7/02, 1980.ьство СССР9/46, 1982. етения являетсйствия и увелийства. Целью иэобшение быстрод дежности уст повыение н кту На фиг.1 схема устрой обнаружителя сое (схема об а струфиг.2 "подгруппеля старше аяема эапро о зап риведен тва; на старшей наружит ГОСУДАРСТВЕННЫЙ. КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР АВТОРСКОМУ СВИДЕТЕЛЬСТ(54) УСТРОЙСТВО ДЛЯ ВСЕЛЕНИЯ ЭКСТРЕМАЛЬНОГО ЧИСЛА(57) Изобретение относится к вычисли" тельной технике, предназначено для выделения экстремального числа и может быть использовано в микропроцес" сорных или многомашинных вычислитель, ных системах е составе устройств для распределения заданий процессорам.Цель изобретения - повышение быстродействия и увеличение надежности.Устройство для выделения экстремального числа содержит и каналов (где и " количество обрабатываемых кодов чисел), шифратор, позиционно шифриру" Изобретение относится к вычислительной техникепредназначено для выделения экстремального (максимального или минимального) числа и может быть использовано в микропроцессорных или многомашинных вычислительных системах в составе устройств для рас .пределения заданий процессорам.,ЯО 1553971 А 1 ющий максимальные входные коды, иприоритетный блок, каждый иэ каналовсостоит из триггера, щ одноразрядныхформирователей прямого или обратногокода (где ш - разрядность обрабаты.ваемых кодов чисел) и элемента И,В каждом из и подблоков переноса,образующих первый (входной) поразрядный блок переноса шифратора, элементыИ группы выполнены трехвходовыми иустановлен дополнительный двухвходо"вой элемент И, а приоритетный блоксодержит первую группу из: е элементов ИЛИ (где з " ближайшее целое,большее или равное 4 и), вторую группуиэ Е элементов ИЛИ (где Е - ближай"шее целое, большее или равное и/в),дее группы блоков элементов И, каждаяиэ которых содержит (к"1) блоков поз элементов И в каждом и.Е-й блокс (ив+в) элементами И, обнаружитель старшей подгруппы запросов, содержащий группу из (Е) элементовИЛИ-НЕ и группу из (Е) элементов И,обнаружитель старшего запроса в под"группе, содержащий группу иэ (е)элементов ИЛИ-НЕ и группу из (з)элементов И. 3 ил.роса в подгруппе); на фиг.3 - схемашифратора,Устройство содержит (Фиг.1) и каналов (и - количество обрабатываемых5кодов чисел), каждый из которых содержит триггер 1,11.п, используемый для хранения признака наличияОбрабатываемого кода числа в соответствующем канале, Каждая группа взаи- Оосвяэанных элементов И 2, ИЛИ-НЕ 3ИЛИ 4 образует одноразрядный Формиователь прямого или обратного кодаоответствующих разрядов каждого изканалов, причем выходы одноразрядных 15Формирователей прямого или обратногоада первого (старшего) разряда кажого из каналов через элемент И 5подключены к соответствующим входамцифратора 6, у которого имеются группы информационных входов 7.11,7.1.27.1,щ, 7,п1, 7,п,2,7,п,т, управляющие входы 8,1. 8,пи выходы 9,19.иЧасть устройства, включающая в 25свой состав группу из 1 блоков элементов И 10, группу из Е элементовИЛИ 11, обнаружитель 12 старшей подгруппы запросов, группу из Я элементов ИЛИ 13 (з - ближайшее целое,большее или равное Й, 1 с - ближайшеецелое, большее или равное -) обнаруп1носитель 14 старшего запроса в подгруппе и группу из Е блоков элементовИ 15, выполняет функции приоритетногоблокаНа Фиг. показаны также установочные входы 16,1.16.п устройства,информационные входы 17,1.1 17,1.240,17,п.тп устройства, вход 18 задания режима работы устройства и выходы19.1, , 19.п устройства,Обнаружитель 12 старшей подгруппызапросов (фиг.2) содержит группу иэ(с) элементов И 21, входы 22.1,22.2, .., 22с,Обнаружитель 14 старшего запросав подгруппе схемно реализуется точнотак же, как обнаружитель 12 (фиг.2).Отличие обнаружителей 12 и 14 заключается, в общем случае, только вчисле входов - у обнаружителя 14 число входов равно в, а не Е .55Шифратор 6 (Фиг,3), выполняющий1функцию позиционной шифрации максимальных входных кодов, содержит в элементов ИЛИ-НЕ 23,123.щ, впоразрядных блоков 24,124,тапереноса и гп п подблоков 25,1,1,5.1.и, , , 25,щ,1. 25,в,п25переноса, каждый из которых содержитэлемент ИЛИ 26,Каждый иэ подблоков 25,2,125.в,и содержит также группу элементов И 27, а каждый из подблоков25.1.1, , 25,1,п состоит из группытрехвходовых элементов И 28 и дополнительного двухвходового элементаИ 29Каждый из и триггеров 1.11.ппредставляет собой обычный КБ-триггери служит для хранения признака наличия обрабатываемого кода числа в соответствующем канале, поступающегопо одноименному входу 16.116,пустройства на вход установки в единицу соответствующего триггера.Устройство работает следующим образом.Исходное состояние устройства характеризуется тем, что все триггеры1.1, , 1.и (Фиг.1) находятся в ну"левом состоянии, На информационныевходы 17,1.1. ,17,1,тч17,п,1,, 17.и,тп устройства поступают гпразрядные коды чисел, а на установочные входы 16.116.п - сигналыпризнаков кодов чисел, подлежащихобработке, задающие размер массиваобрабатываемых кодов чисел.На вход 18 задания режима работыустройства подается единичный сигнал,если необходимо обеспечить функционирование устройства в режиме выделениямаксимального числа, или нулевойсигнал, если требуется работа устройства в режиме выделения минимальногочисла,В режиме выделения максимальногочисла (на входе 18 устройства уста"новлен единичный сигнал) коды чиселс Входов 1711 уво 17 е 1 оп 1 уеоау17.п.117.п,т устройства черезоткрытые элементы И 2, затем черезэлементы ИЛИ 4 и открытые элементыИ 5 поступают на группы информационных входов 7.1.17,1.щ7.п.1,,7.и.щ шифратора 6,В режиме выделения минимальногочисла (на входе 18 устройства установлен нулевой сигнал) коды чиселинвертируются элементами ИЛИ-НЕ 3 изатем через элементы ИЛИ 4 и открытыеэлементы И 5 поступают на группы ин 15539формационных входов 7,1,1,7. 1.тп 7.п. 1 7,п.щ шифратора 6,Шифратор 6 работает следующим образом,Первыми анализируются старшие раз 5ряды кодов чисел (Фиг,3). Если хотябы один из старших разрядов кодовра вен еди ни це, то на выходе элементаИЛИ-НЕ 23,1.сформируется ноль, при 10этом если старший разряд кода -гочисла (1=1,2 п) равен нулю, тоэлемент ИЛИ 26 подблока 251. переноса выдает ноль и все разряды кода1.-го числа не проходят через элементы 15И 28 подблока 25,1.х переноса. Еслистарший разряд кода -го числа равенединице, то все разряды кода 1-гочисла проходят через элементы И 28 .подблока 25.1. переноса. 20Если старшие разряды всех кодовчисел равны нулю, то на выходе элемента ИЛИ-НЕ 23.1 формируется единица, которая дает разрешение на прохождение всех и кодов чисел через, 25элементы И 28 первого поразрядногоблока 24.:1 переноса. Таким образом,на выходах элементов И 28 первогопоразрядного блока 241 переноса фор"мируются коды чисел, подлежащих обработке, начиная с 2-го по а-й разряд,Вторым элементом ИЛИ-НЕ 23.2 ипоразрядным блоком 24.2 переноса анализируются вторые по старшинству разряды обрабатываемых кодов чисел, прошедших через первый блок переноса20.1, такии же образом, как и старшихразрядов, и т,д. В результате этогопроцесса позиционные номера экстре"мальных кодов чисел (максимальных, 40если на вход 18 устройства подан единичный сигнал, или минимальных, еслина вход 18 подан нулевой сигнал) получаются путем совпадения всех щ разрешающих сигналов, сфориированныхсоответствующими подблокаии 25.1.,25,2.25.ш.д переноса.При отсутствии сигнала на какомлибо из установочных входов 16.устройства, т,е. в случае исключения-го кода числа из обрабатываемогомассива чисел, триггер 1. остаетсяв нулевом состоянии, на его выходеформируется нулевой сигнал, которыйзапирает элемент И 5 в -м канале ичерез управляющий вход 8, шифратора6 все элементы И 28 в подблоке 25,1.переноса, прекращая тем самым подачукода -го числа для последующей обра 71 6ботки в шифраторе 6, и элемент И 29, обеспечивая Формирование на выходе 9.1 шифратора 6 нулевого сигнала.Поскольку в обрабатываемом числовом массиве иогут быть одинаковые коды чисел, то на выходах 9.19.п шифратора 6 могут сформироваться сразу несколько единичных сигналов. В этом случае предпочтение отдается тому коду числа, порядковый номер которого наибольший среди одинаковых чисел, Достигается это следующим об" разом. Злеиенты ИЛИ 11 группы опреде" ляют, в каких подгруппах выходов шифратора 6 имеются единичные сигналы, и подают соответствующие сигналы на входы обнаружителя 12 старшей подгруппы запросов (фиг.2), который фор" мируег единичный сигнал на одном иэ своих 1 выходов, соответствующем старшей подгруппе выходов шифратора 6, содержащей единичные сигналы. При этом единичный сигнал старшей под" группы через соответствующие элементы ИЛИ-НЕ 20 запирает все элементы И 21, соответствующие младшим подгруппам. Сфориированный сигнал старшей подгруппы отпирает элементы И 1 О соответствующего блока, и сигналы со старшей подгруппы выходов шифратора 6 поступают через элеиенты И 13 на входы обнаружителя 14, который срабатывает аналогично обнаружителю 12 и выделяет старший единичный сигнал внутри старшей подгруппы. Сформированный таким образом сигнал подается с выхода обнаружителя 14 через соответствующий элемент И 15 блока, соответствующего старшей подгруппе, на соответствующий выход 19.1 19.п устройства.формула и 3 о б р е т е н и н Устройство для выделения экстремального числа, содержащее и каналов (где и - количество обрабатываемых кодов чисел), шифратор, позиционно шифрирующий максимальные входные коды, и приоритетный блок, каждый иэ каналов.состоит из триггера, ш одноразрядных формирователей пряиого или об" ратного кода (где в " разрядность обрабатываемых кодов чисел) и элемента И, причем вход триггера каждого из каналов является соответствующим установочным входом устройства, управляющие входы всех одноразрядных- Формирователей прямого или обратногокода всех каналов объединены и явля 1 ются входом задания режима работы устройства, а информационный вход д-го (и:1ш) одноразрядного формирователя .прямого или обратного кода Каждого из каналов является информаЦионным входом и-го разряда обрабатываемого соответствующим каналом кода Числа, выход первого, соответствующе- о )о старшему разряду кода числа, одно" азрядного формирователя .прямого или братного кода каждого из каналов соединен с одним из входов элемента И Этого же канала, а второй вход элемена И связан с выходом григгера соответствующего канала, выход элемента И каждого иэ каналов подсоединен к пер.вому информационному входу соответствующей этому каналу группы информаци- онных входов шифратора, остальные информационные входы которой с второго по ш-й связаны с выходами соответствующих одноразрядных формирова елей прямого или обратного кода это-. 25 "о же канала, выходы шифратора подключены к входам приоритетного блока, Выходы которого являются выходами устройства, о т л и ч а ю щ е е с я ем, что, с целью повышения быстродействия и увеличения надежности, в каждом из и подблоков переноса, образующих первый (входной) поразрядный блок переноса шифратора, элементы И руппы выполнены трехвходовыми и установлен дополнительный двухвходовой Элемент И, один из входов которого соединен с выходом элемента ИЛИ подблока переноса, другой вход, связан" ный с третьими дополнительными входами элементов И группы, является управляющим входом соответствующей группы информационных входов шифратора, соединенным с выходом триггера соответствующего каналаф а выход до 45 полнительного двухвходового элемента И подсоединен к одному из входов Включенного в последовательную цепь формирования выходного сигнала шифратора элемента И группы соответствующего подблока переноса второго поразрядного блока переноса шифратора, приоритетный блок содержит первую группу из я элементов ИЛИ (где яближайшее целое, большее или равное Гп), вторую группу из 1 с элементов ИЛИ (где 1 - ближайшее целое, большееаили равное "), две группы блоков элементов И, каждая из которых содержит (1-1) блоков по я элементов И в каж" дом и к-й блок с (ия+я) элементами И, обнаружитель старшей подгруппы запросов, содержащий группу из Ь) элементов ИЛИ-НЕ и группу иэ Ь) элементов И, обнаружитель старшего запроса в подгруппе, содержащий груп" пу из (я) элементов ИЛИ-НЕ и группу из (я) элементов И, выходы шифратора с первого по п-й образуют 1 подгрупп выходов, причем -я подгруппа (=1,21 с) включает выходы шифратора от (я-я+1)-го до х я-го, а,1-я подгруппа включает выходы шифратора от (1 с я-я+1)-го до п-го, каж" дый выход шифратора, принадлежащий 1-й подгруппе выходов (1=1,2,1 с), соединен с соответствующим входом 1-го элемента ИЛИ второй группы и первым входом соответствующего элемента И 1-го блока первой группы, выход 1-го элемента ИЛИ второй группы соединен с 1-м входом обнаружителя старшей подгруппы запросов, каждый 1-й выход которого соединен с первыми входами всех элементов И 1-го блока второй группы и вторыми входами всех элементов И 1-го блока первой группы, одноименные выходы групп выходов всех блоков элементов И первой группы соединены с соответствующими входами одноименного элемента ИЛИ первой груп пы, выход р-го элемента ИЛИ первой группы (р=1,2 я) соединен с р-м входом обнаружителя старшего запроса в подгруппе, каждый р-й выход которого соединен с вторыми входами соответствующих элементов И всех блоков второй группы, выходы элементов И блоков второй группы являются соответствующими выходами устройства, входы обнаружителя старшей подгруппы запросов по (1-1)-й включительно соединены с первыми входами одноименных элементов И группы обнаружителя старшей подгруппы запросов, выходы кото" рых являются одноименными выходами обнаружителя старшей подгруппы запросов, а вторые входы соединены с выхо" дами одноименных элементов ИЛИ-НЕ группы обнаружителя старшей подгруппы запросов, 1 с-й вход которого соединен с его 1-м выходом г-й вход обнаружителя старшей подгруппы запросов при г=2,3,;ц (где ц - целая часть чис 1 с+1ла ) соединен с соответствующим2входом (г) -го и предыдущих элементов ИЛИ-НЕ группы до первого включительно обнаружителя старшей подгруппызапросов, г-й вход которого при г==ц+1, 1+2, ,Е соединен с соответствующим входом (г.)-го и предыдущихэлементов ИЛИ-НЕ группы до 1-го вклю"чительно обнаружителя старшей подгруппы запросов, выход 1-го элемента 10ИЛИ-НЕ группы обнаружителя старшейподгруппы запросов соединен с третьими входами (ц) -го и предыдущих элементов И группы обнаружителя старшейподгруппы запросов, входы обнаружителя старшего запроса в подгруппе до(з)-го включительно соединены спервыми входами одноименных элементовИ группы обнаружителя старшего запроса в подгруппе, выходы которых являются одноименными выходами обнаружи-теля старшего запроса в подгруппе,а вторые входы соединены с выходамиодноименных элементов ИЛИ-НЕ группы 711 Ообнаружителя старшего запроса в поД= группе, в-й вход которого соединен с его я-м выходом, 1"й вход обнаружителя старшего запроса в подгруппе при 1=2,3е (где- целая часть чис"з+1ла ) соединен с соответствующим2входом (1-1)-го и предыдущих элементов ИЛИ-НЕ группы до первого включительно обнаружителя старшего запроса в подгруппе, 1-й вход обнаружителя старшего запроса в подгруппе при 1=с+1, с+2, ,;з соединен с соответствующим входом (1-1)-го и предыдущих элементов ИЛИ-НЕ группы до с-го включительно обнаружителя старшего запроса в подгруппе, выход й-го элемента ИЛИ-НЕ группы обнаружителя старшего запроса в подгруппе соединен с третьими входами (с) -го и преды" дущих элементов И группы обнаружителя старшего запроса в подгруппе.церн на Тираж 561 По комитета но изобретениям и о Москва, Ж, Раушская наб одписн Заказ 157 гкнт сс крытиям ид, 4/5 сударственно 11303