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

СП

с

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

Ч

ел о

00 00

о

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

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

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

Наиболее близким по технической сущности к предлагаемому является устройство распределения заданий процессорам, содержащее блок памяти, узел приоритета, группу реверсивных счетчиков, первую группу элементов И, первую группу триггеров, группу мультиплексоров, счетчик, элемент задержки, генератор тактовых импульсов, вторую группу триггеров, вторую и третью группы элементов И, регистр, первый и второй элементы ИЛИ, группу элементов ИЛИ-НЕ, первый-шестой элементы И, формирователь импульсов, элемент РАВНОЗНАЧНОСТЬ, элемент ИЛИ-НЕ, первый и второй триггеры.

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

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

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

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

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

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

сходов признака выполнения зада- РИЯ, вход 27 кода задания, группу выходов Отказ процессора, группу сигнальных выходов 29i-29k.

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

Перед началом работы подачей нулевого импульса на вход 22 устройство переводится а исходное состояние. При этом триггеры 1 и 2, счетчики группы 5, триггеры

5 группы 9 и регистр 12 переводится в нулевое состояние. Нулевой уровень сигнала на прямом выходе триггера 2 индицирует состояние Свободно устройства (выход 24) и запрещает прохождение тактовых импуль0 сов через элемент И 7. Нулевой уровень сигнала из прямом выходе триггера 1 запрещает рзботу генератора 20 тактовых импульсов. Единичный уровень сигнала на выходе элемента ИЛИ 18 разрешает про5 хождение тактовых импульсов на синхров- ход триггера 2. На сигнальном выходе 25 и на выходе группы 29 - нулевые уровни сигналов. Подачей единичного импульса на вход 21 триггер 1 переводится в единичное

0 состояние (Работа) и высоким уровнем сигнала на прямом выходе разрешает работу генератора 20 тактовых импульсов. Синхроимпульсы проходят через элемент И 14 на синхровход триггера 2 и контролируют

5 приход сигнала Запрос на вход 23. Управляющий монитор системы устанавливается на входах 27 устройства код запрашиваемой функции.

На выход блока 8 памяти выдается со0 держимое строки, при этом разряды, содержащие 1, соответствуют процессорам, способным выполнить запрашиваемую функцию. Через время, определяемое быстродействием блока 8 памяти, управляющий

5 монитор устанавливает единичный потенциальный сигнал Запрос на вход 23 уст- ройства. По отрицательному фронту очередного синхроимпульса триггер 2 переводится в единичное состояние и высоким

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

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

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

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

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

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

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

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

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

30

m

Я Ј ni -Я| i 1

где Я) - интенсивность отказов элементов

группы;

п, - число элементов в 1-й группе; m - число групп в устройстве. Большинство цифровых микросхем имеют интенсивность отказов До .

Тогда Я N До - где N - число микросхем, используемых в устройстве. Если условиться, что в предлагаемом устройстве и известном соответствует одна микросхема, то можно рассчитать среднюю интенсивность

отказов обоих устройств. Предлагаемое устройство содержит N 5k + 15 элементов (k - число процессоров в системе), известное - N 8k + 19. Интенсивность отказов определяется соответственно:

Я + 15)- ,

Я (8k + 19) ).

Таким образом, предлагаемое устройство позволяет повысить надежность устройства Bl (8k+ 19)/(5k-M5)p33. При минимальном числе процессоров в системе (k 2) I 1,4. При увеличении k I увеличивается и в пределе равно 1,6.

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

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

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

сора устройства соединен с информационным входом соответствующего триггера фуппы, инверсные выходы которых соединены с гренами входами соответствующих элементов И первой группы, выходы которых соединены с входами элемента ИЛИ- НЕ, вход Сброс устройства соединен с сходами сброса первого и второго триггеров, счетчиков группы, регистра и триггеров группы, вход Пуск устройства соединен с информационным входом второго триггера, вход Запрос - с информационным входом второго триггера, прямой выход второго триггера соединен с входом запуска генератора тактовых импульсов, пыход которого соединен с вторым входом первого и пер- вчм входом оторсно элементов И, выход элемента ИЛИ-НЕ соединен с первым входом третьего элемента И, второй вход которого соединен с прямым выходом первого триггера, а выход является сигнальным выходом устройства и соединен с первым входом второго элемента ИЛИ, отличающееся тем, ч го, с целью сокращения объема оборудования, в устройстве выходы первою элемента И м формирователя импульсов соединены соответственно с первым и вто рым входами первого элемента ИЛИ, ВЫХОДУ учла приоритета являются группой сигнальных выходов устройства и соединены с группой входов FJToporo элемента ИЛИ, выход первого элемента ИЛИ соединен с синхров- ходами триггеров фуппы и регистра, инверсные выходы триггеров группы соединены с входами четвертого элемента И, выход которого соединен с вторым входом второго элемента ИЛИ, выход второго элемента И соединен с синхровходом первого триггера, выходы мультиплексоров группы соединены с первыми входами соответствующих элементов И второй группы, вторые входы которых соединены с выходами соответствующих элементов И первой группы, а выходы - с соответствующими входами регистра.