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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике, в частности к устройствам для распределения задач в вычислительном комплексе. Целью изобретения является сокращение среднего времени обслуживания заданий в вычислительном комплексе. Сокращение среднего времени обслуживания заданий в вычислительном комплексе и более равномерная загрузка процессоров комплекса достигается за счет распределения заданий по критерию максимального количества исходящих дуг. Устройство работает следукщим .образом. Первоначально в триггеры матрицы формирователей дуг по соответствукщим входам заносится информация о топологии графа (вершины которого соответствуют задачам, а ветви - информационно-управляющим связям между ними). В регистры заносятся коды номеров заданий и исходные данные длц их вьшолнения. Устройство работает В три этг. па, На первом этапе производится определение независимых заданий. На втором - выбор среди независимых заданий тех, которые, будучи представленными вершинами информационно-управляющего графа, имеют максимальное количество исходящих дуг. На третьем этапе производится распределение выб- ;ранных заданий по свободным процессорам вычислительного комплекса и корректировка информационно-управляющего графа, т.е. гашение триггеров тех строк матрицы формирователей дуг, которые Соответствуют обслуженным заданиям . 1 ил. ю 4 | ОЭ 00

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

„„SU„„1427381 А 1 (51) 4 С 06 F 15/20, 9/46

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н ABTOPCHOMV СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО.ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4215139/24-24 (22) 25.03,87 (46) 30,09 ° 88. Бюп. У 36 (72) С.В.Ефимов, В,В,Мазаник, М.М.Зарецкий и И.Н.Лучин (53) 681,325 (088,8) (56) Авторское свидетельство СССР

У 716043, кл. С 06 F 15/20, 1980.

Авторское -свидетельство СССР

