Устройство для распределения заданий процессорам

(51)4 С 06 Г 9 46 ТВЕННЫЙ КОМИТЕТ СС ЭОБРЕТЕНИЙ И ОТН(54)(57) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ ЗАДАНИЙ ПРОЦЕССОРАМ, содержащееканалов ( и - число решаемых задач), каждый из которых, кроме первого и ( -го, содержит четыре элемента И, три элемента ИЛИ, элемент ИЛИ-НЕ и триггер, первый канал содержит четыре элемента П, два элемента ИЛИ и триггер, а и -й канал содержит четыре элемента И, два элемента ИЛИ, элемент ИЛИ-НЕ и триггер, причем в каждом канале выходы первого и второго элементов И соединены с соответствующими входами первого элемента ИЛИ, выходы третьего и четвертого элементов И соединены с соответствующими входами второго элемента ИЛИ, нулевой выход триггера 1-)го канала (1 =2 и -1) соединен с первым входом третьего элемента ИЛИ 1 -го канала, второй. вход которого, кроме второго канала, соединен с выходом третьего элемента ИЛИ ( 1 - 1)-го канала и первым входом элемента ИЛИ-НЕ1 -го канала, единичный выход триггера 1-го канала соединен с вторым входом элемента ИЛИ-НЕ1 -го канала, нулевой выход триггера первого канала соединен с вторым входом третьего элемента ИЛИи первым входом элемента ИЛИ-НЕвторого канала, единичный выход тригера и -го канала соединен с первым входом элемента ИЛИ-НЕо -гоканала, второй вход которого соединен с выходом третьего элементаИЛИ ( и -1)-го канала, о т л и ч аю щ е е с я тем, что, с цельюрасширения области применения, оносодержит генератор тактовых импульсов, элемент задержки, элемент И,счетчик импульсов, схему сравнения,регистр, два триггера, два элементаИЛИ-НЕ, а в каждом 1 -м каналеедвигающий регистр, пятый и шестойэлементы И, четвертый и пятый элементы ИЛИ и элемент И-НЕ, а первыйи 1)-й каналы содержат сдвигающийрегистр, пятый и шестой элементы И,третий и Четвертый элементы ИЛИ иэлемент И-НЕ, причем выход генератора тактовых импульсов соединенс первым входом элемента И, второйвход которого соединен с единичнымвыходом первого триггера, единичный вход которого соединен с входом пуска устройства, нулевойвход первого триггера соединен свыходом схемы сравнения, с входомсброса счетчика импульсов, с первыми входами пятых элементов И всехканалов и через элемент задержки -с нулевыми входами триггеров всехканалов, единичные входы которыхсоединены с выходами элементовИ-НЕ соответствующих каналов, первые входы которых соединены с выходами третьих элементов ИЛИ пер183967 лов вого и о -го каналов и четвертых элементов ИЛИ всех остальных каналов и первыми входами шестых элементов И соответствующих каналов, вторые входы которых соединены с выходами первых элементов ИЛИ соответствующих каналов, выход шестого элемента И ,-го канала (; 2,.., л -1) соединен с первым входом пятбго элемента ИЛИ-го канала и с-м входом первого элемента ИЛИ-НЕ, выходы шестых элементов И первого ии -го каналов соединены с первыми входами. четвертых элементов ИЛИ соответственно первого и п -го каналов и с соответствующими входами .первого элемента ИЛИ-НЕ, выход которого соединен с вторыми входами четвертых элементов. ИЛИ первого и-го каналов и пятых элементов ИЛИ всех остальных каналов, выходы четвертого элемента ИЛИ первого и и -го каналов соединены с вторыми входами элементов И-НЕ соответственно с первого и и-го каналов, выход пятого элемента ИЛИ-го канала соединен с вторым входом элемента И-НЕ 1-го канала, единичный выход триггера первого канала соединен с вторым входом пятого элемента И и первыми входами с первого по четвертый элементов И первого канала, единичный выход триггера -го (=2, о ) канала соединен с первыми входами с первого по четвертый элементов И-го каналавыход элемента ИЛИ-НЕ-го канала соединен с вторым входом пятого элемента И -го канала, выходы пятых элементов И всех каналов являются выходами устройства, выхоцы вторых элементов ИЛИ первого и ь -го каналов соединены с первыми входами третьих элементов ИЛИ соответственно первого и и -го каналов и с соответ-. ствующими входами второго элемента ИЛИ-НЕ, выход второго элемента ИЛИ 1 -го канала ( 1 = 2 и -1) соединен с первым входом четвертого элемента ИЛИ 1-го канала и с 1 -м входом второго элемента ИЛИ-НЕ, выход которого соединен с вторыми входамц третьих элементов ИЛИ первого и в -го каналов и четвертых элементов ИЛИ-х каналов, вторые входы первого и второго элементов И каждого канала соединены с соответствующими выходами (в - 1) разряда (- число запросов) сдвигающего регистра своего канала, вторые входы третьего и четвертого элементов И каждого канала соединены с соответствующими выходами в -го разряда сдвигающего регистра своего канала, информационный вход которого соединен.с соответствующим входом кода приоритета устройства, выход элемента И соединен со счетным входом счетчика импульсов и с входами сдвига сдвигаюющих регистров всех каналов, выход счетчика импульсов соединен с первым входом схемы сравнения, второй вход которой соединен с выходом регистра, информационный вход которого соединен с входом кода коэффициента пересчета устройства, вход режима которого соединен с входом второго триггера, единичный и нулевой входы которого соединены с третьими входами соответственно первого и третьего элементов И и второго и четвертого элементов И всех кана Изобретение относится к вычислительной технике, и может быть использовано при организации вычислительного процесса по обработке пакета задач в многопроцессорной (многомашинной) вычислительной системе.Цель изобретения - расширение области применения. На чертеже представлена структурная схема устройства.Устройство содержит: ш - разрядные сдвигающие (со сдвигом на два разряда в сторону старших разрядов) регистры 1 - 1 и (и - количество задач в пакете) по числу задач в пакете первые 2 - 2 вто)2 и рые- э , третьи 4 - 4 п и67 з 11839четвертые 5 - 5 элементы И, вто- фрые 6 - 6 и первые 7 - 7 элементы ИЛИ, элементы ИЛИ 3 - 8,шестые элементы И 91 - 9 , элементы ИЛИ 10 - 10 , элементы И-НЕ 511- 11, триггеры 12 - 12элементы ИЛИ 132 - 1 Зп 1 , элементы ИЛИ-НЕ 144 - 4 п , пятые элементы Ч 15, - 15 , второй элементИЛИ-НЕ 16, первьй элемент ИЛИ-НЕ 17,второй триггер 18, элемент 19задержки, регистр 20, схему 21 сравнения, счетчик 22 импульсов, пер-,вый триггер 23, элемент И 24, генератор 25 тактовых импульсов, вход 1526 режима работы, информационныевходы 27 - 27 , пусковой вход28, установочный вход 29, выходы 30., -30 устройства.В исходном состоянии на регистрах 201 - 1 находятся коды, соответствуюгие весам задач и заносимые по входам 27 - 27 . Все триггеры 12 устанавливают в нулевое состояние (установочные входы не показаны). 25На триггер 18 по входу 26 заносится код режима работы устройства, ана регистр 20 по входу 29 - код ко-.эффициента пересчета счетчика 22, равного числу ш/2-1, (ш - разрядность зОрегистров 1). Единичному (нулевому)состоянию триггера 18 соответствует режим распределения задач попроцессорам вычислительной системыпо критерию минимума (максимума)35веса задачи соответственно. Работа устройства начинается после сброса триггеров 12 установки триггера 23 по входу 26, в результате чего открывается элемент И 24, К этому .40 времени коды с выходов двух триггеров старших разрядов ш -го и (ш - 1)- го регистров 1 поступают через одноименные элементы И 2 или И 3, на третьи. входы которых подается высокий потенциал с обратных выходов одноименных триггеров 12, и элемент ИЛИ 7 для (ш - 1)-го разряда, и элемент И 4 или И 5 (в зависимости от состояния триггера 18) для ш-го50 разряда для последующего анализа,В начале анализируются старшие разряды и кодов, Для этого сигнал с выхода элемента ИЛИ 6 Ы = 1, ,и) поступает на д-й вход элемента ИЛИНЕ 16 и на первый вход элемента ИЛИ 8 на второй вход которого поступает сигнал с выхода элемента ИЛИНЕ 16. Если во всех старших ш-хразрядах регистров 1 храйится нуль,то на выходе элемента ИЛИ-НЕ 16 будет сигнал логической единицы, вовсех других случаях на выходе элемента ИЛИ-НЕ 16 сигнал логическогонуля. Сигнал с выхода элемента ИЛИ 8поступает. на первый вход элементаИ-НЕ 11 и первый вход элемента И 9второй вход которого подсоединен квыходу элемента ИЛИ /. , на котором находится сигнал состояния(ш)-го триггера регистра 11 . Сигнал с выхода элемента И 9,. поступает на -й вход элемента ИЛИ-НЕ 17и на первый вход элемента ИЛИ 10второй вход которого подсоединенк выходу элемента ИЛИ-НЕ 17, а выход - к второму входу элементаИ-НЕ 11 Таким образом, если хотя бы на одном, например, -м регистре 1; ( = 1, , и) в (ш)-м разряде содержится код единицы,то на выходе элемента И 9 будет сигнал логической единицы, который поступает на -й вход элемента ИЛИ-НЕ 17 (при наличии хотя бы одного единичного сигнала на триггерах ш-го и (ш)- го разрядов регистра 11 , 3 = 1, и). С выхода элемента ИЛИ-НЕ 17 сигнал логического нуля поступает на один из входов элементов ИЛИ 1 О, на второй вход каждого из которых поступает сигнал логической единицы с выхода элемента И 9 . Поэтому, если на выходе элемента ИЛИ 6 высокий потенциал, то на выходе элемента И-НЕ 11. нулевой потенциал. В случае, если значение ш-го разряда регистра 1, равна ну лю, то на выходе элемента ИЛИ 6 будет сигнал логического нуля, на выходе элементов ИЛИ 8. , ИЛИ 10 - также сигнал логического нуля, а на выходе элемента И-НЕ 11. появится сигнал логической единицы, который перебросит триггер 12: в единичное состояние, после чего прекращается подача высокого потенциала с обратного выхода триггера 12; на третьи входы элементов И 2; и И 3, (1. = 1,п) .Аналогична работа устройства и при других комбинациях старших двух разрядов регистров 1.Для анализа следующей пары разрядов сравниваемых кодов с вы1193967 ВН КИПИ Тираж 709 6272 4 но хода генератора 25 через элементИ 24 поступает очередной импульссдвига на регистры 11 " 1, , покоторому информация в регйстрах1 сдвигается на два разряда вправо,а к содержимому счетчика 22 прибавляется единица. После сдвигаинформации в регистрах 1 аналогич- .но анализируется следующая па- Ора разрядов.Сдвиг информации на регистрах 21продолжается до тех пор, пока непроизойдет сравнение в схеме 1,после чего триггер 23 и счетчик 1522 сбрасываются.После .окончания цикла работы устройства позиционные номера экстремальных кодов (их может быть несколько) фиксируются на триггерах 12, Приодновременном единичном состоянии,нескольких триггеров 12 на выходах30 устройства (выходах открытых элементов И 151 - 15 появится единичный:сигнал только на одном выходе 30,фпричем х ( 1, где , 1 = 1,п, т.е.предпочтение отдается той задаче, порядковый номер которой наименьшийсреди задач, имеющих одинаковоетребуемое время для решения. Это дос-тигается тем, что высокий потенциалс единичного выхода триггера 12 подается через элементы ИЛИ 13 (1,2,п - 1) на первые входы последующих элементов ИЛИ-НЕ 14; , вследствие чего на всех последующихвыходах 30 (д Ъ з.)будет нулевой сигнал. Сигнал сравнения с выхода схемы21 через элемент 19 задержки сбрасывает в нулевое состояние триггеры 12, подготавливая тем самым устройство к новому циклу работы. Кроме того, для выбранной задачи (пустьее номер будет равным , 1 = 1,п)сбрасывается регистр 11 если триггер18 установлен в нулевое состояниедля режима минимального времениреализации пакета задач, илиустанавливается в единичное состояние, если триггер 18 установлен в единичное состояние для ре-;жима минимального среднего времениожидания задачи в пакете. Филиал ППП "Патент"г.ужгород, ул.Проектная, 4