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

 

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

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

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

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

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

Недостатком устройства является низкое быстродействие функционирования.

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

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

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

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

Устройство содержит первый и второй триггеры 1 и 2, генератор 3 тактовых импульсов, элементы И 4, 5, 20 и 23, формирователь 6 импульсов, блок 7 памяти, счетчик 8, элементы ИЛИ 9 и 24, группу реверсивных счетчиков 10, первую и вторую группы мультиплексоров 11 и 12, триггеров 13 и 16, первую, вторую и третью группы элементов И 15, 17 и 18, первую и вторую группы элементов ИЛИ 14 и 19, узел 21 приоритета, элемент ИЛИ-НЕ 22, вход 25 пуска, вход 26 сброса, вход 27 запроса, вход 28 кода задания, группу входов 29 признака выполнения задания, группу сигнальных входов "Отказ" 30 процессора, сигнальный выход 31 занятости, группу сигнальных выходов 32 признака выбранного процессора, сигнальный выход 33.

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

Перед началом работы подачей нулевого импульса на вход 26 устройство переводится в исходное состояние. При этом триггеры 1 и 2, счетчики группы 10, триггеры группы 13 и группы 16 переводятся в нулевое состояние. Нулевой уровень сигнала на прямом выходе триггера 2 индицирует состояние "свободно" устройства (выход 31) и запрещает прохождение тактовых импульсов через элемент И 5. Нулевой уровень сигнала на прямом выходе триггера 1 запрещает работу генератора 3 тактовых импульсов. На сигнальном выходе 33 и выходах группы 32 нулевые уровни сигналов.

Подачей единичного импульса на вход 25 триггер 1 переводится в единичное состояние и высоким уровнем сигнала на прямом выходе запускает генератор 3 тактовых импульсов.

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

Через время, определяемое быстродействием блока 7 памяти, управляющий монитор устанавливает единичный сигнал "Запрос" на входе 27. При этом единичный сигнал на выходе элемента ИЛИ 24 разрешает прохождение тактовых импульсов через элемент И 4 на синхровход триггера 2, который переводится в единичное состояние, индицирует состояние "занято" устройства (выход 31), разрешает прохождение тактовых импульсов через элемент И 5 и запускает формирователь 6 импульсов. По импульсному сигналу с выхода формирователя импульсов счетчик 8 обнуляется, в триггеры группы 13 заносится информация об отказавших процессорах ("1" на входе группы 30). При этом на выходе соответствующего элемента И группы 15 устанавливается единичный сигнал при условии, что соответствующий процессор не в отказе (нулевое состояние триггера группы 13), его очередь не переполнена (нет сигнала переноса счетчика группы 10) и он способен выполнить запрашиваемую функцию ("1" на выходе блока памяти). Эта информация через элементы ИЛИ группы 14 заносится в триггеры группы 16. Одновременно с установлением сигнала "Занято" на выходе 31 управляющий монитор снимает сигнал "Запрос" с входа 27.

Если нет процессора, способного выполнить поступившую заявку из-за своей специализации, отказа или переполнения очереди, единичный сигнал с выхода элемента ИЛИ-НЕ 22 проходит через элемент И 23 и индицирует сигнал "Отказ по функции" на выходе 33, который проходит через элемент ИЛИ 24 и разрешает прохождение тактовых импульсов на синхровход триггера 2. Триггер 2 переводится в нулевое состояние (состояние "свободно" устройства). Управляющий монитор, получив сигнал "Свободно", снимает код запрашиваемой функции с входа 28. Через некоторое время может быть проведена повторная попытка распределить данный запрос.

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

Счетчик 8 под воздействием тактовых импульсов, поступающих на суммирующий вход с выхода элемента И 5, отсчитывает состояние очереди одновременно начиная с минимальной (00...0 на прямых выходах счетчика) и максимальной (11. . .1 на инверсных выходах). Мультиплексоры группы 11 и группы 12 сравнивают действительное состояние очереди, поступающее с выходов счетчиков группы 10, с отсчитываемыми. Если мультиплексор группы 11 обнаруживает совпадение очереди, то единичный сигнал на его выходе разрешает прохождение через элемент И группы 17 информации в соответствующем процессоре. Если процессор способен выполнить запрашиваемую функцию, то единичный сигнал на выходе соответствующего элемента И группы 17 проходит через элемент ИЛИ группы 19 и поступает на вход узла 21 приоритета. Таких процессоров может быть несколько. Узел 21 приоритета выбирает один из них.

Если совпадение очередей зафиксировал мультиплексор 12 группы, то информация об этом заносится через соответствующий элемент ИЛИ группы 14 в триггер группы 16. Если при этом все триггеры оказываются в нулевом состоянии, то данная очередь минимальна для всех процессоров, способных выполнить запрашиваемую функцию. Тогда на выходе элемента И 20 будет единичный сигнал, который совместно с единичным сигналом от мультиплексора, соответствующего выбранному процессору, разрешает прохождение информации о нем через элемент И группы 18, а дальше через элемент ИЛИ группы 19 на вход узла 21 приоритета.

Единичный сигнал с выхода узла 21 приоритета поступает на вычитающий вход соответствующего счетчика и модифицирует очередь выбранного процессора. Одновременно элемент ИЛИ 24 переводится через элемент И 4 на синхровход триггера 2, который переводится при этом в нулевое состояние (состояние "свободно" устройства). Выбранный процессор получает из системы магистрали код запрашиваемой функции, управляющий монитор, получив от устройства сигнал "свободно", снимает код функции входа 28 устройства. Нулевой уровень сигнала на прямом выходе триггера 2 запрещает прохождение тактовых импульсов через элемент И 5, модификация счетчика 8 прекращается. На этом процессе распределения задания завершается. В дальнейшем устройство работает аналогично выше описанному. Таким образом, в предлагаемом устройстве поиск идет как от наименее загруженного процессора к наиболее загруженному процессору, так и от наиболее загруженного процессора к наименее загруженному. Данный режим позволяет ускорить поиск наименее загруженного процессора, способного выполнить запрашиваемую функцию, и тем самым повысить быстродействие функционирования устройства.

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

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

РИСУНКИ

Рисунок 1