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

 

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

союз советских

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

РЕСПУБЛИК (я)5 G 06 F 9/46

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4640502/24 (22) 20.01.89 (46) 15.07.91, Бюл. ¹ 26 (72) Д.В.Подколзин, С.В.Криштопа, А.B.Ëóговец, В,И.Каменский и С.Г.Баринов (53) 681.325 (088.8) (56) Авторское свидетельство СССР

¹ 866560, кл. G 06 F 9/46, 1979.

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

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

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

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

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

Устройство для распределения задач между процессорами содержит регистр 1 приема, элемент 2 задержки, блок 3 элементов И, триггер 4, элементы И 5 и 6, элемент

ИЛИ 7, элемент И 8, элемен; НЕ 9, элемент. Ж 1663611 Al если количество свободных процессоров меньше, чем требуемых, и обеспечения обслуживания задач отказавших процессоров в случае одновременного отказа этих процессоров. Устройство содержит регистр приема, группу регистров задач, регистр сдвига, регистр поиска. регистр отказов, регистр готовности, две группы блоков элементов И, четыре группы элементов ИЛИ, триггер, элемент задержки, элементы И, ИЛИ, НЕ. Входная заявка содержит информацию о номере задачи и количестве потребных для ее решения процессоров. . Устройство сопоставляет информацию о потребных процессорах с имеющимися ресурсами системы и распределяет задачу по процессорам. В случае единичного или группового отказа процессоров нерешенные задачи распределяются по свободным процессорам. 1 ил.

И 10, регистр 11 сдвига, элемент ИЛИ 12, элемент И 13, элемент НЕ 14, элементы ИЛИ

15 и 16, группу 17 элементов ИЛИ, регистр

18 поиска, группу 19 блоков элементов И, группу 20 регистров задач, группу 21 блоков элементов И, группу 22 элементов И, группу

23 элементов ИЛИ, регистр 24 готовности, регистр 25 отказов, группу 26 элементов

ИЛИ, группу 27 элементов ИЛИ, группу 28 элементов И, группы 29 и 30 сигнальных входов, группу 31 информационных входов, группу 32 информационных выходов и группу 33 сигнальных входов.

Устройство работает следующим образом, В исходном состоянии в первом разряде регистра 18 поиска записан единичный сигнал, все процессоры готовы к работе, а сле1663611 довательно, в регистре 24 готовности записаны единичные сигналы во все разряды по группе 30 входов, по этим же сигналам обнулены всв регистры задач группы 20, по группе 29 входов сигналов не поступало и 5 регистр 25 отказов находится в нулевом состоянии. С выходов регистра 24 готовности единичные сигналы поступают на соответствующие блоки 19 элементов И. Регистр 11 сдвига находится в нулевом состоянии, ну- 10 левой сигнал с выхода элемента ИЛИ 12 поступает на элемент HE 9, с которого единичный сигнал поступает на элемент И 8, остальные входы элемента И 8 соединены с, инверсными выходами регистра 25 отказов, 15 на которых везде присутствуют единичные потенциалы, элемент И 8 открыт, сигнал снего устанавливает триггер 4 в нулевое состояние, регистр 1 приема готов к приему информации, разрешения на сдвиг единич- 20 ного сигнала в регистре 18 поиска нет, так . как на прямых выходах регистра 25 отказов находятся нулевые уровни сигналов, В процессе работы с процессоров могут поступать сигналы готовности к выполнению 25 задач по rpyrtne 30 входов и сигналы отказов по rpynrte 29 входов в виде коротких единичных сигналов.

Очередь задач устанавливается планов— .щиком и находится в запоминающем уст- 30 ройствв, откуда задачи в порядке очереди поступают на регистр 1 приема по сигналу разрешения записи в регистр приема, поступающему с выхода элемента И 8, так как на входданного элемента подаются единич- 35 ные уровни со всех выходов группы инверсных выходов регистра 25 отказов вследствие отсутствия отказавших процессоров. Заявка представляет собой совокупность кода номера задачи и кода числа 40 потребных процессоров, представляющих собой позиционный код, где число единиц соответствует количеству потреб н ых и роцессоров, С групп выходов регистра 1 приема код номера задачи поступает на группу 45

17 элементов ИЛИ, с их выходов — на группу блоков 19 элементов И, а код количества потребных процессоров поступает на входы блока 3 элементов И и далее записывается в регистр 11 сдвига через элемент ИЛИ 7, 50 стоящий в младшем разряде группы входов регистра 11 сдвига. После записи кода потребных процессоров на регистр 11 сдвига данный код появляется на его выходах группы выходов в виде единичных уровней в 55 соответствующих разрядах, затем эти уровни подаются на элемент ИЛИ 12, и выходной сигнал с него разрешает сдвиг содержимого регистра 11 сдвига. Одновременно сигналы с выходов регистра 11 сдвига поступают на соответствующие блоки 19 элементов И. При этом те блоки, на которые поступили единичные сигналы от регистра

