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

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

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

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

Устройство содержит блок 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 задержки, второй элемент И 28, группу сумматоров по модулю два 29, шифратор 30, вторую схему 31 сравнения, третий элемент НЕ 32, пятую и четвертую группы элементов И 33 и 34, третью группу элементов ИЛИ 35, первую группу входов 36 сравнения, выход 37 запрета, вторую группу входов 38, третью группу входов 39 сравнения, первый вход 40, первую группу выходов 41, первый управляющий выход 42, выход 43 синхронизации, вторую группу выходов 44, второй управляющий выход 45, устройство включает в себя также группу сигнальных входов 46 устройства, группу сигнальных выходов 47 устройства, генератор 48 импульсов, группу триггеров 49, группу регистров 50, третий элемент И 51, третий регистр 52 сдвига, шестую группу

«Ј

00

05

ю

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

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

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

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

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

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

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

0 на входы соответствующих сумматоров 29 по модулю два и схемы 31 сравнения.

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

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

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

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

10

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

Если необходимое число процессоров превышает количество процессоров, завершивших выполнение непосредственно предшествующего задания, то, кроме регистра 4 сдвига, в устройстве используется дополнитель- -j ный регистр 18 сдвига для одновременного распределения заданий на любые свободные процессоры. В этом случае сигнал с выхода схемы 31 сравнения разрешает выдачу в регистр 4 сдвига кода количества процессоров, завершивших выполнение задания, непосредственно предшествующего данному. При наличии этого сигнала на выходе элемента И 28 появляется сигнал, поступающий в регистр 18 сдвига и разрешающий прием кода с выходов группы сумматоров 29 по модулю два. Количество единиц в этом коде равно разности между количеством необходимых и свободных процессоров, выполнивших предыдущее задание. Теперь при сдвиге кода в региртре 4 сдвипотенциалы на выходах схем 13 сравнения и затем на выходах группы элементов И 14. На входах 36 и 38 блока управления будут нулевые значения кода свободных с и потребных процессоров и схема 19 сравнения сигнал на выход не выдает, поэтому на выходе элемента НЕ 29 блока управления будет высокий потенциал, поступающий на выход 37 запрета блока управления и далее на второй вход элемента И 51, разрешая прохождение тактового импульса ГТИ 48 на вход третьего сдвигового регистра 52. В результате сдвига анализируется задание, находящееся в очередном по порядку регистре 50 хранения.

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

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

20

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

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

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

40

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

об освобождении регистра 50 для приематретьего регистра сдвига и с управляющим

очередного задания.входом одноименного блока элементов И

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

0

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

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

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

0

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

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

с второй группой кодовых входов устройства,

с второй группой кодовых входов устройства,

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

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

W,47, tf 5,.

в,

ЧвнЫ (

ll llll

Фил.г