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

 

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

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

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

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

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

К А BTOPCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ИЗОБРЕТЕНИЯМ И OTHPblTHRM

ПРИ ГКНТ СССР (21) 4421396/24-24 (22) 11.05.88 (46) 30.01.90. Бюл. У 4 (72) В.Н.Дроник и .С.П.Тюриков (53} 681.325(088.8) (56) Авторское свидетельство СССР

У 966697, кл. G 06 F 9/46, 1980.

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

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

ЗАДАНИЙ ПРОЦЕССОРАМ (57) Изобретение относится к вычислительной технике и предназначено для использования в многопроцессорных или многомашинных вычислительных системах. Цель изобретения — сокращение объема оборудования, Устройство распределения заданий процессорам содержит каналы, каждый из котоИзобретение относится к вычислительной технике и может найти приме- нение в многопроцессорных или,. многомашинных системах при распреде"„ ленин заданий процессорам.

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

На фиг.l приведена структурная схема устройства; на фиг.2 — структурная схема блока выделения максимального кода.

Устройство для распределения заданий процессорам содержит вход 1 запуска устройства, ответные входы 2 устройства, каналы К, каждый из которых содержит триггер 3 и группу элементов НЕ 4» элемент К18 5, элемент

6 задержки, входы 7 и 8 режима.уст„„SU„„ 1 539778 А 1

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

Распределение задач между процессорами осуществляется с учетом априорной информации о времени их выполнения.

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

1 з.п, ф лы, 2 ил. ройства, каналы содержат элементы

1> «

И 9 и 1 О, Устройство содержит также 1«Л триггер ll, каналы К вЂ” элементы ИЛИ

12. Устройство, кроме того, содержит. 1;© блок 13 выделения максимального кода, « Д элементы ИЛИ 14, элемент И 15, эле- « менты KIH-НЕ 16, выходы 17 устрой- QQ ства, группы кодовых входов 18 устройства, управляющие входы 19 блока 13, труппы входов 20 блока

13 и выходы 21 блока 13, Блок 13 (фиг.2) содержит элемен- 3» ты ИЛИ-НЕ 22, элементы ИЛИ 23, эле- й. менты И 24 и 25, узлы 26 выделения кода, Устройство позволяет по имеющейся априорной информации о времени .выполнения задач пакета. осуществлять

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

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

В исходном состоянии триггеры 3 каналов и триггер 1 установлены в нулевое состояние. На кодовые входы

18 поданы двоичные коды .времени выполнения, которые с входов 18 поданы на первые входы элементов И 10 каждого канала и через элементы НЕ 4 — на входы элементов И 9 каждого канала, Ес-.)5 ли устройство работает в режиме минимального времени реализации пакета задач, на вход 7 подан единичный потенциал, если же устройство работает в режиме минимального среднего време- 30 ни ожидания решения задачи, то единичный потенциал подан на вход 8 устройства.

Инициализация устройства производится подачей единичного импульса на вход 1 запуска устройства, который через элемент ИЛИ 5 поступает иа вход элемента 6 задержки. По переднему фрон-. ту импульса устанавливаются в единичное состояние триггеры 3 каждого кана-. ла. Единичные сигналы с .прямых выходов этих триггеров поступают на входы

19 блока 13, на первые входй элементов И 9 и на первые входы элементов

И 10.

Предположим, что устройства рабо— тает в режиме минимального времени реализации пакета задач и на вход 7 устройства подан единичный потенциал., -50

Этот потенциал присутствует на вторых входах всех элементов И 10 групп всех каналов, поэтому разрешена выдача всех кодов через эти элементы на вторые входы элементов ИЛИ 12 каналов и далее на соответствующие выходы

20 каждого канала. Таким образом, на группы входов блока 13 подают коды времени выполнения заданий.

Блок 13 работает следующим образом. Первые (старшие) разряды кодов времени выполнения задач подаются на первые входы 20 первых элементов И каждого узла 26, Аналогично остальные разряды кодов подаются на первые входы соответствующих элементов

И 25 узлов 26. С входов 19 блока 13 единичные сигналы поступают на первые входы первых элементов И 24 и

