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

 

Изобретение относится к вычислительной технике и может быть использовано для построения многопроцессорных вычислительных систем. Цель изобретения - повышение быстродействия устройства. Устройство для управления вычислительной системой содержит матрицу признаков зависимых заданий, триггер пуска, две rpyn-i пы регистров, три группы элементов И, группу блоков элементов И, элемент ИЛИ-НЕ, синхронизатор, две группы блоков элементов ИЛИ, две группы элементов 1-ШИ, регистр готовности процессоров, группу дешифраторов и блок коммутации. Введение двух групп блоков элементов ИЛИ, двух групп элементов -ИЛИ, регистра готовности процессоров, группы дешифраторов и блока коммутации обеспечивает достижение цели. 5 ил., 2 табл. ГчЭ 00 О1

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

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

РЕСПУБЛИН (19) (11) А1 (51),1 G 06 Р 15/20, 9/46

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

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

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

C с

Н А BTOPCHOMY СВИДЕТЕЛЬСТВУ (21) 3897334/24-24 (22) 20.05.85 (46) 23,09.86. Бил. - 35 (72) С.Н.Ткаченко, В.И.Ярмонов, В.С.Харченко, Г.Н.Тимонькин, С.П.Козий и Г.И.Мишак (53) 681.325 (088.8) (56) Авторское свидетельство СССР

N - 1095181, кл. G 06 P 9/46, 1983.

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

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

ЗАДАНИЙ ПРОЦЕССОРАМ (57) Изобретение относится к вычислительной технике и может быть использовано для построения многопроцессорных вычислительных систем.

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

1 мых заданий, триггер пуска, две груп-. пы регистров, три группы элементов

И, группу блоков элементов И, элемент ИЛИ-НЕ, синхронизатор, две группы блоков элементов ИЛИ, две группы элементов ИЛИ, регистр готовности процессоров, группу дешифраторов и блок коммутации. Введение двух групп блоков элементов ИЛИ, двух групп элементов ИЛИ, регистра готовности процессоров, группы дешифраторов и блока коммутации обеспечивает достижение цели. 5 ил., 2 табл.

)259285

)О

t5

2О

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

Цель изобретения — повышение быстродействия устройства.

На фиг.) приведена функциональ— ная, схема устройства; на фиг.2 функциональная схема матрицы приз. наков зависимых заданий; на фиг.3 функциональная схема синхронизатора; на фиг.4 — времечные диаграммы работы синхронизатора импульсов; на фиг.5 — схема алгоритма функционирования устройства.

Устройство (фиг,)) содержит первую 1, -)> и вторую 2, — 2 „, группы регистров, регистр 3 готовности процессоров, матрицу 4 признаков зависимости заданий, триггер 5 пуска, группу блоков 6, -61, элементов И, блок 7 коммутации, содержащий К групп 71 — 7» по )1 блоков элементов

И в каждой группе, вторую группу блоков 8 — 8 элементов ИЛИ, первую группу блоков 9,, — 9) элементов ИЛИ, первую группу элементов ИЛИ 10 1- 10), элемент ИЛИ-НЕ 11, вторую группу элементов И 12 ; )2g, первую группу элементов P 13,, — 1311, группу дешиф— раторов )4) — 14„, вторую группу элементов ИЛИ )5 — )5><, третью группу элементов И )6, — 16, синхронизатор )7 xoUG, первую группу кодовых входов 18. — )8 > устройства, группу информационных входов 19 устройства, вход 20 пуска устройст- ) ва, вторую группу кодовых входов

21)- 21, устройства, группу кодовых выходов 221- 22 устзойства, первую

23„— - 23;, и вторую 24< — ?4„ группы выходов и выход 25 синхронизатора

17.

Матрица 4 признаков зависимости заданий (фиг.2) содержит группу элементов ИЛИ-НЕ 26 — 26,, группу григгеров 27, содержащую 11 строк по N триггеров в кыкдой строке.

Синхронизатор 17 фиг.3) содержит генератор 28 импульсов, группу элементов ИЛИ 29 — 29),, элемен- ИЛИ 30 и группу триггеров 31 — 31Ч .

На схеме алгоритма (фиг.5) функционирования .устройства приняты следующие сокращения и условные обозна ения: МФД вЂ” матрица формирования дуг; KT3 — код топологии заданий, определяющий порядок их выполнения в устройстве; KH3 — код номера задания; 3; (i = ),N) — i е задание;

Р,

mod (m+n) — функция сложения по модулю ; KH33 — код номера завершенного задания; - — символ операции записи (установки) ; — — символ операции выдачи кода.