11 сдвига и регистра 24 готовности. открываются и разрешают запись кода номера задачи по группе 32 выходов на нужный свободный процессор (процессоры), причем одновременно происходят запись кода номера задачи на соответствующий регистр задачи группы 20 регистров задач и обнуление через элементы группы 23 элементов

ИЛИ соответствующего разряда регистра

24 готовности и регистра 11 сдвига, После того, как все разряды регистра 11 сдвига откажутся бнуленными. т,е. заявка распределена, единичный сигнал с выхода элемента И 8 разрешает запись на регистр 1 приема очередной задачи. Злемент 2 задержки предназначен для того., чтобы вследствие разного быстродействия регистра 1 приема и элементов И группы 3 элементов

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

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

-кода номера задачи по группе 32 выходов устройства через определенный блок элементов И группы 19 на этот процессор и определенный регистр задачи группы 20, а также обнуление разрядов в регистре 24 готовности и регистре 11 сдвига, В процессе работы устройства процессоры освобождаются по мере решения задач и импульсы готовности от процессоров, поступающие по соответствующим входам группы 30 входов, записываются а соответствующие разряды регисгра 24 готовности и обнуляют содержимое по старой задаче соответствующего регистра задачи группы 20 регистров задач, подготавливая регистр задачи для приема кода номера задачи очередной заявки.

8 процессе работы устройства могут происходить как единичные, так и массовые отказы процессоров, причем этот процессор (процессоры) мажет быть занят решени1663611

1 ем задачи, а может находится и в режиме ожидания новой задачи. Рассмотрим случай, когда отказывает процессор (процессоры), занятый решением задачи. В ходе распределения задачи при отказе процессора сигнал отказа поступает по соответствующему входу группы 29 входов на соответствующий элемент И группы 28 элементов И, а так как есть разрешающие сигналы с выходов соответствующих элементов ИЛИ группы 27, на входы которых поступает ненулевое содержимое регистров задач группы 20 регистров задач, в которых записаны коды номеров решаемых задач, то с выхода соответствующего (или соответствующих при групповом отказе процессоров) элемента И группы 28 элементов И единица записывается в определенный разряд.

Рассмотрим групповой отказ, т.е. в регистре 25 отказов записано несколько единичных сигналов, С группы инверсных выходов регистра

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

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

6 и 13 и разрешает циклический сдвиг единичного сигнала в регистре 18 поиска.

По окончании распределения текущей заявки на группе выходов регистра 11.сдвига появляются нулевые потенциалы, а на выходе элемента НЕ 9 — единичный сигнал, который разрешает запись единичного сигнала с выхода элемента И 13 через элемент

ИЛИ 7 в младший разряд регистра 11 сдвига. Одновременно единичный сигнал с элемента НЕ 9 поступает на элементы И 8 и 6, Но так как элемент И 8 закрыт, а на элемент

И 6 поступает разрешающий сигнал с элемента ИЛИ 16, то с выхода элемента И 6 этот сигнал устанавливает триггер 4 в единичное состояние. Данный сигнал является стирающим для регистра 1 приема, т.е. происходит чистка регистра 1 приема, B это время на выходах регистра 11 сдвига появляется единичный сигнал в одном из разрядов, при этом нулевой сигнал с элемента НЕ 9 закрывает элемент И 13, чтобы во время циклического сдвига содержимого регистра 11 сдвига на его вход не поступала информация с элемента ИЛИ 7. Два единичных сигнала с выхода триггера 4 и с выхода - элемента ИЛИ 12 открывают элемент И5, единичный сигнал с которого будет присут. ствовать на синхровходе по обнулению ре.элемента И 5 поступает на вход синхронизации регистра 25 отказов, и по нулевому

55 перепаду обнуляется тот разряд, где находится единичный сигнал с выхода элемента

И группы 22 элементов И. Одновременно единичный сигнал с элемента НЕ 9 поступает на элемент И 13. Как только код номера задачи исчезнет с выходов группы 17 эле5

45 гистра 25 отказов до тех пор, пока есть единичный сигнал на выходах регистра 11 сдвига. Единичный сигнал с выхода триггера 4 обеспечивает работу группы 22 элементов

И. Как только единичный сигнал с группы выходов регистра 18 поиска поступит на тот элемент И группы 22 элементов И, на другом входе которого присутствует единичный сигнал с одного из прямых выходов регистра 25 отказов, единичный сигнал этого элемента И группы 22 элементов И прекращает циклический сдвиг содержимого регистра

