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

 

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

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

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

РЕСПУБИИН (19) (11) (51)4 G 06F 9 46

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

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

ПРИ ГКНТ СССР

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

К А BTOPCHOMY СВИДЕТЕЛЬСТВУ вЂ” "" " - - ) (61) 957211 (21) 4292781/24-24 (22) 03.08.87 (46) 23.05.89. Бюл. № !9 (72) А. Я. Матов, И. М. Якуб, В. И. Петров и А. Н. Башкиров (53) 681.325 (088.8) (56) Авторское свидетельство СССР № 957211, кл. G 06 F 9/46, 1981. (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ ЗАДАНИЙ ПРОЦЕССОРАМ (57) Изобретение относится к вычислительной технике и может быть использовано в многопроцессорных системах для распределения заданий между процессорами. Цель изобретения — повышение быстродействия.

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

Цель изобретения — повышение быстродействия устройства.

На фиг. 1 показана структурная схема устройства; на фиг. 2 — схема блока управления.

Устройство содержит блок I управления, регистр 2 готовности процессоров, элемент ИЛИ 3, первый регистр 4 сдвига, первую группу элементов И 5, первую группу элементов ИЛИ 6, процессоры 7, группы кодовых входов 8 устройства, группы кодовых входов 9 устройства, формирователь 10 импульсов, группы кодовых входов 11 устройства, регистры 12 номера задания, группу схем 13 сравнения, третью группу элементов И 14, группу элементов 15 запрета, вторую группу элементов И 16, вторую группу элементов ИЛИ 17, второй

Цель достигается введением группы регистров, трех блоков элементов ИЛ И, формирователя импульсов, группы триггеров, шестой группы элементов И, генератора импульсов, третьего регистра сдвига, третьего элемента И, группы блоков элементов И, обеспечивающих циклический опрос и анализ информации об имеющихся заданиях. В устройстве организуется очередь заданий и поиска в ней задач, для которых число потребных процессоров меньше или равно числу свободных процессоров в системе. За счет этого сокращается время простоя процессоров. При этом в первую очередь выделяются процессоры, выполнившие задание, непосредствен но предшеству ющее да иному. 2 ил. регистр 18 сдвига, блок управления содержит схему 19 сравнения, первый элемент НЕ 20, пусковой триггер 21, генератор 22 импульсов, второй элемент НЕ 23, первый элемент

24 задержки, первый элемент И 25, триггер 26 управления, второй элемент 27 задержки, второй элемент И 28, группу сумматоров по модулю два 29, шифратор 30, вторую схему 31 сравнения, третий элемент HE 32, пятую и четвертую группы элементов И 33 и 34, третью группу элементов ИЛИ 35, первую группу входов 36 сравнения, выход 37 запрета, вторую группу входов 38, третью группу входов 39 сравнения, первый вход 40, первую группу выходов 41, первый управляющий выход 42, выход 43 синхронизации, вторую группу выходов 44, второй управляющий выход 45, устройство включает в себя также группу сигнальных входов 46 устройства, группу сигнальных выходов 47 устройства, генератор 48 импульсов, группу триггеров 49, группу регистров 50, третий элемент И 51, третий регистр 52 сдвига, шестую группу

1481762 элементов И 53, группу блоков элементов

И 54, первый блок элементов ИЛИ 55, второй блок элементов ИЛИ 56, третий блок элементов ИЛИ 57.

Устройство работает следующим образом, Наличие единичных сигналов на сигнальных выходах 47 устройства свидетельствует о том, что соответствующие регистры 50 свободны и готовы к приему информации об очередном задании. Если очередное задание готово, то код номера задания, код номера задания предшествующего дан. ному и число процессоров, требуемых для

его реализации, поступают на один из свободных регистров 50, причем.одновременно единичный сигнал поступает на соответствующий сигнальный вход 46 устройства, переводя соответствующий триггер 49 в единичное состояние и обеспечивая низкий потенциал на его выходе 47, который свидетельствует о занятости данного регистра хранения. Исход:.ая информация о задании записывается в регистр 50 через группы входов 8, 9, 11, причем по группе входов 8 поступает код числа процессоров, необходимых для решения задания, по входу 9 — код номера задания, по входу 11 — код номера задания, предшествующего данному.

