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

 

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

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

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

РЕСПУБЛИН

А1

„„SU„,1233161 (51) 4 G 06 F 15/20, 9/00

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

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

К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 3803200/24-24 (22) 16.10.84 (46) 23.05.86. Бюл. № 19 (72) В.В. Мазаник, В.М. Неффа и С.В. Ефимов (53) 681.333(088.8) (56) Авторское свидетельство СССР

¹ 716043, кл. G 06 F 15/20, 1980.

Авторское свидетельство СССР № 1037267, кл. G 06 F 15/20, 1983. (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ

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

3161

4 123

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

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

На фиг. 1 представлена структурная схема устройства; на фиг. 2 структурная схема блока для выбора максимальногA числа.

Предлагаемое устройство содержит матрицу 1 (размером И х М ) формирователей дуг, первый элемент ИЛИ 2, блок 3 выбора максимального числа, триггеры 4, первую rpynny элементов

ИЛИ 5, первую группу элементов И б, группу счетчиков 7„ счетчик 8, группу схем 9 сравнения, первую группу триггеров 10, вторую группу элементов И 11, первую и вторую группы регистров 12 и 13, третью группу элементов И 14, вторую группу элементов

ИЛИ 15, вторую группу триггеров 16, второй элемент ИЛИ 17, элемент И 18, генератор !9 импульсов, третью груп— пу элементов ИЛИ 20, четвертую группу элементов И 21, группу элементов

ИЛИ-НЕ 22, группу дешифраторов 23, четвертую группу элементов ИЛИ 24, третий элемент ИЛИ 25, элемент

ИЛИ-НЕ 26, первый и второй элементы

27 и 28 задержки, группу блоков поразрядных узлов 29 анализа, третью, четвертую и пятую группы элементов

И 30 — 32, пятую и шестую группы элементов ИЛИ 33 и 34, третью группу триггеров 35, группу элементов И-НЕ 36 седьмую группу элементов ИЛИ 37,, третью группу регистров 38, третью группу элементов И 39, первую, вторую, третью, четвертую и пятую группы входов 40 — 44, вход 45 выход 46, группу выходов 47 7устройства, первую группу входов 48, первый вход 49, вторую группу входов 50, второй вход

51 и группу выходов 52 блока 3 выбора максимального числа.

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

В исходном состоянии триггеры 4 и 10, счетчики 7 и 8 обнулены.

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

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

В соответствующий регистр 13 по входу 42 „--аносится код номера задания и исхсдные для его выполнения. В

-и регистр 12 (j =1,1×,, где М вЂ” количество заданий) по входам 41 заносится код времени выполнения (длительности) -го задания. В общем случае коды времен выполнения заданий отличаются друг от друга.

В работе JjcTpaAcTBB можно выдепить три этапа.

На. первом этапе производится оп—

2О ределение независимых заданий (планирование обработки заданий). При этом на выходе элементов ИЛИ 5 в столбцах, соответствующих начальным .вершинам информационно-управляющего графа, появляются низкие потенциалы, так как начальные вершины не содержат входящих дуг и триггеры 4 в этих толбцах находятся в нулевом состоянии, импульс запуска по вхоцу 45 че— 0 рев элемент ИЛИ 2 поступает на вторые входы всех элементов И 6 и счетный вход счетчика 8. Импульс запуска устанавливает в единичное состояние все триггерь1 10. При этом импульс запуска не проходит через элементы И 6 на

35 счетчики 7 тех столбцов матрицы 1, все триггеры 4 которых находятся в нулевом состоянии. Кроме того, импульс запуска устанавливает в единич4О ное состояние все триггеры 10. В динамике функционирования устройства

J -й триггер устаиавливается в нулевое состояние после назначения J -го задания на процессор.

Далее содержимое каждого счетчик ка 7 поступает на первый вход соответствующего элемента 9 сравнения, а на другой .вход этого элемента — информация со счетчика 8. При несовпадении показаний счетчиков 7 и 8 эле мент 9 сравнения вырабать,вает сигнал, который поступает на второй вход соответ=твуюцего элемента И 11. На выходе, -го элемента И 11 появляется единичный сигнал только в том случае, если -и триггер 10 находится в единичном состоянии, а на выходе j -го элемента 9 сравнения — также единичный с:игнал, 1233161

На втором этапе работы устройства производится выбор из числа независимых заданий задания с максимальной длительностью выполнения. Производится это следующим образом. В исходном состоянии в триггеры регм.тров 38 блока 3 выбора максимального числа записаны коды времени выполнения заданий (из регистров 12 они поступают по входам 50 блока 3). Совокупность 1О сравниваемых чисел задается путем установки в единичное состояние триггеров 36 блока 3 для выбора максимального числа сигналами с выходов соответствующих элементов И 11 по входам 48 блока 3 выбора максимального числа. Запуск блока 3 выбора максимального числа по входу 51 обеспечивается импульсом с генератора 19 импульсов через элемент И 18 при ус- 2о ловии, что хотя бы один процессор вычислительной системы свободен (при наличии сигнала на входах 43 устройства, устанавливающего 1 -й триггер

16 в единичное состояние, †1,, д где — число процессоров вычислительной системы, в соответствии с чем на выходе элемента ИЛИ 17 находится единичный сигнал). При этом обеспечивается поразрядный анализ сравниваемых чисел следующим образом.

Если в первом разряде чисел имеется и О и 1, то через элементы И 30 и 31 узлов 29,„ анализа на группу элементов ИЛИ 33 и 37 поступают единич35 ные сигналы. На выходе элемента И-НЕ

36 сформируется нулевой сигнал, который закрывается элементом И 39; . Через элементы И 32 узлов анализа и элементы ИЛИ 34, относящихся к тем

40 регистрам, в первом разряде которых записан О, единичный сигнал поступает на входы установки в нулевое состояние соответствующих триггеров 35.

Элементы И 30 и 31 соответствующих узлов анализа закрываются, и единич45 ный сигнал находится только на выходе элемента ИЛИ 37. На выходе элемента

И-НЕ формируется единичный сигнал, по которомуоткрывается элементИ 39.Далее производится анализ следующего разряда оставшихся сравниваемых чисел.

Если же в первом разряде сравниваемых чисел только нулевые коды или только единичные, то на выходе элемента И-НЕ 36 находится единичный сигнал, который открывает элемент

И 39. Следовательно, в этом случае сразу производится анализ второго или последующих разрядов. После того, как все разряды сравниваемых чисел проанализированы, на выходе элемента

И 39 формируется единичный уровень.

При этом на выходах 52 блока 3 выбора максимального числа содержится унитарный код j номера задания с максимальной длительностью выполнения из числа заданных (унитарный код

00100 указывает, что выбран третий номер задания).

Единичный сигнал на К-м выбранном выходе 52 блока 3 выбора максимального числа разрешает прохождение кода номера К-го задания и его исходных данных иэ К-ro регистра 13 через К-й блок элементов И 14, блок элементов

ИЛИ 15 на первые входы блоков элементов И 21. Кроме того, сигнал с К-го выхода 52 блока 3 выбора максимального числа устанавливает в нулевое состояние К-й триггер 10, чем исключается из дальнейшего анализа К-е задание.

На третьем этапе работы устройства обеспечивается назначение выбранного задания на свободный процессор вычислительной системы и коррекция матрицы информационно управляющего графа, т.е. установка в нулевое состояние триггеров 4 матрицы 1 тех строк, номера которых соответствуют кодам номеров задания, обслуженных процессорами. Сигналы готовности процессоров по входам 43 устройства устанавливают в единичное состояние соответствующие триггеры 16 и разрешают прохождение кода номера К выбранного задания с максимальной длительностью через блок элементов И 21, соответствующий свободному процессору с минимальным номером. Это обеспечивается блоком элементов ИЛИ-НЕ 22, в котором

j --й вход 43 устройства соединен с входами (1 + 1, )-ых элементов

ИЛИ-НЕ. Таким образом, сигнал на 1 -м

"младшем" входе 43 устройства запрещает прохождение информации через блоки элементов И 21 с большими номерами. Код номера К задания и исходные данные для его выполнения поступают на группу выходов 47 устройства. Кроме того, на выходе t -го элемента

ИЛИ 20 появляется единичный сигнал, который устанавливает в нулевое состояние i -й триггер 16, чем показывает занятость -го процессора вычислительной системы.

12331Ь 1

По окончании обслуживания К-го задания <-м процессором на -м входе готовности 43 устройства появляется единичный сигнал, на группе входов

44 — код номера К обслуженного задания. Код К дешифруется дешифратором

23, через К-й элемент ИЛИ 24 обнуляет триггеры 4 К-й строки матрицы 1 и через элемент ИЛИ 25 поступает на вход элемента ИЛИ 2, выполняя затем функции импульса запуска, и начинается повторное выполнение первого этапа работы устройства.

При обнулении всех триггеров 4 матрицы 1 на выходах всех элементов

ИЛИ 5 находятся нулевые сигналы, а на выходе элемента ИЛИ-НЕ 26 — единичный сигнал. Этот сигнал через элемент 27 задержки обнуляет счетчики

7 и 8 и поступает на выход 4б устройства. На этом работа устройства заканчивается.

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

Устройство для распределения задач в вычислительной системе, содержащее матрицу формирователей дуг из N N триггеров (N — число реализуемых задач), первый, второй и третий элементы ИЛИ, первую группу триггеров, первую и вторую группы регистров, первую, вторую, третью и четвертую группы элементов И, первую, вторую и третью

35 группы элементов ИЛИ, элемент И, элемент ИЛИ-НЕ, первый и второй элементы задержки, группу счетчиков, счетчик, группу схем сравнения, с -й вход (с, = 1, 1 ) первой группы информационных входов устройства соединен с единичным входом с j -го триггера матрицы формирователей дуг, единичные выходы триггеров j --го столбца матрицы формирователей дуг подклю45 чены к входам j --ro элемента ИЛИ первой группы, выходы элементов ИЛИ первой группы соединены с входами элемента ИЛИ-НЕ и первыми входами со- ответствующих элементов И первой

50 группы, выходы которых подключены к счетным входам соответствующих счетчиков групп, выходы которых соединены с первыми входами соответствующих схем сравнения группы, выходы схем сравнения группы соединены с первыми входами соответствующих элементов И второй группы, j -й вход второй группы информационных входов устройства соединен с информационным входом J -го регистра первой группы, выходы регистров первой группы соединены с первыми входами соответствующих элементов И третьей группы, выходы которых соединены с входами элементов ИЛИ второй группы, выходы которых подключены к первым входам элементов И четвертой группы, выходы которых соединены с группой информационных выходов устройства, запускающий вход устройства подключен к единичным входам триггеров первой группы и первому входу первого элемента

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

И второй группы и первому входу элеьюнта И,, выход которого соединен с первым запускающим входом блока выбора максимального числа и входом второго элемента задержки, выход которого соединен с вторым запускающим входом блока выбора максимального числа

7 1233161 8 и третьими входами элементов И тре- НЕ группы, выход i --го (i = 1, N — I) тьей группы, выхоцы элементов И чет- элемента ИЛИ-НЕ группы соединен с .вертой группы подключены к входам со- третьим входом i + 1 элемента И четответствующих элементов ИЛИ третьей вертай группы, входы дешифраторов гРУппы, выходы котоРых соединены с 5 группы являются группой входов коца нулевыми входами соответствующих номера обслуженного задания устройст— триггеров второй группы, единичные ва, выходы дешифраторов соединены с выхоцы которых подключены к входам входами соответствующих элементов ИЛИ второго элемента ИЛИ, выход которого четвертой группы, выходы которых соесоединен с вторым входом элемента И, 1О динены с входами третьего элемента ИЛИ единичные входы триггеров второй груп- и нулевыми входами триггеров соогветпы соединены с информационными входа- ствующей строки матрицы формироватеми четвертой группы входов устройст- лей дуг, а выход третьего элемента ИЛИ ва, вторыми входами элементов И чет- соединен с вторым входом первого элевертой группы, входами элементов ИЛИ-15 мента ИЛИ.

ЧЗ

1233161

4be,, ?

Составитель С. Назаров

Техред G.| oïêñ Корректор Е. Сирохман

Редактор Н. Рогулич

Подписное

Заказ 2772/51 Тираж 671

ВНИИПИ Государственного комитета СССР по делам изоб.ретений и открытий

113035, Москва, Ж-35, Раушская. наб., д. 4 5

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