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

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано в высокопроизводительных многопроцессорных и многомашинных системах . Цель изобретения - сокращение объема оборудования. Устройство содержит триггеры 1, 2, 9, формирователь импульсов 3, счетчики 4, 5, группу мультиплексоров 6, элементы И 7, 10, 14-16, 19. блок памяти 8, элемент ИЛИ-НЕ 11. регистр 12. узел приоритета 13, элементы ИЛИ 17,18, генератор тактовых импульсов 20. В устройстве поиск идет от наименее загруженного процессора к наиболее загруженному. 1 ил.

СОК)З СОВЕТСКИХ

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

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

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ юЪ (21) 4877051/24 (22) 22.10.90 (46) 23.08,92, Бюл. И 31 (72) В.А.Грибков, С.В.Федораев, А.А.Никитин и М.П.Сйчик (56) Авторское свидетельство СССР

N 1205144, кл. 6 06 F 9/46, 1986.

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

М 1444770, кл. 6 06 F 9/46, 1986.

Козырь И,Я. Качество и надежность интегральных микросхем. — M. В ысшая школа, 1987. (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ

ЗАДАНИЙ ПРОЦЕССОРАМ

„„5U„„1756889 А1

2 (57) Изобретение относится к автоматике и вычислительной технйке и может быть использовано в высокопроизводительных многопроцессорных и многомашинных системах. Цель изобретения — сокращение объема оборудовайия, Устройство .содержит . триггеры 1, 2, 9 формирователь импульсов

3, счетчики 4, 5, группу мультиплексоров 6. элементы И 7, 10, 14-16, 19, блок памяти 8, элемент ИЛИ-НЕ 11, регистр 12, узел приоритета 13, элементы ИЛИ 17, 18, генератор тактовых имйульсов 20. В устройстве поиск идет от наименее загруженного процессорак наиболее загруженному. 1 ил.

40

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

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

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

И, формирователь импульсов, элемент РАВНОЗНАЧНОСТЬ, элемент ИЛИ-НЕ, первый и второй триггеры.

Недостатком устройства является низкая надежность при выходе из строя его элементов. 3

Цель изобретения — сокращение объема оборудования.

Для поиска наименее загруженного процессора, способного выполнить запрашиваемую функцию (может быть несколько одинаково загруженных процессоров) с помощью счетчика формируется последовательность состояний очереди задания, начиная с нулевого (отсутствие заявок в очереди), Таким образом, поиск идет от наиме- 4 нее загруженного процессора к наиболее загруженному. Данный режим позволяет уменьшить общее число элементов устройства; не теряя при этом достоверности функционирования, и ри увеличении надежности устройства в целом.

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

Устройство содержит триггеры 1 и 2, формирователь 3 импульсов, счетчик 4, :, группу 5 реверсивных счетчиков, группу 6 мультиплексоров, элемент И 7, блок 8 памяти, группу 9 триггеров, группу 10 элементов

И, элемент ИЛИ-НЕ 11, регистр 12, узел 13 .приоритета, элементы И 14 — 16, элементы

ИЛИ 17 и 18, группу 19 элементов И, генератор 20 тактовых импульсов, вход 21 пуска, вход 22 сброса, вход 23 запроса, выход 24 занятости, сигнальный Выход 25, группу входов 26 — 26к признака выполнения задания, вход 27 кода задания, группу выходов

28 -28, "Отказ" процессора, группу сигнальных выходов 291 — 29»

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

Перед началом работы подачей нулевого импульса на вход 22 устройство переводится в исходное состояние. При атом триггеры 1 и 2, с Гетчики группы 5, триггеры группы 9 и регистр 12 переводится в нулевое состояние, Нулевой уровень сигнала на прямом выходе триггера 2 индицирует состояние "Свободно" устройства (выход 24) и запрещает прохождение тактовых импульсоВ через элемент И 7, Нулевой уровень сигнала на прямом выходе триггера 1 запрещает работу Генератора 20 тактовых импульсов. Единичный уровень сигнала на выходе элемента ИЛИ 18 разрешает прохождение тактовых импульсов нэ синхровход триггера 2. Нэ сигнальном выходе 25 и на выходе группы 29 — нулевые уровни сигналов. Подачей единичного импульса на вход 21 триггер 1 переводится В единичное состояние ("Ðàáîòà") и высоким уровнем сигнала на прямом выходе разрешает работу Генератора 20 TBKTGBblx импульсов. Синхроимпульсы проходят ерез элемент И 14 на синхровход триггера 2 и контролируют приход сигнала "Запрос" на вход 23. Управляющий монитор системы устанавливается на входах 27 устройства код запрашиваемой функции.

На выход блока 8 памяти выдается содержимое строки, при этом разряды, содержащие "1", соответствуют процессорам, способным выполнить запрашиваемую функцию. Через время, определяемое быстродействием блока 8 памяти, управляющий монитор устанавливает единичный потенциальный сигнал "Запрос" на вход 23 устройства. По отрицательному фронту очередного синхроимпульса триггер 2 переводится в единичное состояние и высоким уровнем сигнала на прямом выходе разрешает прохождение тактовых импульсов через элемент И 7. Единичный сигнал с прямого выхода триггера 2 поступает также на сигнальный выход 24 устройства (состояние "Занято" устройства) и на вход формирователя 3 импульсов. По импульсному сигналу с выхода формирователя 3 импульсов счетчик 4 обнуляется, а в триггеры 9 группы заносится информация, поступающая на входы группы 28 "Отказ" процессора

1756889

30

Л = ), ni А1, 45

