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

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

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

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

Устройство содержит группу триг- геров 1, группу регистров 2 хранет ния, группу элементов И 3, группу блоков элементов И 4, группу формирователей 5 импульсов элемент И 6, элемент НЕ 7, регистр 8 номера задачи, блок 9 сдвигающего регистра, блок 10 анализа, регистр 1 готовности процессоров, п ау- вый 1 2 и третий 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 содержит

элемент И 33, элемент 34 задержки и элемент НЕ 35.

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

Узел 36 блока 10 анализа (фиг. 4) «содержит элемент И 4 и элемент ИЛИ 42.

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

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

ры 2, регистр 8, сдвигающий регистр 31 обнулены, триггеры 1 находятся в нулевом состоянии, элементы И 3 закрыты по вторым входам запрещающим сигналом с прямых выходов соответ- ствуюгцих триггеров 1 . Блоки элементов И 4 закрыты по управляющим входам запрещающш-1 сигналом от соответствующего элемента И 3. На информационных входах и выходах блоков элементов И 4, регистра 8, блока 9, блоков элементов И 16, элементов ИЛИ 17, входах сброса регистра 11 готовности, входах 25 сброса блока 9 и на входах 2 нулевая информация. Нулевые сигналы с выходов 26 блока 9 поступают на входы элемента ИЛИ 15 .и на втЬрые управляющие входы соот- ветствук1Щих блоков элементов И 16, закрьшая; их. Нулевой сигнал с выхода элемента ИЛИ 15 поступает на первый вход первого элемента И 12, на второ входе которого действует нулевой сигнал с выхода 26 старшего разряда блока 9,, на вход элемента 14 задержк и на третий вход элемента И 13-. Таким образом, элемент И 12 закрыт нулевым сигналом по двум входам, а элемент И 13 - по второму и третьему вxoдaJM. Нулевой сигнал с вьпсода элемента И 12 поступает на вход 23 блок 9. Нулевой сигнал с выхода элемента И 13 через вход 24 блока 9 поступает на элемент И 33 задающего генератора 32, закрьтая его. Генератор 32 находится в ждущем режиме. Так как процессоры свободны, весь регистр 11 готовности заполнен единицами. Единичные сигналы с информационных выходов регистра 11 поступают на входы 27 блока 1 О и ца первые управляющие дь соответствующих блоков элементов И 16. Так как на всех входах 27 блока 10 анализа присутствуют единичные сигналы, то на первом (28) и втором выходах блока также единичные сигналы, которые подаются соответственно на первый вход третьего элемента И 13 и на второй вход второго элемента И 6. Нулевой сигнал с выхода элемента ИЛИ 15 инвертируется на элементе НЕ 7 и поступает на первые входы соответствующих элементов К 3 и на первьй вход элемента И 6, с выхода которого единичный сигнал подается на первые входа остальных элементов И 3. На управляющий вход 30 подается нулевой управ.ляющий сигнал.

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

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

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

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

10 сигнала (), который поступая на С-вход триггера (на входы С, 3 и К которого постоянно подается нулевой потенциал), устанавливает триггер 1 в нулевое состояние. Эле15 мент И 3 закрьгоается и по второму входу нулевым потенциалом с прямого выхода триггера 1. Единичный сигнал с инверсного выхода триггера 1 группы подается на .сигнальный выход 19

20 устройства, указывая, что задача принята на обслуживание. Одновременно единичный сигнал с инверсного выхода триггера 1 поступает на входы соответствующих элементов И 3,-Еди25 ничные сигналы с группы выходов 26 блока 9 поступают на входы элемента ИЛИ 15 и на вторые управляющие входы блоков элементов И 16. С выхода элемента ИЛИ 15 единичный сиг0

0

