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

 

УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ ЗАДАЧ МЕЖДУ ПРОЦЕССОРАМИ, содержащее регистр готовности процессоров, элемент ИЛИ, п блоков элементов И, где п - число процессоров, группу элементов И, элемент И и группу регистров хранения, причем первая группа информационных входов первого регистра хранения группы является первой группой информационных входов устрой- . ства,вторая группа информационных входов первого регистра хранения группы является второй группой информационных входов устройства, управляющий вход каждого регистра хранения группы соединен с выходом соответствующего элемента И группы, первая и вторая группы вькодов каждого регистра хранения группы, кроме последнего, соединены соответственно с первой и второй группами информационных входов последующего регистра хранения группы, первая группа выходов последнего регистра хранения группы соединена с группой информационных входов каждого блока элементов И, группа выходов каждого блока элементов И подключена к.одноименной группе информационных выходов устройства, группа информационных входов регистра готовности процессоров соединена с группой сигнальных входов устройства,первые входы элементов И группы объеди-, нены между собой, отличающее с я тем, что, с целью повышения быстродействия устройства за счет организации параллельного распределения задач между процессорами, в него введены коммутатор, элемент ИЛИ-НЕ, формирователь импульсов, причем группа информационных входов коммутатора подключена к группе выходов последнего регистра хранения группы, группа управляющих входов коммутатора подключена к группе выходов регистра готовности процессоров и входам элемента ИЛИ, каждьй выход первой группы выходов коммутатора подключен к соответствующему входу группы обнуляющих входов регистра готовности процессо .ров и к. управляющему входу соответствующего блока элементов И, вторая группа выходов коммутатора подключена к входам элемента ШТИ-НЕ,. выход кото s| рого подключен к управляющему входу :о регистра готовности процессоров и первому входу последнего элемента И группы, второй вход которого подключен к выходу элемента ШШ, а выход - к первому входу элемента И, второй вход которого подключен к выходу младщего разряда последнего регистра хранения группы, а выход к входу формирователя импульсов, выход которого подключен к последнему входу элемента ИПИ-НЕ, выход каждого элемента И группы, начиная , с последнего, подключен к второьсу входу предьдущего элемента И группы.

СОЮЗ С08ЕТСКИХ

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

РЕСПУБЛИК (19) (I I) 006F 4

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

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

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

ПО ДЕЛАМ ИЭОБРЕТЕКИЙ И ОТКРЫТИЙ (21) 3703892/24-24 (22) 23.02.84 (46) 07.08.85. Вюл. 9 29 . (72) А.Я.Матов, С.Е.Карловский, В.Д.Костюченко и В.М.Прохоров (53) 68 1.325 (088.8) (56) Авторское свидетельство СССР

N - 903875, кл. G 06 F 9/00, 1982.

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

Ф 866560, кл. G 06 Г 9/46, 1981. (54)(57) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ ЗАДАЧ МЕЖДУ ПРОЦЕССОРАМИ, содерmagee регистр готовности процессоров, элемент ИЛИ, п блоков элементов И, где п — число процессоров, группу элементов И, элемент И и группу ре" гистров хранения, причем первая группа информационных входов первого регистра хранения группы является первой группой информационных входов устройства, вторая группа информационных входов первого регистра хранения группы является второй группой информационных входов устройства, управляющий вход каждого регистра хранения группы соединен с выходом соответствующего элемента И группы, первая и вторая группы выходов каждого регистра хранения группы, кроме последнего, соединены соответственно с первой и второй группами информационных входов последующего регистра хранения группы, первая группа выходов последнего регистра хранения группы соединена с группой информационных входов каждого блока элементов И, группа выходов каждого блока элементов И подключена к одноименной группе информационных выходов устройства, группа информационных входов регистра готовности процессоров соединена с группой сигнальных входов устройства,первые входы элементов И группы обьеди-, нены между собой, о т л и ч а ю щ е е» с я тем, что, с целью повышения быстродействия устройства за счет организации параллельного распределения задач между процессорами, в него введены коммутатор, элемент ИЛИ-HE формирователь импульсов, причем группа информационных входов коммутатора подключена к группе выходов последнего регистра. хранения группы, группа управляющих входов коммутатора под- Я ключена к группе выходов регистра готовности процессоров и входам элемента ИЛИ, каждый выход первой группы выходов коммутатора подключен к соответствующему входу группы обнуляющих входов регистра готовности процессоров и к. управляющему входу соответствующего блока элементов И, вторая группа выходов коммутатора подключена к входам элемента ИЛИ-НЕ,. выход которого подключен к управляющему входу регйстра готовности процессоров и первому входу последнего элемента

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

l 117179

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

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

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

Устройство содержит первую группу информационных входов 1 устройства, вторую группу информационных входов 2 устройствр, группу регистров. 3 хранения, группу элементов И

4, коммутатор 5, группу информационных входов 6 коммутатора 5, группу входов 7 коммутатора 5, первую группу выходов 8 коммутатора 5, вторую рр группу выходов 9 коммутатора 5, элемент ИЛИ-НЕ 10, элемент ИЛИ 11, регистр 12 готовности процессоров, блок элементов И 13,группы информационных выходов 14 устройства, группу сигнальных входов 15 устройства.

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

