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

 

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

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

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

РЕСПУБЛИК

Ш4 С 06 Р 9/46

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

К АВТОРСКОМ,Ф СВИДЕТЕЛЬСТВУ

4ь

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21).3929064/24-24 (22) 11.07.85 (46) 15.02.87 Бюл. В 6 (72) A.Х.Ганитулин и В.Г.Попов (53) 681.325(088.8) (56) Авторское свидетельство СССР

В 1151966, кл. G 06 F 9/46, 1983.

Авторское свидетельство СССР

В 1151965, кл. G 06 F 9/46, 1983. (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ

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

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

„.Я0„„129О324 И

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

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

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

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

Устройство содержит группу входов 1 заявок устройства, группу регистров 2 хранения, группу элементов

И 3, группу блоков элементов И 4, f5 группу блоков элементов И 5, группу элементов ИЛИ 6, группу элементов

ИЛИ 7, регистр 8 сдвига, элемент

HJIH-HE 9, элемент И 10, группу блоков элементов И 11, группу элемен- 20 тов ИЛИ 12, группу информационных выходов 13 устройства, регистр 14 готовности, элемент задержки 15, элемент ИЛИ 16, элемент ИЛИ 17, триггер 18 режима, элемент И 19, элемент

И 20, элемент И 21, элемент И 22, группу элементов И 23, элемент И 24, элемент задержки 25, элемент задержки 26, регистр 27 отказов процессоров, группу элементов И 28, буферный регистр 29, группу элементов И 30, группу блоков элементов И 31, группу схем сравнения 32, группу элементов И 33, генератор 34 импульсов, группу элементов задержки 35, триг- 35 гер 36 управления, сигнальный выход

37 устройства, вход 38 запуска устройства, группы сигнальных входов

39, 40 устройства.

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

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

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

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

4 2

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

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

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

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

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

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

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

l э3 элемента ИЛИ 16 открыт элемент И 21, по соответствующим входам элементы

И 3 и через элементы И 23 — блоки элементов И 4.

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

Через некоторое время, определяемое элементом задержки 35, код количества потребных процессоров через соответствующие б3!оки элементов И 5 и элементы ИЛИ 7 передается в регистр 8 сдвига. Время задержки элементами задержки 35 определяется временем переходных процессоров в регистрах 2.

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

И 10.

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

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

3 12903 ствующему количеству единиц кода регистра 8, то код номера задачи из регистров 2 хранения через открытые элементы И 4 соответствующих блоков, элементы ИЛИ 6 и группу блоков эле5 ментов И 11 поступает на выходы 13.

Одновременно, единичные сигналы с выходов соответствующих элементов

ИЛИ 12 устанавливают в нулевое состояние одноименные разряды регистров 10

8 и 14. При этом регистр 8 оказывается в нулевом состоянии.

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

В первом случае, когда все разряды регистра. 8 установлены в состояние 25

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

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

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

Во втором случае, когда в регистре 8 на все разряды установле- 45 ны в состояние ™О", на выходе элемента ИЛИ-НЕ 9 формируется нулевое сигнал, закрывающий элементы И 3, 20 и 24 и открывающий по инверсным входам элементы И 22 и 10. Так как эле- 50 .мент И 24 закрыт, то задержанный сигнал с выхода элемента задержки 15 не изменяет состояние триггера 36 °

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

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

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

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

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

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

18 устанавливается в состояние "1" через элемент И 20.

После установки триггера 18 в состояние " 1" блокируется передача сигналов отказов в регистр 29, закрываются элементы И 24, 23, 3 и открываются элементы И 19 и 33.

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

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

129032ч

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

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

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

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

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

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

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

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

Если сигналы отказов отсутствуют, то триггер 18 остается в нулевом состоянии, а задержанным сигналом с выхода элемента задержки 15 триггер Зб управления переводится в состсяние "0", подготавливая очередчой цикл распределения процессоров.

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

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

1290324

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

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

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

1 соответствующему входу z-го элемента

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

9 1290324 регистра отказов процессоров, выход каждого элемента И первой группы чеГ рез одноименный элемент задержки группы подключен к входу одноименного

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

Составитель M.Êóäðÿøåâ

Техред А. Кравчук Корректор С.Черни

Редактор N.Áàíäóðà.

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

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

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

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