На одном из выходов регистра 52 сдвига действует единичный сигнал, поступающий на первый вход соответствующего элемента И 53 группы и на управляющий вход соответствующего блока элементов И 54, с первой группы выходов которого код номера предыдушего задания поступает на соответствующую группу входов блока элементов ИЛИ 55, с выходов которого этот код поступает на первые входы группы схем 13 сравнения. Со второй группы выходов блока элементов И 54 код номера задания поступает через блок элементов

ИЛИ 56 на первые входы блоков элементов И 5 и 16, с третьей группы выходов блока элементов ИЛИ 54 код необходимого числа процессоров через блок элементов ИЛИ 57 поступает на первую группу входов 36 сравнения блока 1 управления, на вторую группу входов 39 сравнения блока 1 поступает код числа свободных процессоров не меньше, чем требуется для выполнения задания, на выходе схемы 19 сравнения появится сигнал, устанавливающий триггер 21 в единичное состояние. Сигнал с выхода триггера 21 устанавливает в единичное состояние триггер 26. При этом на первом управляющем выходе 42 блока 1 появляется сигнал записи кода с выходов элемента ИЛИ 35 в регистр 4 сдвига. Количество необходимых для выполнения процессоров отражается количеством единиц в соответствуюших разрядах входов 8. Соответственно

55 по входу 9 на группы элементов И 5 и 16 поступает код номера задания, которое должны отрабатывать выбранные процессоры, а по входам 11 на элементы 13 сравнения подается код номера задания, непосредственно предшествующего данному.

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

15 запрета появляются сигналы, образующие коды количества свободных процессоров. Номер элемента 15 запрета определяется совпадением единичных разрядов в регистре 2 готовности и нулевых сигналов, вырабатываемых элементами И 14. Код количества процессоров, выполнивших непосредственно предшествующее задание, с выходов элементов И 14 поступает на входы шифратора 30, а с его выходов подается на входы соответствующих сумматоров 29 по модулю два и схемы 3! сравнения.

Если для выполнения задания потребуется количество процессоров, не превышающих количество процессоров, выполнивших предыдушее задание, схема 31 сравнения сигнал не вырабатывает. При этом на выходе элемента HE 32 появляется сигнал, разрешающий выдачу кода числа необходимых процессоров с входов 8 через элементы И 34 и ИЛИ 35 на информационные входы регистра 4 сдвига. С появлением сигнала на выходе элемента 24 задержки происходит сброс триггера 26 и снятие сигнала записи кода в регистр 4 сдвига.

После записи кода в регистр 4 сдвига на выходах определенных элементов И 5 группы определяется совпадением одноименных единичных сигналов с разрядом регистра 4 сдвига и выходом элементов И 14.

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

18. Если при этом - в регистре 4 сдвига остались единичные разряды, о чем свидетельствует сигнал на выходе элемента

ИЛИ 3, то триггер 21 остается в единичном состоянии. В этом случае импульсы сдвига, вырабатываемые генератором 22 импульсов, поступают через элемент И 25, элемент 26

1481762

1О !

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

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

Если необходимое число процессоров превышает количество процессоров, завершивших выполнение непосредственно предшествующего задания, то, кроме регистра 4 сдвига, в устройстве используется дополнительный регистр 18 сдвига для одновременного распределения заданий на любые свободные процессоры. В этом случае сигнал с выхода схемы 31 сравнения разрешает выдачу в регистр 4 сдвига кода количества процессоров, завершивших выполнение задания, непосредственно предшествующего данному. При наличии этого сигнала на выходе элемента И 28 появляется сигнал, поступающий в регистр 18 сдвига и разрешающий прием кода с выходов группы сумматоров 29 по модулю два. Количество единиц в этом коде равно разности между количеством необходимых и свободных процессоров, выполнивших предыдущее задание.

Теперь п ри сдвиге кода в регистре 4 сдвига и в регистре 18 сдвига код номера задания появится на выходе соответствующих групп элементов И 5 и 16. При совпадении одноименных единичных разрядов в регистре 4 сдвига и сигналов на выходах элементов И 16 код номера задания выдается в соответствующие процессоры 7 и регистры 12, а через элементы ИЛИ 6 обнуляет соответствующие разряды регистров 2, 4 и 18. При обнулении всех разрядов регистра 4 сдвига и регистра 18 сдвига сигнал с выхода элемента ИЛИ 3 снимается. По отрицательному перепаду на выходе элемента ИЛИ 3 срабатывает формирователь 10, сигнал с его выхода поступает на вторые входы всех элементов И 53.

