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

fO

11290324

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

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

На чертеже показана структурная схема устройства.

Устройство содержит группу входов 1 заявок устройства, группу регистров 2 хранения, группу элементов И 3, группу блоков элементов И 4, группу блоков элементов И 5, группу элементов ИЛИ 6, группу элементов ИЛИ 7, регистр 8 сдвига, элемент ИЛИ-НЕ 9, элемент И 10, группу блоков элементов И 11, группу элементов ИЛИ 12, группу информационных выходов 13 устройства, регистр 14- готовности, элемент задержки 15, элемент ИЛИ 16, элемент ИЛИ 17, триггер 18 режима, элемент И 19, элемент И 20, элемент И 21, элемент И 22, группу элементов И 23, элемент И 24, элемент задержки 25, элемент задержки 26, регистр 27 отказов процессоСигналом запуска триггер 36 устанавливается в состояние 1 определяя начало цикла работы устройства.

Устройство может работать в одном из двух режимов:

1)режим распределения процессоров задаче в соответствий с требуемым количеством процессоров, указанным в заявке,

2)режим перераспределения процессоров при поступлении отказов процессоров в процессе решения задачи.

Установка режима распределения производится триггером 18 режима.

Первый режим начинается с приема заявки в регистры 2 с последуюпщм распреэделением процессоров следую- 20 щим образом.

Так как регистр 8 находится в нулевом состоянии, то единичным сигналом с выхода элемента ИЛИ-НЕ открыты элементы И 3 и 20. Единичным сигналом с нулевого выхода триггера 18 режима открыты по соответствующим входам элементы И 3, 23, 8 и 24.

При наличии сигналов готовности в регистре 14 единичным сигналом

J5

25

ров, группу элементов И 28, буферный элемента ИЛИ 16 открыт элемент И 21, регистр 29, группу элементов И 30, группу блоков элементов И 31, группу схем сравнения 32, группу элементов И 33, генератор 34 импульсов, группу элементов задержки 35, триггер 36 управления, сигнальный выход 37 устройства, вход 38 запуска устройства, группы сигнальных входов 39, 40 устройства.

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

Исходное состояние устройства характеризуется тем, что триггеры 36, 18, регистры 8, 27, 29 установлены в состояние О (не показано). В регистр 14 готовности по входам 40 принимаются сигналы готовности процессоров.

На группу входов 1 устройства поступают заявки на решение задачи, которые вырабатываются планирующей системой, в сопровогвдении сигнала запуска по входу 38„

Заявка содержит двоичный код номера задачи и позиционный код количества потребньгх процессоров для ее решения в виде соответствующего числа смежных единиц, размещенных, начиная с младшего разряда.

по соответствующим входам элементы И 3 и через элементы И 23 - блоки элементов И 4.

По первому импульсу генератора

35 через элемент Pf 21 с помощью элементов И 3 заявка с-входа 1 принимается в те регистры 2 хранения, которым соответствует наличие сигналов готовности процессоров в регистре 14.

40 Через некоторое время, определяемое элементом задержки 35, код количества потребных процессоров через соответствующие б}1оки элементов И 5 и эле менты 1 ШИ 7 передается в регистр 8

45 cpflura. Время задержки элементами задержки 35 определяется временем переходных процессоров в регистрах 2.

После приема кода в регистр 8 сдви га на выходе элемента ИЛИ-НЕ 9 фор50 мируется нулевой сигнал, закрывающий элементы ИЗ, 20, 24 и открывающий по инверсным входам элементы И 22 к И 10.

Дальнейшая работа зависит от пози55 ционного кода сигналов готовности в регистре 14.

Если шсло единиц в смежных позициях регистра 14, начиная с младшего разряда, больше либо равно соответO

f Сигналом запуска триггер 36 устанавливается в состояние 1 определяя начало цикла работы устройства.

Устройство может работать в одном из двух режимов:

1)режим распределения процессоров задаче в соответствий с требуемым количеством процессоров, указанным в заявке,

2)режим перераспределения процессоров при поступлении отказов процессоров в процессе решения задачи.

Установка режима распределения производится триггером 18 режима.

