Устройство для выделения экстремального числа Советский патент 1990 года по МПК G06F7/02 

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

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

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

Устройство содержит (фиг.1) п каналов (п - количество обрабатываемых кодов чисел), каждый из которых содержит триггер 1.1,.. 0,1.11, используемый для хранения признака наличия Обрабатываемого кода числа в соответствующем канале. Каждая группа взаи- освязанных элементов И 2, ИЛИ-НЕ 3 k ИЛИ 4 образует одноразрядный формирователь прямого или обратного кода Соответствующих разрядов каждого из Каналов, причем выходы одноразрядных формирователей прямого или обратного н|ода первого (старшего) разряда каж- дЪго из каналов через элемент И 5 Подключены к соответствующим входам Шифратора 6, у которого имеются трупг|ы информационных входов 7.1.1, 7.1.2,...,7.1.т, 7.п.1, 7.п.2, ..„, 7.п.т, управляющие входы 8.1,...,8.п и выходы 9.1р...,9.п.

Часть устройства, включающая в свой состав группу из k блоков элементов И 10, группу из k элементов ИЛИ 11, обнаружитель 12 старшей подгруппы запросов, группу из S элементов ИЛИ 13 (s - ближайшее целое, бЬльшее или равное Vn, k - ближайшее целое, большее или равное -), обнаружитель 1 старшего запроса в подгрупп е и группу из k блоков элементов И 15, выполняет функции приоритетного блока.

На фиг.1 показаны также установочные входы 16.1, о.., 1б0п устройства, информационные входы 17.Ы, 17.1.2, ..., 17.1.го, ..., 17оП.1, 17.п.2, ...,17,п.m устройства, вход 18 задания режима работы устройства и выходы 19.1, ..., 19.п устройства.

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

j 9 /- А К

Обнаружитель 14 старшего запроса в подгруппе схемно реализуется точно так же, как обнаружитель 12 (фиг.2). Отличие обнаружителей 12 и 14 заключается, в общем случае, только в числе входов - у обнаружителя 14 число входов равно s, а не k .

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

функцию позиционной шифрации максимальных входных кодов, содержит m

0 5

5

элементов ИЛИ-НЕ 23с1,с..,23от, т поразрядных блоков 24.1,...,24.т переноса и т-п подблоков 25.1.1, ..., 25.Кп, .,о, 25.т.1,...,25.го.п переноса, каждый из которых содержит элемент ИЛИ 26.

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

Каждый из п триггеров 1.11.п

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

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

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

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

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

В режиме выделения минимального числа (на входе 18 устройства установлен нулевой сигнал) коды чисел инвертируются элементами ИЛИ-НЕ 3 и затем через элементы ИЛИ 4 и открытые элементы И 5 поступают на группы ин

формационных входов 7.1.1, „..,

7.1.т,..о,7.п.1,...,7.л.т шифратора

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

Первыми анализируются старшие разряды кодов чисел (фиг.З). Если хотя бы один из старших разрядов кодов равен единице, то на выходе элемента ИЛИ-НЕ 23.1 сформируется ноль, при этом, если старший разряд кода 1-го числа (,2,,о.,п) равен нулю, то элемент ИЛИ 26 подблока 25.1.1 переноса выдает ноль и все разряды кода i-ro числа не проходят через элемент И 28 подблока 25.1.1 переноса. Если старший разряд кода 1-го числа равен единице, то все разряды кода 1-го числа проходят через элементы И 28 подблока 25.1.1 переноса.

Если старшие разряды всех кодов чисел равны нулю, то на выходе элемента ИЛИ-НЕ 23.1 формируется единица, которая дает разрешение на прохождение всех п кодов чисел через элементы И 28 первого поразрядного блока 24.1 переноса. Таким образом, на выходах элементов И 28 первого поразрядного блока 24.1 переноса фор

10

.

15

53971