Этот единичный сигнал пройдет через тот элемент И 53, на первом входе которого действует единичный сигнал с выхода регистра 52, т. е. через элемент И 53, соответствующий назначенному заданию. Выходным сигналом элемента И 53 сбросятся в нулевое состояние соответствующий триггер 49, регистр 50. На сигнальном выходе

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

В результате обнуления регистра 50 хранения будут сняты сигналы с выходов блоков элементов ИЛИ 55 и 57. Нулевые сигналы с их выходов определяют низкие потенциалы на выходах схем 13 сравнения и затем на выходах группы элементов

И 14. На входах 36 и 38 блока управления будут нулевые значения кода свободных и потребных процессоров и схема 19 сравнения сигнал на выход не выдает, поэтому на выходе элемента НЕ 29 блока управления будет высокий потенциал, поступающий на выход 37 запрета блока управления и далее на второй вход элемента И 51, разрешая прохождение тактового импульса

ГТИ 48 на вход третьего сдвигового регистра 52. В результате сдвига анализируется задание, находящееся в очередном по порядку регистре 50 хранения.

Если число свободных процессоров меньше количества потребных, то схема 19 сравнения блока управления также не выдаст сигнала на выходе и схема будет работать аналогично описанному.

Такой просмотр осуществляется до тех пор„пока не найдено задание, для которого число потребных процессоров меньше или равно числу свободных. Период следования импульсов генератора 48 выбирается из условия достаточности времени для сдвига в регистре 52, срабатывания блока элементов

И 54, блока элементов ИЛИ 57 и блока 1 в части сравнения кодов с входов 36 и 39.

Фо р щ.:г а и зоб гге тен а»

Устройство для распределения заданий процессорам по авт. св. Хо 957211, отлпчаюигееея тем, что, с целью повышения быстродействия, в него введены группа триггеров, генератор импульсов, группа регистров, третий элемент И, третий регистр сдвига, шестая группа элементов И, группа блоков элементов И, первый, второй и третий блоки элементов ИЛИ и формирователь импульсов, причем каждый сигнальный вход устройства соединен с входом установки в «1» одноименного триггера группы, инверсный выход каждого из которых соеди= нен с одноименным сигнальным выходом устройства, первая группа входов каждого регистра группы соединена с первой группой кодовых входов устройства, вторая группа входов каждого регистра группы соединена с второй группой кодовых входов устройства, третья группа входов каждого регистра группы соединена с третьей группой кодовых входов устройства, вход сброса каждого регистра группы соединен с входом установки в «О» одноименного триггера группы и с выходом одноименного элемента И шестой группы, первый вход каждого из которых соединен с одноименным выходом третьего регистра сдвига и с управляющим входом одноименного блока элементов И группы, группа информационных входов каждого из которых соединена с группой выходов одноименного регистра группы, вторые входы всех элементов И шестой группы соединены с выходом формирователя импуль1481762

Фиг. 1 сов, вход которого соединен с выходом элемента ИЛИ, выход генератора импульсов соединен с первым входом третьего элемента И, второй вход которого соединен с выходом запрета блока управления, выход третьего элемента И соединен с входом сдвига третьего регистра сдвига, выход старшего разряда которого соединен с входами младшего разряда этого же регистра, входы первого блока элементов ИЛИ соединены с первыми группами выходов блоков элементов И группы, выходы первого блока элементов ИЛИ соединены с первыми входами схем сравнения группы, входы второго блока элементов ИЛИ соединены с вторыми группами выходов блоков элементов И группы, выходы второго блока элементов ИЛИ соединены с первы ми входами элементов И первой и второй групп, входы третьего блока элементов ИЛИ соединены с третьими группами выходов блоков

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

481762

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

Редактор С. Патрушева Техред И. Верес Корректор М. Васильева

Заказ 2691/50 Тираж 669 Подписное

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

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

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