Устройство для распределения заданий процессорам Советский патент 1984 года по МПК G06F9/50 

Изобретение относится к вычислительной технике и может быть использовано в разработках аппаратного диспетчера при организации мультипрограммной обработки пакета программ в ЦВМ, а также в устройствах, предназначенных для решения задач теории расписаний в специализированных процессорах.

Известно устройство для распределения заданий, содержащее матрицу ячеек памяти, блок анализа строк, содержащий приемный регистр, узел опроса, регистр назначений, шифратор регистр, генератор, счетчик назначения, схему сравнения, триггеры, элементы ИЛИ, И и НЕ lj .

Недостатками известного устройства являются сложность и низкое быстродействие при решении пакета в ЦВМ,

Наиболее близким к предлагаемому является устройство для распре,целения заданий, содержащее первый узел поиска максимального кода (УЦМК), п групп блоков первьсх элеме-нтов И (где О - количество задач в пакете), группы первых и вторых регистров,П групп блоков вторых элементов И, группу блоков третьих элементов И, группу схем сравнения, группу первых элемен тов НЕ, второй УПМК, группы первых и вторых элементов И-НЕ, группу вторьЕХ элементов НЕ, группу четвертых элементов И, группу третьих элементов И, группу блоков пятых элементов И, третий УПМК, группу третьих элементов НЕ, группу элементов И.ПИ Zj .

Недостаток да.нного устройства большие аппаратные затраты.

Цель изобретения - сокращение обо рудования.

