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

 

Изобретение относится к вычислительной технике и может быть использовано для построения многопроцессорных вычислительных систем. Цель изобретения - повышение быстродействия устройства. Устройство для управления вычислительной системой содержит матрицу признаков зависимых заданий, триггер пуска, две 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 функциональная схема матрицы приз. наков зависимых заданий; на фиг.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

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

 

Похожие патенты:

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

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

Изобретение относится к вычислительной технике и может быть использовано в многопроцессорных вычислиIn ,, I ё йОу й| тельных системах

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

Изобретение относится к вычисли тельной технике и может быть использовано в многопроцессорных ЭВМ для аппаратурной реализации функций операционной системы по диспетчироваиию заданий, готовых к выполнению

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

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

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

Изобретение относится к техническим средствам информатики и вычислительной технике и может быть использовано для решения задач по распределению ресурсов и параметров в экономике, распределения памяти в ЭВМ, вычислительных системах и комплексах, в сетях ЭВМ

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

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

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

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

 

Наверх