У 1037267, кл. G 06 F 15/20, 1983. (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ

ЗАДАЧ В ВЫЧИСЛИТЕЛЬНОМ КОМПЛЕКСЕ (57) Изобретение относится к вычислительной технике, в частности к устройствам для распределения задач в вычислительном комплексе. Целью изобретения является сокращение среднего времени обслуживания заданий в вычислительном комплексе. Сокращение среднего времени обслуживания заданий в вычислительном комплексе и более равномерная загрузка процессоров комплекса достигается за счет распределения заданий по критерию максимального количества исходящих дуг. Устройство работает следующим образом.

Первоначально в триггеры матрицы формирователей дуг по соответствующим входам заносится информация о топологии графа (вершины которого соответствуют задачам, а ветви — информационно-управляющим связям между ними).

В регистры заносятся коды номеров заданий и исходные данные для.их выполнения. Устройство работает в три этапа, На первом этапе производится оп. ределение независимых заданий. На втором — выбор среди независимых заданий тех, которые, будучи представленными вершинами информационно-управляющего графа, имеют максимальное количество исходящих дуг, На третьем этапе производится распределение выбранных заданий по свободным процессорам вычислительного комплекса и корректировка информационно-управляющего графа, т.е. гашение триггеров тех строк матрицы формирователей дуг, которые соответствуют обслуженным заданиям, 1 ил.

1427381

Изобретение относится к области вычислительной техники, в частности к устройствам управления вычислительными комплексами.

Пелью изобретения является сокращение среднего времени обслуживания заданий в вычислительном комплексе.

На чертеже приведен пример реализации устройства. 10

Устройство содержит матрицу 1 размером N N (N — число задач) из триг- геров 2, третью группу блоков элементов И 3, rpynny блоков 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 синхронизации устройства.

Устройство работает следующим образом.

В исходном состоянии триггеры 2, 11 обнулены. Первоначально в триггеры 2 по входам 24 заносится информа- 45 ция о топологии графа (вершины которого соответствуют задачам, а ветви— информационно-управляющим связям между ними) ° Номер триггера, установленного в единичное состояние, определяется пересечением строки с номером, равным номеру начальной вершины ветви, и столбца с номером, равным номеру ее конечной вершины. В соответствующий регистр 16 по входу 25 заносится код номера задания и исходные данные для его выполнения.

В работе устройства можно выделить три этапа.

На первом производится определение независимых заданий. На выходах соответствующих элементов ИЛИ-НЕ 9

s столбцах, которые соответствуют начальным вершинам информационно-управляющего графа, появятся высокие потенциалы, так как начальные вершины не содержат входящих ветвей и триггеры 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 1ð тех строк, номера которых соответствуют кодам номеров задач, обслуженных процессорами. Выбранный блок элемен- тов И 17 пропускает на вход блока элементов ИЛИ 18 код номера задания и исходных данных с выхода соответствующего регистра 16. По входам 28 устройства подаются сигналы готовности от процессоров комплекса на входы первого блока 7 преобразования кода, который выбирает среди них младший и оповещает его по соответствующему выходу 30 готовности устрой» ства о том, что ему предстоит обслужить очередное задание. Сигнал с выхода элемента 14 задержки, необходимой для учета времени срабатывания устройства, в совокупности с сигналом с соответствующего выхода первого блока 7 преобразования кода открыва30 ет блок элементов И 22 и пропускает на его выход, т.е. на вход младшего свободного процессора в комплексе, код номера выбранного задания и исходные данные для его выполнения.

Момент выдачи определяется сигналом 35 на синхровыходе 32 устройства. В том случае, если еще остались независимые задания (сигнал на выходе элемента

ИЛИ 15 имеет единичное значение) и в комплексе остались свободные про- 40 цессоры, сигнал на выходе элемента

ИЛИ 23 имеет единичное- значение, устройство будет запущено вновь сигналом с выхода элемента И 13. При окончании обработки одного из заданий 45 поступит сигнал по соответствующему, входу 27 установки в ноль устройства, который установит в нулевое состояние триггеры соответствующей строки матрицы 1 и, пройдя через элемент 50

ИЛИ 12, при наличии независимых заданий и свободных процессоров вновь запустит устройство. Окончание обслуживания всех заданий сигнализируется нулевым значением на выходе 29 устройства.

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

Формула и з о б р е т е н и я

Устройство для распределения задач в вычислительном комплексе, содержащее матрицу N„N триггеров (где

N — число задач), первую и вторую группы блоков элементов И, группу элементов ИЛИ-HE первую группу элементов И, группу триггеров, первый, второй и третий элементы ИЛИ, элемент

И, элемент задержки, группу регистров, блок элементов ИЛИ, причем P-й информационный вход устройства подключен к выходам установки в " 1" триггеров Р-й строки матрицы триггеров (Р=1,М где N -число задач), К-й вход (К=1,N) номера задачи устройства соединен с информационньм входом

P-го регистра группы, вход запуска устройства соединен с первым входом первого элемента ИЛИ и входами установки в "0" триггеров группы, К- и вход сброса устройства соединен с входами установки в "0" триггеров %-й строки матрицы, выход КР-гс триггера матрицы подключен к К-му входу Р-го эле мента ИЛИ-НЕ группы, выход.rrepacro элемента ИЛИ соединен с первым входом элемента И, выходы элементов БЛИНЕ группы подключены к входу второго элемента ИЛИ, первым входам элементов И первой группы, выходы которых соединены с входами установки в " 1" триггеров группы и с вторыми входами ,блоков элементов И первой гру пы, выход M-го разряда P-ro регистра группы соединен с P-м входом М-го блока элементов И второй группы, выходы триггеров группы соединены с (N+1)-ми входами элементов ИЛИ-HE группы, выход второго элемечта ИЛИ соединен с выходом конца работы устройства и с вторым входом элемента

И, выход которого через элемент задержки соединен с (N+2) ì входом первого элемента ИЛ1, с первыми входами блоков элементов И второй группы и с синхровыходом устройства, выходы блока элементов ИЛИ соединены с вторыми входами элементов И третьей группы, выходы которых соединены с информационным выходом устройства, выход третьего элемента ИЛИ соединен с третьим входом элемента И, о т л и5 14 ч а ю щ е е с я тем, что, с целью сокращения среднего времени обслуживания зацаний в вычислительном комплексе, в него введены третья группа блоков эпементов И, группа блоков контроля данных, группы блоков преобразования кодов, вторая группа элементов И, первый и второй блоки преобразования кодов, группы шифраторов, матрица элементов сравнения, причем вход готовности устройства подключен к входу второго преобразователя кодов, выход которого соединен с выходом готовности устройства, третьими входами блоков элементов И второй группы и с входом третьего элемента

ИЛИ, выход КР-го элемента матрицы триггеров соединен с первым входом

Р-ro элемента И К-го блока третьей группы, выход которого соединен с

Р-м входом К-го блока контрол:". данных группы, выход первого элемента ИЛИ соединен с вторыми входами блоков

2?381 элементов И третьей группы, выходы элементов ИЛИ-HE группы соединены с третьими входами блоков элементов И третьей группы, К-й выход P-r o блока контроля данных группы соединен с

К-м входом P-ro блока преобразователя кодов группы, К-й выход которого подключен к К-му входу P-го шифратора группы, r-й (r=1,R, где R

=intflog NJ), выход которого подключен к первым входам r-го разряда

PK-х (Р-1,N-1, К вЂ” Р+1,N) и к вторым входам r-ro разряда КР-х элементов сравнения матрицы, выход признака

"Больше" PK-го элемента сравнения матрицы соединен с (K-1)-м входом, а выход признака "Меньше" — с К-м входом P-го элемента И второй группЫ, выход которого подключен к P-му вхоО ду первого блока преобразования кодов группы, выход которого соединен с вторыми входами элементов И первой группы.

Э

ВНИИПИ Заказ 4854/46 Тираж ?04 Подписное

Произв.-полигр. пр-тие, r. Ужгород, ул. Проектная, 4