Первый режим начинается с приема заявки в регистры 2 с последуюпщм распреэделением процессоров следую- 0 щим образом.

Так как регистр 8 находится в нулевом состоянии, то единичным сигналом с выхода элемента ИЛИ-НЕ открыты элементы И 3 и 20. Единичным сигналом с нулевого выхода триггера 18 режима открыты по соответствующим входам элементы И 3, 23, 8 и 24.

При наличии сигналов готовности в регистре 14 единичным сигналом

5

5

элемента ИЛИ 16 открыт элемент И 21,

по соответствующим входам элементы И 3 и через элементы И 23 - блоки элементов И 4.

По первому импульсу генератора

через элемент Pf 21 с помощью элементов И 3 заявка с-входа 1 принимается в те регистры 2 хранения, которым соответствует наличие сигналов готовности процессоров в регистре 14.

Через некоторое время, определяемое элементом задержки 35, код количества потребных процессоров через соответствующие б}1оки элементов И 5 и элементы 1 ШИ 7 передается в регистр 8

cpflura. Время задержки элементами задержки 35 определяется временем переходных процессоров в регистрах 2.

После приема кода в регистр 8 сдвига на выходе элемента ИЛИ-НЕ 9 формируется нулевой сигнал, закрывающий элементы ИЗ, 20, 24 и открывающий по инверсным входам элементы И 22 к И 10.

Дальнейшая работа зависит от позиционного кода сигналов готовности в регистре 14.

Если шсло единиц в смежных позициях регистра 14, начиная с младшего разряда, больше либо равно соответствующему количеству единиц кода регистра 8, то код номера задачи из регистров 2 хранения через открытые элементы И 4 соответствующих блоков, элементы ИЛИ 6 и группу блоков эле- с ментов И 11 поступает на выходы 13. Одновременно ,единичные сигналы с выходов соответствующих элементов ИЛИ 12 устанавливают в нулевое состояние одноименные разряды регистров fO 8 и 14, При этом регистр В оказывается в нулевом состоянии.

Если же число смежных единиц кода в регистре 8 превышает число смежных единиц в регистре 14 либо число 15 единиц в регистре 14 равно или больше потребного числа процессоров для решения задачи, то эти единицы размещены в регистре 14 в произвольном порядке - и после гашения одноименных 20 разрядов регистров 8 и 14 рассмотренным порядком в регистре 8 ряд разрядов останется в единичном состоянии..

В первом случае, когда все разряодин разряд в сторону старших разр дов. Если после этого сдвига не пр исходит совпадения единиц в одноим ных разрядах регистров 8 и 14 рассмотренным образом, организуется очередной сдвиг кода регистра 8. С помощью элемента И 10 обеспечива ется циклический сдвиг кода в регистре 8 путем передачи старшей ед ницы в младший его разряд.

Процесс циклического сдвига буд продолжаться до тех пор, пока не б дет назначено требуемое число процессоров. В этом случае единичный сигнал с выхода элемента ШШ-НЕ 9 за крывает цель циклического переноса и обеспечивает установку в нулевое состояние триггера 36.

Второй режим работы устройства организуется при поступлении сигна лов отказов от распределения проце соров. Эти сигналы фиксируются в с

ды регистра.8 установлены в состояние25 ответствующих разрядах регистра 27

О

что означает завершение распреотказов процессоров.

деления процессоров задаче, организуется очередной цикл следующим образом.

Задержанным сигналом элементами задержки 25, 26 и 15 через элемент И 24 триггер 36 устанавливается в состояние О. Единичный сигнал

|С нулевого выхода триггера 36 поступает на выход 37 устройства и используется в качестве сигнала готовности устройства к очередному циклу распределения.

Очередной цикл.распределения начинается после подачи следующей заявки на входы 1 в сопровождении сигнала запуска по входу 39.

Во втором случае, когда в регистре 8 на все разряды установлены в состояние О, на выходе элемента ИЛИ-НЕ 9 формируется нулевое сигнал, закрывающий элементы ИЗ, 20 и 24 и открывающий по инверсным вхокрываются элементы И 19 и 33.