нал поступает на вход элемента НЕ 7, первый вход первого элемента И 12, третий вход третьего элемента И 13 и вход элемента 14 задержки. Единичный сигнал, инвертируясь на элементе НЕ 7, закрывает по первьм входам соответствующие элементы И 3 и элемент И 6, с выхода которого нулевой сигнал закрывает по первым входам остальные элементы И 3, блокируя тем самым поступление новой информации на регистр 8 и блок 9 до окончания распределения процессоров. Так как количество необходимых для решения задачи процессоров .поступает на группу информационных входов 22 блока 9 в позиционном коде, то на выходе 26 старшего разряда блока 9 присутствует нулевой сигнал, который, поступая на второй вход элемента И 12, закрывает его. На вы- ходе элемента И 12 и, следовательно, на входе 23 младшего разряда блока 9 устанавливается нулевой сигнал. Эле-- мент 14 задержки введен для блокировки сдвига сдвигающего.регистра 31 при первом распределении задачи между процессорами.

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

5

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

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

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

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

5 0 5 0 5 О

2-

С

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

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

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

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

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

7

регистр готовности процессоров первую группу блоков элементов И, блок сдвигающих регистров, группу элементов ИЛИ, первый элемент И, элемент ИЛИ, группу регистров хранения, сигнальные входы устройства соединены с группой информационных входов регист ра готовности процессоров, каждый выход pyппы выходов которого соединен с первым управляющим входом соответствующего блока элементов И первой группы, группа выходов каждого блока элементов И первой группы подключена к группе информационных выходов устройства и к группе входов соответствующего элемента ИЛИ группы, выход которого подключен к одноименному входу группы входов сброса регистра готовности процессоров и к одноименному входу группы входов сброса блока сдвигающих регистров, каждый выход группы выходов которого подключен к второму управляющему входу одноименного блока элементов И первой группы и к соответствующему входу элемента ИЛИ, выход которого подключен к первому входу первого элемента И, второй вход которого подключен к выходу старшего разряда группы выходов блока сдвигающих регистров, выход первого элемента И подключен к входу младшего разряда блока сдвигающих регистров, о т - личающееся тем, что, .с целью расширения функциональных возможностей устройства за счет организации обслуживания с .усеченным приоритетом, в него введены группа триггеров, вторая группа блоков элементов И, групп й из т, где m - число источников запоосов, элементов И, группа фopмиpoвateлeй импульсов, регистр-номера задачи, второй и третий элементы И, элемент НЕ, элемент задержки, блок анализа, причем вход элемента НЕ подключен к выходу элемента ИЛИ, выход элемента НЕ подключен к первым входам элементов И группы, с первого по га/2-й, и к первому входу второго элемента И, выход которого соединен с первыми входами элементов И группы с (М/2-1)-го по т-й второй вход каждого i-ro (...m) элемента И группы соединен с прямым выходом 1-го триггера группы, единичный вход которого подключен к выходу i-ro формирователя импульсов группы, вход которого является i-м запросным входом устройства, инверс42950 , 8

ный выход i-ro триггера группы является i-M сигнальным выходом устройства, инверсный выход каждого триггера группы соединен с соответствую5 щим входом каждого последующего элемента И группы, выход каждого элемента И группы соединен с синхронизирующим входом одноименного триггера группы И с управляющим входом

to одноименного блока элементов И второй группы, группа информационных входов каждого из которых соединена с группой информационных выходов одноименного регистра хранения группы,

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

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

30 задержки, второй вход третьего элемента И подключен к выходу элемента задержки, третий вход третьего эЛе- мента И подключен к первому.выходу блока ангшиза, второй выход которого

,„ подключен к BTOpoNry входу второго элемента И, группа входов блока анализа подключена к группе выходов регистра готовности процессоров, группа информационных входов каждого ре4Q гистра хранения группы является i-й группой информационных входов устройства, вход запуска устройства соединен с входом блока анализа.

2. Устройство по п. 1, отличающееся тем, что блок анализа содержит п групп из Е узлов анализа, где п - число процессоров, а 2 п, причем в каждой j-й (j 1, п) группе узлов анализа первый выход k-ro ...(E-l)j узла анализа подключен к первому входу (k + +1)-го узла этой группы, а первый вход первого узла подключен- к информационному входу группы инфор- мационных входов блока анализа, в каждой м-й группе узлов анализа , (n-i)j второй выход каждого k-ro узла анализа подключен к вто912429

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

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

10

2 f-so.

,

г

.

г«

i7S

С

г&п

Sr

50

10

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

29

о Л/

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

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

ВНИИПИ Государственного комитета СССР

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

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

LL,

I I J8y

Q}l/s.4

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

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

Подписное

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