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

1

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

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

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

Предлагаемое устройство содержит матрицу 1 (размером N N ) формирователей дуг, первый элемент ШШ 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 - 32, пятую и шестую группы элементов ИЛИ 33 и 34, третью группу триггеров 35, группу элементов И-НЕ 3 седьмую группу элементов 1-1ПИ 37,, третью группу регистров 38, третью группу элементов И 39, первую, вторую, третью, четвертую и пятую группы входов 40 - 44, вход 45, выход 46, группу выходов 47 устройства, первую группу входов 48, первый вход 49, вторую группу входов 50, второй вход 51 и группу выходов 52 блока 3 выбора максимального числа.

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

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

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

S

0

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

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

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

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

задания на процессор.

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

5

0

5

. 31

На втором этапе работы устройства производится выбор из числа независимых заданий задания с максимальной длительностью выполнения. Производится это следующим образом. В исходном состоянии в триггеры реги-стров 38 блока 3 выбора максимального числа записаны коды времени вьшолнения заданий (из регистров 12 они поступают по входам 50 блока 3). Совокупность сравниваемых чисел задается путем установки в единичное состолние триггеров 36 блока 3 для выбора максимального числа сигналами с выходов соответствующих элементов И 11 по входам 48 блока 3 выбора максимального числа. Запуск блока 3 выбора максимального числа по входу 51 обеспечивается импульсом с генератора 19 импульсов через элемент И 18 при ус- ловии, что хотя бы один процессор вычислительной системы свободен (при наличии сигнала на входах 43 устройства, устанавливающего i-и триггер 16 в единичное состояние, -1 1,и , где h- число процессоров вычислительной системы, в соответствии с чем на выходе элемента ИЛИ 17 находится единичный сигнал). При этом обеспечивается поразрядный анализ сравниваемых чисел следующим образом Если в первом разряде чисел имеется и О и 1, то через элементы И 30 и 31 узлов 29 анализа на группу элементов ИЛИ 33 и 37 поступают единичные сигналы. На выходе элемента И-НЕ 36 сформируется нулевой сигнал, который закрывается элементом И 39, . Через элементы И 32 узлов анализа и элементы ИЛИ 34, относящихся к тем регистрам, в первом разряде которых записан О, единичный сигнал поступает на входы установки в нулевое состояние соответствующих триггеров 35. Элементы И 30 и 31 соответствукщих узлов анализа закрываются, и единичный сигнал находится только на выходе элемента ИЛИ 37. На выходе элемента И-НЕ формируется единичный сигнал, по которому открывается элемент И 39.Далее производится анализ следующего разряда оставшихся сравниваемых чисел.

Если же в первом разряде сравниваемых чисел только нулевые коды или

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

233

5ю 1520 25 зо. 35

40

45

55

1614

сразу производится анализ второго или последующих разрядов. После того, как все разряды сравниваемых чисел проанализированы, на выходе элемента И 39 формируется единичный уровень. При этом на выходах 32 блока 3 выбора максимального числа содержится унитарный код j номера задания с максимальной длительностью выполнения из числа заданных (унитарный код 00100 указывает, что выбран третий номер задания).

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

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

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

При обнулении всех триггеров 4 матрицы 1 на выходах всех элементов ИЛИ 5 находятся нулевые сигналы, а на выходе элемента ИЛИ-НЕ 26 - единичный сигнал. Этот сигнал через элемент 27 задержки обнуляет счетчики 7 и 8 и поступает на выход 46 устройства. На этом работа устройства заканчивается.

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

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

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

o

5 0

5

Q

0

5

5

0

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

7123

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

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

ilJ ... Е

1±

и ю i

-iLa

8

161

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

V7

LJ

Ш-Ш

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

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

Техред СиСопко Корректор Е. Сирохман

Заказ 2772/51Тираж 671Подписное

БНЙИШ Государйтвенного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская.наб., д. 4/5

Производственно-пол

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

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