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

 

Изобретение относится к вычислительной технике, предназначено для выделения экстремального числа и может быть использовано в микропроцессорных или многомашинных вычислительных системах в составе устройств для распределения заданий процессорам. Цель изобретения - повышение быстродействия и увеличение надежности. Устройство для выделения экстремального числа содержит N каналов (где N - количество обрабатываемых кодов чисел), шифратор, позиционно шифрирующий максимальные входные коды, и приоритетный блок, каждый из каналов состоит из триггера, M одноразрядных формирователей прямого или обратного кода (где M - разрядность обрабатываемых кодов чисел) и элемент И. В каждом из N подблоков переноса, образующих первый (входной) поразрядный блок переноса шифратора, элементы И группы выполнены трехвходовыми и установлен дополнительный двухвходовой элемент И. Приоритетный блок содержит первую группу из S элементов ИЛИ (где S - ближайшее целое, большее или равное √N), вторую группу из K элементов ИЛИ (где K - ближайшее целое, большее или равное N/S), две группы блоков элементов И, каждая из которых содержит (K-1) блоков по S элементов И в каждом и K-й блок с (N - K<SP POS="POST">.</SP>S + S) элементами И, обнаружитель старшей подгруппы запросов, содержащий группу из (K - 1) элементов ИЛИ-НЕ и группу из (K - 1) элементов И, обнаружитель старшего запроса в подгруппе, содержащий группу из (S - 1) элементов ИЛИ-НЕ и группу из (S - 1) элементов И. 3 ил.

СОЮЗ СОВЕТСКИХ

СОРИА ЛИСТИЧЕСНИХ

РЕСПУБЛИК (51) G 06 Р 7/02

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К А ВТОРСНОМ,Ф СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ. КОМИТЕТ пО изОБРетениям и DTKpbfTHRM

ПРИ ГКНТ СССР

1 (21) 3926963/24-63 (22) 04.07.85 (46) 30 ° 03.90. Бюл. h" 12 (71) Харьковский авиационный институт им. Н.Е.Жуковского (72) lO.È.ßëèíè÷, В.Ю.Ларченко, В.И.Хлестков и М.Ф.Холодный (53) 681.325 (088.8) (56) Авторское свидетельство СССР

1г 894702, кл. C 06 F 7/02, 1980.

Авторское свидетельство СССР

8 964643, кл. C 06 F 9/46, 1982. (54) УСТРОЙСТВО ДЛЯ ВЫДЕЛЕНИЯ ЭКСТРЕМАЛЬНОГО 4ИСЛА (57) Изобретение относится к вычисли" тельной технике, предназначено для выделения экстремального числа и может быть использовано в микропроцессорных или многомашинных вычислитель, ных системах в составе устройств для распределения заданий процессорам.

Цель изобретения - повышение быстродействия и увеличение надежности.

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

ÄÄSUÄÄ 1553971 A1

2 ющий максимальные входные коды, и приоритетный блок, каждый иэ каналов состоит из триггера, m одноразрядных формирователей прямого или обратного кода (где m - разрядность обрабатываемых кодов чисел) и элемента И, В каждом из и подблоков переноса, образующих первый (входной) поразрядный блок переноса шифратора, элементы

И группы выполнены трехвходовыми и установлен дополнительный двухвходо" вой элемент И, а приоритетный блок содержит первую группу из: е элементов ИЛИ (где s - ближайшее целое, большее или равное 4п), вторую группу иэ k элементов ИЛИ (где k - ближай" шее целое, большее или равное и/э), две группы блоков элементов И, каждая фр иэ KQTopblx содержит (Е-1) блоков по

s элементов И в каждом и.k-й блок С с (и-k s+s) элементами И, обнаружитель старшей подгруппы запросов, со- Я держащий группу из (k-1) элементов

ИЛИ-НЕ и группу из (k-1) элементов И, обнаружитель старшего запроса в под- Ql группе, содержащий группу иэ (е-1) Ql элементов ИЛИ-НЕ и группу из (в-1) элементов И. 3 ил. ЯР

Целью изобретения является повышение быстродействия и увеличение надежности устройства.

На фиг.1 приведена структурная схема устройства; на фиг.2 - схема обнаружителя старшей подгруппы запросов (схема обнаружителя старшего зап1553971 роса в подгруппе); на фиг.3 - схема шифратора .

Устройство содержит (фиг. 1) и каналов (n - количество обрабатываемых

5 кодов чисел), каждый из которых содержит триггер 1.1,..., l.п, используемый для хранения признака наличия обрабатываемого кода числа в соответс твующем канале. Каждая группа взаи- 10 освяэанных элементов И 2, ИЛИ-НЕ 3

