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

 

Изобретение относится к вычислительной технике и может быть использовано для распределения заданий процессорам мультипроцессорной системь). Устройство для распределения заданий процессорам содержит Матрицу формирователей весов ДУГ, группу элементов запрета, группу счетчиков, группу блоков элементов ; И, блок сортировки информации, регистр приоритетов,регистр выбранных вершин, блок управления. В матрицу формирователей весов дуг заносится информация о топологии ориентированного графа и весах дуг. При поступ лении входного сигнала в регистрирующих счетчиках накапливаются импульсы , число которых пропорционально времени максимального пути для соответствующей вершины графа. После того как будет сформирована необходимая информация в счетчиках, в соответствующий разряд регистра приоритетов с помощью блока сортировки информации будет записана логическая единица и на обслуживание выберется готовая вершина, для которой время максимального пути наибольшее. 3 ил. I W со х :о

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

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

РЕСПУБЛИК

А1 (5D 4 G 06 F 9/46

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

Н АSTOPCKOMY СВИДЕТЕЯЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 4011248/24-24 (22) 14 ° 01.86 (46) 23.06.87. Бюл. У 23 (72) А.Я.Матов, В.Д;Костюченко, П.В.Ефимов и С.В.Кравчук (53) 681.325 (088.8) (56) .Авторское свидетельство СССР

У 664175, кл. G 06 F 9/46, 1975.

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

N 877553, кл. С 06 Г 9/46, 1979. (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ ЗАДАНИЙ ПРОЦЕССОРАМ . (57) Изобретение относится к вычислительной технике и может быть использовано для распределения заданий процессорам мультипроцессорной системы. Устройство для распределения заданий процессорам содержит матрицу формирователей весов дуг, группу элементов запрета, группу счетчиков, группу блоков элементов ,И, блок сортировки информации, регистр приоритетов, регистр выбранных вершин, блок управления. В матрицу формирователей весов дуг заносится. информация о топологии ориентированного графа и весах дуг, При поступлении входного сигнала в регистрирующих счетчиках накапливаются импульсы, число которых пропорционально времени максимального пути для соответствующей вершины графа. После того как будет сформирована необходимая информация в счетчиках, в соответствующий разряд регистра приоритетов с помощью блока сортировки информации будет записана логическая едини- Ж ца и на обслуживание выберется готовая вершина, для которой время максимального пути наибольшее. 3 ил.

1 13

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

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

На фиг. 1 показана структурная схема устройства (для N=3 вершин); на фиг, 2 — блок сортировки информации на фиг. 3 — ячейка итеративной сети.

Устройство содержит матрицу 1 формирователей весов дуг, состоящую из формирователей 2« -2» весов дуг,каждый из которых состоит из счетчикй

3, первого и второго триггеров 4 и

5 и элементов И 6 — 6>, элемент 7 задержки, генератор 8 тактовых импульсов, блока 9 управления, включающий элементы И 10 и 11, триггер

12, элемент И 13, вход 14 пуска устройства, сигнальный выход 15 устройства, элементы 16, — 16 запрета,. регистрирующие счетчики 17 — 17з, блоки элементов И 18, — 18» блок 19 сортировки информации, группу входов

20 и выходов 21 блока 19, группу входов 22 сброса счетчиков 17, регистр

23 приоритета, регистр 24 выбранных вершин, группу информационных выходов 25, — 25, первую и вторую группы информационных входов 26 — 26 и

27, — 27 устройства, вход 28, ячейки 29, элементы НЕ 30, блок элемен— тов И 31, входы 32-38, выходы 39-41, элементы И 42 и 44 и элементы НЕ 43 и 45.

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

В исходном состоянии регистры 23 и 24, счетчики 17 и 17> находятся в нулевом состоянии, а триггер 12 в единичном состоянии, в счетчик 17, записано максимальное число, в матрицу 1 заносится информация о топологии ориентированного графа. При этом триггеры 4 и 5 формирователей

2, моделирующие ветви графа, устанавливаются в единичное состояние.

Соответствующий формирователь 2 определяется пересечением строки с номером, равным номеру начального узла моделирующей ветви, и столбца с номером ее конечного узла ° В счетчике 3 соответствующих формировате19031

5

f5

ЗО

2 лей 2 заносятся числа импульсов, дополняющие длительность ветвей до полной емкости счетчиков. После записи исходной информации на выходах элементов И 6, объединяющих выходы формирователей 2 в столбцах, соответствующих начальным узлам графа, устанавливаются высокие потенциалы.

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

4 и 5, находящиеся в этом столбце, находятся в нулевом состоянии ° Исходный граф заносится в матрицу в инверсном порядке, т.е, матрица сличимости заносимого графа транспортирована относительно главной диагонали. Это позволяет для расчета максимальных путей в графе использовать процедуру динамического программирования.

С появлением пускового сигнала на входе 14 срабатывает триггер 14 блока 9 управления и устанавливается в нулевое состояние. С инверсного выхода этого триггера поступает единичный потенциал и открывает элемент

И 10, в результате чего импульсы с генератора 8 через элемент И 10 поступают на входы всех элементов 16

16> запрета и на счетные входы счетчиков 3 всех формирователей 2. При этом начинают работать счетчики 3 тех формирователей 2, которые моделируют веса дуг, исходящих из начального узла графа, за счет подачи высокого потенциала с выхода элемента

И 6 на разрешающие входы счетчиков

3 формирователей 2 « — 2,z . Импульсы от генератора 8 проходят на регистрирующие счетчики 17 всех вершин графа, кроме начальной, так как на выходе элемента И 6 устанавливается высокий потенциал, следовательно, элемент 16 запрета не пропускает импульсы от генератора 8 на регистрирующий счетчик 17 .

Отсчитав число импульсов, пропорциональное весу моделируемой дуги, счетчик 3 одного из формирователей

2 переполняется, устанавливается в нулевое состояние соответствующий триггер 4 и на вход соответствующего элемента И 6 поступает высокий потенциал с инверсного выхода этого триггера. Если на остальных входах этого элемента И 6 находится высокий

3 13190 потенциал, единичный уровень поступает на соответствующий элемент 16 запрета и закрывает его. Это свидетельствует о том, что все веса дуг, входящих в узел графа, номер которого соответствует номеру столбца формирователей 2, объединенных этим элементом И 6, сформированы, При этом формируется разрешение работы счетчиков 3 формирователей 2, моделирующих 10 ветви графа, исходящие из формированного узла графа. На выходе счетчика

17 данного столбца фиксируется время максимального пути для данной вершины графа. 15

Подсчитывание импульсов в счетчиках 17 продолжается до тех пор, пока на выходах всех элементов И 6 не присутствует высокий потенциал. Это свидетельствует о том, что все узлы 20 исследуемого графа сформированы. Все это время на выходах 2 1 блока сортировки информации 19 присутствуют нулевые потенциалы, так как он закрыт по управляющему входу 28. Одновремен- 25 ное наличие единичных потенциалов на входах элемента И 11 приводит к срабатыванию триггера 12 блока 9 управления. На вход элемента И 10 поступает нулевой потенциал, который пре- 30 кращает подачу импульсов генератора

8 в схему. В это же время сигналом с единичного вьгхода триггера 12 сбрасываются все триггеры 5, которые установлены в единичное состояние и информация записанная в них, переписывается в триггеры 4, так как триггеры 4 и 5 управляются передним фронтом импульса.

Таким образом, в триггеры 4 всех формирователей 2 переписывается информация о топологии ориентированного графа. После этого единичный потенциал, задержавшись на линии 4 задержки 7 на время, необходимое для срабатывания элементов матрицы формирователей 1, поступает на управляющий вход 28 блока сортировки информации и открывает его. Так как gp начальная вершина графа.не зависит ни от каких других, на всех входах элемента И 6 появляются единичные потенциалы, на его выходе появляется высокий потенциал, который, поступая на вход элемента И 18,, разрешает подачу с выхода счетчика 17, кода на вход 20» блока 19 сортировки информации, который обеспечивает появление высокого потенциала на одном или нескольких выходах, которые соответствуют максимальному ко1 ду,,подаваемому на его входы. Вследствие этого высокий потенциал с выхода 21, блока 19 сортировки информации записывается в первый разряд регистра 23 приоритетов, на выходе которого в первом разряде появляется высокий потенциал и поступает на выход 25< и далее к диспетчеру вычислительной системы, который выбирает на реализацию соответствующую программу. После выбора соответствующей программы для реализации ее в вычислительной системе диспетчер записывает единицу в соответствующий разряд регистра 24 выбранных вершин, которая обнуляет соответствующий разряд регистра 23 и счетчик 17.

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

После выполнения данной подпрограммы диспетчер посылает единичный сигнал на соответствующий вход 27, который обнуляет триггеры 4 соответствующей строки формирователей 2. После этого появляются единичные сигналы на выходе элемента И 6 одного или нескольких столбцов. Дальнейшая работа устройства происходит аналогично описанному. При наличии в регистре

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

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

Блок 10 сортировки информации содержит однородную структуру размером

М х М (фиг. 2), где M — разрядность счетчика 17, N — количество столбцов . матрицы 1 (фиг ° 1), блок элементов И

31 с управляющим входом 32. Таким образом, на каждую строку матрицы (входы 20, — 20 ) поступает одно число, а одноименные разряды всех чисел рас. положены в одноименных столбцах матрицы (старшие разряды слева). Для

13190

x = xvaz, 4 5 (x =xvaz — вертикальные каналы у =у поиска максимума используется алгоритм поразрядного сравнения всех чисел, который состоит в следующем.

1-й шаг. Просматриваются информационные входы 20, — 20 левого (первого) столбца, т.е. старшие разряды всех N чисел, Если все эти разряды содержат нули, на следующем шаге просматриваются вторые разряды всех

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

j.-й шаг. Просматриваются информа- 15 ционные входы j-го столбца в тех строках, которые выделены на (j-1)-м шаге. Если все эти разряды содержат нули, на следующем шаге просматриваются (j+1)-е разряды тех же строк. Если 20 на просматриваемых информационных входах имеются как нули, так и единицы, на (j+)-м шаге просматриваются только строки, соответствующие единицам. Выделенное на последнем (М-м) шаге подмножество строк содержит максимальное число.

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

В горизонтальном направлении имеется цепь, просматривающая последовательно, слева направо, информационные входы и продолжающая этот про- 35 смотр, если на данном информационном входе находится единица или если на всех просматриваемых информационных входах в данном столбце находятся нули, Эту работу выполняет двоичный канал, 10 реализующий в каждой ячейке 29 (фиг.3) итеративной сети логическую функцию

z =z (av у), где z — сигнал на боковом выходе 39 ячейки 29;

z — сигнал на боковом входе 38, а — информационный вход 37 у — переменная, характеризующая содержимое просматриваемых

50 ячеек данного столбца (вход

36) : у = 1, если все.они содержат нули и у = 0 — в противном случае.

На входе 38 (z) всех ячеек левого столбца матрицы поданы граничные константы z =1 (вход 34 блока 19 сортировки информации). Поэтому наличие сигнала z =1 (на выходе 39) в гори31 6 зонтальном канале любой строки означает, что данная строка подлежит дальнейшему просмотру (в противном случае сигнал z принимает значение "О", которое в дальнейшем измениться не может).

В каждом столбце организована вер. тикальная цепь, проверяющая содержи- . мое всех просматриваемых ячеек и вырабатывающая переменную у. Эту работу выполняет двоичный канал, реализующий в каждой ячейке 29 логическую функцию где х — сигнал на нижнем выходе

40 ячейки 29, х — сигнал на верхнем входе 35 ячейки 29.

На входы х (вход 35) всех ячеек

29 верхней строки матрицы подаются граничные константы х = О. Поэтому межэлементный сигнал х (выход 40) принимает значение " 1" в первой же (начиная сверху) ячейке 29, которая подлежит просмотру (z 1), и содержит единицу (а = 1), причем х = 1 в дальнейшем измениться не может.

Только в таком случае, если в проверяемом столбце нет ни одной такой ячейки, в вертикальном канале сохраняется х = 0 и на выходе 41 ниж> ней (N-й) ячейки столбца вырабаты(> вается x „ = О.

Для правильной работы горизонтальных каналов организован еще один проходной вертикальный канал у (вход 36) и соединен в каждом столбце его вход с выходом х (выход 40) через инвертор 30. Вся система логических функций ячейки итеративной сети, реализующей поиск максимума, имеет следующий вид: =z(avy} — горизонтальный канал у =х — вспомогательная функция. о и

После подачи граничных сигналов

z,=1, х =0 сигналы z =1 на правой границе матрицы установятся в строке или нескольких строках, которые содержат максимальные числа.

Разрешающий сигнал поступает на вход 28 блока 19 сортировки информации и поступает на управляющий вход

32 блока элементов И 31, разрешая

7 13190 прохождение информации с выхода матрицы через блок элементов И 31 на выходы 21, — 21ц блока 19 сортировки.

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

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

И, регистр приоритетов, регистр выбранных вершин, блок сортировки, причем в каждом формирователе весов дуг матрицы выход переполнения счетчика 20 соединен с К-входом первого триггера, нулевой выход первого триггера формирователей весов дуг i-ro (i

1,N) столбца матрицы соединен с соответствующими входами i-ro элемен- 25 та И группы, выход которого соединен с входами запуска счетчиков формирователей весов дуг i-й строки, R-вход триггера блока управления соединен с входом пуска устройства, первый вход 30 первого элемента И блока управления соединен с выходом генератора тактовых импульсов, входы второго элемента И блока управления соединены с выходами элементов И группы, а выход второго элемента И блока управления подключен к S-входу триггера блока управления, группа выходов i-ro счет чика группы соединена с группой входов i-ro блока элементов И группы 40 блоков элементов И, группа выходов которого соединена с i-й группой информационных входов блока сортировки информации, i-й выход которого соединен с входом установки i-го раз- 45 ряда регистра приоритетов, выходы которого являются группой информационных выходов устройства, группа входов установки регистра выбранных вершин является первой группой ин- 50

31 8 формационных входов устройства, о тл и ч а ю щ е е с я тем, что, с целью расширения области применения устройства, в каждый формирователь весов дуг введены матрицы формирователей, второй триггер, а в устройство введено N элементов запрета,элемент задержки, в блок управления введен третий элемент И, причем в каждом формирователе весов дуг матрицы нулевой выход второго триггера соединен с I-входом первого триггера, R-входы первых триггеров формирователей весов дуг i-й строки матрицы соединены между собой и подключены к i-му входу второй группы информационных входов устройства, прямые входы элементов запрета соединены с выходом первого элемента И блока упавления, выход i-ro элемента запреа соединен со счетным входом i-ro егистрирующего счетчика, группа вхо,дов третьего элемента И блока управления соединена с группой выходов регистра выбранных вершин, выход третьего элемента И блока управления соединен с сигнальным выходом устройства и с входами сброса всех разрядов регистра выбранных вершин, выход i-го разряда регистра выбранных вершин соединен с входом сброса.

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

И группы соединен с входом i-го блока элементов И группы блоков элементов И и с инверсным входом i-rо элемента запрета того же столбца, прямой выход триггера блока управления соединен с К-входами вторых тригге- ров всех формирователей весов дуг матрицы и с входом элемента задержки, выход которого соединен с управляющим входом блока сортировки инфор. мации, нулевой выход триггера блока управления соединен с вторым входом первого элемента И блока управления, выход которого соединен со счетными входами счетчиков всех формирователей весов дуг матрицы.

1319031 вериг. 7

131 9031

35 зб 37

Фиа 3

Корректор Г.Решетник

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

Составитель M.Ñîðo÷àí

РедактоР Н.РогУлич ТехРеД 11.Уоданич

Закаэ 25 13/43 Тираж 672 Подписное

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

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

2!у

272

Йи