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

,12331 БЛИ 6 Р 15/20, 9 АНИЕ ИЗОБРЕТЕНИЯ ВТОРСКОМУ СВИ 21) 3803200/24-2422) 16.10.8446) 23.05.86. Бюл.72) В.В. Мазаник,С.В, Ефимов53) 681.333(088,8) 19Н свидетельство СССР06 Е 15/20, 1980.идетельство СССРС 06 Г 15/20, 1983.(56) АвторскоеВ 716043, кл.Авторское сУ 1037267, кл ЕЛЕНИЯЕМЕ АСПРЙ СИсит ся к области и. Цель изобрееднего времени в вычислительво содержит блок числа, регистры, ешифраторы, элеэлемент сравГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ(57) Изобретение отнвычислительной технитения - сокращение собслуживания заданийной системе. Устройсвыбора максимальногосчетчики, триггеры,менты И, элементы ИЛИ нения,элемент задержки,элементИЛИ-НЕ,генератор импульсовНовым в устройстве является использование блокавыбора максимального числа, триггеров, дешифраторов, элементов ИЛИ,генератора импульсов и элемента ИЛИ-НЕ, позволяющее назначать наобслуживание свободными процессорамив первую очередь заданий с максимальной длительностью выполнения, обеспечить параллельное планирование заданий и коррекцию информационно-управляющего графа связности между заданиями. Устройство выявляет независимые по информационно-управляющим связям задания, из их числа выбираетзадания с максимальной длительностьювыполнения и назначает их на свободные процессоры, производит после выполнения заданий процессорами коррекцию информационно-управляющего графа связности между заданиями. 2 ил. ффЖ123Изобретение относится к вычислительной технике, в частности к устройствам для распределения задач ввычислительных системах.Цель изобретения - сокращение времени обслуживания заданий в вычислительной системе.На Фиг. 1 представлена структурная схема устройства, на Фиг, 2структурная схема блока для выборамаксимального числа,Предлагаемое устройство содержитматрицу 1 (размером И х М ) Формирователей дуг, первый элемент ИЛИ 2,блок 3 выбора максимального числа,триггеры 4, первую группу элементовИЛИ 5, первую группу элементов И б,группу счетчиков 7 счетчик 8, группу схем 9 сравнения, первую группутриггеров 10, вторую группу элементов И 11, первую и вторую группы регистров 12 и 13, третью группу элементов И 14, вторую группу элементовИЛИ 15, вторую группу триггеров 16,второй элемент ИЛИ 17, элемент И 18,генератор 19 импульсов, третью группу элементов ИЛИ 20, четвертую группу элементов И 21, группу элементовИЛИ-НЕ 22, группу дешифраторов 23,четвертую группу элементов ИЛИ 24,третий элемент ИЛИ 25, элементИЛИ-НЕ 26, первый и второй элементы27 и 28 задержки, группу блоков поразрядных узлов 29 анализа, третью,четвертую и пятую группы элементовИ 30 - 32, пятую и шестую группы элементов ИЛИ 33 и 34, третью группутриггеров 35, группу элементов И-НЕ 36седьмую группу элементов ИЛИ 37 третью группу регистров 38, третью группу элементов И 39, первую, вторую,третью, четвертую и пятую группы входов 40 - 44, вход 45, выход 46, группу выходов 47 устройства, первуюгруппу входов 48, первый вход 49,вторую группу входов 50, второй вход51 и группу выходов 52 блока 3 выбора максимального числа,Устройство работает следующим образом.В исходном состоянии триггеры 4и 10, счетчики 7 и 8 обнулены.Первоначально в триггеры 4 матрицы 1 Формирователей дуг по входам 40заносится информация о топологии графа (вершины которого соответствуютзаданиям, а дуги - информационно-управляющим связям между ними). При,этом соответствующие триггеры 4 ус 3161 ить три этапа.На. первом этапе производится оп О ределение независимых заданий (плацирование обработки заданий). Приэтом ца вь 1 ходе элементов ИЛИ 5 встолбцах, соответствующих начальнымвершинам информационно-управляющегографа,фпоявляются низкие потенциалы,так как начальные вершины не содержат входящих дуг и триггеры 4 в этихтолбцах находятся в нулевом состоянии, импульс запуска по вхоцу 45 чеЗо реЗ элемент ИЛИ 2 поступает на вторыевходы всех элементов И 6 и счетныйвход счетчика 8, Импульс запуска устанавливает в единичное состояние всетриггеры 10, При этом импульс запуска не проходит через элементы И 6 на.35счетчики 7 тех столбцов матрицы 1,все триггеры 4 которых находятся внулевом состоянии, Кроме того, импульс запуска устанавливает в единич Оное состояние все триггеры 10. В динамике функционирования устройства-й триггер устаиавливается в нулевое состояцие после назначения д -го задания ца процессор.Далее содержимое каждого счетчика 7 поступает на первый вход соответствующего элемента 9 сравнения, ана другой .вход этого элемента - инФормация со счетчика 8. При несовпадении показаний счетчиков 7 и 8 эле 5 мент 9 сравнения вырабатьвает сигнал,который поступает на второй вход соответствующего элемента И 11. На выходе з -го элемента И 11 появляетсяединичный сигнал только в том случае,если-й триггер 10 находится в единичном состоянии, а на выходе ,-гоэлемента 9 сравнения - также единичный сигнал,танавливаются в единичное состояние,Номер триггера, установленного в единичное состояние, определяется пересечением строки с номером, равным 5 номеру начальной вершины дуги, истолбца с номером, равным номеру ееконечной вершины.В соответствующий регистр 13 повходу 42 заносится. код номера зада О ния и исхсдные для его выполнения. В-и регистр 12 (=1,Мгде М - количество заданий) по входам 41 заносится код времени выполнения (длительности)-го задания. В общем 15 случае коды времен выполнения заданий отличаются друг от друга.В работе устройства можно выде 1233161На втором этапе работы устройства производится выбор из числа независимых заданий задания с максимальной длительностью выполнения. Производится это следующим образом. В исходном состоянии в триггеры регм.тров 38 блока 3 выбора максимального числа записаны коды времени выполнения заданий (из регистров 12 они поступают по входам 50 блока 3). Совокупность 1 О сравниваемых чисел задается путем установки в единичное состояние триггеров 36 блока 3 для выбора максимального числа сигналами с выходов соответствующих элементов И 11 по входам 48 блока 3 выбора максимального числа. Запуск блока 3 выбора максимального числа по входу 51 обеспечивается импульсом с генератора 19 импульсов через элемент И 18 при ус О ловии, что хотя бы один процессор вычислительной системы свободен (при наличии сигнала на входах 43 устройства, устанавливающего 1 -й триггер 16 в единичное состояние, -1 =1,, 25 где- число процессоров вычислительной системы, в соответствии с чем на выходе элемента ИЛИ 17 находится единичный сигнал). При этом обеспечивается поразрядный анализ сравниваемых чисел следующим образом. Если в первом разряде чисел имеется и 0 и 1, то через элементы И 30 и 31 узлов 29, анализа на группу элементов ИЛИ 33 и 37 поступают единич 35 ные сигналы, На выходе элемента И-НЕ 36 сформируется нулевой сигнал, который закрывается элементом И 39;, Через элементы И 32 узлов анализа и элементы ИЛИ 34, относящихся к тем40 регистрам, в первом разряде которых записан О, единичный сигнал поступает на входы установки в нулевое состояние соответствующих триггеров 35, Элементы И 30 и 31 соответствующих узлов анализа закрываются, и единич 45 ный сигнал находится только на выходеэлемента ИЛИ 37. На выходе элемента И-НЕ формируется единичный сигнал,по которомуоткрывается элементИ 39.Далее производится анализ следующего разряда оставшихся сравниваемых чисел.Если же в первом разряде сравнива. емых чисел только нулевые коды или только единичные, то на выходе элемента И-НЕ 36 находится единичный сигнал, который открывает элемент И 39, Следовательно, в этом случае сразу производится анализ второго илипоследующих разрядов. После того, каквсе разряды сравниваемых чисел проанализированы, на выходе элементаИ 39 формируется единичный уровень.При этом на выходах 52 блока 3 выбора максимального числа содержитсяунитарный кодномера задания с максимальной длительностью выполнения из числа заданных (унитарный код00100 указывает, что выбран третийномер задания).Единичный сигнал на К-м выбранномвыходе 52 блока 3 выбора максимальногочисла разрешает прохождение кода номера К-го задания и его исходных данных иэ К-го регистра 13 через К-й блок элементов И 14, блок элементов ИЛИ 15 на первые входы блоков элементов И 21. Кроме того, сигнал с К-го выхода 52 блока 3 выбора максимального числа устанавливает в нулевое состояние К-й триггер 10, чем исключается из дальнейшего анализа К-е задание.На третьем этапе работы устройства обеспечивается назначение выбранного задания на свободный процессор вычислительной системы и коррекция матрицы информационно управляющего графа, т,е. установка в нулевое сос-. тояние триггеров 4 матрицы 1 тех строк, номера которых соответствуют кодам номеров задания, обслуженных процессорами. Сигналы готовности процессоров по входам 43 устройства устанавливают в единичное состояние соответствующие триггеры 16 и разрешают прохождение кода номера К выбранного задания с максимальной длительностью через блок элементов И 21, соответствующий свободному процессору с минимальным номером. Это обеспечивается блоком элементов ИЛИ-НЕ 22, в котором-й вход 43 устройства соединен с входами ( 1 + 1,ь )-ых элементов ИЛИ-НЕ. Таким образом, сигнал на 1 -м "младшем" входе 43 устройства запрещает прохождение информации через бло. ки элементов И 21 с большими номерами, Код номера К задания и исходные данные для его выполнения поступают на группу выходов 47 устройства. Кроме того, на выходе 1 -го элемента ИЛИ 20 появляется единичный сигнал, который устанавливает в нулевое состояние 1 -й триггер 16, чем показывает занятость-го процессора вычислительной системы.По окончании обслуживания К-го задания (-м процессором на-м входе готовности 43 устройства появляется единичный сигнал, на группе входов 44 - код номера К обслуженного задания, Код К дешифруется дешифратором 23, через К-й элемент ИЛИ 24 обнуляет триггеры 4 К-й строки матрицы 1 и через элемент ИЛИ 25 поступает на вход элемента ИЛИ 2, выполняя затем функции импульса запуска, и начинается повторное выполнение первого этапа работы устройства,При обнулении всех триггеров 4матрицы 1 на выходах всех элементов ИЛИ 5 находятся нулевые сигналы, а на выходе элемента ИЛИ-НЕ 2 б - единичный сигнал, Этот сигнал через элемент 27 задержки обнуляет счетчикии 8 и поступает на выход 4 б устройства. На этом работа устройства заканчивается.Формула из обретенияУстройство для распределения задачв вычислительной системе, содержащеематрицу формирователей дуг из м мтриггеров ( М - число реализуемых задач), первый, второй и третий элементы ИЛИ, первую группу триггеров,первую и вторую группы регистров, первую, вторую, третью и четвертую группыэлементов И, первую, вторую и третью35группы элементов ИЛИ, элемент И, элемент ИЛИ-НЕ, первый и второй элементы задержки, группу счетчиков, счетчик, группу схем сравнения, с-йвход (с,3 = 1,И 1 ) первой группы информационных входов устройства соединен с единичным входом с 1 -го триггера матрицы формирователей дуг, единичные выходы триггеров 1 -го столбца матрицы формирователей дуг подклю 45чены к входам 1 -го элемента ИЛИпервой группы, выходы элементов ИЛИпервой группы соединены с входамиэлемента ИЛИ-НЕ и первыми входами со-ответствующих элементов И первой50 группы, выходы которых подключены ксчетным входам соответствующих счетчиков групп, выходы которых соединены с первыми входами соответствующихсхем сравнения группы, выходы схем сравнения группы соединены с первыми 55 входами соответствующих элементов И второй группы, 1 -й вход второй группы информационных входов устройства соединен с информационным входом-го регистра первой группы,выходы регистров первой группы соединены с первыми входами соответствующих элементов И третьей группы, выходы которых соединены с входами элементов ИЛИ второй группы, выходы которых подключены к первым входам элементов И четвертой группы, выходы которых соединены с группой информационных выходов устройства, запускающий вход устройства подключен к единичным входам триггеров первой группы и первому входу первого элементаИЛИ, выход которого соединен с вторыми входами элементов И первой группыи счетным входом счетчика, выход ко -торого соединен с вторыми входамисхем сравнения группы, выход элемента И-НЕ соединен с входом первогоэлемента задержки, выход которого является выходом завершения работы устройства и подключен к входам обнуления счетчиков группы и счетчика, о тл и ч а ю щ е е с я тем, что, с целью сокращения времени обслуживаниязадач в вычислительной системе, вустройство введены блок выбора максимального числа, вторая группа триггеров, генератор импульсов, группа эле.ментов ИЛИ-НЕ, группа дешифраторов,четвертая группа элементов ИЛИ, причем вход-го регистра второй группы соединен с 1 -м входом третьейгруппы иНформационных входов устройства, выходы регистров второй группысоединены с соответствующими входамипервой группы входов блока выборамаксимального числа,-й выходгруппы выходов которого соединен свторым входом соответствующего элемента И третьей группы и нулевым вхо.дом-го триггера первой группы,единичные выходы триггеров первойгруппы соединены с вторыми входамисоответствующих элементов И второйгруппы, выходы которых подключены ксоответствующим входам второй группывходов блока выбора максимальногочисла, выход генератора импульсовподключен к третьим входам элементовИ второй группы и первому входу элеьюнта И выход которого соединен спервым запускающим входом блока выбора максимального числа и входом второго элемента задержки, выход которого соединен с вторым запускающим входом блока выбора максимального числа7 1233161 8и третьими входами элементов И тре- НЕ группы, выход-го ( 1 = 1, м - 1) тьей группы, выходы элементов И чет-элемента ИЛИ-НЕ группы соединен с ,вертой группы подключены к входам со- третьим входом 1 + 1 элемента И четответствующих элементов ИЛИ третьей вертай группы, входы дешифраторов группы, выходы которых соединены с 5 группы являются группой входов кода нулевыми входами соответствующих номера обслуженного задания устройсттриггеров второй группы, единичные ва, выходы дешифраторов соединены с выходы которых подключены к входам входами соответствующих элементов ИЛИ второго элемента ИЛИ, выход которого четвертой группы, выходы которых соссоединен с вторым входом элемента И, 10 динены с входами третьего элемента ИЛИ единичные входы триггеров второй груп- и нулевыми входами триггеров соогветпы соединены с информационными входа- ствующей строки матрицы формироватеми четвертой группы входов устройст- лей дуг, а выход третьего элемента ИЛИ ва, вторыми входами элементов И чет- соединен с вторым входом первого элевертой группы, входами элементов ИЛИмента ИЛИ.ЧЗ1233161 Составитель С. Назаро Техред С,Сопко Сирохм Коррек актор Н. Рогули одписно Заказ 2772/ да из с 5 а,Производственно-полиграфическое предприятие, г. Уж ул. Проектная ВНИИПИ по де 113035, Г 1 о