Устройство для распределения заданий в неоднородной вычислительной среде

 

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

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

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

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

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4802566/24 (22) 25,01.90 (46) 07.04.92. Бюл. rV. 13 (72) B.Ë.Ëÿñêîâñêèé, А.С,Скорытченко и

А.Н.Сударик (53) 681.325 (088.8) (56) Авторское свидетельство СССР

N 1205144, кл. G 06 F 9/46, 1984.

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

М 1619273, кл. G 06 F 9/46, 1989. . (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ

ЗАДАНИЙ В Н ЕОДНОРОДНОЙ В ЫЧИСЛИТЕЛЬНОЙ СРЕДЕ (57) Изобретение относится к вычислительной технике и может найти применение в многопроцессорных системах для распределения нагрузки между процессорами.

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

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

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

Наиболее близким к изобретению является устройство для распределения заданий процессорам, содержащее формирователь импульсов, регистр, два триггера, два эле,. Ы „, 1725220 А1

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

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

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

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

Iv (Л ()

1 .31 ,О !

1725220

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

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

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.

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

В исходном состоянии все триггера, счетчики и сумматоры устройства и регистр

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

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

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

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

55 шиваемой функции через блоки элементов

И 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 устройст1725220

35

55 ва и устанавливает в нулевое состояние триггер 8, регистр 9, сумматоры 17, счетчики

25 и триггер 24. При наличии сигнала на выходе переполнения двух и более счетчиков устанавливается тот триггер 27, номер которого меньше, так как соответствующие элементы И 29 с большими номерами запираются сигналом с выхода счетчика 25 с наименьшим номером. Тем самым достигается однозначный выбор процессора для назначения.

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

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

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

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

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

1725220

Составитель В.Лясковский

Техред М,Моргентал Корректор Э.Лончакова

Редактор В.Данко

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

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

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

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