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

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

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

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

Устройство (фиг.) содержит первую 1;|-1ц и вторую 2 , группы регистров, регистр 3 готовности процессоров, матрицу 4 признаков зависимости заданий, триггер 5 пуска, группу блоков б, -6|,, элементов И, блок 7 коммутации, содерлсапдай К групп 7| - 7i; по N блоков элементов И в каж,цой группе, вторую группу блоков 8|- 8|j элементов ИЛИ, первую группу блоков 9 элема-нтов И.ПИ, первую группу элементов ИЛИ 1 О - 1 0 элемент ИЛИ-НЕ 11, вторую группу элементов И 12,- 12ц, первую группу элементов И 13,,- IBff, группу дешифраторов 14,- 14к, вторую группу элеме |тов ИЛИ 13(- 15,,, третью группу элементов И 16jj, синхронизатор 7 кода, первую группу кодовых входов ISf.; устройства, группу информадисн Га1х входов 19 устройстваS вход 20 пуска устройства,, вторую группу кодовых входов

21

21,

J- ly устройства S группу кодовых выходов 22 J- устройства, первую 23ц- 23fj и вторую 24,- 24 группы выходов и выход 25 синхронизатора 17.

Матрица 4 признаков зависимости :заданш{ (фиг.2) содержит группу элементов РШИ-НЕ 26|,j, группу триггеров 27, coдepжatt yю Н строк по N триггеров в каждой строке. Синхронизатор 17 (фиг.З) содержит генератор 28 и fflyльcoв, группу элементов ШИ 29,,- 29к, элемент ИЛИ 30 и группу триггеров 31};.

На схеме алгоритма .(фиг.З) функционирования .устройства приняты следующие сокращения и условные обозначения : МФД - матрица формирования дуг; КТЗ - код топологии заданий, .оп ределяющий порядок их выполнения в

устройстве; КНЯ - код номера задания; 3; (i 1,N) - i-e задание; Р; (i 1,N) - i-й выход распределителя; Г; (1 1 ,N) - выход i -го

разряда регистра 3 готовности;

mod (m+n) - функция сложения по модулю ; КНЗЗ - код номера завершенного задания;- символ-операции

записи (установки ; - символ

операции выдачи кода.

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

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

Регистр 3 готовности процессоров

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

ров для исполнения задания, а нулевое - занятому состоянию- процессоров.

Рассмотрим работу устройства , (фиг.1 и 5). В исходном состоянии все элементы памяти установлены

в нулевое состояние, кроме регистра 3, который установлен в единичное состояние, свидетельствующее о готовности процессоров к работе. Цепи начальной установки на фиг.1 не

показаны.

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

распределение независимых заданий по процессорам; освобождение процессоров после выполнения заданий.

Определение независимых заданий сводится к следующему. В матрицу 4

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

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

3

вершины. Одновременно с этим в соответствующие регистры Ij- 1 J с входов 18,- I8f (фиг.1 и 4) заносятся коды номеров заданий и исходные- данные для их выполнения.

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

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

Таблица 1

259285

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

3задание

4задание

3

4

10

15

20

25

30

35

40

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

Таким образом, если соответствующий процессор свободен, о чем свидетельствует единичное состояние соответствующего разряда регистра 3, то в очередном такте работы синхронизатора 17 и при наличии независимых заданий в устройстве на выходе 22, (i 1 ,К) соответствующего блока элементов 8; ИЛИ (i 1,К) установится код номера задания и исходных данных, что и свидетельствует о занятии процессора. При этом единичным сигналом с выхода элемента ИЛИ 0j (i 1.К),проходящим через элемент И 13; )i 1,К) в нулевое состояние будет переведен t -и разряд регистра 3. Кроме того, в нулевое состояние будет установлен регистр Ij (), соответствующий распределенному заданию. Установка в нулевое состояние регистра 1) осуществляется единичным сигналом с выхода блока 9j (,N) элементов ИЛИ, который формируется при соответствующем состоянии выходов распределителя 17 и проходящему через элемент И 2j (j 1,N).

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