В исходном состоянии информация о задачах на группах информационных входов . и 2 устройства отсутствует, Регистры 3 хранения группы обнулены, на входах 6 и выходах 8 и 9 коммутатора 5 действуют нулевые сигналы. Поскольку на

35 выходах 8 коммутатора 5 нулевая информация, то нулевые сигналы действуют на управляющих входах блоков элементов И 13 и на группе входов сброса регистра 12 готовности про- 4О цессоров. Так как .все процессоры свободны, то регистр 12 готовности процессоров заполнен нулями и на группе его выходов, следовательно, на входах элемента ИЛИ 11 и на груп-45 пе входов 7 коммутатора 5 действуют единичные сигналы. Единичный сигнал с выхода элемента ИЛИ 11 поступает на второй вход последнего элемента

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

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

Нулевой сигнал с выхода элемента И 15 поступает на вход формирователя 16, с выхода которого нулевой сигнал подается на последний вход элемента ИЛИНЕ 10. Нулевые сигналы с первой группы входов последнего регистра 3 хранения группы поступают на группы информационных. входов каждого блока элементов И 13 группы и на группу выходов 14.

Программа "Планировщик операционной системы" (ЭПП ОС) строит упоря- доченный по приоритетам список задач и выдает информацию о задачах на первую и вторую группу информационных входов 1 и 2 устройства, причем на первую группу выдается номер задачи, а на вторую — количество потребных для ее решения процессоров в позиционном коде. Так как на управляющих входах регистров 3 хранения действуют единичные сигналы с выходов соответствующих элементов И, то информация о задачах последовательно переписывается с регистра на регистр. Первая задача, поступающая в устройство для распределения, записывается в последний регистр 3 хранения, предпоследняя — в первый регистр хранения, а последняя остается на первой и второй группах информационных входов 1 и 2 устройства.

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

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

20

3 зиционный код количества потребных для решения задачи процессоров с второй группы выходов последнего регистра 3 хранения подается на группу информационных входов 6 коммутатора 5. Так как для решения задачи всегда требуется минимум один процессор, то на выходе младшего разряда последнего регистра 3 õðàнения и, следовательно, на входе 6 коммутатора 5 при поступлении на распределение любой задачи всегда будет единичный сигнал, который поступает на второй вход элемента

И 15, на первом входе которого действует единичный сигнал с выхода элемента И 4, единичный сигнал с выхода элемента И l5 подается на вход формирователя 16.

Единичный сигнал с выхода формирователя 16 поступает на последний вход элемента ИЛИ-НЕ 10. На выходе элемента ИЛИ-НЕ 10 устанавливается нулевой сигнал, который подается

25 на первые входы всех элементов И 4, закрывая их, Нулевые сигналы с выходов элементов И 4 поступают на управ. ляющие входы соответствующих регистров 3 хранения, блокируя дальнейший сдвиг информации по регистрам. Одно30 временно нулевой сигнал с выхода элемента ИЛИ-НЕ 10 подается на управ,ляющий вход регистра 12 готовности процессоров, с выхода которого информация о наличии свободных процессоров, выдаваемая в позиционном коде, поступает на группу входов 7 коммутатора 5 и на входы элемента ИЛИ 11.

Единичные сигналы с выходов 8 коммутатора 5 поступают на управляю- 4О щий вход соответствующего блока элементов И 13 и на информационные входы триггеров регистра 12 готовности процессоров, соответствующих назначенн м на реше ие задачи процессорам. 45

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

По окончании цикла распределения единичный сигнал с выхода формирователя 16 снимается и, если требования задачи полностью удовлетворе" ны, т.е. нет единичных сигналов на выходах 9 коммутатора 5, на выходе

1791 4 элемента ИЛИ-НЕ 10 появляется единичный сигнал, который подается на

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

И 4 действуют единичные сигналы.

Единичный сигнал с выхода элемента

И 4 поступает на управляющий вход последнего регистра 3 хранения, осуществляя сброс информации, и одновременно подается на второй вход предпоследнего элемента И 4, на первом входе которого действует единичный сигнал с выхода элемента ИЛИ-НЕ

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

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

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

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

1 171791

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

Редактор Л.Гратилло Техред Л.Мартяшова

Корректор Л. Пилипенко

Заказ 4864/41 Тираж 710

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

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

Подписное

Филиал ППП "Патент", r.Óæãîðoä, ул.Проектная,4 на каком-либо выходе 9 коммутатора 5, на выходе элемента ИЛИ-НЕ 10 будет нулевой сигнал, который подается на первый вход последнего элемента И 4, блокируя поступление на распределение следующей задачи. Так как мультипроцессорная система загружается задачами различной временной степени трудности поочередно, то процессоры закан- 10 чивают решение задач динамично. После окончания решения какой-либо задачи

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

15 подается на соответствующий вход группы входов регистра 12 готовности процессоров. Единичный сигнал с выхода последнего поступает на вход 7 распределяющего блока 5 и на вход элемента ИЛИ 11, с выхода которого он подается на второй вход последнего элемента И 4. Наличие единичного сигнала на входе 7 позволяет назначить освободившийся процессор на решение перераспределенной задачи. Назначение производится описанным образом.

По окончании распределения всего списка заданий устройство возвращается в исходное состояние.

Применение предлагаемого изобретения позволяет повысить быстродействие устройства.