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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИН 09) ИИ 3 Ш С 06 Р 9/46ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙОПИСАНИЕ ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(56) 1. Авторское свидетельство СССРВ 696471, кл. С 06 Р 15/20, 1979,2, Авторское свидетельство СССРУ 959083, кл. С 06 Р 9/46, 1982(54)(57) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ ЗАДАНИЙ ПРОЦЕССОРАМ, содержащеедве группы регистров, группу узлов,сравнения, группу элементов И, группу элементов И-НЕ, два узла вьщеления максимального кода, группу элементов ИЛИ, элемент И, первые входырегистров первой группы соединеныс соответствующими выходами первогоузла вьщеления максимального кода,о т л и ч а ю щ е е с я тем, что,с целью сокращения оборудования, оносодержит две группы элементов И, суммирующий и вычитающий счетчики, игенератор тактовых импульсов, причемвторые входы регистров первой группысоединены с соответствующими выходами второго узла вьщеления максимального кода и с первыми входами элементов И второй группы, вторые входы.которых соединены с выходом вычитающего счетчика, первые входы элементов И третьей группы соединены с соответствующими выходами первого узлавьщеления максимального кода, вторыевходы элементов И третьей группы соединены с выходом суммирующего счетчика, выходы ь -х элементов И второй и третьей групп ( ь: 1п, где я число задач в пакете) соединены с соответствующими входами ь -го элемента ИЛИ группы, выход которого соединен с входом ь -го регистра второй группы, выход которого является выходом устройства, выходы -го и (1-1)- го регистров ( = 1,3,5 2-1) первой группы соединены с входами соответствующего узла сравнения группы, первый выход / -го узла сравнения группы (1=1 соединен с первым( входом 1 -го элемента И первой группы, второй выход 1-го узла сравнения группы соединен с первым входом 19 (ь+и)-го элемента И первой группы, третий выход 1 -го узла сравнения груп пы соединен с первыми входами 1 -го и (,ьл)-го элементов И - НЕ группы, выходы элементов И первой группы соединены с вторыми входами соответствуГ ющих элементов И-НЕ группы, выход )-го элемента И-НЕ группы соединенс; -м информационным входом первого узла выделения максимального кода, выход-го (= +12 п) элемента И-НЕ группы соединен с соответствующим информационным входом второго узла вьщеления максимального кода, выход генератора тактовых импульсов соединен с первым входом элемента И,. второй вход которого является входом устройства, выход элемента И соеди- ф нен с тактовыми входами первого и второго узлов вьщеления максимального кода,с вторыми входами элементов И первой группы и с входами суммирую" щего и вычитающего счетчиков.1126963 Фие 3 Составитель Г,Пономареваор А.Ревин Техред О,Ващишина Корректор С.Шекма Ред Зака 1 о ное илиад ППП "Патент", г.ужгород, ул,Проектная,41/38 Тираж 698 ВНИИПИ Государствен по делам изобрете 113035, Москва, Ж-Эого комитета СССий и открытийРаушская наб., 1126963Изобретение относится к вычислительной технике и может быть использовано в разработках аппаратного диспетчера при организации мультипрограммной обработки пакета программ в ЦВМ, а также в устройствах, предназначенных для решения задач теории расписаний в специализированных процессорах.Известно устройство для распределения заданий, содержащее матрицу ячеек памяти, блок анализа строк, содержащий приемный регистр, узел опроса, регистр назначений, шифратор, регистр, генератор, счетчик назначе ния, схему сравнения, триггеры, элементы ИЛИ, И и НЕНедостатками известного устройства являются сложность и низкое быстродействие при решении пакета в ЦВМ, 20Наиболее близким к предлагаемомуявляется устройство для распределения заданий, содержащее первый узел поиска максимального кода (УПМК), г 1 групп блоков первых элементов И (где 25 й - количество задач в пакете), группы первых и вторых регистров,О групп блоков вторых элементов И, группу блоков третьих элементов И, группу схем сравнения, группу первых элемен-З 0 тов НЕ, второй УПМК, группы первых и вторых элементов И-НЕ, группу вторых элементов НЕ, группу четвертых элементов И, группу третьих элементов И, группу блоков пятых элементов И, третий УПМК, группу третьих элементов НЕ, группу элементов ИЛИ 21 .Недостаток данного устройствабольшие аппаратные затраты.Целг изобретения - сокращение обоРудования.Поставленная цель достигается тем,что устройство для распределения заданий процессорам, содержащее двегрупггы регистров, группу узлов сравнения,группу элементов И,группу элементов И-НЕ,два узла выделения максимального кода, группу элементов ИЛИ,элемент И,первые входы регистров первой группы соединенысоответствующими выхода ми первого узла выделения максимального кода, содержит две группы элементов И, суммирующий и вычитающий счетчики, и генератор тактовых импульсов, причем вторые входы регист ров первой группы с.одинены с соответствующими выходами второго узла вьделения максимального кода и с пер -выми входами элементов И второй группы, вторые входы которых соединеныс выходом вычитающего счетчика, первые входы элементов И третьей группы соединены с соответствующими выходами первого узла выделения максимального кода, вторые входы элементов И третьей группы соединены с выходом с.;ммирующего счетчика, выходы-х элементов И второй и третьейгрупп ( в -1 г, где и - число задачв пакете) соединены с соответствующими входами-го элемента ИЛИ группы, выход которого соединен с входом-го регистра второй группы, вьгходкоторого является выходом устройства,выходы-го и (1-1)-го регистров(1 =1,.;,52 п) первой группы соединены с входами соответствующегоузла сравнения группы, первый выходт-го узла сравнения группы (=1,11)соединен с первым входом : - го элемента И первой группы, второй выход4 -го узла сравнения группы соединенс первым входом (+ и)-го элемента Ипервой группы, третий выход- го уз -ла сравнения группы соединен с первыми входами -го и (п)-го элементовИ-НЕ группы, выходы элементов И первой группы соединены с вторыми входами соответствующих элементов И-НЕгруппы, выход-го элемента И-НЕгруппы соединен с-ым информационным входом первого узла выделениямаксимального кода, выход ) -го (==и+1,20) элемента И - НЕ группы соединен с соответствующим информационным входом второго узла выделениямаксимального кода выход генераторатактовых импульсов соединен с пер -вым входом элемента И, торой входкоторого является входом устройства,выход элемента И соединен с тактовыми входами первого и второго узловвыделения максимального када, с вторыми входами элементов И первой группы.и с входами суммирующего и вычитающего счетчиков. Сущность изобретения заключаетсяв том, что устройство назначае. задачи для реализации в соответствиис модифицированным алгоритмом ДЖОНСОНА (решение задачи о двух станках),при этом за один такт работы устройства определяются номера очередностисразу двух задач из пакета,На фиг. 1 представлена структурная схема устройства для рапределе -3 1126ния заданий; на фин. 2 - структурная 1схема узла сравнения кодов; на фиг.3 -схема узла вьделения максимальногокода.Устройство для распределения заданий содержит регистры 1111 и11 1, прой группы (гделичество задач в пакете), в которыев исходном состоянии заносятся обратные коды, соответствующие времени . Ообработки задач на первой и второйфазах соответственно, узлы 22 исравнения группы, генератор 3 такто-,вых импульсов, элемент И 4, первуюгруппу элементов И 511 51, группу 15элементов И-НЕ 61 62 ц, суммирующий 7 и вычитающий 7 р счетчики,узлы 8 и 8 вьделения максимального кода, элементы И 9, ,9 третьейгруппы, элементы И 9 ,9 второй 20группы, группу элементов ИЛИ101 10 д, вторую группу регистров1111, выходы 1212, и вход 13.Узел 2 сравнения кодов содержитгруппы элементов ИЛИ в14114 п 25(где п 1 - разрядность кодов), узлы15 15 анализа разрядов, каждыйиз которых содержит элемент ИЛИ 16,группы элементов И 17, элемент НЕ 18,элемент И 19, выходы 20420 щ, входы 211,21, выходы 22 и 23.Узел 8 вьделения максимального кода содержит группу элементов ИЛИ 24,группы элементов ИЛИ-НЕ 25, группыэлементов ИЛИ 26, группы элементов35И 27, группу элементов И . 284 28 п,группу элементов НЕ 29129 д.группу элементов И 30 430 п, выходные триггеры 3131 п, входы32 ц 32, вход 33, выходы341 34 пУстройство работает следующим образом,В исходном состоянии в группу регистров 11111, заносятся обратные 45коды, соответствующие времени первойфазы реализации задач - времени ввода задач, в группу регистров 17 171 74заносятся обратные коды пропорциональные времени второй фазы реализации задач, т.е. сумме временирешения задач и вывода результатових решения. В нулевом состоянии будут регистры 11 и счетчик 7 . На вхо.т1ды узлов 2, .,1=1,л) подаются обратные коды, т.е. коды с инверсныхвыходов регистров 1, 1,. Узлы22 представляют собой схемы вы 963деления максимального кода, но таккак информация на них подается ужев обратном коде, то в этих узлах выбираются минимальные числа из кодов,занесенных в регистры 11 и 1 у;Узел сравнения 2 работает следующим образом.На входы 21 211 (где Гп - разрядность кодов) поступает код первойфазы 1-й задачи, а на входы 2121, -код второй фазы 1 -й задачи, Старшиеразряды кодов поступают на соответствующие входы элементов ИЛИ-НЕ 14 .Если старшие разряды двух кодов равны нулю, то на выходе элемента 141появляется высокий потенциал, который будет поступать на первый входэлементов ИЛИ 16 узлов 151 и 151.Так как на вторых входах элементовИЛИ 16 низкие потенциалы (старшиеразряды кодов равны нулю), то этотвысокий потенциал будет поступатьна первые входы элементов И 17 узлов 15 и 151. Этим обеспечиваетсяпрохождение остальных разрядов кодов,на следующие узлы сравнения 15 - 15и т.д.Если старшие разряды кодов равныединице, то на выходе элемента ИЛИНЕ 141 появится низкий потенциал,Высокие потенциалы старших разрядовкодов через элементы ИЛИ 16 узлов15 и 15 поступят на первые входыэлементов И 17, что обеспечит прохож-дение остальных разрядов кодов наследующие узлы сравнения 15 и 15и т.д,Если же старший разряд первого кода равен единице, а второго - нулю то на выходе элемента ИЛИ-НЕ 14 1 появится низкий потенциал, который подается на первый вход элементов ИЛИ 16 узлов 15 и 15 .На второй вход элемента ИЛИ 16 узла 15 подается высокий потенциал (единица старшего разряда первого кода), поэтому на его выходе будет высокий потенциал, который позволит прохождение остальных разрядов первого кода на следующий узел 15 1 сравнения. На второй вход элемента ИЛИ 16 узла 151 подается низкий потенциал (ноль старшего разряда второго кода), поэтому на его выходе будет низкий потенциал, который не позволит прохождение остальных разрядов второго кода на следующий узел сравнения 15, Последующие узлы 15 работают аналогично, 1126963Таким образом, если код числа, подаваемого на входы 21,211 не меньше кода, подаваемого на входы 21121 , то высокий потенциал появится на выходе 22, Если же код числа, подаваемого на входы 2121;, меньше кода, подаваемого на входы 2 1 21, то высокий потенциал появится на выходе 23.С выходов 20 20 будет снимать 10 ся обратный код максимального числа или прямой код минимального числа.Работа устройства начинается после подачи разрешающего сигнала на вход 13 - первый вход элемента И 4.После окончания этапа сравнения кодов в узлах 212 и при наличии разрешающего сигнала на входе 13, с генератора 3 тактовьп. импульсов будут поступать тактовые импульсы. Час- М тота следования тактовых импульсов определяется временем, необходимым для сравнения кодов и временем записи кода номера задачи в регистры 11 11, . Далее тактовые импульсы25 будут поступать на. первые входы элементов И 5 5 , вторые входы кои фторых подсоединены к соответствующим выходам узла 2, а также на вхо ды счетчиков 7 и 7.30Если прямой код числа в регистре 1не превосходит кода числа в регистре 1, то с первого выхода узла 21 сравнения будет сниматься единичный сигнал, который через элемент д И 51, поступит на первый вход группы элементов И-НЕ 6 В результате прямой код минимального числа с третьего выхода узла 2сравнения инвертируется на выходе группы элементов 4 О И-НЕ 61, и поступает на узел 8,Ф Если код числа в регистре 1, не меньше кода, находящегося в регистре 1 у, то единичный сигнал будет на 45 втором выходе схемы 2 сравнения. Этот высокий потенциал будет поступать через элемент. И 5, на первьй вход группы элементов 6, . В результате прямой код минимального числа Я с третьего узла 2 сравнения инвертируется и поступает на узел 8,Увел 8 обеспечивает (на одном иэ И своих выходов), выработку единичного сигналасоответствующего макси мальному коду (из поступивших на его выходы)и работает следующим образом. На входы 321 ф 32 32 3232 я,32 я,(где р - число за- даЧ в очереди, а е - разрядность кода) поступают коды чисел с выходовсоответствующих групп элементов И-НЕ 6.Старшие разряды кодов подаются одновременно на первые входы элементов ИЛИ 26 и на соответствующий вход элемента ИЛИ-НЕ 25 . Кроме того, все входы узла 8 объединены группой элементов ИЛИ 24.Если старшие разряды кодов равны нулю, то на выходе элемента ИЛИ-НЕ 251 будет высокий потенциал, который поступает на вторые входы соответствующих элементов ИЛИ 26, с выходов которых будут сниматься высокие потенциалы, поступающие на первые входы элементов И 27. Этим обеспечивается прохождение остальных разрядов кодов через элементы И 27 для последующего сравнения. На элемент ИЛИ-НЕ 25 поступают уже вторые разряды кодов и так далее,Если старший разряд хотя бы одного из кодов равен единице, то на выходе элемента ИЛИ-НЕ 25 появитсянизкий потенциал, который поступаетна вторые входы элементов ИЛИ 26, на первые входы которых поступаютстаршие разряды кодов. Если старшийразряд кода равен единице, то на выходе соответствующего элемента ИЛИ 26 будет высокий потенциал, которыйразрешает прохождение остальных разрядов данного кода для последующего сравнения, Разряды кодов с нулем в старшем разряде проходить через элементы И 27 не будут, так как на выходах .соответствующих элементовИЛИ 26 будут низкие потенциалы.В результате на с -ответствующем выходе 34 1 ( =1 о ) появится единичный сигнал.Если имеется несколько одинаковых максимальных кодов, то единичные сигналы появятся на выходах соответствующих элементов И 8. Для того, чтобы на выходе узла 8 появился только один единичный сигнал, все выходы элементов И 28 (кроме 0 -го) подключены к соответствующим элементам НЕ 29, Таким образом, если с выхода элемента И 28 будет сниматься единичный сигнал, то он будет поступать через элемент И 301 на триггер 31, который в исходном состоянии находил 1126963ся в состоянии хранения нуля, и наэлемент НЕ 291. С выхода элементаНЕ 291 будет сниматься нулевой потенциал, который запретит прохождениеединичных сигналов с других выходов .: 5элементов И 28 через элементы И 30 с(1:10). На выходе узла 8 появитсятолько один единичный сигнал.Если один из единичных сигналовбудет сниматься с выхода элементаИ 282 (при нуле на выходе элементаИ 281), то он будет проходить черезэлемент И 30, на второй вход которого поступает высокий потенциал свыхода элемента НЕ 29 ,и поступать 15Эдалее на триггер 31 . Кроме того,этот единичный сигнал с выхода элемента И 28 будет поступать на эле 2мент НЕ 292, на выходе которого появится нулевой потенциал, который запретит прохождение остальных единичных сигналов и т.д. Если на все входы узла 8 поступают нулевые коды,то на всех выходах элементов И 28,( 1=1 П ) появятся единичные сигнала и для того, чтобы на выходе узла8 не появился единичный сигнал, всевходы узла 8 объединены элементомИЛИ 24, выход которого соединен спервым входом элемента И 301. Таким 30образом если на входах узла 8 - нулевые коды, то на выходе элементаИЛИ 24 снимается нулевой сигнал, который запрещает прохождение единичного сигнала на триггер 311. Единич- З 5ным сигналом с выхода элемента И 28запрещается прохождение остальныхединичных сигналов на выходные триггеры. Триггеры 31 ( 1:1,,й) сбрасываются в нулевое состояние тактовыми импульсами по входу 33.Таким образом, в регистры 111111заносятся коды номеров задач. Этикоды формируются на счетчиках 71 дляпер ой фазы и 72 - для второй фазы.В соответствии с алгоритмом функционирования устройства весь наборрешаемых задач делится на две группы(в зависимости от соотношений ве 11сов реализации задач по первой ивторой фазам),Если "вес" реализации задачи на первой фазе не. больше кода реализа" ции задачи на второй фазе, то задач относится к первой группе и код "веса" первой фазы данной задачи поступает на узел 81 .Если код "веса" реализации задачи на первой фазе больше кодавеса" реализации задачи на второй фазе, то задача относится к второй группе и код "веса" второй фазы поступает на узел 82 . Поэтому если с 1 -го выхода узла 8, снимается единичный сигнал, то с е -го выхода узла 8 у единичный сигнал сниматься не может, так . как задача становится в очередь по коду одной из фаз.Единичные сигналы с выходов узлов 8и 82 сбрасывают в нулевое состояние входные регистры 111, 121 ..,11 12 иКроме того, единичные сигналы с выходов узла 81 поступают на группы элементов И 919 , а единичные сигналы с выходов узла 8- на группы элементов И 92 9 . Коды номера задачи формируется на счетчиках 71 для первой фазы и 7 - для второй фазы под действием тактовых импульсов, Если задача ставится в очередь по первой фазе, то код номера задачи снимается с выхода счетчика 71 и, проходя через группу элементов И 91, и группу элементов ИЛИ 10, записывается в выходном регистре 11Если задача ставится в очередь по второй фазе, то код номера задачи снимается с выхода счетчика 7 .Рассмотрим работу устройства на конкретном примере.Пусть количество задач в пакете пять. На входные регистры 1 д , 12111, 125 занесены обратные ко ды, соответствующие времени реалмзации задач на первой и второй фаза соответственно. Пусть далее "веса" кодов фаз задач трехраэрядные.Исходные данные приведены в таб лице 1..Фазы Регистр первая 101 110 Код 100 110 001 Регистр й 4 вторая 101 101 001 Код 011 101 Т аблица 2 Знак Код реализации на первой фазе Код реализации на второй фазе И узласравнения Обратныйкод щах В выхода единичного сигначисла или прямой код ппп числа ла 101 21 101 010 110 001 001 011 100 011 001 110 101 010 001 Коды "весов" задач на первой и второй фазах поступают на соответствующие узлы сравнения кодов 2. Если обратный код реализации задачи на первой фазе не меньше обратного кода "веса" задачи на второй фазе, то вы, сокий потенциал появится на первом выходе узла 2 (иначе высокий потенци 25 Процесс функционирования устройства продолжается с приходом на вход 13 разрешающего сигнала, который 5 С поступает на первый вход элемента И 4 и разрешает прохождение тактовых импульсов с генератора 3 на элементы И 544 5.4, 52 52, счетчики 7 и 72 и узлы 8 и 8 у, 55Тактовый импульс, поступая на эле-, менты И 544 54 у, разрешает прохождение единичного сигнала с первого ал появится на втором выходе узла 2), С третьего выхода узла 2 будет сниматься обратный код максимального числа или прямой код минимального числа.Таким образом, для данного приме, ра на выходах узлов 242.появятся коды, приведенные в таблице 2. выхода узла 2; (4 =15) на вторые входы группы элементов И-НЕ 6 6 Этим разрешается прохождение и инвертирование обратного кода максимального числа или прямого кода минимального числа на входы групп элементов И-НЕ 644 64 .Далее каждый инвертированный код поступает на соответствующие входы узла 84 . Этот же тактовый импульс поступает на элементы И 52 52,1126963 разрешая прохождение единичного сигнала с второго выхода узла 2, =15) на группы элементов И-НЕ 616 . Этим осуществляется инвертирование обратного кода максимального числа или прямого кода минимального числа, которые поступают на вторые входы группы элементов И-НЕ 61 6 с третьего выхода узлов сравнения 2 ( 1:15). Далее этот 10 инвертированный код поступает на соответствующие входы узла 8 у .Единичный сигнал будет сниматься с того выхода узла 8 (8 или 8), коТ а б л и ц а 3 Узел 81 34 Выход узла 8 Неинвертиро -ванный код Такты Инв. код 0 0 0 0 101 010 О 0 0 110 001 0 0 0 100 011 0 0 0 110 001 0 0 0 0 Узел 82 О 0 0 0 0 0 0 0 0 0 О 0 0 0 0 0 101 О 0 0 0 010 С приходом первого тактового импульса на счетчике 7 сформируется код единицы, а на счетчике 7 - код числа пять. Разрядность счетчиков 55 определяется по известной формуле,Таким образом, на первом тактеединичный сигнал с второго выхода узла 81 будет поступать на группу элеВ исходном состоянии на счетчике 71, - ноль, а на счетчик 7 в исходном состоянии занесен код числа (И+1), (где и - число задач в пакете). В данном примере на счетчик 7 занесен код числа 6, Счетчик 7 суммирующий, а счетчик 7 - вычитающий. торый соответствует максимальному коду, Этим единичным сигналом сбрасываются в нулевое состояние соответствующие входные регистры (два - по количеству фаз). Этот же единичный сигнал поступает на соответствующую группу элементов И 9 и разрешает прохождение кода номера задачи, сформулированного на счетчике 7, на выходной регистр 11; (1= 15). В каждом такте с выхода узла 8 будет сниматься только один единичный сигнал.Работу узла 8 определения максимального кода поясняет таблица 3.13 11 ментов И 9 н код,единицы с счетчика 7 через группу элементов И 91 и группу элементов ИЛИ 10 записывается в регистр 11, В этом же такте единичный сигнал снимается с пятого выхода узла 8 и поступает на группу элементов И 9, а код числа пять с выхода счетчика 7 поступает через 26963 14 группы элементов И 9 и ИЛИ 10 и записывается в регистр 11. Для данного примера во втором и остальных тактах единичные сигналы будут .сниматься только с выходов узла 81, т;е, остальные задачи будут ставиться в очередь по первой фазе.