Л=(5k+ 1.5) 10 г, Г =(8k+19) 10 r ) устройства. При этом на выходе элемента

ИЛИ 18 устанавливается нулевой уровень сигнала, который запрещает прохОждение синхроимпульсов через элемент И 14. Одновременно управляющий монитор, получив от устройства сигнал "Занято", снимает сигнал "Запрос" с входа 23 устройства..Если какой-либо процессор неработоспособен (нулевой сигнал на инверсном выходе соответствующего триггера группы 9) или оче- 10 редь задания его переполнена (нулевой сигнал на выходе переноса соответствующего счетчика группы 5), то информация о таком процессоре, поступающая от блока.8 памяти через соответствую1ций элемент И 15 группы 10, не проходит и он не участвует в распределении запроса, Если на данный момент нет процессоров, способных выполнить запрашиваемую функцию, то на выходе 25 устройства формируется единичный сигнал в виде команды

"Отказ по функции", который переводит в единичное состояние элемент ИЛИ 18 и тем самым разрешает прохождение тактовых импульсов через элемент И 14. При этом триггер 2 переводится в нулевое состояние (состояние "Свободно" устройства). Управляющий монитор, получив сигнал "Свободно", снимает код запрашиваемой функции с входов 27 устройства. Через некоторое время.может быть проведена повторная попытка распределить данный запрос.

Если есть процессоры, способные выполнить запрашиваемую функцию, то происходит процесс распределения запроса на. 35 наименее загруженный процессор. Распре- . деление ведется следующим образом. Происходит сравнение состояния счетчика 4, первоначально равного нулю и увеличивающегося с каждым тактовым импульсом на 1, 40 с состояйием счетчиков группы 5, соответствующим очереди задания процессора, Совпадение определяется наличием единичного сигнала на выходе соответствую-. щего мультиплексора груйпы 6 и свидетельствует об обнаружении наименее загруженого процессора.

Если найденный процессор способен выполнить запрашиваемую функцию (единичный сигнал на выходе соответствующего элемента И группы 10), то информация о нем проходит через соответствующий элемент И груйпы 19 и поступает на вход регистра 12. Таких процессоров может быть несколько, поэтому в регистре 12 фиксируются все наименее загруженные процессоры, способные выполнить запрашиваемую функцию. С помощью узла 13 приоритета выбирается один иэ них, и на соответствующем выходе 29 группы формируется единич6 ный сигнал, который, поступая на суммирующий вход соответствующего счетчика группы 5, модифицирует очередь задания процессора. Одновременно элемент ИЛИ

