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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 9) 15/20, 9/ 51) 4 ЕТЕН У 36Мазаник,чин льство СС 5/20, 198 ство СССР 15/20, 19 ПРЕДЕЛЕНИЯКОМПЛЕКСЕ Ь Ь ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИ ИСАНИЕ ИЗОВТОРСИОМУ СВИДЕТЕ(46) 30,0988, Бюп, (72) С.В.Ефимов, В,В М.М,Зарецкий и И.Н.Л (53) 681,325 (088,8) (56) Авторское свиде р 716043, кл. С 06 РАвторское свидетел У 1037267, кл. С 06 (54) УСТРОЙСТВО ДЛЯ ЗАДАЧ В ВЫЧИСЛИТЕЛЬН(57) Изобретение относится к вычислительной технике, в частности к устройствам для распределения задач в вычислительном комплексе. Целью изобретения является сокращение среднего времени обслуживания заданий в вычислительном комплексе. Сокращение сред, него времени обслуживания заданий в вычислительном комплексе и более равномерная загрузка процессоров комплекса достигается за счет распределения заданий по критерию максималь 1427381 А 1 ного количества исходящих дуг. Устройство работает следующим .образом.Первоначально в триггеры матрицы формирователей дуг по соответствующимвходам заносится информация о топологии графа (вершины которого соответствуют задачам, а ветви - информационно-управляющим связям между ними).В регистры заносятся коды номеров заданий и исходные данные для.их выполнения. Устройство работает в три зтапа, На первом зтапе производится определение независимых заданий. Навтором - выбор среди независимых заданий тех, которые, будучи представленными вершинами информационно-упревляющего графа, имеют максимальноеколичество исходящих дуг, На третьемэтеле производится рвспределение ввлранных заданий по свободным процессо- .рам вычислительного комплекса и корректировка информационно-управляющего графа, т.е. гашение триггеров техстрок матрицы формирователей дуг, которые соответствуют обслуженным заданиям. 1 ил.Изобретение относится к области вычислительной техники, в частности к устройствам управления вычислитель" ными комплексами.Целью изобретения является сокращение среднего времени обслуживания заданий в вычислительном комплексе.На чертеже приведен пример реали- зации устройства. 10Устройство содержит матрицу 1 размером М И (М - число задач) из триг- геров 2, третью группу блоков элементов И 3, группу блоков 4 контроля данных, содержащих матрицы элементов И 5, ИЛИ 6, группу блоков 7 преобразования кодов, содержащих блок элементов И(И-НЕ) 8, блок элементов ИЛИ-НЕ 9, первую группу элементов И 10, группу триггеров 11, первый элемент ИЛИ 12, элемент И 13, элемент 14 задержки, второй элемент ИЛИ 15, группу регистров 16, первую группу блоков элементов 17 И блок элементов ИЛИ 18, группу шифраторов 19, матрицу элементов 20 сравнения, вторую группу элементов И 21, вторую группу блоков элементов И 22, третий элемент ИЛИ 23, группу входов установки в единицу устройства 24, группу входов 25 номера задачи устройства вход 26 запуска устройства, группу входов 27 установки в ноль устройства, входы 28 готовности, устройства, выход 29 конца работы устройства, сигнальный выход 30 готовности устройства, группу информационных выходов 31 устройства, выход 32 синхронизации устройства. 40Устройство работаетследующим образом.В исходном состоянии триггеры 2, 11 обнулены. Первоначально в триггеры 2 по входам 24 заносится информа ция о топологии графа (вершины которого соответствуют задачам, а ветви - информационно-управляющим связям между ними)Номер триггера, установленного в единичное состояние, определяется пересечением строки с номером, равным номеру начальной вершины ветви, и столбца с номером, равным номеру ее конечной вершины. В соответствующий регистр 16 по входу 25 заносится код номера задания и исходные данные для его выполнения.В работе устройства можно выделить три этапа. На первом производится определение независимых заданий, На выходах соответствующих элементов ИЛИ-НЕ 9 в столбцах, которые соответствуют начальным вершинам информационно-управляющего графа, появятся высокие потенциалы, так как начальные вершины не содержат входящих ветвей и триггеры 2 в этих столбцах находятся в нулевом состоянии, Импульс запуска по входу 26 устройства устанавливает в нулевое состояние триггеры 11 и, пройдя через элемент ИЛИ 12, откроет элементы И 3, которые пропустят на выход значения сигналов на выходах триггеров 2 в тех строках матрицы 1, которые соответствуют независимыма заданиям, сто обеспечивается подачей .сигналов с выходов соответствующих элементов ИЛИ-НЕ 9 на входы элементов И 3. На втором этапе производится выбор среди независимых заданий тех, которые, будучи представленными в графе, имеют максимальное количество исходящих дуг. Количество исходящих дуг иэ вершины указывает количество триггеров 2, установленных в единичное состояние, в соответствующей этдй вершине строке. Таким образом, коды количества исходящих дуг из вершин, соответствующих независимым заданиям, поступают на блоки 4 контроля данных, где они с помощью матриц элементов И 5, ИЛИ 6 образуются в коды, где нулевые значения отделены от единичных, затем на группу блоков 7 преоб" разования кодов, где с помощью элементов И(ИЛИ-НЕ) 8 эти коды преобразуются в унитарные коды количества исходящих дуг, которые далее поступают на соответствующие шифраторы 19. где унитарные коды преобразуются в двоичные. Двоичные коды количества исходящих дуг подаются на матрицу элементов 20 сравнения, На выходе элементов И 21 появляются единичные сигналы и том случае, если в соответствующих вершинах графа количество исходящих дуг максимально. Второй блок 7 преобразования кода выбирает среди единичных сигналов с выходов, элементов И 21 один, который вырабатывается на элементе И 21 с младшим номером, и подаст его на вход соответствующего элемента И 10, сигнал с выхода которого откроет соответству381 3 1427ющий блок элементов И 17 и установитв единичное состояние триггер 11,На третьем этапе обеспечиваетсяраспределение независимых выбранныхзаданий по свободным процессорам, выдача процессорам вычислительногокомплекса исходных данных для обслуживания заданий и установка в нулевое состояние триггеров 2 матрицы 1 10тех строк, номера которых соответствуют кодам номеров задач, обслуженных процессорами. Выбранный блок элемен-тов И 17 пропускает на вход блокаэлементов ИЛИ 18 код номера задания 15и исходных данных с выхода соответствующего регистра 16. По входам 28устройства подаются сигналы готовности от процессоров комплекса на входы первого блока 7 преобразованиякода, который выбирает среди нихмладший и оповещает его по соответствующему выходу 30 готовности устройства о том, что ему предстоит обслужить очередное задание. Сигнал свыхода элемента 14 задержки, необходимой для учета времени срабатыванияустройства, в совокупности с сигналомс соответствующего выхода первогоблока 7 преобразования кода открыва 30ет блок элементов И 22 и пропускает на его выход, т.е. на вход младшего свободного процессора в комплексе, код номера выбранного задания и исходные данные для его выполнения. Момент выдачи определяется сигналом 35 на синхровыходе 32 устройства. В том случае, если еще остались независимые задания (сигнал на выходе элемента ИЛИ 15 имеет единичное значение) и в комплексе остались свободные про цессоры, сигнал на выходе элемента ИЛИ 23 имеет единичное значение, устройство будет запущено вновь сигналом с выхода элемента И 13. При окончании обработки одного из заданий 45 поступит сигнал по соответствующему , входу 27 установки в ноль устройства, который установит в нулевое состояние триггеры соответствующей строки матрицы 1 и, пройдя через элемент 50 ИЛИ 12, при наличии независимых заданий и свободных процессоров вновь запустит устройство, Окончание обслуживания всех заданий сигнализируется нулевым значением на выходе 29 уст ройства.Таким образом, устройство выбирает задачи и распределяет их для решения между процессорами вычислительного комплекса таким образом, чтопроцессоры работают без простоев,Формула изобретения Устройство для распределения задач в вычислительном комплексе, содержащее матрицу ИИ триггеров (где И - число задач), первую и вторую группы блоков элементов И, группу элементов ИЛИ-НЕ, первую группу элементов И, группу триггеров, первый, второй и третий элементы ИЛИ, элемент И, элемент задержки, группу регистров, блок элементов ИЛИ, причем Р-й информационный вход устройства подключен к выходам установки в " 1" триггеров Р-й строки матрицы триггеров (Р=1,М где И -число задач), К-й вход (К=1,И) номера задачи устройства соединен с информационньм входом Р-го регистра группы, вход запуска устройства соединен с первым входом первого элемента ИЛИ и входами установки в "О" триггеров группы, К-й вход сброса устройства соединен с входами установки в "О" триггеров %-й строки матрицы, выход КР-гс триггера матрицы подключен к К-му входу Р-го эле мента ИЛИ-НЕ группы, выход. первого элемента ИЛИ соединен с первым входом элемента И, выходы элементов БЛИНЕ группы подключены к входу второго элемента ИЛИ, первым входам элементов И первой группы, выходы которых соединены с входами установки в " 1" триггеров группы и с вторыми входами ,блоков элементов И первой гру,.пы, выход М-го разряда Р-го регистра группы соединен с Р-м входом М-го блока элементов И второй группы, выходы триггеров группы соединены с (0+1)-ми входами элементов ИЛИ-НЕ группы, выход второго элемечта ИЛИ соединен с выходом конца работы устройства и с вторым входом элемента И, выход которого через элемент задержки соединен с (И+2)-м входом первого элемента ИХЯ, с первыми входами блоков элементов И второй группы и с синхровыходом устройства, вы" ходы блока элементов ИЛИ соединены с вторыми входами элементов И третьей группы, выходы которых соединены с информационным выходом устройства, выход третьего элемента ИЛИ соединен с третьим входом элемента И, о т л и"2381 ЭЗаказ 4854/46 Тираж 04 Подписи НИИПИ Произв,-п пр-тие 5 14 ч а ю щ е е с я тем, что, с целью сокращения среднего времени обслуживания зацаний в вычислительном комплексе, в него введены третья группа блоков эпементов И, группа блоков контроля данных, группы блоков преобразования кодов, вторая группа элементов И, первый и второй блоки преобразования кодов, группы шифраторов, матрица элементов сравнения, причем вход готовности устройства подключен к входу второго преобразователя кодов, выход которого соединен с выходом готовности устройства, третьими входами блоков элементов И второй группы и с входом третьего элемента ИЛИ, выход КР-го элемента матрицы триггеров соединен с первым входом Р-го элемента И К-го блока третьей группы, выход которого соединен с Р-м входом К-го блока контрол.". данных группы, выход первого элемента ИЛИ соединен с вторыми входами блоков элементов И третьей группы, выходы элементов ИЛИ-НЕ группы соединены с третьими входами блоков элементов И третьей группы, К-й выход Р-го блока контроля данных группы соединен с К-м входом Р-го блока преобразователя кодов группы, К-й выход которого подключен к К-му входу Р-го шифратора группы, г-й (г=1,К, где К =п 1 о И), выход которого подключен к первым входам г-го разряда РК-х Р,0-1, К-Р+1,В) и к вторым входам г-го разряда КР-х элементов сравнения матрицы, выход признака "Больше" РК-го элемента сравнения матрицы соединен с (К)-м входом, а выход признака "Меньше" - с К-м входом Р-го элемента И второй группЫ, выход которого подключен к Р-му входу первого блока преобразования кодов группы, выход которого соединен с вторыми входами элементов И первой группы. Ужгород, ул. Проектная, 4