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

Союз Советски кСоциалистически кРеспублик ВТОРСКОМУ СВИДЕТЕЛЬСТВ 6 ) Дополнительное к авт, сеид-ву М 65855 22) Заявлено 040480 (21) 2904436/18-2(51) М. Кл,С 06 Е 7/02 оелинением заявк дарстаеилыи комитет СССР . риорите) Заявитель 54) УСТРОЙСТВО ДЛЯ ВЫДЕЛЕНИЯ ЭКСТРЕМАЛЬНОГЦИСЛА Изобретение относится к вычислительной технике и может быть использовано при организации вычислительногоlпроцесса по обработке пакета задач вмногопроцессорной или многомашиннойвычислительной системе,По основному авт.св. Ю 658558 известно устройство, содержащее элементы ИЛИ-НЕ, поразрядные узлы переноса, группы элементов И и ИЛИ 1 1).Однако известное устройство невозможно использовать для распределения заданий процессорам в мультипроцессорной вычислительной системе,Цель изобретения - расширение области применения устройства.Поставленная цель достигаетсятем, цто в устройство для выделенияэкстремального числа введены перваяи вторая группы из и триггеров, группа из (плтп) элементов И (где П - чис 20ло задач в пакете, а - число разрядов в кодах "веса" задач), (и) дополнительных элементов ИЛИ, группа из (и) элементов ИЛИ-НЕ, первыевходы которых соединены с первымивыходами триггеров первой группы,кроме выхода первого триггера первойгруппы, вторые выходы которых соединены с первыми входами соответствую"щих дополнительных элементов ИЛИ, выходы 1-ых ( = 2,п) дополнительныхэлементов ИЛИ соединены со вторымивходами (1-1)-ых элементов ИЛИ-НЕ,группы, выходы триггеров второй группы соединены с первыми входами соответствующих элементов И группы, группа входов триггеров второй группыявляется группой установочных входовустройства, единичные входы триггеров первой группы соединены с выходами элементов И групп последнегопоразрядного узла переноса, нулевыевходы этих триггеров соединены свходом сброса устройства, первыевходы элементов И группы являютсягруппой кодовых входов устройства,выходы элементов ИЛИ-НЕ группы и894702 первого триггера первой группы являются группой выходов устройства, выходы триггеров второй группы соединены со вторыми входами элементов Ивторой группы, выход каждого щ-гоэлемента И группы соединен с соответствующим входом первого выходного элемента ИЛИ-НЕ,На чертеже представлено предлагаемое устройство, структурная схема.Устройство содержит по числу решаемых задач в пакете триггеры 1второй группы, группу элементов И 2,выходные элементы ИЛИ-НЕ 3,1,33 тгпоразрядные узлы переноса ,44 р,группы элементов И или ИЛИ 5.И,52,5состоящие из элементов ИЛИ Ь и элементов И 7, триггеры 81, 8 8первой группы, дополнительные элементы ИЛИ 9 1, 9 9 И , элементыИЛИ-НЕ группы 10,1,10 , 10,И , группу кодовых входов 11 11 , ,11устройства, установочные входы12 , 12, , 12 и устройства, груп. пу выходов 13,1,1313, устройства, входсброса устройства 14.Устройство работает следующим образом. На входы 11 устройства поступают щ-разрядные коды и чисел, а на установочные входы 12 по мере решения задач поступают единичные сигналы- признаки решения задачи, которые перебрасывают соответствующие триггеры 1 в единичное состояние, обеспечивая тем самым прекращение подачи кодов чисел через элементы И 2 группы на входы первого поразрядного узла переноса и на входы элемента ИЛИ-НЕ ЗВ исходном состоянии все триггеры 1 находятся в нулевом состоянии, а их нулевые выходы подключены к входам элементов И 2 группы.В первый момент анализируются старшие разряды кодов чисел. Если хотя бц один иэ старших разрядов кодов равен "1", то на выходе элемента 3 формируетая "0". При этом если старший разряд э.-го числа (1=1,п) равен "0", то все разряды 1-го числа не проходя через элементы И 7 1-ой группы первого поразрядного узла Если старший разряд д-го числа равен 1 то разряды 1-го числа проходят через элементы И 7 -ой группы первого поразрядного узла переноса. Э 0 15 26 23 ЭО ЭЗ 49 4Если старшие разряды всех кодовчисел равны нулю, то на выходе элемента ИЛИ-НЕ 3 формируется "1", которая дает разрешение на прохождениевсех п кодов чисел через элементыИ 7 первого поразрядного узла переноса,Если старшие разряды всех кодовчисел равны нулю, то на выходе элемента ИЛИ-НЕ 3 формируется "1, которая дает разрешение на прохождениевсех и кодов чисел через элементы И7 первого поразрядного узла переноса.На выходе элементов И 7 группы)лементов 5 Формируются прямые кодычисел, начиная со второго по щ-ыйразряд, Вторым элементом ИЛИ-НЕ 3совместно с элементами ИЛИ б поразрядного узла переноса 4 анализируются вторые по старшинству разрядыи чисел таким же образом как и старших разрядов, На выходе элемента ИЛИНЕ 3 формируется второй по старшинству разряд экстремального числа, ана выходах элементов И 7 - коды чисел, начиная с третьего по щ-ый разряд и т.д.Таким образом, код номера экстремального числа получается путем совпадения всех щ сигналов запрета,сформированных в каждом поразрядномузле переноса 4. При сигналах запрета, равных "1", на одном или болеевыходах элементов И 7 последнего поразрядного узла переноса 4 формируется код с " 1" в разрядах, соответствующих экстремальным кодам чисел(в решаемом пакете задач могут бытьзадачи, требующие одинаковое времядля решения) Появление единичных сигналов на выходах элементов И 7 последнего поразрядного узла переноса 4 вызывает переброс соответствующих триггеров 8 в единичное состояние. При одновременномединичном состоянии нескольких триггеров 8 на выходе устройства появится единичный сигнал только в одной выходной д-ой шине, причем э.;2 3, где 1=1,п и 1=1,и т.е. предпочтение отдается той задаче, порядковый номер которой наибольший среди задач с одинаковым требуемым временем решения. Это достигается тем, что высокий потенциал с выхода триггера 8, соответствующего решаемой задаче, со старшим порядковым номером подается черезказ 11190/78 Тираж 718 Подписно илиад ППП "Па ИИП 89 У 02 нт", г, Ужгород, ул. Проектная,