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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 119) (11 51)4 С 06 Г 9/4 ДАРСТВЕННЫЙ НОМИТЕТ ССЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫ ГО И ОПИСАНИЕ ИЗОБРЕТЕН АВТОРСКОМУ СВИДЕТЕЛЬСТВУ а ав ског о,о СС 1982 СССР 198 идетельств Г 9/46,тельство 6 Г 9/46, области ехники,ройствам(71) Харьковский ордена Леционный институт им.Н.Е.Жук(54) УСТРОЙСТВО ДЛЯ РАСПРЕДЗАДАНИЙ ПРОЦЕССОРАМ(57) Изобретение относитсяавтоматики и вычислительнойа точнее - к приоритетным у для распределения заданий процессорам, и предназначено для использования в высокопроизводительных многопроцессорных или многомашинных вычислительных и управляющих системах.Целью изобретения является повышениебыстродействия работы устройства.Устройство для распределения заданийпроцессорам содержит группу изсчетчиков ( и - число решаемых задачв пакете), первую группу из 11 элементов ИЛИ-НЕ, блок памяти, группы изи элементов ИЛИ, вторую группу из(п) элементов ИЛИ-НЕ, первую группу из п. элементов И, вторую группуиз 1 п элементов И (в .-разрядность адресного входа блока памяти), четыреэлемента И и элемент ИЛИ, 1 ил.4 12348Изобретение относится к автоматике и вычислительной технике и предназначено для использования в высокопроизводительных многопроцессорных или многомашинных вычислительных иуправляющих системах,Цель изобретения - повышение быстродействия устройстваНа чертеже изображена структурнаясхема устройства для распределениязаданий процессорам.Устройство содержит элементы ИЛИ 1,счетчики 2,. элементы ИЛИ-НЕ 3, элементы ИЛИ-НЕ 4, элементы И 5, блок 6памяти, элементы И 7-11, элемент ИЛИ12, группь 1 кодовых входов 13 устройства, адресные входы 14 устройства,сигнальный вход 15 устройства, тактовый вход 16 устройства, сигнальныйвход 17 устройства, информационныевыходы 18 устройства, сигнальныйвыход 19 устройства.Устройство работает следующимобразом.Исходное состояние устройства характеризуется тем, что импульсы натактовом входе 16 устройства отсутствуют, в связи с чем на информационных выходах 18 устройства и на егосигнальном выходе 19 сигналов небудет (нулевые уровни сигналов).Блок 6 памяти содержит информаци 1 оо топологии графа, описывающего набор информационно связанных задач. Поадресу, соответствующему номеру1, , о - 1) некоторой вершиныграфа, в блок 6 памЯти занесено 0 -разрядное число, имеющее в соответствующем о -м разряде единицу, если из-й вершины графа исходит дуга ведущая в о - ю вершину графаПо нулевому адресу, соответствующему конечной верщике графа, в блок 6памяти занесен нуль. В счетчики 2 с одноименных групп входов 13 заносятся коды степени захода соответствующих вершин графа, представляющие количества дуг, входящих в соответствующие вершинь 1 графа. В зависимости от того, какие счетчики - вычитающие или суммирующие используются в качестве счетчиков 2, степень захода вершин представляется соответственно прямым или .Гопол нительным кодом. 5Соответствие вершины графа и счетчика 2 определяется зесом вершины, представляющим собой величину макси 38 2мальцого пути из данной вершины до конечной вершины графа, описывающего набор информационно связанных задач и имеющего в качестве весов дуг длительности решения задач. Первому счетчику 2 (самому верхнему ца чертеже) должна соответствовать вершина графа с наибольшим весом, второму счетчику 2 - вторая по весу вершина графа и т,д. Последнему счетчику 2 будет соответствовать конечная вершина графа, имеощая нулевой вес, Такое соответствие вершин и счетчиков 2 позволяет минимизировать время решения всего пакета информационно связанных задач, так как из некоторой совокупности запрашивающих решения запач (для решвния которых имеется вся необхоцимая информация) первой реша,ется задача, имеющая больший вес.Рабста устройства начинается с приходом первого тактового импульса ца вход 16 устройства. Так как на выходах элемецтов ИЛИ-НЕ 3 группы, соответствующих счетчикам 2, в которые занесен яулевой код степени захода., установлены единичные сигналы запросов,то на выходе элемента ИЛИ 12 будет единичный сигнал, который при наличии сигнала на входе 17 устройства (свидетельствует о наличии свободных процессоров) проходит на выход элемента И 11, запрещая работу элемента И 9 по его инверсному входу и разрешая передачу тактового импульса со входа 16 устройства через элемент И,10 на входы всех элементов И 5 группы, при этом тактовый импульс проходит на выход только одного из элементов И 5, соответствующего запросу на рещение задачи с наибольшим весом, т.е. проходит на выход самого верхнего на чертеже элемента И 5, принимающего сигнал запроса с выхода одноименного элемента ИЛИ-НЕ 3 группы. Все остальные расположенные ниже элементы И 5 группы запираются нулевыми сигналами с выходов соответствующих элементов ЕПИ-НЕ 4 группы. Сформированный таким образом на одном из выходов 18 устройства импульсный сигнал инициирует решение соответствующей задачи на одном из свободных прсцессоров вычислительной системы ц одновременно с этим через одноименный элемент ИЛИ 1 группы по переднему фронту переключает од1234838 4 нал, свидетельствующий об окончании решения пакета задач. 3ноименный счетчик 2, выводя его изнулевого состояния и тем самым снимая запрос на решение уже распределенной для решения задачи,Новый цикл работы устройства начинается с приходом очередуого тактового импульса на вход 16 устройства. При наличии свободных.процессоров и сигнала запроса на выходе элемента ИЛИ 12 тактовый импульс через 10элемент И 10 поступает на входывсех элементов И 5 группы и проходитна тот же вьмод 18 устройства, который соответствует запросу на решениезадачи с наибольшим весом. Происходит распределение выбранной задачидля решения на одном из свободныхпроцессоров, и одновременно снимается запрос на ее решение,Если при поступлении очередноготактового импульса на вход 16 устройства элемент И 10 оказывается запертым нулевым сигналом с выхода элемента И 11, возникающем при отсутствиизапросов на решение задач либопри отсутствии свободных процессоров, то анализируется состояниевхода 15 устройства, т.е. наличие задач, решение которых в вычислительной системе закончено, Приналичии единичного сигнала на входе15 устройства тактовый импульс черезэлемент И 9 поступает на входы всехэлементов Игруппы, разрешая выдачу на адресные входы блока 6 памяти 35адреса решенной задачи с адресныхвходов 14 устройства, в результатечего формируются импульсные сигналына тех выходах блока 6 памяти, которые соответствуют задачам, непосредственно информационно связанным срешенной задачей, и происходит изменение на единицу кодов степени захода этих задач (при этом могут сформироваться запросы на решение некото рых из этих задач, если станут нулевыми их коды степени захода). Работа устройства продолжается до тех пор, пока не будет решена последняя задача, соответствующая конечной вершине графа, после чего вычислительная система устанавливает на входе 15 устройства единичный сигнал при нулевом адресе на входах 14 устройства.55 Очередной тактовый импульс, пройдя через открытые элементы И 9 и 8, формирует на выходе 19 устройства сигФормула из об ре те ния Устройство для распределения заданий процессорам, содержащее группу счетчиков, блок памяти, группу элементов ИЛИ, две группы элементов ИЛИ-НЕ, две группы элементов И, четыре элемента И, о т л и ч а ю щ ее с я тем, что, с целью повышения быстродействия, устройство содержит элемент ИЛИ, причем каждый вход группы адресных входов устройства соединен с первым входом одноименного элемента И первой группы и с одноименным инверсным входом первого элемента И, прямой вход которого соединен с выходом второго элемента И и с вторыми входами элементов И первой группы, выходы которьм соединены с адресными входами блока памяти, каждый выход которого соединен с первым входом одноименного элемента ИЛИ группы, второй вход каждого из которых соединен с выходом одноименного элемента И второй группы и является соответствующим информационным выходом устройства, тактовый вход которого соединен с первыми входами второго и третьего элементов И, второй вход которого соединен с выходом четвертого элемента И и с инверсным входоМ второго элемента И, второи вход кото рого является первым сигнальным вхохом устройства, второй сигнальный вход которого соединен с первым входом четвертого элемента И, второй вход которого соединен с вьмодом элемента ИЛИ, входы которого соединены с выходами элементов ИЛИ-НЕ пер,вой группы, входы каждого из которых соединены с выходами одноименных счетчиков группы, счетный вход каждого из которых соединен с выходомодноименного элемента ИЛИ группы, группа информационных входов каждого счетчика группы соединена с одноименной группой кодовых входов устройства, сигнальный выход которого соединен с выходом первого элемента И, выход каждого из . (И- разрядность числа) элементов ИЛИ-НЕ первой группы соединен с первым входом одноименного элемента И второй группы, вторые входы элементов И второй группы соединены с выходом, третьего элемента И,1234838 ставитель М, 1(удрящхред М.Ходанкч Коррек И. Муска едактор опча иран 671 э 986/51 одписно нного комитета СССения и открытийРаущская наб. д,ВНИИПИ Государств по дела.м иэобре13035, Москва, 3(-35 Проектная изводственно-полиграфическое предприятие гвьгход каждого элемента ИЛИ-НЕ первойгруппы с первого по к -й (где сцелая часть числа 0,5 и ) соединен ссоответствующим входом одноименногои последующих элементов ИЛИ-НЕ второйгруппы до 1 - го включительно, выходкаждого элемента ИЛН-НЕ первой группы с (к+1)-го по (я) - й соединенс соответствующим входом одноименного и последующих элементов ИЛИ-НЕ второй группы до (п)-го включительно, выход каждого 1 -го (1=1, ,я) элемента ИЛИ-НЕ второй группы соединен стретью входом (+ 1)-го элемента И второй группы, выход к - го элемента ИЛИ-НЕ второй группы соединен счетвертыми входами 1+ 2 - го и всехс 10 последующихэлементов И второй группы.