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

 

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

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

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

РЕСПУБЛИК (5Н4 G 06 F 9/4

У;";у;.

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

К A BTOPCHOMY СВИДЕТЕЛЬСТВУ для распределения заданий процессорам, и предназначено для использования в высокопроизводительных многопроцессорных или многомашинных вычислительных и управляющих системах.

Целью изобретения является повышение быстродействия работы устройства.

Устройство для распределения заданий процессорам содержит группу из счетчиков (и — число решаемых задач в пакете), первую группу из h элементов ИЛИ-НЕ, блок памяти, группы из и элементов ИЛИ, вторую группу из (н-1) элементов ИЛИ-НЕ, первую группу из п элементов И, вторую группу из tn элементов И (e .-разрядность ад- Й ресного входа блока памяти), четыре элемента И и элемент ИЛИ. 1 ил.

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3819426/24-24 (22) 03.12.84 (46) 30.05.86, Бюл. ¹ 20 (71) Харьковский ордена Ленина авиационный институт им.Н.Е.Жуковского (72) Ю.И.Ялинич, В.Ю.Ларченко, К.К.Фурманов и М.Ф.Холодный (53) 681.325(088.8) (56) Авторское свидетельство СССР № 966697, кл. G 06 F 9/46, 1982.

Авторское свидетельство СССР №- 1001101, кл. С 06 F 9/46, 1983. (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ

ЗАДАНИЙ ПРОЦЕССОРАМ (57) Изобретение относится к области автоматики и вычислительной техники, а точнее — к приоритетным устройствам

„.SU 1 4 3 А1

4 12348

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

Цель изобретения — повышение быстродействия устройства„

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

Устройство содержит элементы ИЛИ 1, счетчики 2,. элементы ИЛИ-НЕ 3, элементы ИЛИ-НЕ 4, элементы И 5, блок 6 памяти, элементы И 7-11, элемент ИЛИ

12, группы кодовых входов 13 устройства, адресные входы 14 устройства, сигнальный вход 15 устройства, тактовый вход 16 устройства, сигнальный вход 17 устройства, информационные выходы 18 устройства, сигнальный выход 19 устройства.

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

Исходное состояние устройства характеризуется тем, что импульсы на тактовом входе 16 устройства отсутствуют, в связи с чем на информационных выходах 18 устройства и на его сигнальном выходе 19 сигналов не будет (нулевые уровни сигналов).

Блок 6 памяти содержит информаци!о о топологии графа, описывающего набор информационно связанных задач. По адресу, соответствующему номеру (= 1, ..., и — 1) некоторой вершины графа, в блок 6 памяти занесено q -разрядное число, имеющее в соответствующем q -м разряде единицу, если из

I é вершины графа исходит дуга„ ведущая в q — ю вершину графа.

По нулевому адресу, соответствующему конечной вершике графя, в блок 6 памяти занесен нуль.

В счетчики 2 с одноименных групп входов 13 заносятся коды степени захода соответствующих вершин графа, представляющие количества дуг, входя-щих в соответствующие вершины графа.

В зависимости от того, какие счетчики — вычитающие или суммируюи„ие используются в качестве счетчиков 2, степень захода вершин представляетcR соответственно прямым или дополнительным кодом.

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

Рабста устройства начинается с приходом первого тактового импульса на вход 16 устройства. Так как на выходах элементов ИЛИ-НЕ 3 группы, соответствующих счетчикам 2, в которые занесен лулевой код степени захода, установлены единичные сигналы запросов,то на выходе элемента ИЛИ 12 будет единичный сигнал, который при наличии сигнала ка входе 17 устройства (свидетельствует о наличии свободных процессоров) проходит на выход элемента И 11, запрещая работу элемента И 9 по его инверсному входу и разрешая передачу тактового импульса со входа 16 устройства через элемент И,10 на входы всех элементов И 5 группы, при этом тактовый импульс проходит на выход только одного из элементов И 5, соответствующего .запросу на решение задачи с наибольшим весом, т.е. проходит на выход самого верхнего на чертеже элемента И 5, принимающего сигнал запроса с выхода одноименного элемента ИЛИ-HI, 3 группы. Все остальные расположенные ниже элементы И 5 группы запираются нулевыми сигналами с выходов соответствующих элементов

ЕПИ-НЕ 4 группы.

Сформированный таким образом на одном из выходов 18 устройства HM пучьсный сигнал инициирует решение соогветс".-вующей задачи на одном из свободных прсцессоров вычислительной системы н одновременно с этим через одноименный элемент ИЛИ 1 группы по переднему фронту переключает од1234838 4 нал, свидетельствующий об окончании решения пакета задач. з ноименный счетчик 2, выводя его из нулевого состояния и тем самым снимая запрос на решение уже распределенной для решения задачи.

Новый цикл работы устройства начинается с приходом очередуого тактового импульса на вход 16 устройства. При наличии свободных.процессоров и сигнала запроса на выходе элемента ИЛИ 12 тактовый импульс через 10 элемент И 10 поступает на входы всех элементов И 5 группы и проходит на тот же вьмод 18 устройства, который соответствует запросу на решение задачи с наибольшим весом. Происходит распределение выбранной задачи для решения на одном из свободных процессоров, и одновременно снимается запрос на ее решение, Если при поступлении очередного тактового импульса на вход 16 устройства элемент И 10 оказывается запертым нулевым сигналом с выхода элемента И 11, возникающем при отсутствии запросов на решение задач либо при отсутствии свободных процессоров, то анализируется состояние входа 15 устройства, т.е. наличие задач, решение которых в вычислительной системе закончено. При наличии единичного сигнала на входе

15 устройства тактовый импульс через элемент И 9 поступает на входы всех элементов И 7 группы, разрешая выдачу на адресные входы блока 6 памяти 35 адреса решенной задачи с адресных входов 14 устройства, в результате чего формируются импульсные сигналы на тех выходах блока 6 памяти, которые. соответствуют задачам, непосред- 40 ственно информационно связанным с решенной задачей, и происходит изменение на единицу кодов степени захода этих задач (при этом могут сформироваться запросы на решение некото-45 рых из этих задач, если станут нулевыми их коды степени захода).

Работа устройства продолжается до тех пор, пока не будет решена послед-50 няя задача, соответствующая конечной вершине графа, после чего вычислительная система устанавливает на входе 15 устройства единичный сигнал при нулевом адресе на входах 14 устройства.SS

Очередной тактовый импульс, пройдя через открытые элементы И 9 и 8, формирует на выходе 19 устройства сигФормула из об ре те ния

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

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

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

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

Редактор F.. Копча Техред М.Ходанич Корректор И. Муска

Заказ ?986/51

Тираж 671

Подписное

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

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

Производственно-по: I-. графическое предприятие,, г,. Ужгород, ул. Проектная, 4 вьгход каждого элемента ИЛИ-НЕ первой группы с первого по 4 -й (где к целая часть числа 0,5 и ) соединен с соответствующим входом одноименного и последующих элементов ИЛИ-НЕ второй группы до k — го включительно, выход каждого элемента ИЛН-НЕ первой группы с (k+1)-го по (н-1) — и соединен с соответствующим входом одноименного и последующих элементов ИЛИ-НЕ второй группы до (rl-1)-го включительно, выход каждого l -го (1 =1, ...,n ) элемента ИЛИ-НЕ второй группы соединен с третью входом (i+1) — го элемента И второй группы, выход k — ro элемента ИЛИ-НЕ второй группы соединен счетвертыми входами k+ 2-ro и всех

10 последующихэлементов И второй группы.