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

 

Союз Советски к

Социалистические

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (6I ) Дополнительное к авт. сеид-ву N 658558 (22) Заявлено 040480 (21) 2904436/18-24 с присоединением заявки М (23) Приоритет (5 t ) M. Кл.

G 06 Е 7/02

Государстаоииый комитет

СССР .

Опубликовано 301 281 Бюллетень Ж 48 (53) УДК 681. 325 (088. 8) по делам изобретений и открытий

Дата опубликования описания 301Z81 (72) Автор изобретения

В.А. Титов

«»

)

1 (7l) Заявитель (54) УСТРОЙСТВО ДЛЯ ВЫДЕЛЕНИЯ ЭКСТРЕМАЛЬНОГО

ЧИСЛА

Изобретение относится к вычислительной технике и может быть использовано при организации вычислительного

l процесса по обработке пакета задач в многопроцессорной или многомашинной вычислительной системе.

По основному авт.св. N 658558 известно устройство, содержащее элементы ИЛИ-НЕ, поразрядные узлы переноса, группы элементов И и ИЛИ (l j.

Однако известное устройство невозможно использовать для распределения заданий процессорам в мультипроцессорной вычислительной системе.

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

Поставленная цель достигается тем, что в устройство для выделения экстремального числа введены первая и вторая группы из и триггеров, группа из (п тп) элементов И (где и - чис20 ло задач в пакете, m — число разрядов в кодах "веса" задач), (и-2) дополнительных элементов ИЛИ, группа из (n-1) элементов ИЛИ-НЕ, первые входы которых соединены с первыми выходами триггеров первой группы, кроме выхода первого триггера первой группы, вторые выходы которых соединены с первыми входами соответствую" щих дополнительных элементов ИЛИ, выходы i-ых (i = Z,n-l) дополнительных элементов ИЛИ соединены со вторыми входами (i-1)-ых элементов ИЛИ-НЕ, группы, выходы триггеров второй группы соединены с первыми входами соответствующих элементов И группы, группа входов триггеров второй группы является группой установочных входов устройства, единичные входы триггеров первой группы соединены с выходами элементов И групп последнего поразрядного узла переноса, нулевые входы этих триггеров соединены с входом сброса устройства, первые входы элементов И группы являются группой кодовых входов устройства, выходы элементов ИЛИ-НЕ группы и первого триггера первой группы являются группой выходов устройства, выходы триггеров второй группы соединены со вторыми входами элементов И второй группы, выход каждого m-ro элемента И группы соединен с соответствующим входом первого выходного элемента ИЛИ-НЕ.

На чертеже представлено предлагаемое устройство, структурная схема.

Устройство содержит по числу решаемых задач в пакете триггеры 1 второй группы, группу элементов И 2, выходные элементы ИЛИ-НЕ 3.1,3 ...3 поразрядные узлы переноса 4,4 ...4, группы элементов И или ИЛИ 5+, 5 2,... 5 состоящие из элементов ИЛИ Ь и элементов И 7, триггеры 8,1, 8>... 8 первой группы, дополнительные элементы ИЛИ 91, 9 ... 9И, элементы

ИЛИ-НЕ группы 10,1,10,... !ОИ1,. группу кодовых входов 11, tl,...,11 устройства, установочные входы

12, 12,... 12и устройства, груп. пу выходов !3,13д,...,13,„ устройства, вход сброса устройства 14.

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

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

3 °

B исходном состоянии все триггеры 1 находятся в нулевом состоянии, а их нулевые выходы подключены к входам элементов И 2 группы.

В первый момент анализируются старшие разряды кодов чисел. Если хотя бы один иэ старших разрядов кодов равен "1", то на выходе элемента 3 формируетая "0". При этом если старший разряд i-го числа (i=1,и) равен "0", то все разряды i-ro числа не проходя через элементы И 7 i-ой группы первого поразрядного узла 4 Если старший разряд i-го числа равен "1", то разряды 1-го числа проходят через элементы И 7 i-ой группы первого поразрядного узла переноса.

894702

4$

М

5 о

26

2S

Э$

49 ф

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

И 7 первого поразрядного узла переноса.

Если старшие разряды всех кодов чисел равны нулю, то на выходе элемента ИЛИ-HE 3 формируется "1, которая дает разрешение на прохождение всех и кодов чисел через элементы И

7 первого поразрядного узла переноса.

На выходе элементов И 7 группы лементов 5 формируются прямые коды чисел, начиная со второго по m-ый разряд. Вторым элементом ИЛИ-НЕ 3 совместно с элементами ИЛИ б поразрядного узла переноса 4 анализируются вторые по старшинству разряды и чисел таким же образом как и старших разрядов. На выходе элемента ИЛИНЕ 3 формируется второ" по старшинству разряд экстремального числа, а на выходах элементов И 7 — коды чисел, начиная с третьего по m-ый разряд и т.д.

Таким образом, код номера экстремального числа получается путем совпадения всех m сигналов запрета, сформированных в каждом поразрядном узле переноса 4. При сигналах запрета, равных "1", на одном или более выходах элементов И 7 последнего поразрядного узла переноса 4! формируется код с " 1" в разрядах, соответствующих экстремальным кодам чисел (в решаемом пакете задач могут быть задачи, требующие одинаковое время

Для решения).

Появление единичных сигналов на выходах элементов И 7 последнего поразрядного узла переноса 4 вызывает переброс соответствующих триггеров 8 в единичное состояние. При одновременном единичном состоянии нескольких триггеров 8 на выходе устройства появится единичный сигнал только в одной выходно" i-ой шине, причем i r j, где i=1,и и j=1,n т.е. предпочтение отдается той задаче, порядковый номер которой наибольший среди задач с одинаковым требуемым временем решения. Это достигается тем, что высокий потенциал с выхода триггера 8, соответствующего решаемой задаче, со старшим порядковым номером подается через элементы ИЛИ 9 на первые входы предыдущих элементов ИЛИ-НЕ 10, вторые входы которых подключены к одноименным нулевым выходам триггеров 8.

Таким образом, позиционный код номера экстремального числа получается на выходах 13 устройства.

При назначении очередной i-ой задачи пакета на решение подается единичный сигнал на соответствующий триггер 1„, в результате чего прекращается подача кода i-ro числа с выходов элементов И 2 группы для последующего сравнения, а также на вход 14 устройства, в результате чего все триггеры 8 перебрасываются в нулевое. состояние и работа устройства по выбору очередной задачи из .пакета происходит аналогичным образом.

Применение изобретения позволяет расширить область применения устройства. е

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

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

894702

Ь (n-1) элементов ИЛИ-НЕ, первые входы которых соединены с первыми выходами триггеров первой группы кроме выхода первого триггера первой группы, вторые выходы которых соединены с первыми входами соответствующих дополнительных элементов ИЛИ, выходы

i-ых (i=2,n-1) дополнительных элементов ИЛИ соединены со вторыми входа"

1Е ми (1-1)-ых элементов ИЛИ-НЕ группы, выходы триггеров второй группы соединены с первыми входами соответствующих элементов И группы, группа входов триггеров второй группы яв15 ляется группой установочных входов устройства, единичные входы триггеров первой группы соединены с выходами .элементов И групп последнего поразрядного узла переноса, нулевые

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

2% первого триггера первой группы являются группой выходов устройства, выходы триггеров второй группы соединены со вторыми входами элементов

И группы, выход каждого m-ro элеменэф та И группы соединен с соответствующим входом первого выходного элемента ИЛИ-НЕ.

Источники информации, принятые во. внимание при экспертизе

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

Ю 658558, кл. G 06 Р 7/02, 1976