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

 

Устройство для распределения задач между процессорами относится к вычислительной технике и может быть использовано для распределения задач между процессорами в мультипроцессорных системах. Целью настоящего изобретения является расширение функциональных возможностей устройства за счет организации, обслуживания с усеченным приоритетом. Приоритетное обслуживание необходимо в системах, работающих в реальном масштабе времени , где большие требования предъявляются к своевременности обработки информации . Закрепление за приоритетными задачами определенного вычислительного ресурса повьшает вероятность их своевременного решения, снижая время старения срочной информации. Устройство содержит группу из m триггеров, группу из m регистров хранения, группу из m элементов И, первую группу из п блоков элементов И, вторую группу из m блоков элементов И, первый, второй и третий элементы И, элемент НЕ, регистр номера задачи, блок сдвигающего регистра, регистр готовности процессоров, блок анализа, элемент ШШ, группу из п элементов ИЛИ, элемент задержки. 2 з.п.ф-лы, 4 ил. i С/) to NU ts5 QD СЛ

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

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

РЕСПУБЛИК (51) 4 G 06 F 9/46 (" -"" е

13, 13 ЖОтЩ

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

К Д BTOPCHOMY СВИДЕТЕЛЬСТВУ

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

Г10 ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3784227/24-24 (22) 25.08.84 (46) 07.07.86. Бюл. № 25 (72) А. Я. Матов, В. Д. Костюченко, С. Е. Карловский, А. В. Печников и В. П. Коротеев (53) 681.325(088.8) (56) Авторское свидетельство СССР

¹ 629538, кл. С 06 F 9/00, 1978.

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

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

„„SU„„1242950 А1 счет организации обслуживания с усеченным приоритетом. Приоритетное обслуживание необходимо в системах, работающих в реальном масштабе времени, где большие требования предъявляются к своевременности обработки информации. Закрепление за приоритетными задачами определенного вычислительного ресурса повышает вероятность их своевременного решения, снижая время старения срочной информации. Устройство содержит группу из ш триггеров, групну из ш регистров хранения, группу из ш элементов И, первую группу из и блоков элементов И, вторую группу из m блоков элементов И, первый, второй и третий элементы И, элемент

НЕ, регистр номера задачи, блок сдвигающего регистра, регистр готовности процессоров, блок анализа, элемент

ИЛИ, группу из и элементов ИЛИ, элемент задержки. 2 з.п.ф-лы, 4 ил.

1242950 2

345

45 с,б .15

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

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

На фиг. 1 представлена структурная схема устройства; на фиг. 2 — структурная схема блока сдвигающего регистра; на фиг. 3 — структурная схема блока анализа; на фиг. 4 — структурная схема узла анализа.

Устройство содержит группу триггеров 1, группу регистров 2 хране-, ния, группу элементов И 3, группу блоков элементов И 4, группу формиро- . вателей 5 импульсов элемент И 6, элемент

НЕ 7, регистр 8 номера задачи, блок 9 сдвигающего регистра, блок 10 анализа,,регистр 11 готовности процессоров, ггау- . вый 12 и третий 13 элементы И, элемент 14, задержки, элемент ИЛИ 15, группу блоков элементов И 16, группу элементов

ИЛИ 17, запросные входы 18 устройства, сигнальные выкоды 19 устройства, информационные входы 20 устройства, сигнальные входы 21 устройства, группу входов 22 и входы 23 и 24 блока 9, группу входов 25 и выходы 26 блока 9, входы 27 и выход 28 блока 10, информационные выходы 29 устройства и вход 30 запуска устройства.

Блок 9 сдвигающего регистра (фиг. 2) содержит собственно сдвигающий регистр 31 и задающий генератор 32.

Задающий генератор 32 содержит элемент И 33, элемент 34 задержки и элемент НЕ 35.

Блок 10 анализа (фиг. 3;) содержит узел 36 анализа, входы 37 и выходы

38 узлов 36, входы 39 и вьгходы 40 узлов 36. Узел 36 блока 10 анализа (фиг. 4) содержит элемент И 41 и элемент

ИЛИ 42.

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

В исходном состоянии информация о задачах на входах 20 отсутствует, сигналы на входы 18 не поступают, на сигнальных выходах 19 устройства— потенциалы, свидетельствующие о готовности устройства к работе. Регистры 2, регистр 8, сдвигающий регистр

31 обнулены, триггеры 1 находятся в нулевом состоянии, элементы И 3 закрыты по вторым входам запрещающим сигналом с прямых выходов соответствующих триггеров 1. Блоки элементов И 4 закрыты по управляющим входам запрещающим сигналом от соответствующего элемента И 3, На информационных входах и выходах блоков элементов И 4, регистра 8, блока 9, блоко:в элементов И 16, элементов

ИЛИ 17, входах сброса регистра 11 готовности, входах 25 сброса блока 9 и на входах 21 нулевая информация.

Нулевые сигналы с выходов 26 блока 9 поступают на входы элемента ИЛИ 15 и на вторые управляющие входы соответствующих блоков элементов И- 16, закрывая их. Нулевой сигнал с выхода элемента ИЛИ 15 поступает на первый вход первого элемента И 12, на втором входе. которого действует нулевой сигнал с выхода 26 старшего разряда блока. 9., на вход элемента 14 задержки и на третий вход элемента И 13- Таким образом, элемент И 12 закрыт нулевым сигналом по двум входам, а

3 элемент И 13 — по второму и третьему входам. Нулевой сигнал с выхода элемента И 12 поступает на вход 23 блока

9. -Нулевой сигнал с выхода элемента

И 13 через вход 24 блока 9 поступает на элемент И 33 задающего генератора

32, закрывая его. Генератор 32 находится в ждущем режиме. Так как процессоры свободны, весь регистр 11 готовности заполнен единицами. Единичные сигналы с информационных выходов регистра ll поступают на входы 27 блока 10 и на первые управляющие входы соответствующих блоков элементов

И 16. Так как на всех входах 27 бло1 ка 10 анализа присутствуют единичные сигналы, то на первом (28) и втором выходах блока также единичные сигналы, которые подаются соответственно на первый вход третьего элемента

И 13 и на второй вход второго элемента И 6. Нулевой сигнал с выхода элемента ИЛИ 15 инвертируется на элемен те НЕ 7 и поступает на первые входы соответствующих элементов И 3 и на первый вход эпемента И 6, с выхода которого единичный сигнал подается на первые входы остальных элементов

И 3. На управляющий вход 30 подается нулевой управляющий сигнал.

124?950 4

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

18 на вход формирователя 5 импульсов, короткий единичный импульс с выхода которого поступает на установочный. вход соответствующего триггера 1 и устанавливает его в единичное состояние, снимая единичные сигналы с входов соответствующих элементов И 3.

Единичный сигнал с прямого выхода триггера 1 поступает на второй вход элемента И 3 группы, на первом входе которого действует единичный сигнал с выхода элемента НЕ 7 либо с выхода элемента И 6, а на остальных входах — единичные сигналы с инверсных выходов триггеров 1. На выходе элемента И 3 группы устанавливается е иничный сигнал, который, поступая на управляющий вход блока элементов

И 4, открывает его.

Код номера задачи с регистра 2 через открытый блок элементов И 4 в парафазном коде записывается в регистр 8. Применение парафазного кода для передачи кода номера задачи позволяет избежать нуления регистра

8 номера задачи перед записью в него новой информации. Так как сдвигающий регистр 31 после распределения очередной задачи между процессорами обнуляется, то для передачи количества потребных для решения задачи процессоров используется обычный код, т.е. используется информация только с прямых выходов триггеров регистра 2 хранения. Код количества необходимых для решения задачи процессоров через открытый блок элементов И 4 поступает на группу информационных входов 22 блока 9 и записывается в сдвигающий регистр 31

На выходе элемента ИЛИ 15 после этого появляется единичный потенциал, который поступает на вход эле5

55 мента HF 7, нулевой потенциал, появляющийся на выходе НЕ 7, закрывает по первому входу соответствующие элементы И 3 и элемент И 6, нулевой потенциал с выхода которого закрывает по первому входу остальные элементы И 3. На выходе элемента

И 3, который перед этим открыт, формируется задний фронт единичного сигнала (1 †"O"), который поступая на С-вход триггера 1 (на входы С, 3 и К которого постоянно подается нулевой потенциал), устанавливает триггер 1 в нулевое состояние. Элемент И 3 закрывается и по второму входу нулевым потенциалом с прямого выхода триггера 1. Единичный сигнал с инверсного выхода триггера 1 группы подается на .сигнальный выход 19 устройства, указывая, что задача принята на обслуживание. Одновременно единичный сигнал с инверсного выхода триггера 1 поступает на входы соответствующих элементов И 3 .. Единичные сигналы с группы выходов 26 блока 9 поступают на входы элемента ИЛИ 15 и на вторые управляющие входы блоков элементов И 16. С вы— хода элемента ИЛИ 15 единичный сигнал поступает на вход элемента НЕ .7, первый вход первого элемента И 12, третий вход третьего элемента И 13 и вход элемента 14 задержки. Единичный сигнал, инвертируясь на элементе НЕ 7, закрывает по первым входам соответствующие элементы И 3 и элемент И 6, с выхода которого нулевой сигнал закрывает по первым входам остальные элементы И 3, блокируя тем самым поступление новой информации на регистр 8 и блок 9 до окончания распределения процессоров.

Так как количество необходимых для решения задачи процессоров,поступает на группу информационных входов

22 блока 9 в позиционном коде, то на выходе 26 старшего разряда блока

9 присутствует нулевой сигнал, который, поступая на второй вход элемента И 12, закрывает его. На выходе элемента И 12 и, следовательно, на входе 23 младшего разряда блока 9 устанавливается нулевой сигнал. Элемент 14 задержки введен для .блокировки сдвига сдвигающего.регистра 31 при первом распределении задачи между процессорами.

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

1242950 после прохождения сигнала через соответствующий блок элементов И 16, соответствующий элемент ИЛИ 17 и сброса триггера сдвигающего регист .ра 31. Единичный сигнал с выхода 26 блока 9 поступает на второй управляющий вход блока элементов И 16, на первом управляющем входе которого действует единичный сигнал с соот- 10 ветствующего выхода регистра 11, а на информационных входах — код номера задачи, поступающий с регистра 8.

Под воздействием единичного сигнала с выхода 26 группы информационных выходов блока 9 блок элементов И 16 открывается и код номера задачи поступает на соответствующую группу выходов 29 и на группу входов соответствующего элемента ИЛИ 17. Еди- 2î ничный сигнал с выхода элемента

ИЛИ 17 поступает на вход группы входов 25 блока 9 и на вход группы входов сброса регистра 11 готовности, устанавливая в нулевое состояние со- 2 ответствующий триггер сдвигающего регистра 31 и соответствующий триг гер регистра ll. Нулевой сигнал с выхода регистра 11 готовности поступает на информационный вход 27 блока ЗО

10 анализа.

Блок 10 анализа работает следующим образом.

Блок 10 анализа представляет собой двумерную итеративную сеть размером из узлов Зб. Каждый узел 36 представляет собой конечный автомат без памяти.

Узел Зб обеспечивает распространение сигналов в двух направлениях: сверху вниз и слева направо. Блок 10 анализа выполняет операцию взвешивания (подсчета числа единиц). На информационные (граничные) входы 27 блока 10 анализа поступает позиционный код количества свободных процессоров от регистра 11 готовности. На управляющий вход 30 блока подается нулевой граничный сигнал, который поступает на входы 30 узлов 36. Таким образом, на первых входах элементов И 4! и ИЛИ 42 действует нулевой сигнал с входов 39. Допустим, что свободен только первый процессор.

Тогда единичный сигнал через вход 27, блока 10 и вход 37„ узла 36 подается на вторые входы элементов И 41„ и ИЛИ 42,„. Так как элемент И 41„ эакрыт по первому входу нулевым граничным сигналом, то единичный сигнал через элемент ИЛИ 42„ и выход 40,„ подается на вход 39 „ узла 36,„. Через вход 39, единичный сигнал поступает на первые входы элементов И 41, и ИЛИ 42 „ на вторых входах которых ,действует нулевой сигнал с информационного входа 27 блока, закрывая элемент И 41 . Единичный сигнал через элемент И 42>< и выход 40 узла поступает на вход 39 „ узла 36„, где операция повторяется. Таким образом, единичный сигнал распространяется по первому столбцу узлов 36 и выделяется на управляющем выходе 28 блока 10. Аналогично блок 10 работает при,любом свободном процессоре. Единичный сигнал может распространяться только в первом столбце и только вниз, так как его распространение вправо ограничивают закрытые элемен— ты И 41.

Распределение задачи между процессорами при условии незанятости всех процессоров осуществляется параллельно, TBK как все блоки элементов И 16 имеют на своем первом управляющем входе разрешающий потенциал, поступающий с соответствующих выходов группы информационных выходов регистра 1! готовности, сдвигающий регистр

31 блока 9 попностью обнуляется. Нулевые сигналы с информационных выходов 26 блока 9 поступают на входы элемента ИЛИ 15, с выхода которого нулевой сигнал подается на первый вход элемента И 12„ первый вход элемента И 13,, закрывая их„. и на вход элемента НЕ 7. На втором вход элемента И 12 действует нулевой сигнал с выхода 26 старшего разряда блока 9. Нулевые сигналы с выходов элементов И 12 и 13 подаются на вход 23 младшего разряда и управляющий вход 24 блока 9 соответственно.

Нулевой сигнал, инвертируясь на элементе HE 7, поступает на первые входы элементов И 3 и на первый вход элемента И б.

Дальнейшая работа происходит аналогично.

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

1 . Устройство для распределения задач между процессорами, содержащее

1242950 8

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

ИЛИ, группу регистров хранения, сигнальные входы устройства соединены с группой информационных входов регистра готовности процессоров, каждый выход 1 руппы выходов которого соединен с первым управляющим входом соответствующего блока элементов И первой группы, группа выходов каждого блока элементов И первой группы подключена к группе информационных выходов устройства и к группе входов соответствующего элемента ИЛИ группы, выход которого подключен к одноименному входу группы входов сброса регистра готовности процессоров и к одноименному входу группы входов сброса блока сдвигающих регистров, каждый выход группы выходов которого подключен к второму управляющему входу одноименного блока элементов И первой группы и к соответствующему входу элемента ИЛИ, выход которого подключен к первому входу первого элемента И, второй вход которого подключен к выходу старшего разряда группы выходов блока сдвигающих регистров, выход первого элемента И подключен к входу младшего разряда блока сдвигающих регистров, о т— л и ч а ю щ е е с я тем, что,,с целью расширения функциональньгх возможностей устройства за счет организации обслуживания с,усеченным приоритетом, в него введены группа триггеров, вторая группа блоков элементов И, группа из m, где m — число источников запоосов, элементов И, . группа формирователей имггульсов, регистр номера задачи, второй и третий элементы И, элемент НЕ, элемент задержки, блок анализа, причем вход элемента НЕ подключен к выходу элемента ИЛИ, вьгход элемента НЕ подключен к первым входам элементов И группы, с первого по m/2-й, и к первому входу второго элемента И, выход которого соединен с первыми входами элементов И группы с (M/2-1)-го по m-й второй вход каждого i-ro (i=2/l...ш) элемента И группы соединен с прямым вьгходом -го триггера группы, единичный вход которого подключен к выходу i — ro формирователя импульсов группы, вход которого является i-м запросным входом устройства, инверс5

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

2. Устройство по п. 1, о т л и ч а ю m е е с я тем, что блок анализа содержит п групп из E узлов ! анализа, где п — число процессоров, а p. < n, причем в каждой j — и (j

=1, п) группе узлов анализа первый выход k-го (k=1...(г -1)) узла анализа подключен к первому входу (k +

+l)-ro узла этой группы, а первый вход первого узла подключен к j-xy информационному входу группы информационных входов блока анализа, в каждой м-й группе узлов анализа (м=l, (и-1)1 второй выход каждого

k-го узла анализа подключен к вто9 1 2

1 рому входу k-ro узла (3+ )-й груп пы, вторые входы всех узлов анализа первой группы подключены к управляю— щему входу блока анализа, второй выход первого узла анализа,п-й группы подключен к первому управляющему выходу блока, а второй выход 9-го узла п-й группы подключен к второму управляющему выходу блока.

3. Устройство по пп. 1 и 2, о т— л и ч а ю щ е е с я тем, что в блоке

42950 анализа каждый узел анализа содержит элемент И и элемент И3!И, причем первый вход элемента И подключен к первому входу узла и к первому входу элемента KIH второй вход элемента И вЂ” к второму входу узла и к второму входу элемента ИЛИ, а выход элемента И вЂ” к первому

Ф выходу узла, выход элемента ИЛИ

10 подключен к второму выходу узла.

1242950 е а е у/

Составитель М. Кудряшев

Техред О. Гортвай Корректор М. Максимишинец

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

Заказ 3706/48 Тираж 671

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

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

Подписное

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