Матрица 4 признаков зависимости заданий предназначена для хранения кода топологии заданий, определяющего последовательность их выполнения.

Если строка матрицы 4 не содержит триггеров 27, установленных в единичном состоянии, то соответствующее задание является независимым.

Регистр 3 готовности процессоров предназначен для хранения признаков состояний процессоров вычислительной системы. Единичное состояние разрядов регистра соответствует состоянию готовности соответствующих процессоров для исполнения задания, а нулевое — занятому состоянию- процессоров.

Рассмотрим работу устройства (фиг,1 и 5). В исходном состоянии все элементы памяти установлены в нулевое состояние, кроме регистра 3, который установлен в единичное состояние, свидетельствующее о готовности процессоров к работе. Цепи начальной установки на фиг.1 не показаны.

В работе устройства можно выделить следующие этапы, реализуемые в режиме совмещения во времени: определение независимых заданий; распределение независимых заданий по процессорам; освобождение процессоров после выполнения заданий.

Определение независимых заданий сводится к следующему, В матрицу 4 признаков зависимых заданий заносится информация о топологии графа, описывающего очередность выполнения заданий. Выполняемые устройством задания могут быть зависимьжи и независимыми. Для зависимых заданий соответствующий триггер 27 матрицы 4 (фиг,2) устанавливается в единичное состояние. Номер триггера 27, устанавливаемого в единичное состояние, 55 определяется пересечением столбца матрицы с номером, равным номеру начальной вершины ветви и строки с номером, равным номеру ее конечнбй

1259285

Продолжение табл.!

3 задание

4 задание

Таблица

1 задание

2 задание

50 вершины. Одновременно с этим в соответствующие регистры 11 в lц с вхо- дов 18< — 18N (фиг.l и 4) заносятся коды номеров заданий и исходные . данные для их выполнения. 5

К моменту поступления сигнала пуска на вход 20 устройства и на выходах, соответствующих независимым заданиям элементов 26 — 26 ИЛИНЕ фиг.2 устанавливаются единич- 1О ные потенциалы. Для независимого задания все триггеры 27 соответствующеи строки установлены в нулевое состояние. Таким образом, коды номеров независимых заданий с выходов 15 соответствующих регистров 1, — lg поступают на выходы соответствующих блоков 61 в 61 элементов И группы.

По поступлению сигнала пуска на вход 20 в устройстве осуществляется 10 распределение независимых заданий по процессорам. При этом сигналом . пуска триггер 5 пуска устанавливается в единичное состояние и на выходах синхронизатора 17 разреша- 25 ется формирование тактовой сетки импульсов (фиг.3 и 4). Распределение заданий по процессорам осуществляется по алгоритму кругового циклического опроса с параллельным наз- З0 начением заданий процессорам. В каждом такте работы синхронизатора 17 производится попытка распределения К заданий. Например для случая И = 4, К = 2 последовательность возможных распределений за цикл работы синхронизатора 17 имеет вид представленный в табл. 1.

Из приведенного примера следует, что за цикл работы синхронизатора 17 каждое задание совершает две попытки распределения (К=2) на два процессора. При этом в случае благоприятной комбинации независимых заданий возможно их параллельное распределение по процессорам. Очевидно что с увеличением N и К число благоприятных комбианций будет также возрастать.

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

22; (i = 1,К) соответствующего блока элементов 8; ИЛИ (i = 1,К) установится код номера задания и исходных данных, что и свидетельствует о занятии процессора. При этом единичным сигналом с выхода элемента ИЛИ

10 (i = 1.К),проходящим через элемент И 13; )i = 1,К) в нулевое состояние будет переведен 1 -й разряд регистра 3. Кроме того, в нулевое состояние будет установлен ре— гистр 1 (j=l,N), соответствующий распределенному заданню. установка в нулевое состояние регистра ll осуществляется единичным сигналом с выхода блока 9l (j--l,N) элементов

ИЛИ, который формируется при соответствующем состоянии выходов распределителя 17 и проходящему через элемент И 12! (j = 1,N).

Например, для случая К = 2,1! = 4 этот процесс может быть представлен табл.2.!

259285

Таблица 2

Регистр

Такт Выход

Выход

1 1

1 КНЗ 1 КНЗ

2 КИЗ 2 КНЗ 3

3 КНЗ 3 КНЗ 2

4 КНЗ 4 КНЗ 1

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

По завершению выполнения задания t -й процессор выставляет код номера завершенного задания и сигнал готовности на соответствующих входах 21 (i = 1.К),При этом код