ИЛИ 4 образует одноразрядный формиователь прямого или обратного кода оответствующих разрядов каждого из.

Каналов, причем выходы одноразрядных 15

Формирователей прямого или обратного

>1ада первого (старшего) разряда кажЦого из каналов через элемент И 5 г>одключены к соответствующим входам

» ифратора 6, у которого имеются груп- 20 г ы информационных входов 7. l ° 1, 7 ° 1 ° 2 ° ° ° 17 ° l em 7,п ° 1 7,п ° 2 ° °,р

7,n.m, управляющие входы 8.1,...,8.п и выходы 9.1,...,9.п °

Часть устройства, включающая в 25 свой состав группу из k блоков элементов И 10, группу из k элементов

ИЛИ 11, обнаружитель 12 старшей подгруппы запросов, группу из S элементов ИЛИ 13 (s - ближайшее целое, большее или равное >й, k - ближайшее целое, большее или равное -) обнаруи житель 14 старшего запроса в подгруп пе и группу из k блоков элементов

И 15, выполняет функции приоритетного блока °

На фиг.! показаны также установочные входы 16. I, ..., 16.п устройства, информационные входы 17.1.1 17.1.2

17. t .m...,, 17.п. 1, 17,п,2, ..., 17,п.л устройства, вход 18 задания режима работы устройства и выходы

19 ° 1, ° ... 19.п устройства.

Обнаружитель 12 старшей подrруппы запросов (фиг.2) содержит группу иэ (k-1) элементов ИЛИ-НЕ 20, группу из (k-1) элементов И 21, входы 22.1, 22.2, . ° ., 22 ° k, Обнаружитель 14 старшего запроса в подгруппе схемно реализуется точно так же, как обнаружитель 12 (фиг.2).

Отличие обнаружителей 12 и 14 заключается, в общем случае, только в числе входов - у обнаружителя 14 число входов равно s, а не k °

Шифратор 6 (фиг.3), выполняющий

I функцию позиционной шифрации максимальных входных кодов, содержит m элементов ИЛИ-HE 23„.1,...,23,m, m поразрядных блоков 24,1,...,24.m переноса и m п подблоков 25,1.1, 5.l.n, ..., 25.тп.1,....,25.m.n

25 переноса, каждый из которых содержит элемент ИЛИ 26, Каждый иэ подблоков 25.2.1,..., 25.m.n содержит также группу элементов И 27, а каждый из подблоков

25.1.1, ..., 25,1.п состоит из группы трехвходовых элементов И 28 и дополнительного двухвходового элемента

И 29 °

Каждый из и триггеров 1.1,...,1.п представляет собой обычный RS-триггер и служит для хранения признака наличия обрабатываемого кода числа в соответствующем канале, поступающего по одноименному входу 16„1,...,16.п устройства на вход установки в единицу соответствующего триггера.

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

Исходное состояние устройства характеризуется тем, что все триггеры

1.1, ..., l.n (фиг.l) находятся в нулевом состоянии. На информационные входы 17.1.1,...,17.1.my...,17.п.l, ...,17.п,m устройства поступают mразрядные коды чисел, а на установочные входы 16.1,...,16.п - сигналы признаков кодов чисел, подлежащих обработке, задающие размер массива обрабатываемых кодов чисел.

На вход 18 задания режима работы устройства подается единичный сигнал, если необходимо обеспечить функционирование устройства в режиме выделения максимального числа, или нулевой сигнал, если требуется работа устройства в режиме выделения минимального числа.