18 переводится в единичное состояние и разрешает прохождение синхроимпульсов через элемент И 14 на синхровход триггера

2. При этом триггер 2 переводится в нулевое состояние (состояние "Свободно" устройства). Выбранный процессор получает с системной магистрали код запрашиваемой функции. а управляющий монитор; получив от устройства сигнал "Свободно", снимает код запрашиваемой функции с входов 27 устройства. Нулевой уровенЬ сигнала на прямом выходе триггера 2 запрещает прохождение тактовых импульсов через элемент И 7, и модификация состояния счетчика прекращается. На этом процесс распределения эадайия завершается. В дальнейшем устройство работает аналогично вышеописанному.

Предлагаемое устройство распределения заданий процессором и известное представляют собой последовательные схемы по надежности. Следовательно, интенсивность отказов устройств может быть определена следующим образом:

1.=1 где Л1 — интенсивность отказов элементов

i-й группы;

n — число элемеНтов в i-й rpynne;

m — число групп в устройстве.

Большинство цифровых микросхем имеют интенсивность отказов 4, = 10 r .

Тогда Л = N . 4, где И вЂ” число микросхем, о используемых в устройстве. Если условиться, что в предлагаемом устройстве и известном соответствует одна микросхема, то можно рассчитать среднюю интенсивность отказов обоих устройств. Лредлагаемое устройство содержит N:= 5k+ 15 элементов (k — число процессоров в системе), известное — N = Sk + 19; Интенсивность отказов определяется соответственно:

Таким образом, предлагаемое устройство позволяет повысить надежность устройства в (= (8k + 19)/(5k + 1б) раз.

При минимальном числе процессоров в системе (k = 2) I - 1,4. При увеличении k I увеличивается и в пределе равно 1,6.

1756809

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

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

Составитель В.Грибков

Техред M,Ìîðãåíòàë Корректор M Петрова

Редактор В,Петраш

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

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

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

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

Устройство для распределения заданий процессорам, содер>кащее блок памяти, узел приоритета, группу триггеров, генератор тактовых импульсов, группу мультиплексоров, регистр, два элемента ИЛИ, два триггера, четыре элемента И, формирователь импульсов, счетчик, элемент ИЛИ+! Е, группу реверсивных счетчиков, две группы элементов И, при этом вход кода задания устройства соединен с адресным входом блока памяти, информационные выходы которого соединены с первыми входами соответствующих элементов И первой группы, информацйонные выходы регистра соединены с- входами узла приоритета, прямой выход первого триггера соединен с первым . входом первого элемента И, входом запуска формирователя импульсов и одновременно является выходом занятости устройства, выход формирователя импульсов соединен са входом сброса счетчика, выход первого элемента И соединен со счетным входом счетчика, информационные выходы которого соединены с адресными входами мультиплексоров группы, выходы узла приоритета соединены с суммирующими входами соответствующих счетчиков группы, групйа входов признака выполнения задания устройства соединена с вычитающими входами соответствующих счетчиков группы, информационные выходы которых соединены с информационными входами соответствующих мультиплексоров группы, а выходы переноса — с вторыми входами соответСтвующих элементов И первой группы, каждый вход группы входов "Отказ" процессора устройства соединен с информационным входом соответству ащего триггера группы, инверсные выходы которых соединены с третьими входами соответствующих

5 элементов И первой группы, выходы которых соединены с входами элемента ИЛИНГ, вход "Сброс" устройства соединен с входами сброса первого и второго триггеров, счетчиков группы, регистра и триггеров

10 группы, вход "Пуск" устройства соединен с информационным входом второго триггера, вход "Запрос" — с информационным входом второго триггера, прямой выход второго триггера соединен с входом запуска генера15 тора тактовых импульсов, выход которого соединен с вторым входам первого и первым входам второго элементов И, выход элемента ИЛИ-НЕ соединен с первым входом третьего элемента И, второй вход которого

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

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

40 с первыми входами соответствующих элементов И второй группы, вторые входы которых соединены с выходами соответству ащих элементов И первой группы, а выходы — с соответствующими входами регистра, 45