30 номера задания записывается в реГистр 2" (3 = 1 К), а с007pc" TÑTÁç÷Î щий -и разряд регистра 3 устанавливается в единичное состояние, что позволяет использовать 1 -й процессор для распределения, не дожидаясь завершения процесса снятия зависимости заданий.

Так как учет завершенного задания произведен в регистре ?, (i

t 40

1,К), то на соответствующем .! -ом (j = 1,,N) выходе дешифратора 14; (i = 1,К) будет установлей единичный потенциал, При этом на выходе элемента И 16 1 (i = 1,N) будет сфор— мирован единичный сигнал тактовым импульсом с выхода 23> синхронизатора, по которому в нулевое состояние устанавливается ) -й (j= 1,N) столбец триггеров 27 матрицы 4 приз-, наков зависимых заданий. Последнее приводит к снятию зависимости заданий от завершенного. По очеред-. ному импульсу с выхода. 23 синхронизатора в нулевое состояние устанавливается соответствующий регистр

2, (i = 1,К).Работа устройства продолжается до завершения выполнения всех заданий. При этом на выходе элемента ИЛИ-НЕ ll формируется единичный сигнал, переводящий триггер в нулевое состояние, которым запрещается формирование тактовых импульсов на выходах синхронизатора

17. На этом работа устройства завершается.

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

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

20 ход которого соединен с входом запуска синхронизатора, выход каждого элемента ИЛИ-НЕ группы матрицы признаков зависимых заданий соединен с входом одноименного блока элементов И группы, о т л и ч а ющ е е с я тем, что, с целью повьппения быстродействия, оно дополнительно содержит первую и вторую группы блоков элементов ИЛИ, первую и вто- tp рую группы элементов ИЛИ, регистр готовности процессоров, группу дешиф-. раторов, блоки коммутации, содержащий .К (К вЂ” число процессоров) групп по 1 блоков элементов И в 15 каждой группе, причем выходы с первого по .5 -й блок элементов И группы соединены с первыми входами одноименных групп блоков элементов

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

К-ю группу блока коммутации соединены с входами одноименных блоков элементов ИЛИ второй группы, выходы которых соединены с входами одноименных элементов ИЛИ первой груп- 30 пы и образуют группу выходов устройства, выходы с первого по К-й элементов ИЛИ первой группы соединены с первыми входами одноименных элементов И первой группы, выходы которых соединены с входами установки в "0" одноименных разрядов регистра готовности процессоров, выходы блоков элементов ИЛИ первой группы соединены с первыми входами соответствующих 40 элементов И второй группы, выходы которых соединены с входами установки в "0" одноименных регистров первой группы, каждый вход номера задания второй группы устройства соединен с информационным входом одно- .

285 Я именного регис гра второй группы, выходы которых соединены с «ходами сдноименных деп|ифраторов группы, выходы с первого по Н -й каждого дешифратора группы соединены с одноименными входами с первого по К -й элементов ИЛИ второй группы соответ-, ственно, выходы которых соединены с первыми входами одноименных элементов И третьей группы, выход каждого элемента И третьей группы соединен с входами установки в "0" каж— дого триггера одноименного столбца матрицы признаков зависимых заданий, каждый вход управления вводом номера задания второй группы устройства соединен с входом синхронизации одноименного регистра второй группы, а также с входом установки в "1 одноименного разряда ре— гистра готовности процессоров, М+1-е выходы регистров первой группы соединены с входами элемента ИЛИНЕ, выход которого соединен с входом установки в "0" триггера пуска, выходы первой группы синхронизатора соединены с вторыми входами одно.именных. блоков элементов И с первой по К-ю группу блока коммутации соответственно, выходы второй группы синхронизатора соединены с вторыми входами одноименных элементов И второй группы, дополнительный выход синхронизатора соединен с вторыми входами элементов И первой группы, выходы с первого по К-й регистра готовности процессоров соединены с третьими входами блоков элементов И одноименной группы блока коммутации, первый выход первой группы выходов синхронизатора соединен с входами установки в "0" регистров второй группы, а N-й выход первой группы выходов синхронизатора соединен с вторыми входами элементов И третьей группы.!

259285

1259285

1259785 юг. 5

Составитель A.Ëôàûàñüåâ

Редактор Н.Яцола Техред !.Xoданиz Корректор А.Тяско

Заказ 5L 24/48 Тираж 611 Подписное

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

1(3035,. Москва, (-35, Раушская наб., д.4/5

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