Устройство для распределения заданий процессорам Советский патент 1986 года по МПК G06F9/50 

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

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

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

Устройство содержит элементы ИЛИ 1, счетчики 2,. элементы 3, элементы ИЛИ-НЕ А, элементы И 5, блок 6 памятиJ элементы И 7-11, элемент ИЛИ 12, группы, кодовых входов 13 устройства, адресные входы 14 устройства, сигнальный, вход 15 устройства} так- товьш вход 16 устройства,.сигнальный вход 17 устройства, информационные выходы 18 устройства, сигнальный выход 19 устройства.

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

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

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

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

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

Соответствие вершины графа и счетчика 2 определяется весом вершины, пред ста в.пятщим величину макси)

5

0

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

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

Сформированный таким образом на одном из выходов 18 устройства импульсный сигнал инициирует решение соогветствующей задачи на одном из 5 свободньЕ процессоров вычислительной системы и одновременно с этим через одноименный элемент ИЛИ 1 группы по переднему фронту переключает од0

5

0

5

3.

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

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

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

Работа устройства продолжается до тех пор, пока не будет решена последняя задача, соответствующая конечной вершине графа, после чего вычислитель ная система устанавливает на входе 15 устройства единичный сигнал при нулевом адресе на входах 14 устройства Очередной тактовый импульс, пройдя через открытые элементы И 9 и 8, формирует на выходе 19 устройства сиг8384

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

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

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

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

одноименного элемента ИЛИ группы,

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

элемента И и с инверсным входом

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

вход которого соединен с выходом

элемента ИЛИ, входы которого соединены с выходами элементов ИЛИ-НЕ пер- ,вой группы, входы каждого из которых соединены с выходами одноименных

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

выход каждого элемента HJM-HE первой группы с первого по -и (где k целая часть числа 0,5 h ) соединен с соответствующим входом одноименного и последующих элементов ИЛР1-НЕ второй группы до k -го включительно, выход каждого элемента ИЛИ-НЕ первой группы с (k+1)-ro по (ц-1)-й соединен с соответствующим входом одноименно-

14 14 Ю 15

Редактор Е. Копча

Составитель М. Кудряшев Техред М.Ходанич

Заказ 2986/51

Тираж 671

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

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

го и последующих элеь ентов ИЛИ-НЕ второй группы до Сп-1)-го йключИтель- но, выход каждого i -го (, ...,и) элемента ИЛИ-НЕ второй группы соединен с третьим входом (i+1)-ro элемента И второй группы, выход k -го элемента ИЛИ-НЕ второй группы соединен с четвертыми входами, k4- 2-го и всех последующих элементов И второй группы.

ffi

17

Корректор И. Муска

Подписное

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