дам элементы И 22 и 10. Так как эле- 50 сигналов отказов в регистр 29, за- мент И 24 закрыт, то задержанный сиг- крьшаются элементы И 24, 23, 3 и от- нал с выхода элемента задержки 15 не изменяет состояние триггера 36. Поэтому очередным сигналом генератора импульсов при наличии сигналов готовности в регистре 14 через элементы И 21 и 22, поступающим на вход

В данном режиме определяется чис- 55 ло отказавших процессоров при решени задачи с одним и тем же номером. Это обеспечивается следующим образом.

управления сдвигом регистра 8, обеспечивается сдвиг его содержимого на

один разряд в сторону старших разрядов. Если после этого сдвига не происходит совпадения единиц в одноименных разрядах регистров 8 и 14 рассмотренным образом, организуется очередной сдвиг кода регистра 8. С помощью элемента И 10 обеспечивается циклический сдвиг кода в регистре 8 путем передачи старшей единицы в младший его разряд.

Процесс циклического сдвига будет продолжаться до тех пор, пока не будет назначено требуемое число процессоров. В этом случае единичный сигнал с выхода элемента ШШ-НЕ 9 за- крывает цель циклического переноса и обеспечивает установку в нулевое состояние триггера 36.

Второй режим работы устройства организуется при поступлении сигналов отказов от распределения процессоров. Эти сигналы фиксируются в соответствующих разрядах регистра 27

отказов процессоров.

Режим перераспределения процессоров устанавливается триггером 18

после завершения распределения про цессоров, т.е. когда регистр сдвига окажется в нулевом состоянии, следующим образом.

В нулевом состоянии триггера 18

единичным сигналом с нулевого его выхода открыты элементы И 28, ем обеспечивается отслеживание сигналов отказов в регистре 29. После того, как регистр 8 окажется в нулевом состоянии, единичным сигналом с выхода элемента ИЛИ-НЕ 9 открываются элементы И 19, 20 и при наличии обобщенного сигнала отказа с выхода элемента ИЛИ 17 задержанным сигналом с

выхода элемента задержки 26 триггер 18 устанавливается в состояние 1 через элемент И 20.

После установки триггера 18 в состояние 1 блокируется передача

крываются элементы И 19 и 33.

сигналов отказов в регистр 29, крьшаются элементы И 24, 23, 3

сигналов отказов в регистр 29, за- крьшаются элементы И 24, 23, 3 и от-

В данном режиме определяется чис- ло отказавших процессоров при решении задачи с одним и тем же номером. Это обеспечивается следующим образом.

Посредством элементов И 30, включенных по приоритетной схеме с

выходами регистра 29, производится выбор старшего по приоритету процессора. При этом меньшей номер раэ- яда регистра 29 соответствует большему приоритету.

Выбранным сигналом приоритета разрешается передача кода номера задачи данного отказавшего процессора через соответствующий блок элементов И 31 на вторые группы входов схем сравнения 32, На первые входы схем сравнения 32 поступают двоичные коды номеров задач с первых групп выходов соответствующих регистров 2 хранения,

В схемах сравнения 32 производится сравнение кодов номеров задач с кодом номера задачи выбранного отказавшего процессора. При этом на выходах схем сравнения 32 формируется позиционный код числа процессоров, назначенных задаче с выбранным ноЫе- ром элементами И 31, С помощью элементов И 33 из сигналов схем сравнения 32 селектируются сигналы отказавших процессоров, зафиксированных в регистре, распределенных для решения задачи с одним и тем же номером.

По очередному импульсу генератора 34 через элемент И 21 при наличии свободных процессоров позиционный код числа отказавших процессоров через элементы И 33 и ИЛИ 7 передается в регистр 8 сдвига. Одновременно устанавливаются в состояние О соответствующие разряды регистра 29

Распределение , процессоров производится аналогично рассмотренно1 1у.

Если после передачи кода числа отказавших процессоров в регистр 8 сдвига и распределения свободных процессоров регистр 8 окажется в нулевом состоянии, то задержанным сигналом с выхода элемента задержки 25 через элемент И 19 триггер 18 устанавливается в состояние О,