Поставленная цель достигается тем что устройство для распределения заданий процессорам, содержащее две , группы регистров , группу узлов сравнения, группу элементов И,группу элементов И-НЕ,два узла выделения максимального кода, группу элементов И.ПИ,элемен И,первые входы регистров первой группы соединены с сооаветствующими выходами первого узла вьиеления максимального кода, содержит две группы эле. ментов И, сум№1рующий и вычитающий счетчики, и генератор тактовЬХ импульсов, причем вторые входы регистров первой группы соединены с соотнетствую 1и- ми выходами второго узла вьщеления максимального кода и с первыми входами элементов И второй группы, вторые входы которых соединены с выходом вычитающего счетчика, первые входы элементов И третьей группы соединены с соответствуюш 1ми выходами первого узла вьщеления максимального кода, вторые входы элементов И третьей группы соединены с выходом суммиру1ощего счетчика, выходы 1-х элементов И второй и третьей групп (.,,iri, где п - число задач в пакете) соединены с соответствующими входами 1 -го элемента ИЛИ группы, выход которого соединен с входом f-ro регистра второй группы, вькод которого является выходом устройства выходы j-го и (j-1)-ro регистров .(,.;,5,.,,,2n1) первой групп и) соединены с входам 1 соответствующего узла сравнения группы, первый выход 1-го узла сравнения группы (t-1,,,.)i соединен с первым входом i: -го элемента И первой группы, второй выход 4-го узла сравнения группы соединен с первым входом (i-(-n)-ro элемента И первой группы, третий выход i -го узла сравнения группы соединен с первыми входами 1-го и (i4ri)-ro элементов И-НЕ группы, выходы элементов И первой группы соединены с вторьми входами соответствующих элементов И-НЕ группы, выход ( -го элемента И-НЕ группы соединен с -ым информационным входом первого узла выделения максимального кода, выходj -го (j , . , , , 2п) элемента И-НЕ группы соединен с соответствующим информационным входом второго узла выделения максимального кода, вьгход генератора тактовых импульсов соединен с первым входом элемента И, второй вход которого является входом устройства, выход элемента И соединен с тактовыми входами первого и второго узлов вьщеления максимального кода, с вторыми входами элементов И первой группы, и с входами суммирующего и вычитающего счетчиков,

Сущность изобретения заключается в том, что устройство назначает задачи для реализахщи в соответствии с модифицированным алгоритмом ДЖОНСОНА (решение задачи о двух станках) при этом за, один такт ра.боты устройства определяются номера очередности сразу двух задач из пакета.

На фиг. 1 представлена структурная схема устройства для распределения заданий; на фир, 2 - структурная схема узла сравнения кодов; на фиг.Зсхема узла вьщеления максимального кода.

Устройство для распределения заДании содержит регистры 1(..,1 и 4l Чи первой группы (где - количество задач в пакете) ,, в которые в исходном состоянии заносятся обратные коды, соответствуюище времени обработки задач на первой и второй фазах соответственно, узлы 2 . .. 2 сравнения группы, генератор 3 тактовых импульсов, элемент И 4, первую группу элементов И ...5:2и группу элементов И-НЕ 6 ... суммирующий 7i и вычитающий 1 счетчики, узлы 8д и 8п выделения максимального кода, элементы И 9 ...9 третьей группы, элементы И 92,...9 второй группы, группу элементов ИЛИ 10f...10, вторую группу регистров 11, . . . 11 г|, выходы 1 2 ... 1 2 и вход 13

Узел 2 сравнения кодов содержит группы элементов ИЛИ-НЕ 14 . . . 14 (где№ - разрядность кодов), узлы

15 ... 15 анализа разрядов, каждый из которых содержит элемент ИЛИ 16, группы элементов И 17, элемент НЕ 18, элемент И 19, выходы 20;,...20, входы 21,. , . 212 , выходы 22 и 23. Узел 8 вьщеления максимального ко да содержит группу элементов ИЛИ 24, группы элементов ИЛИ-НЕ 25, группы элементов ИЛИ 26, группы элементов И 27, группу элементов И 28...28fi, группу элементов НЕ 29...29n-f , группу элементов И 30||.,.30р, выходные триггеры 3 . . .2,0, входы ...32р, вход 33, выходы 34...34п. Устройство работает следующим образом. В исходном состоянии в группу регистров 1 ( п заносятся обратные коды, соответствующие времени первой фазы реализации задач - времени Ь да задач, в группу регистров 1 заносятся обратные коды, пропорциональные времени второй фазы peaлизации задач, т.е. сумме време ни решения задач и вывода результатов их решения. В нулевом состоянии будут регистры 1 1 и счетчик 7 . На вхо ды узлов 2, , 1-1,...п) подаются обратные коды, т.е. коды с инверсных выходов регистров 1,; ... 1, . Узлы 2f...2n представляют собой схемы выделения максимального кода, но так как информация на них подается уже

I в обратном коде, то в этих узлах выбираются минимальные числа из кодов, занесенных в регистры и 1 j

Узел сравнения 2 работает следуюдам образом.

На входы 21 , . . .2 5,у, (где гп - разрядность кодов) поступает код первой фазы 1-й задачи, а на входы 21j. ..21jкод второй фазы t-и задачи. Старшие разряды кодов поступают на соответствующие входы элементов ИЛИ-НЕ 14. Если старшие разряды двух кодов равны нулю, то на выходе элемента 14| появляется высокий потенциал, который будет поступать на первый вход элементов HJM 16 узлов 15(И как на вторых входах элементов ИЛИ 16 низкие потенциалы (старшие разряды кодов равны нулю), то этот высокий потенциал будет поступать на первые входы элементов И 17 узлов 15( и 15,2- Этим обеспечивается прохождение остальных разрядов кодов, на следующие узлы сравнения 15 и т.д.

Если старшие разряды кодов равны единице, то на выходе элемента ИЛИ появится низкий потенциал, Высокие потенциалы старших разрядов кодов чере элементы ИЛИ 16 узлов 1 5,, и 1 5 ,.1, поступят на первые входы Элементов И 17, что обеспечит прохождение остальных разрядов кодов на следующие узлы сравнения и т.д. Если же старший разряд первого кода равен единице, а второго - нулю,, то ка выходе элемента ИЛИ-НЕ 14 появится низкий потенциал, который подается на первый вход элементов ИЛИ 16 узлов .Ha второй вход элемента ИЛИ 16 узла 15jj подается высокий потенциал (единица старшего разряда первого кода), поэтому на его выходе будет высокий потенциал, который позволит прохождение остальных разрядов первого кода на следующий узел ISj, сравнения. На второй вход элемента ИЛИ 16 узла 15ijподается низкий потенциал (ноль старшего разряда второго кода), поэтому на его выходе будет низкий потенциал, который не позволит прохождение остальных разрядов второго кода на следующий узел сравнения ISj. Последующие узлы 15 работают аналогично. Таким образом, если код числа, подаваемого на входы 21,..,21( не меньше кода, подаваемого на входы 21,j ...21, то высокий потенциал появится на выходе 22. Если же код числа, подаваемого на входы 21 ...2 меньше кода, подаваемого на входы 21,j ...21, то высокий потенциал появится на выходе 23. С выходов 20j...20f будет снимать ся обратный код максимального числа или прямой код минимального числа. Работа устройства начинается посл подачи разрешающего сигнала на вход 13 - первый вход элемента И 4. 1 После окончания этапа сравнения кодов в узлах 2...2и:и при наличии разрешающего сигнала на входе 13, с генератора 3 тактовыг импульсов бу дут поступать тактовые импульсы. Час тота следования тактовых импульсов определяется временем, необходимым для сравнения кодов и временем записи кода номера задачи в регистры 11 ... . 1 Ц . Далее тактовые импульсы будут поступать на.первые входы элементов И 5 вторые входдз которых подсоединены к соответствующим выходам узла 2, а также на вхо- ды счетчиков 7 и 7. Если прямой код числа в регистре не превосходит кода числа в регистре Ij , то с первого выхода узла 2 сравнения будет сниматься еди ничный сигнал, который через элемент И 5 поступит на Первый вход групп элементов И-НЕ 6,; . В результате пря мой код минимального числа с третье го вьгхода узла 2 сравнения инверти руется на выходе группы элементов И-НЕ и поступает на узел 8,, Если код числа в регистре 1,; не меньше кода, находящегося в регистр tj , то единичный сигнал будет на втором выходе схемы 2| сравнения. Этот высокий потенциал будет поступать через элемент. И на первый вход группы элементов . В резуль тате прямой код минимального числа с третьего узла 2 сравнения инвертируется и поступает на узел 8. Узел 8 обеспечивает (на одном из .1г своих выходов) , выработку единичного сигнала соответствующего макси- 55 мальному коду (из поступивших на его выходы)J и работает следующим образом. На входы 32 , . . ., 32 32rt... .32, (где п - число , ..,ji.f5, |1 - чпили задач в очереди, am- разрядность ко- да) поступают коды чисел с выходов соответствующих групп элементов Й-НЕ 6. Старшие разряды кодов подаются одновременно на первые входы элементов ИЛИ 26 и на соответствующий вход элемента ИЛК-НЕ 254 Кроме того, все входы узла 8 объединены группой элементов ИЛИ 24. Если старшие разряды кодов равны нулю, то на выходе элемента Р1ЛИ-НЕ 25 будет высокий потенциал, который поступает на вторые входы соответствующих элементов ИЛИ 26, с выходов которьпс будут сниматься высокие потенщлалы, поступающие на первые вход элементов И 27. Этим обеспечивается прохождение остальных разрядов кодов через элементы И 27 для последующего сравнения. На элемент ИЛИ-НЕ 25} поступают уже вторые разряды кодов и так далее. Если старший разряд хотя бы одного из кодов равен единице, то на выходе элемента ИЛИ-НЕ 25 появится низкий потенциал, который поступает на вторые входы элементов ИЛИ 26, на первые входы которых поступают старшие разряды кодов. Если старший разряд кода равен единице, то на выходе соответствующего элемента ИЛИ 26 будет высокий потенциал,который разрешает прохождение остальных разрядов данного кода для последующего сравнения. Разряды кодов с нулем в старшем разряде проходить через элементы И 27 не будут, так как на выходах .соответствую1цих элементов РШИ 26 будут низкие потенциалы. В результате на соответствующем выходе 34j (t-1..,n) появится единичный сигнал. Если имеется несколько одинаковых максимальных кодов, то единичные сигналы появятся на выходах соответствующих элементов И 28. Для того, чтобы на выходе узла 8 появился только один еди1гичный сигнал, все выходы элементов И 28 (кроме II -го) подключены к соответствующим элементам НЕ 29. Таким образом, если с выхода элемента И 28 будет сниматься единичный сигнал, то он будет поступать через элемент И 30 на триггер 31, который в исходном состоянии находился в СОСТОЯШ1И хранения нуля, и на элемент НЕ 29j . С выхода элемента НЕ 29( будет сниматься нулевой поте циал, который запретит прохождение единичных сигналов с других выходов элементов И 28 через элементы И 30t ...)). На выходе узла 8 появится только один единичный сигнал. Если один из единичных сигналов будет сниматься с выхода элемента И 28 (при нул на выходе элемента И 28j), то он будет проходить чере элемент И 30л, на второй вход которого поступает высокий потенциал с выхода элемента НЕ 29 ,и поступать далее на триггер 31ij.- Кроме того, этот единичный сигнал с выхода элемента И 282 поступать на элемент НЕ 29,, на выходе которого поя вится нулевой потенциал, который запретит- прохождение остальных единичных сигналов и т.д. Если на все вхо ды узла 8 поступают нулевые -коды, то на всех выходах элементов И 28J ( 1-1. . .Г) ) появятся единичные сигнала и для того, чтобы на выходе узла 8 не появился единичный сигнал, все входы узла 8 объединены элементом ИЛИ 24, выход которого соединен с .первым входом элемента И 30 . Таким образом если на входах узла 8 - нулевые коды, то на выходе элемента |ИЛИ 24 снимается нулевой сигнал, который запрещает прохождение единичного сигнала на триггер 31,. Единичным сигналом с выхода элемента И 28 запрещается прохождение остальных единичных сигналов на выходные триггеры. Триггеры 31i ( ,...,п) сбрасываются в нулевое состояние тактовыми импульсами по входу 33. Таким образом, в регистры 11. заносятся коды номеров задач. Эти коды формируются на счетчиках 7, для первой фазы и 7 - для второй фазы. В соответствии с алгоритмом функционирования устройства весь набор решаемых задач делится на две группы (в зависимости от соотношений весов реализации задач по первой и второй фазам). Если вес реализации задачи на первой фазе не. больше кода реализации задачи на второй фазе, то задачу относится к первой группе и код ве са первой фазы данной задачи поступает на узел 8. Если код веса реализации задачи на первой фазе больше кода веса реализап 1и задачи на второй фазе, то задача относится к второй группе и код веса второй фазы поступает на узел 82. Поэтому если с i -го выхода узла 8 снимается единичный сигнал, то с |-го выхода узла 8 единичный сигнал сниматься не может, так как задача становится в очередь по коду одной из фаз. Единичные сигналы с выходов узлов 8 J и 8 сбрасывают в нулевое состояние входные регистры 1 , Jм..,t, Кроме того, единичные сигналы с выходов узла 8 поступают на группы элементов И 9 ...9;,, а единичные сигналы с выходов узла 8 - на группы элементов И 92 ...9,„. Коды номера задачи формируется на счетчиках 7( для первой фазы и 7 - для второй фазы под действием тактовых импульсов. Если задача ставится в очередь по первой фазе, то код номера задачи снимается с выхода счетчика 74 и, проходя через группу элементов И 9 и группу элементов ИЛИ , записывается в- выходном регистре 11 Если задача ставится в очередь по второй фазе, то код номера задачи снимается с выхода счетчика 7. Рассмотрим работу устройства на конкретном примере. Пусть количество задач в пакете пять. На входные регистры ц 2( Ь 25 занесены обратные кo ы, соответствующие времени реализации задач на первой и второй фазаз соответственно. Пусть далее веса кодов фаз задач трехразрядные. Исходные данные приведены в таблице 1.

Таблица 1

УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ ЗАДАНИЙ ПРОЦЕССОРАМ, содержащее две группы регистров, группу узлов .сравнения, группу элементов И, группу элементов И-ПЕ, два узла выделения максимального кода, группу элементов ИЛИ, элемент И, первые входы регистров первой группы соединены с соответствующими выходами первого узла вьиеления максимального кода, отл.и чающееся тем, что, с целью сокращения оборудования, оно содержит две группы элементов И, суммир.ующий и вычитающий счетчики, и генератор тактовых импульсов, причем вторые входы регистров первой группы соединены с соответствующими выходами второго узла вьщеления максимального кода и с первыми входами элементов И второй группы, вторые входы .которых соединены с выходом вычитающего счетчика, первые входы элементов И третьей группы соединены с соответствующими выходами первого узла вьщеления максимального кода, вторые входы элементов И третьей группы соединены с выходом суммирующего счетчика, выходы 4 -X элементов И второй и третьей групп ( 1 ,. .., п , где П -: число задач в пакете) соединены с соответствующими входами t-го элемента ИЛИ группы, выход которого соединен с входом 1 -го регистра второй группы, выход которого является выходом устройства, выходы j-ro и (j-1)го регистров (,3,5,..., 2п-1) первой группы соединены с входами соответствующего узла сравнения группы, первый выход / -го узла сравнения группы (i-1,...,r)) соединен с первым входом 1 -го элемента И первой группы, второй выход i-го узла сравнения группы соеди 1ен с первым входом (i-vn)-ro элемента И перво.й группы, (Л третий выход -го узла сравнения груп пы соединен с первыми входами -го и (Чп)-го элементов И-НЕ группы, выходы элементов И первой группы сое1динены с вторыми входами соответствующих элементов И-НЕ группы, вьрсод 1-го элемента И-НЕ группы соединен с i -м информационным входом первого узла вьделения максимального кода, выход j-го (j n-t-1 ,. . . ,2п) элемента И-НЕ группы соединен с соответствующим информационным входом второго узла вьщеления максимального кода, выход генератора тактовых импульсов соединен с первьгм входом элемента И, , второй вход которого является входом устройства, выход элемента И соединен с тактовыми входами первого и второго узлов выделения максимального кода,с вторыми входами элементов И первой группы и с входами суммирующего и вычитающего счетчиков.

Коды весов задач на первой и второй фазах поступают на соответствующие узлы сравнения кодов 2. Если обратньй код реализации задачи на первой фазе не меньше обратного кода веса задачи на второй фазе, то высокий потенциал появится на первом выходе узла 2 (иначе высокий потенциПроцесс функционирования устройства продолжается с приходом на вход «3 разрешающего сигнала, который 50 поступает на первый вход элемента И 4 и разрешает прохождение тактовых импульсов с генератора 3 на элементы И 5ц ... 21 счетчики 7 J и и узлы 8 . и 8 .55

Тактовый импульс, поступая на элементы И 5fj .. -Sij , разрешает прохождение единичного сигнала с первого

ал появится на втором выходе узла 2) С третьего выхода узла 2 будет сниматься обратный код максимального числа или прямой код минимального числа.

Таким образом, для данного приме, ра на выходах узлов 2... 2 -появятся коды, приведенные в таблице 2.

Таблица2

выхода узла 2 , (i 1. . .5) на вторые входы группы элементов И-НЕ 6 ...6„. Этим разрешается прохождение и инвертирование обратного кода максимального числа или прямого кода минимального числа на входы групп элементов И-НЕ 6ff .. .6fi .

Далее каждый инвертированный код поступает на соответствующие входы узла 8. Этот же тактовый импульс поступает на элементы И 52 ...52с, 11 разрешая прохождение единичного сиг нала с второго выхода узла 2j ( « :1...5) на группы элементов И-НЕ 6,,...6 2с Этим осуществляется инвер тированиё обратного кода максимального числа или прямого кода минималь ного числа, которые поступают на вто рые входы группы элементов И-НЕ 6,. . . с. третьего выхода узлов сравнения 2 ( i41...5). Далее этот инвертированный код поступает на соответствуюпще входы узла 82. Единичный сигнал будет сниматься с того выхода узла 8 (8 или 8), ко

Узел 8,

101

2 3 110 100

4 110

5

Узеп 8i

В исходном состоянии на счетчике 7(, - ноль, а на счетчик 7j в исходном состоянии занесен код числа (hil), (где и - число задач в пакете) . В данном примере на счетчик 7 занесен код числа 6. Счетчик 7 суммирующий, а счетчик 7 - вычитающий.

о о о о о

о

1

о о о о о

о 1

о о о о

о о

С приходом первого тактового импульса на счетчике 7 сформируется код единицы, а на счетчике 7 - код числа пять. Разрядность счетчиков определяется по известной формуле.

Таким образом, на первом такте единичный сигнал с второго выхода узла 8( будет поступать на группу эле3торыи соответствует максимальному коду. Этим единичным сигналом сбрасываются в нулевое состояние соответствующие входные регистры (два - по количеству фаз). Этот же единичный сигнал поступает на соответствующую группу элементов И 9 и разрешает прохождение кода номера задачи, сформулированного на счетчике 7, на выходной регистр 11 (...5). В каяздом такте с выхода узла 8 будет сниматься только один единичный сигнал. Работу узла 8 определения максимального кода поясняет таблица 3. ТаблицаЗ 1311 ментов И 9,2 и код единицы с счетчика 7| через группу элементов И 9 и группу элементов ИЛИ lOj записывается в регистр 11g. В этом же такте единичный сигнал снимается с пятого выхода узла Sg и поступает на группу элементов И 9 , а код числа пять с выхода счетчика 7 поступает через 3 группы элементов И 92 и ИЛИ Ю и записывается в регистр 1Ij. Для данного примера во втором и остальных тактах единичные сигналы будут .сниматься только с выходов узла 8, т.е. остальные задачи будут ставиться в очередь по первой фазе.