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

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

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

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

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

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

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

4

JND 1СЛ

IW |N О

На чертеже приведена структурная схема устройства.

Устройство содержит сигнальный вход

Iустройства, группы информационных входов 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.

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

В исходном состоянии все триггера, счетчики и сумматоры устройства и регистр 9 обнулены. В l-м регистре 1-го блока 13 записано значение кода, соответствующего допустимому времени ожидания обслуживания заявки на l-ю функцию при назначении ее на 1-й процессор, представленное в обратном коде (рассчитывается заранее, как разность между допустимым временем ожидания и временем решения Е-й функции на i-м процессоре).

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

Код запрашиваемой функции поступает по входам 4 в регистр 9. Одновременно на управляющем входе3 появляется сигнал запроса на выполнение запрашиваемой функции, который устанавливает триггер 8 в единичное состояние и подается на формирователь 7 импульсов, на выходе которого появляется импульс, поступающий на элемент 10 задержки. Сигнал с единичного выхода триггера 8 открывает.блок элементов И

I1и разрешает прохождение кода запрашиваемой функции с регистра 9 на дешиф- ратор 14. На выходе дешифратора 14, соответствующем коду запрашиваемой функции, появится сигнал, открывающий соответствующие блоки элементов И 15. Коды допустимого времени ожидания запрашиваемой функции через блоки элементов И 15 и блоки элементов ИЛИ 16 поступают на соответствующие входы сумматоров 17. По информационным входам 2 устройства через блоки элементов И 12, открываемые по второму входу задержанным управляющим сигналом устройства, с выхода элемента 10 задержки на соответствующие сумматоры 17 поступают коды суммарного времени дообслуживания всех заявок в соответствующих процессорах. Таким образом, в сумматорах 17 производится операция вычитания из кода обслуживания заявок на соответствующем процессоре кода допустимого времени ожидания запрашиваемой функции на соответствующем процессоре.

Импульс, поступивший с элемента 10 задержки на элемент 19 задержки, задерживаясь в последнем, поступает на единичный вход триггера 24, на первый вход элемента И 23 и первые входы блоков элементов И 22. Результат операции вычитания, полученный в сумматоре 17, поступает на соответствующий счетчик 25 только в том случае, когда на знаковом выходе этого сумматора 17 присутствует единичный сигнал, открывающий соответствующий блок элементов И 22, при поступлении на него импульса с выхода элемента 19 задержки. Одновременно сигналы со знаковых выходов сумматоров 17 через элемент ИЛИ-НЕ 20 поступают на второй вход элемента И 23. При поступлении импульса с элемента 19 задержки на первый вход элемента И 23 на его выходе появится единичный сигнал только в случае, когда все знаковые разряды сумматоров 17 имеют нулевое значение, т.е. запрашиваемая функция ни на одном процессоре не может быть выполнена без нарушения директивного срока. Импульс с выхода элемента И 23, проходя через элемент ИЛИ 28, поступает на выход 6 устройства, а также устанавливает триггер 26 в единичное состояние, сигнал с инверсного выхода которого подается на вход элемента И 21, закрывая его и тем самым запрещая прохождение импульсов с генератора 18 на счетчики 25.

Высокий потенциал с прямого выхода триггера 24 поступает на вход элемента И 21 и в случае, когда с инверсного выхода триггера 26 на вход элемента И 21 поступает единичный сигнал, разрешает поступление импульсов с генератора 18 на счетные выходы счетчиков 25. На выходе переполнения того счетчика 25 появится импульс, вход в котором максимален. Импульс переполнения устанавливает соответствующий триг-. гер 27 в единицу и через элемент ИЛИ 28 прступает на сигнальный выход 6 устройства и устанавливает в нулевое состояние триггере, регистр9, сумматоры 17,счетчики 25 и триггер 24. При наличии сигнала на выходе переполнения двух и более счетчиков устанавливается тот триггер 27, номер которого меньше, так как соответствующие элементы И 29 с большими номерами запираются сигналом с выхода счетчика 25 с наименьшим номером. Тем самым достигается однозначный выбор процессора для назначения.

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

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

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

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

единичному входу первого триггера группы, выходы переполнения счетчиков группы соединены с входами второго блока элементов И, группа выходов которого соединена с единичными входами, соответствующих

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

входом М-го блока элементов ИЛИ, выход которого соединен с вторым информационным входом соответствующего сумматора группы.

Г

jj

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

Л

liL

П

X

t

-----1

Gi

r: j L

т

TOsJ

II

-Й

О U