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

(54) УСТРОЙСТВО ДЛЯ ВЫДЕЛЕНИЯ ЭКСТРЕМАЛЬНОГО ЧИСЛА

Изобретение относится к вычислите льной технике и может быть использов но при организации вычислительного процесса по обработке пакета задач многопроцессорной или многомашинной вычислительной системе. По основному авт.ев, № 658558 известно устройство, содержащее элементы ИЛИ-НЕ, поразрядные узлы переноса, группы элементов И и ИЛИ f1 . Однако известное устройство невозможно использовать для распределения заданий процессорам в мультипроцессорной вычислительной системе. Цель изобретения - расширение области применения устройства. Поставленная цель достигается тем, что в устройство для выделения экстремального числа введены первая и вторая группы из п триггеров, груп па из () элементов И (где п - чис ло задач в пакете; m - число разрядов в кодах веса задач), (п-2) доподнительных элементов ИЛИ, группа ИЗ (п-1) элементов ИЛИ-НЕ, первые входы которых соединены с первыми выходами триггеров первой группы, кроме выхода первого триггера первой группы, вторые выходы которых соединены с первыми входами соответствую щих дополнительных элементов ИЛИ, i-ых (i 2,п-1) дополнительных элементов ИЛИ соединены со вторыми входами (1-1)-ых элементов ИЛИ-НЕ, группы, выходы триггеров второй группы соединены с первыми входами соответствующих элементов И группы, группа входов триггеров второй группы является группой установочных входов устройства, единичные входы триггеров первой группы соединены с выходами элементов И групп последнего поразрядного узла переноса, нулевые входы этих триггеров соединены с входом сброса устройства, первые входы элементов И группы являются группой кодовых входов устройства, выходы элементов ИЛИ-НЕ группы и

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

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

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

W Wn

1Г

устройства, установочные входы 12,, 12,.,,,,. 12 устройства, группу выходов 13.(, 13,,.., 13 устройства, вход сброса устройства 14,

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

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

3i

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

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

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

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

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

На выходах элементов И 7 - коды чисел, начиная с третьего по т-ый разряд и т.д.

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

для решения),

Появление единичных сигналов на выходах Элементов И 7 последнего поразрядного узла переноса 4.вызывает переброс соответствующих триггеров 8 в единичное состояние. При одновременном единичном состоянии нескольких триггеров 8 на выходе устройства появится единичный сигнал только в одной выходной i-ой шине, причем , где ,n и ,n т.е. предпочтение отдается той задаче, порядковый номер которой наибольший среди задач с одинаковым требуемым временем решения, Это достигается тем, что высокий потенциал с выхода триггера 8, соответствующего решаемой задаче, со старшим порядковым номером подается через 5 элементы ИЛИ 9 на первые входы пре дыдущих элементов ИЛИ-НЕ 10, вторы входы которых подключены к бдноимен ным нулевым выходам триггеров 8. Таким образом, позиционный код номера экстремального числа получается на выходах 13 устройства. При назначении очередной i-ой задачи пакета на решение подается единичный сигнал на соответствующий триггер-1, в результате чего прекращается подача кода i-ro числа с выходов элементов И 2 группы для последующего сравнения, а также на вход Н устройства, в результате чего все триггеры 8 перебрасываются в нулевое, состояние и работа устройства по выбору очередной задачи из пакета происходит аналогичным образом. Применение изобретения позволяет расширить область применения устройства. Формула изобретения Устройство для выделения экстремального числа по авт.св. № 658558, отличающееся тем, что, с целью расширения области применения устройства, оно содержит первую вторую группы из п триггеров,.групп из (п-Нп)элементов И (где п - число задач в пакете; m - число разрядов в кодах веса задач), (n-Z) дополнительных элементов ИЛИ, группу из 2 ,(п-1) элементов ИЛИ-НЕ, первые входы которых соединены с первыми выходами триггеров первой группы кроме выхода первого триггера первой группы, вторые выходы которых соединены с первыми входами соответствующих дополнительных элементов ИЛИ, выходы i-ых (,п-1) дополнительных элементов ИЛИ соединены со вторыми входами (1-1)-ых элементов ИЛИ-НЕ группы, выходы триггеров второй группы соединены с первыми входами соответствующих элементов И группы, группа входов триггеров второй группы является группой установочных входов устройства, единичные входы триггеров первой группы соединены с выходами .элементов И групп последнего поразрядного узла переноса, нулевые входы этих триггеров соединены с входом сброса устройства, первые входы элементов И группы являются группой кодовых входов устройства, выходы элементов ИЛИ-НЕ группы и первого триггера первой группы являются группой выходов устройства, выходы триггеров второй группы соединены со вторыми входами элементов И группы, выход каждого т-го элемента И группы соединен с соответствующим входом первого выходного элемента ИЛИ-НЕ. .Источники информации, принятые во- внимание при экспертизе 1. Авторское свидетельство СССР № 658558, кл. G Об F 7/02, 1976

I I

fm-i

r

I m mm

I I jj

ra

LIJT

т

/5rf

щ

ur

/tf,

/Ji Т rj/