И 25 всех узлов 26.

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

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

На втором шаге аналогично просматриваются вторые разряды кодов, причем в работе принимают участие те узлы

26, в которых бып единичный сигнал переноса с предыдущего, в данном случае первого элемента ИЛИ 23 груп4 пы, и т.д.

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

С выхода элемента ИЛИ 5 единичный импульс поступает на вход элемента

6 задержки, а также на вход установки в нуль триггера Il,.не меняя его состояния. Через время, выбранное с учетом того, чтобы завершились переходные процессы в блоке 13, передним фронтом задержанного импульса триггер

11 устанавливается в единичное состояние, разрешая выдачу единичного сигнала на соответствующий выход 17, который указывает, что на выполнение назначена соответствующая задача.

В общем случае, когда в пакете выявлено несколько задач с одинаковым временем выполнения, единичные сигналы возникают на соответствующих выходах 21 блока 13, а на выходах

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

153977 решения. Это достигается наличием цепи элементов 14 и 16.

На этом первый этап назначения задач заканчивается.

I 5

Когда задача взята на выполнение, на соответствующий вход 2 подается единичный импульс, который через элемент ИЛИ 5 поступает на элемент 6 задержки, и, кроме того, передний фронт этого импульса перебрасывает триггер 11 в нулевое состояние. В результате этого прекращается выдача сигнала на соответствующий выход

17 устройства. B то же время единичный импульс с входа 2 устанавливает триггер 3 соответствующего канала в, нулевое состояние. В результате этого закрываются элементы И 9 и 10 и выдача кода времени выполнения задачи на 20 выходы 20 этого канала прекращается, Кроме того, с выхода этого триггера поступает нулевой сигнал на соответствующий вход 19 блока 13. Так как на соответствующие входы 20 и на вход 25

19 блока 13 подаются .нулевые сигналы, этот узел 26 не принимает участие в дальнейшей работе блока 13. Данная задача пакета исключается из рассмотрения. 30

Далее работа устройства происходит аналогично описанному.

Если устройство работает в режиме минимального среднего времени ожидания решения задачи, то первой должна выбираться на выполнение та задача, у которой время выполнения минимальное. В этом случае единичный управляющий сигнал подается на вход 8 устройства. Этот сигнал открывает по второ- 40 му входу элементы И 9 каждого канала, что в свою очередь разрешает выдачу обратных кодов времени выполнения задач (через элементы НЕ 4, элементы

И 9 группы, элементы ИЛИ 12 группы) 4 на выходы 20 каналов. В остальном работа устройства полностью аналогична описанному, но теперь первой выбирается задача, имеющая минимальноевремя выполнения. 50

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

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

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

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

2.Устройство по п,l, о т л и ч а ю— щ е е с я,тем, что блок выделения максимального кода содержит группу элементов ИЛИ-НЕ, узлы выделения кода, каждый из которых содержит две группы элементов И и группу элементов ИЛИ, причем i-й вход j -й группы входов блока, где i=1 и, n - разрядность кода задания, j =1 Ê, К -, 1539778 количество заданий, соединен с первым входом i-ro элемента И первой группы

j-ro узла вьщеления кода, выходы

i-x элементов И первой группы каждого узла выделения кода соединены с входами i-ro e eHT K1H-HE группы, выход i-ro элемента ИЛИ-НЕ группы соединен с первыми входами i-x элементов

И второй группы всех узлов выделения кода, вторые входы первых элементов

И первой и второй групп g --го узла выделения кода соединен с 1-м управляющим входом блока, выходы i-x элементов И первой и второй групп в каждом узле вьщеления кода соединены с входами i-го элемента ИЛИ группы данного узла выделения кода, выход

i-го элемента ИЛИ группы в каждом узле вьщеления кода соединен с вторыми входами (i+1) -х элементов И первой и второй групп данного узла вьщеления кода, выходы последних элементов ИЛИ группы являются выходами блока.

1539778

Составитель М.Кудряшев

Техред М. Ходанич Корректор Л.Патай

Редактор M,Ïåòðîâà

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

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

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

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