ботки в шифраторе 6, и элемент И 29, обеспечивая формирование на выходе 9.i шифратора 6 нулевого сигнала.

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

25

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

мируются коды чисел, подлежащих обра- 30- ветствующего блока, и сигналы со

ботке, начиная с 2-го по m-й разряд,

Вторым элементом ИЛИ-НЕ 23.2 и поразрядным блоком 24.2 переноса анализируются вторые по старшинству разряды обрабатываемых кодов чисел, про- шедших через первый блок переноса 24.1, таким же образом, как и старших разрядов, и т.д. В результате этого процесса позиционные номера экстремальных кодов чисел (максимальных, если на вход 18 устройства подан единичный сигнал, или минимальных, если на вход 18 подан нулевой сигнал) получаются путем совпадения всех m разрешающих сигналов, сформированных соответствующими подблоками 25.1.1, 25.2.1,...,25„т.1 переноса.

При отсутствии сигнала на каком- либ.о из установочных входов 16.1 устройства, т.е. в случае исключения 1-го кода числа из обрабатываемого массива чисел, триггер 101 остается в нулевом состоянии, на его выходе формируется нулевой сигнал, который запирает элемент И 5 в i-м канале и через управляющий вход 8.1 шифратора 6 все элементы И 2.8 в подблоке 25.1.1 переноса, прекращая тем самым подачу кода 1-го числа для последующей обра

0

,

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

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

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

11553971

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

8

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

Йтого же канала, а второй вход элемен-5 ратора от (i S-s+)-ro до i«s-ro,

та И связан с выходом триггера соот- Йе/гствующего канала, выход элемента И каждого из каналов подсоединен к первому информационному входу соответст-, Дующей этому каналу группы информаци- фнных входов шифратора, остальные информационные входы которой с второго по m-й связаны с выходами соответствующих одноразрядных формирова20

а k-я подгруппа включает выходы ш ратора от (k-s-s+l)-ro до n-го, к дый выход шифратора, принадлежащи

j-й подгруппе выходов (,2

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

телей прямого или обратного кода это- 25 соединен с j-м входом обнаружителя

Го же канала, выходы шифратора подключены к входам приоритетного блока, Е&ЫХОДЫ которого являются выходами устройства, отличающееся teM, что, с целью повышения быстродействия и увеличения надежности, в каждом из п подблоков переноса, обра- фующих первый (входной) поразрядный блок переноса шифратора, элементы И группы выполнены трехвходовыми и установлен дополнительный двухвходовой флемент И, один из входов которого Соединен с выходом элемента ИЛИ подблока переноса, другой вход, связанный с третьими дополнительными входами элементов И группы, является управляющим входом соответствующей группы информационных входов шифратора, соединенным с выходом триггера соответствующего канала, а выход дополнительного двухвходового элемента И подсоединен к одному из входов включенного в последовательную цепь формирования выходного сигнала шифратора элемента И группы соответствующего подблока переноса второго пораз- рядного блока переноса шифратора, Приоритетный блок содержит первую группу из s элементов ИЛИ (где s - ближайшее целое, большее или равное Уп), вторую группу из k элементов

ИЛИ (где k - ближайшее целое, большее или равное -), две группы блоков эле8

8

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

0

а k-я подгруппа включает выходы шифратора от (k-s-s+l)-ro до n-го, каждый выход шифратора, принадлежащий

j-й подгруппе выходов (,2k),

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

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

пы, выход р-го элемента ИЛИ первой

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

ла

k+K Г

соединен с соответствующим

У

ti.n}W )&l№K 1)Sito( Ы Фи,1

tt.K Я.К-1 И.к-S 22.4+1 22.q, 22.q-1 22.-2

Фиг. 2 8.n Za.m U3 Ш 8.1 Urn W Ш W

Составитель Н.Васильев

Редактор Л.Веселовская Техред м.Дидык

уфу у

Корректор М.Кучеря рая