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

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

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

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

Устройство содержит матрицу 1 размером N N (N - число задач) из триггеров 2, третью группу блоков элементов ИЗ, группу блоков 4 контроля данных, содержащих матрицы элементов И 5, ИЛИ 6, группу блоков 7 преобразования кодов, содержащих блок элементов И(И-НЕ) 8, блок элементов ИПИ-НЕ 9, первую группу элементов И 10, группу триггеров 11, первьй эле- мент ИЛИ 12J элемент И 13, элемент 14 задержки, второй элемент ИЛИ- 15, ;группу регистров 16, первую группу блоков элементов 17 И, блок элементов ИЛИ 18, группу шифраторов 19, матрицу элементов 20 сравнения, вторую группу элементов И 21, вторую группу блоков элементов И 22, третий элемент ИЛИ 23, группу входов установки в единицу устройства 24, груп- пу входов 25 номера задачи устройства, вход 26 запуска устройства, группу входов 27 установки в ноль устройства, входы 28 готовности, устройства выход 29 конца работы устройства, сигнальнью выход 30 готовности уст- ройства, группу информационных выходов 31 устройства, выход 32 синхронизации устройства.

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

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

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

На первом производится определение независимых заданий. На выходах соответствующих элементов ИЛИ-НЕ 9 в столбцах, которые соответствуют начальным вершинам информационно-управляющего графа, появятся высокие потенциалы, так как начальные вершины не содержат входящих ветвей и триггеры 2 в этих столбцах находятся в нулевом состоянии. Импульс запуска по входу 26 устройства устанавливает в нулевое состояние триггеры 11 и, пройдя через элемент ИЛИ 12, откроет элементы ИЗ, которые пропустят на выход значения сигналов на выходах триггеров 2 в тех строках матрицы 1, которые соответствуют независимым заданиям, сто обеспечивается подачей .сигналов с выходов соответствующих элементов ИЛИ-НЕ 9 на входы элемен- 03 из.

На втором этапе производится выбор среди независимых заданий тех, которые, будучи представленными в графе, имеют максимальное количество исходящргх дуг. Количество исходящих дуг иг вершины указывает количество триггег-ов 2, установленных в единичное состояние, в соответствующей этд вершине строке. Таким образом, коды количества исходящих дуг из вершин, соответствующих независимым заданиям поступают на блоки 4 контроля данных где они с помощью матриц элементов И 5, ИЛИ 6 образуются в коды, где нулевые значения отделены от единичных, затем на группу блоков 7 преобразования кодов, где с помощью элементов И(ИЛИ-НЕ)| 8 эти коды преобразуются в унитарные коды количества исходящих дуг, которые далее поступают на соответствующие шифраторы 19,- где унитарные коды преобразуются в двоичные. Двоичные коды количества исходящих дуг подаются на матрицу элементов 20 сравнения. На выходе элементов И 21 появляются единичные сигналы в том случае, если в соответ- ствзпощих вершинах графа количество исходящих дуг максимально. Второй блок 7 преобразования кода выбирает среди единичных сигналов с выходов, элементов И 21 один, которьй вырабатывается на элементе И 21 с младшим номером, и подаст его на вход соответствующего элемента И 10, сигнал с. выхода которого откроет соответству

3

ющий блок элементов И 17 и установи в единичное состояние триггер 11,

На третьем этапе обеспечивается распределение независимых выбранных заданий по свободным процессорам, выдача процессорам вычислительного комплекса исходных данных для обслуживания заданий и установка в нулевое состояние триггеров 2 матрицы 1 тех строк, номера которых соответствуют кодам номеров задач ,обслуженных процессорами. Выбранный блок элементов И 17 пропускает на вход блока элементов ИЛИ 18 код номера задания и исходных данных с выхода соответствующего регистра 16. По входам 28 устройства подаются сигналы готовности от процессоров комплекса на входы первого блока 7 преобразования кода, которьй выбирает среди них младший и оповещает его по соответствующему выходу 30 готовности устрой

ства о том, что ему предстоит обслужить очередное задание. Сигнал с выхода элемента 14 задержки, необходимой для учета времени срабатывания устройства, в совокупности с сигналом с соответствующего выхода первого блока 7 преобразования кода открывает блок элементов И 22 и пропускает на его выход, т.е. на вход младшего свободного процессора в комплексе, код номера выбранного задания и исходные данные для его выполнения. Момент вцдачи определяется сигналом на синхровыходе 32 устройства. В том случае, если еще остались независимые задания (сигнал на выходе элемента ИЛИ 15 имеет единичное значение) и в комплексе остались свободные процессоры, сигнал на выходе элемента ИЛИ 23 имеет единичное- значение, устройство будет запущено вновь сигналом с вькода элемента И 13. При окончании обработки одного из заданий поступит сигнал по соответствующему входу 27 установки в ноль устройства которьй установит в нулевое состояние триггеры соответствующей строки матрицы 1 и, пройдя через элемент ИЛИ 12, при наличии независимых заданий и свободных процессоров вновь запустит устройство. Окончание обслуживания всех заданий сигнализируется нулевым значением на выходе 29 устройства.

Таким образом, устройство выбирает задачи и распределяет их для ре

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

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

Устройство для распределения задач в вычислительном комплексе, содержащее матрицу триггеров (где N - число задач), первую и вторую группы блоков элементов И, группу элементов ИЛИ-НЕ, первую группу элементов И, группу триггеров, первый.

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

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

матрицы, выход КР-го триггера матрицы подключен к К-му входу Р-го эле мента ИЛИ-НЕ группы, выход.первого элемента ИЛИ соединен с первым входом элемента И, выходы элементов ИЛИ- НЕ группы подключены к входу второго

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

выход М-го разряда Р-го регистра группы соединен с Р-м входом М-го блока элементов И второй группы, выходы триггеров группы соединены с (К+1)-ми входами элементов liFM-HE

группы, выход второго элемента ИЛИ соединен с выходом конца работы устройства и с вторьм входом элемента И, выход которого через элемент задержки соединен с (N+2)-M входом первого элемента ИЛИ, с первыми входами блоков элементов И второй группы и с синхровыходом устройстваJ выходы блока элементов ИЛИ соединены с вторыми входами элементов И третьей

группы, выходы которых соединены с информационным выходом устройства, выход третьего элемента ИЖ соединен с третьим входом элемента И, о т л иfjg

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

ВНИИПИ Заказ 4854/46 Тираж 704

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

Подписное