В режиме выделения максимального числа (на входе 18 устройства уста" новлен единичный сигнал) коды чисел с входов 17.1.1,...,17.1.mp..., 17.п.1,...,17.n.m устройства через открытые элементы И 2, затем через элементы ИЛИ 4 и открытые элементы

И 5 поступают на группы информационных входов 7.1.1,...,7.1.m, 7.п.l, ...,7.n.m шифратора 6.

В режиме выделения минимального числа (на входе 18 устройства установлен нулевой сигнал) коды чисел инвертируются элементами ИЛИ-НЕ 3 и затем через элементы ИЛИ 4 и открытые элементы И 5 поступают на группы ин15539 формационных входов 7.1.1, 7. 1.m, 7.п. 1, ..., 7.п .m шифратора 6.

Шифратор 6 работает следующим образом.

Первыми анализируются старшие раз5 ряды кодов чисел (фиг.3). Если хотя бы один из старших разрядов кодов ра вен еди ни це, то на выходе элемента

ИЛИ-Н Е 23. 1, сформи руется ноль, при этом, если старший разряд кода i-ro числа (i=1 2,...,и) равен нулю, то элемент ИЛИ 26 подблока 25.1.i переноса выдает ноль и все разряды кода

1.-го числа не проходят через элементы 15

И 28 подблока 25. 1. i переноса. Если старший разряд кода i-го числа равен единице, то Все разряды кода i-ro числа проходят через элементы И 28 подблока 25.1.i переноса. 20

Если старшие разряды всех кодов чисел равны нулю, то на выходе элемента ИЛИ-НЕ 23.1 формируется единица, которая дает разрешение на прохождение всех и кодов чисел через . 25 элементы И 28 первого поразрядного блока 24.:1 переноса. Таким образом, на выходах элементов И 28 первого поразрядного блока 24 ° 1 переноса формируются коды чисел, подлежащих обра- 30 ботке, начиная с 2-го no m-й разряд, Вторым элементом ИЛИ-НЕ 23.2 и поразрядным блоком 24.2 переноса анализируются вторые по старшинству разряды обрабатываемых кодов чисел, прошедших через первый блок переноса

24.1, таким же образом, как и старших разрядов, и т.д. В результате этого процесса позиционные номера экстремальных кодов чисел (максимальных, 40 если на вход 18 устройства подан единичный сигнал, или минимальных, если на вход 18 подан нулевой сигнал) получаются путем совпадения всех m разрешающих сигналов, сформированных соответствующими подблоками 25.1.i, 25.2.i,...,25.m.i переноса.

При отсутствии сигнала на какомлибо из установочных входов 16.i устройства, т.е. в случае исключения

i-ro кода числа из обрабатываемого массива чисел, триггер 1.i остается в нулевом состоянии, на его выходе формируется нулевой сигнал, который запирает элемент И 5 В i-м KaHBJle u через управляющий вход 8.i шифратора

6 все элементы И ?8 в подблоке 25.1.i переноса, прекращая тем самым подачу кода i-ro числа для последующей обра71 6 ботки в шифраторе 6, и элемент И 29, обеспечивая формирование на выходе

9.i шифратора 6 нулевого сигнала.

Поскольку в обрабатываемом числовом массиве могут быть одинаковые коды чисел, то на выходах 9.1,...,9.п шифратора 6 могут сформироваться сразу несколько единичных сигналов.

В этом случае предпочтение отдается тому коду числа, порядковый номер которого наибольший среди одинаковых чисел. Достигается это следующим образом. Элементы ИЛИ 11 группы определяют, в каких подгруппах выходов шифратора 6 имеются единичные сигналы, и подают соответствующие сигналы на входы обнаружителя 12 старшей подгруппы запросов (фиг.2), который фор" мируег единичный сигнал на одном иэ своих k выходов, соответствующем старшей подгруппе выходов шифратора 6, содержащей единичные сигналы. При этом единичный сигнал старшей под" группы через соответствующие элементы

ИЛИ-НЕ 20 запирает все элементы И 21, соответствующие младшим подгруппам.

Сформированный сигнал старшей подгруппы отпирает элементы И 10 соот- ветствующего блока, и сигналы со старшей подгруппы выходов шифратора

6 поступают через элементы И 13 на входы обнаружителя 14, который срабатывает аналогично обнаружителю 12 и выделяет старший единичный сигнал внутри старшей подгруппы. Сформированный таким образом сигнал подается с выхода обнаружителя 14 через соответствующий элемент И 15 -блока, сООт» ветствующего старшей подгруппе, на соответствующий выход 19.1,..., 19.п устройства.

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

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

1553971 кода всех каналов объединены и явля1 ются входом задания режима работы устройства, а информационный вход

n-ro (n=1,... m) одноразрядного форИирователя прямого или обратного кода

Каждого из каналов является информаЦионным входом п-го разряда обрабатываемого соответствующим каналом кода

Числа, выход первого, соответствующе- о

rto старшему разряду кода числа, одно" азрядного Формирователя . прямого или братного кода каждого из каналов оединен с одним из входов элемента И

Этого же канала, а второй вход элемен-5

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

Информа ционные входы которой с второго по m-й связаны с выходами соответствующих одноразрядных формирова1 елей прямого или обратного кода это-. 25

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

t ðóïïû выполнены трехвходовыми и установлен дополнительный двухвходовой

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

И подсоединен к одному из входов

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

ИЛИ (где k - ближайшее целое, большее и или равное -), две группы блоков элементов И, каждая из которых содержит (k-1) блоков по s элементов И в каждом и k-й блок с (и-k s+s) элементами И, обнаружитель старшей подгруппы запросов, содержащий группу из (k-1) элементов ИЛИ-НЕ и группу иэ (1 -1) элементов И, обнаружитель старшего запроса в подгруппе, содержащий группу из (s-1) элементов ИЛИ-НЕ и группу из (s-1) элементов И, выходы шифратора с первого по п-й образуют k подгрупп выходов, причем i-я подгруппа (i=1,2» »,k-1) включает выходы шифратора от (1 s-в+1)-го до i s-го, а .k-я подгруппа включает выходы шифратора от (k s-в+1)-ro до п-ro, каждый выход шифратора, принадлежащий

j-й подгруппе выходов (j=1,2... °,k), соединен с соответствующим входом

j-ro элемента ИЛИ второй группы и первым входом соответствующего элемента И j-го блока первой группы, выход j-ro элемента ИЛИ второй группы соединен с j-м входом обнаружителя старшей подгруппы запросов, каждый

j-й выход которого соединен с первыми входами всех элементов И j-го блока второй группы и вторыми входами всех элементов И j --го блока первой группы, одноименные выходы групп выходов всех блоков элементов И первой группы соединены с соответствующими входами одноименного элемента ИЛИ первой груп. пы, выход р-го элемента ИЛИ первой группы (р=1,2,...,s) соединен с р-м входом обнаружителя старшего запроса в подгруппе, каждый р-й выход которого соединен с вторыми входами соответствующих элементов И всех блоков второй группы, выходы элементов И блоков второй группы являются соответствующими выходами устройства, входы обнаружителя старшей подгруппы запросов по (k-1)-й включительно соединены с первыми входами одноименных элементов И группы обнаружителя старшей подгруппы запросов, выходы которых являются одноименными выходами обнаружителя старшей подгруппы запросов, а вторые входы соединены с выходами одноименных элементов ИЛИ-НЕ группы обнаружителя старшей подгруппы запросов, k-й вход которого соединен с его k-м выходом r-й вход обнаружи- теля старшей „подгруппы запросов при г=2,3,...;ц (где ц - целая часть чисk+1 ла ---) соединен с соответствующим

15539 входом (r.-1) -ro и предыдущих элементов ИЛИ-НЕ группы до первого включительно обнаружителя старшей подгруппы запросов, r-й вход которого при r=

=q+1, q+2, ...,k соединен с соответствующим входом (r-1.) -го и предыдущих элементов ИЛИ-HE rp o o q-го вклю" чительно обнаружителя старшей подгруппы запросов, выход q-го элемента 10

ИЛИ-НЕ группы обнаружителя старшей подгруппы запросов соединен с третьими входами (q-1) -ro и предыдущих элементов И группы обнаружителя старшей подгруппы запросов, входы обнаружите- 1 ля старшего запроса в подгруппе до (s-1)-го включительно соединены с первыми входами одноименных элементов

И группы обнаружителя старшего запроса в подгруппе, выходы которых являются одноименными выходами обнаружи- теля старшего запроса в подгруппе, а вторые входы соединены с выходами одноименных элементов ИЛИ-НЕ группы

71 о обнаружителя старшего запроса в поД= группе, s-й вход которого соединен с его s-м выходом, 1"й вход обнаружителя старшего запроса в подгруппе при

1=2,3, е (где - целая часть чисs+1 ла ---) соединен с соответствующим

? входом (I-1)-ro и предыдущих элементов ИЛИ-НЕ группы до первого включительно обнаружителя старшего запроса в подгруппе, 1-й вход обнаружителя старшего запроса в подгруппе при

1=t+1, с+2, ...,s соединен с соответствующим входом (1-1)-ro и предыдущих элементов ИЛИ-HE группы до

t-го включительно обнаружителя старшего запроса в подгруппе, выход t-ro элемента ИЛИ-НЕ группы обнаружителя старшего запроса в подгруппе соединен с третьими входами (t-1) -го и предыдущих элементов И группы обнаружителя старшего запроса в подгруппе.

1553971 йК и й -2 22.)+1 22.У 22. g-f 22. -2 22.2

Фиг. 2

Йа 7а.m 1аЮ1а2 Еа1 Ж1 Опт 718 712 О1

s !

Подписное

Тираж 561

ВНИИПИ Государственного комитета по изобретениям и о гкрытиям при ГКНТ СССР

113035, Москва, И-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101

Редактор Л. Веселовская ее

Заказ 457

Составитель H.8àñèëüåâ

Техред M. дидык Корректор И. Кучеря яая