По нулевому состоянию триггера 18 разрешается передача сигналов отказов из регистра 27 в регистр 29. Если имеются сигналы отказов, то задержанным сигналом с выхода элемента задержки триггер 18 снова устанавливается в состояние 1,

В дальнейшем устройство работает аналогично рассмотренному режиму перераспределения процессоров.

Если сигналы отказов отсутствуют, то триггер 18 остается в нулевом состоянии, а задержанным сигналом с Е1ьгхода элемента задержки 15 триггер 36 управления переводится в состояние О, подготавливая очередной цикл распределения процессоров,

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

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

элемента И первой группы, первая

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

выходов каждого регистра хранения группы соединена с группой входов одноименного блока элементов И второй группы, одноименные выходы группы выходов блоков элементов И первой группы соединены с группами входов одноименных элементов .ИЛИ первой группы, выходы которых соединены с группами входов блоков элементов И третьей группы, группа выхоДов каж : ого блока которой соединена с группой входов одноименного элемента ИЛИ третьей группы и с соответствующей группой выходов устройства, одноименные выходы группы выходов блоков элементов И второй, группы соединены с группами входов одноименных элементов ИЛИ второй группы, выходы элементов ИЛИ, второй группы соединены с группой информационных

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

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

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

О

5

0

5

.четвертым входам элементов И первой группы, к вторым входам элементов И второй группы, к первым входам элементов И четвертой группы и к второму входу шестого элемента И, единичный выход триггера режима соединен с вторыми входами элементов И третьего группы и с третьим входом четвертого элемента И, вторая группа сигнальных входов устройства соединена с единичными разрядными входами регистра отказов процессоров, выходы которого соединены с вторыми входами элементов И четвертой группы, выходы которых подключены к единичным входам одноименных разрядов буферного регистра, единичные выходы которого подключены к входам второго элемента ИЛИ, выход которого соединен с третьим входом пятого элемента И, единичный выход первого разряда буферного регистра подключен к третьему входу первого элемента И третьей группы и к входу первого блока элементов И четвертой группы, единичный выход i-ro разряда буферного регистра (,3,...n, п - число процессоров) подключен к первому входу (i-1)-ro элемента И пятой группы и к третьему входу i-ro элемента И третьей . группы, нулевой выход (i-l)-ro разряда буферного регистра подключен к соот

ветствующим входам (1-1)-го, (i-2)-ro,...,(п-1)-го элементов И пятой группы, выход j-ro элемента И пятой группы (J-1 ...п-1) соединен с входом i-ro блока элементов И четвертой группы, первая группа выходов каждого регистра хранения группы соединена с группой входов одноименного блока элементов И четвертой группы и первой группой входов одноименной схемы сравнения группы, вторая группа входов каждой схемы сравнения группы подключена к группе выходов одноименного блока элементов И четвертой группы, i-й выход группы выходов блока элементов И четвертой группы подключен к соответствующему входу i-ro элемента ИЛИ первой группы, выходы схем сравнения группы соединены с четвертыми входами одноименных элементов И третьей группы, выходы которых подключены к соответствующим входам одноименных элементов ИЛИ второй группы и к нулевым входам одноименных разрядов

9129032410

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

Изобретение относится к вычислительной технике и может быть использовано для построения многопроцессорных вычислительных систем. Цель изобретения - расширение функциональных возможностей устройства за счет учета групповых отказов процессоров в ходе решения задачи. Устройство содержит группу регистров хранения, регистр готовности, регистр сдвига, три группы элементов И, три группы блоков элементов И, четьфе элемента И, два элемента ИЛИ и четыре группы элементов ИЛИ. Новым в устройстве является использование регистра отказов процессоров, буферного регистра, двух групп элементов И, группы блоков элементов И, группы схем сравнения, группы элементов задержки, трех элементов задержки, триггера режима, триггера управления, элемента ИЛИ-НЕ, двух элементов И, генератора импульсов и их связей, что обеспечивает достижение цели изобретения. Устройство обеспечивает высокую достоверность при любом характере потока отказов процессоров. 1 ил. С/)

Редактор М.Бандура.

Составитель М.Кудряшев Техред А.Кравчук Корректор С .Черни

Заказ 7903/47Тираж 673 ,Подписное

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

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