18 описка, также единичный сигнал с данного элемента И группы 22 элементов И поступает на соответствующий вход группы входов обнуления Ilo синхроимпульсу, при этом данный разряд обнуляется по окончании распределения данной задачи по синхроимпульсу, Кроме того, единичный сигнал с этого момента И группы 22 элементов И поступает на элемент ИЛИ 15, с выхода элемента ИЛИ 15 — на вход элемента НЕ 14, с выхода которого нулевой сигнал закрывает элемент И 13. чтобы до тех пор, пока есть единичный сигнал с данного элемента И группы 22 элементов И, а следовательно. пока присутствует код номера задачи на входах блоков 19 элементов И после ее распределения (после исчезновения единичного сигнала с выходов регистра 11 сдвига) за счет неравномерной глубины схемы, не записать в регистр 11 сдвига в младший разряд единичный (чтобы не распределить вновь старую задачу) сигнал, По разрешающему сигналу с соответствующего элемента И группы 22 элементов И открывается один из блоков группы 21 блоков элементов И и код номера отказавшей задачи через этот блок поступает на группу

17 элементов ИЛИ с группы выходов соответствующего регистра задачи группы 20 регистров задач, с выходов группы 17 элементов ИЛИ код номера этой задачи поступает на входы блоков 19 элементов И, и происходит распределение задачи на процессоры, как и при работе без отказавших процессоров. Как только код номера задачи будет распределен, на выходах группы выходов регистра 11 сдвига появляются нулевые сигналы, при этом с выхода элемента

ИЛИ 12 нулевой сигнал поступает на элементы НЕ 9 и И 5. Нулевой перепад с выхода

1663611 ментов ИЛИ, с выхода элемента И 13 произойдет запись очередного единичного сигнала в регистр 11 сдвига через элемент ИЛИ

7. Нулевые сигналы с выходов элементов И группы 22 элементов И разрешают циклический сдвиг единичного сигнала в регистре

18 поиска. Если в регистре 25 отказов записаны единичные сигналы, то обработка задач отказавших процессоров протекает аналогично описанному выше.

В случае распределения последней задачи отказавших процессоров после синхроимпульса с выхода элемента И 5 ка прямых выходах регистра 25 отказов окажутся все нулевые сигналы, элемент И 8 откроется, когда на него поступят единичный сигнал с выхода элемента НЕ 9 и все единичные сигналы с группы инверсных выходов регистра 25 отказов, при этом единичный сигнал с выхода элемента И 8 обнулит триггер 4 и разрешит запись на регистр 1 приема очередной заявки. 8 это время нулевой сигнал с выхода элемента ИЛИ 16 поступит на элемент И 13 быстрее. чем единичный сигнал с элемента НЕ 14 за счет различной глубины прохождения сигнала, что предотвратит запись единичного сигнала с выхода элемента И 13 через элемент.

ИЛИ 7 в младший разряд регистра 11 сдвига.

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

16 прекращает циклический сдвиг содержимого регистра 18 поиска и подает запрещающий нулевой сигкал ка элемент И 6.

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

Рассмотрим. случай, когда отказывают процессора, ке занятые решением задачи. находящейся в режиме ожидания. Сигналы отказа поступают по группе 29 входов «л обкуляют соответствующие разряды регистра 24 готовности через элементы группы

26 элементов ИЛИ, чтобы задача не распределилась ка отказавшие процессоры. Одновременно эти поступившие сигналы отказов поступают на один из входов элементов И группы 28 элементов И, Но в регистрах задач группы 20 регистров задач отказавших процессоров информация не записана (она обнулена предшествовавшим отказу сигналом готовности с процессоров), и на выходах соответствующих элементов MJlM группы 27 элементов ИЛИ присутствуют нулевые сигналы, которые запрещают запись сигналов отказа на регистр 25 отказов, чтобы устройство не работало вхолостую. В процессе работы процессоры могут восстанавливать своб работоспособность, при этом сигналы готовности по группе 30 входов записываются в регистр 24 готовности и обнуляют содержимое соответствующих регистров задач группы 20 регистров задач, подготавливая их к приему новой задачи. °

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

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

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

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

1663б11

10 с выходами одноименных блоков элементов

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

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

ИЛИ и тактовым входом регистра сдвига.

20 выходом четвертого элемента И, а также с

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

5

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

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

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

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

Техред М,Моргентал Корректор С.Шевкун

Редактор А,Лежнина

Производственно-издательский комбинат "Патент", г. Ужгород, ул,Гагарина, 101

Заказ 2266 Тираж 407 Подписное

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

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