1КНЗ 1КНЗ4 ф

2КНЗ 2КНЗ3

3КНЗ 3КНЗ2

4КНЗ 4КНЗI I ф

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

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

Так как учет завершенного задания произведен в регистре 2, (i - 1,К) то на соответствующем j -ом (J ) выходе дешифратора 4; (i 15К) будет установлен единичный потенциал. При этом на выходе элемента И 16J (i ,N) будет сформирован единичный сигнал тактовым импульсом с выхода 23 синхронизатора, по которому в нулевое состояние устанавливается -и -(j 1 ,N) столбец триггеров 27 матрицы 4 признаков зависимых заданий. Последнее приводит к снятию зависимости заданий от завершенного. По очеред- импульсу ,с выхода 23 синхронизатора в нулевое состояние устанавливается соответствующей регистр 2; (i 1,К).Рабо та устройства продолжается до завершения: вьтолнения всех заданий. При этом на выходе

Таблица 2

ф

М

is

is

м

ч

20

5

0

5

0

5

0

5

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

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

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

ход которого соединен с входом запуска синхронизатора, выход каждого элемента ШШ-НЕ группы матрицы признаков зависимых заданий соединен с входом одноименного,блока элементов И группы, отличающееся тем, что, с целью повышения быстродействия, оно дополнительно содержит первую и вторую группы блоков элементов ИЛИ, первую- и вторую группы элементов ИЛИ, регистр готовности процессоров, группу дешиф раторов, блоки коммутации,- содержащий К (К - число процессоров) групп по fJ блоков элементов И в каждой группе, причем выходы с пер-- вого по N -и блок элементов И группы соединены с первыми входами одноименных групп блоков элементов И блока коммутации, выходы с первого по N -и блок элементов И каждой группы блока коммутации соединены с входами одноименных блоков элементов ИЛИ первой группы, выходы блоков элементов И с первой по К-ю группу блока коммутации соединены с входами одноименных блоков элементов ИЛИ второй группы, выходы которых соединены с входами одноименных элементов ИЛИ первой группы и образ5тот группу выходов устройства, выходы с первого по К-й элемен тов ИЛИ первой группы соединены с первыми входами одноименных элементов И первой группы, выходы которых соединены с входами установки в О одноименных разрядов регистра готовности процессоров, выходы блоков элементов ИЛИ первой группы соединены с первыми входами . соответст вующих элементов И второй группы, выходы котор ых соединены с входами установки в О одноименньпс регистров первой группы, каждый вход номера задания второй группы устройства соединен с информационным входом одно592858

именного регистра второй группы, выходы которых соединены с входами одноименных дешифраторов группы, выходы с первого по N -и каждого де- 5 шифратора группы соединены с одноименными входами с первого по N -и элементов ИЛИ второй группы соответ-, ственно, выходы которых соединены с первыми входами одноименных эле- 10 ментов И третьей группы, выход каждого элемента И третьей группы соединен с входами установки в О каждого триггера одноименного столбца матрицы признаков зависимых за- 15 Дании, каждый вход управления вводом номера задания второй группы уст 15ойств.а соединен с входом синхронизации одноименного регистра второй группы, а также с входом установ- 20 ки в 1 одноименного разряда регистра готовности, процессоров, М+1-е выходы регистров первой группы соединены с входами элемента ИЛИ- НЕ, выход которого соединен с входом

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

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

5 входами элементов И первой группы, выходы с первого по К-й регистра готовности процессоров соединены с третьими входами блоков элементов И одноименной группы блока коммута40 ции, -первый вьпсод первой группы выходов синхронизатора соединен с входами установки в О регистров второй группы, а N-й выход первой группы выходов синхронизатора сое- 1 :динен с вторыми входами элементов И третьей группы.

.D

MfpA- кгз

M(1-l,(-N)

-™,

Рчв. 5

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