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

(54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ ЗАДАНИЙ ПРОЦЕССОРАМИзобретение относится к вычислительной технике и может быть использовано при автоматизации выбора очередной программы из набора информационно-свя-занного набора программ для решения в управляющей многопроцессорной вычиста:- тепьной системе.Известно устройство для выбора задач в целевой системе обработки данных, содержащее дешифратор индекса зврвчи, вход которого соединен с входом устройства, регистр данных, элементы И, ИЛИ, блок имитации дуг и вершин графа, элементы запрета, регистры результатов и триггерный узел памяти 1 .Наиболее близким к предлагаемому является устройство дпя распределения заданий процессорам, содержащее матрицу формирователей весов дуг, каждый из которых содержит триер и счетчик выход которого подключен к входу триггера, выход триггера каждого столбца матрицы формирователей весов дуг соединен с соответствукншпд входом перво 2го элемента И, генератор тактовых импульсов, блок управления в составе второго,элемента И схемы начального пуска,третьего элемента И, триггера, четвертый элемент И, И -разрядные регистрприоритетов, регистр выбранных в,пятых элементов И, комбинапионнуюсхему, по числу столбцов матричной модели сети дополнительные триггеры,шестые элементы И 21.Недостатком известных устройствявляется низкая надекность,Цепь изобретения - повышение надежности,Указанная цепь достигается тем, чтов устройство для распредвтения заданийпроцессорам, содержащее матричную модель сети, блок управления, первый выход которого подключен к управляющемувходу шифратора, выходы которого соединены с входами риистра приоритета,входы кагорого являются выходами устройстваа и подключены к первым входамэлементов И первой грутпы, вторые вхо3 940ды которых соединены с выходами регистра выбранных вершин, входы которого яиикгся входами усгройсгвв, выходы элементов И первой группы соединены с Входами триггеров первой группы, Вы.ходы которых подключены к первым,выходам элементов И второй группы, выходы которых соединены с информационными входами шифратора, первую труппу счетчиков и третью грутату элементов И выходы которых подключены к входам счетчиков первой группы, выходь которых соединены с вторыми входами элементов И второй груцпы, ВЪедены вторая, группа триггеров, вторая группе счетчиков, четвергая группа элементов И и группа элементов ИЛИ-НЕ, входы которых соединены соответственно с выходами матричной модели сети, выходы элементов ИЛИ-НЕ группы подключены к первым Входам элементов И четвертой группы, вторые входы которых соединены с первыми входами элементов И третьей группы и подключены к второму выходу бпока упраьпения, выходы элементов И четвертой грушы подключены к Входам счетчиков второй группы, выходы которых соединены с входами матричной модели сети и с входами триггеров второй грлщы, выходы которых подключены к вторым входам элементов И третьей группы и к входам блока управления.На чертеже показана структурная сх ма устройства дпя распределения заданий процессорам.Устройство содержит матричную модель 1 сети в составе трютеров 2, по числу строк матрицы группу элементов ИЛИ-НЕ 3, по числу столбцов матрицы чегвергую группу элементов И 4, вторую группу счетчиков 5, вторую группу триггеров 6, третью группу элементов И 7, первую группу счетчиков 8, первую группу триг- . геров 9, вторую группу элементов И 10, регистр 11 выбранных вершин, регистр 12 приоритетна, первую группу элементов И 13, а также шифратор 14, генератор 15 тактовых импульсов, первый элемент И 16, схему 17 начального пуска, второй элемент И 18, дополнитепьный триггер 19, пусковой вход 20 устройства, информационные входы 21 устройстве и выход 22 устройства. Блок 23 управления включает генератор 15, элементы И 16 и 18, схему 17 начального пуска, триггер 19, входы 20 и 21 и выход 22. Первоначально в модель 1 заноситсяинформация о топологии моделируемогограа, При этом триггеры 2( 1,1 е и ), которые являются формирователями дуг; устанавливаются в единичное состояние если есть информационнаяСВЯЗЬ ИЗ 1 -Ой ВЕРШИНЫ ВЮ ВРРЩИНУСоответствуюший триггер 2,; определ.ется пересечением 1-ой строки и-го О столбца, Другие триггеры 2, а такжетриггеры 6, 9 и 19, счетчики 8 находятся в нулевом состоянии, В счетчики 5соогветствуюших вершин графа заносятсячисла импульсов, дополняющие веса"15 вершин до полной емкости счетчиков.После занесения исходной информации нвВходах элементов ИЛИ-НЕ 3, объединяющих выходы триггеров 2 в строках, сасгветствуюшим конечным вершинам графа,будут высокие потенциалы, Это объясняется тем, что в однонаправленном графебез циклов и петель конечные вершиныне содержат выходяших ветвей, а следсвательно, все триггеры 2 в этой строкебудут в нулевом состоянии.Первоначально в устройстве происходит определение величин максимальныхпутей из данной вершины до конечнойвершины графа, описывающего набор информационно-связанных задач, При этомс появлением пускового сигнале на входе 20 схемы 17 начального пуска импульсы с выхода генератора 15 поступают на входы элементов И 4 и 7, а далеена все счетчики 8, так как в исходном З 5состоянии все триггеры 6 находятся внулевом состояниИ, а управляемые входыэлементов И 7 подключены к нулевьгмвыходам трютеров 6. Кроме того, счетные импульсы поступают через элементыИ 4 на те счетчики 5, дпя которых тригогеры 2 одноименной строки матрицы находятся в нулевом состоянии. Поэтомуна выходе соответствукаих элементовИЛИ-НЕ 3 появляется высокий потенциал,благодаря чему на управляемом входеодноименного элемента И 4 будет высокий потенциал.Огсчитев число импульсов, пропорциональное "весу" моделируемой верши 50 55 Устройство работает следующим образом. ны, счетчик 5 переполняется, устанавливает в единичное состояние соответствуюший триггер 6, а все триггеры 2 в ценном столбце матукчной модели - в нулевое состояние, Переброс триггера 6 в единичное состояние обеспечвает прекращение подачи счетных импульсов через элемент И 7 на вход регистрирующего счетчика 8, на котором фиксирует4 бно, с точностью до одного триггера, на(И - И ) счетчиков, в которые заносятся числа импульсов, даполняюшие веса"вершин до полной емкости счетчиков) посравнению с известным, Сокрашение аппаратных затрат в устройстве, выполнявшем те же функции, привопит к соответствующему увеличению на аежности устройства,формула иэобрет енияУстройство дпя распределения эаданиФпроцессорам, содержащее матричную модель сети, блок управлппи, первый вы-ход которого подключен к управляющемувходу шифратора, выходы которого соединены с входами регистра приоритста,выходы которого являются выходами устроиства и подключены к первым входамэлементов И первой группы, вторые входы которых соединены с выходами регистра выбранных вершин, входы которогоявляются входами .устройства, выходыэлементов И первой группы соединены свходами триггеров первой группы, выходыкоторых подключены к первым входамэлементов И второй группы, выходы которых соединены с информационными входами шифратора, первую группу счетчикови третью группу элементов И, выходыкоторых подключены к входам счетчиковпервой группы, выходы которых соединены с вторыми входами элементов И второй группы, о т л и ч а ю ш е е с ятем, что, с целью повышения надежностиустройства, в него введены вторая группа Триггеров, вторая группа счетчиков,четвертая группа элементов И и группаэлементов ИЛИ-НЕ, входы которых социнены соответственно с выходами матричной модели сети, выходы элементовИЛИ-НЕ группы подключены к первымвходам элементов И четвертой группы,вторые входы которых соединены с первымн входами элементов И третьей группы и подключены к второму выходублока управления, выходы элементов Ичетвертой группы подключены к входамсчетчиков второй группы, выходы которых соединены с входами матричной модели сети и с входами триггеров второйгруппы, выходы которых подключены квторым входам элементов И третьейгруппы и к входам блока управления.Источники информашипринятые во внимание при экспертизе1. Авторское свидетельство СССР% 664175, кл, 606 Р 15/20, 1976.2. Авторское свидетельство СССРпо заявке М 2886510/18-24,кл, 606 Г 15/20, 1979 (прототип)е 5 94018ся код максимального луги из даннойвершины до конечной вершины графа информационно-связанного набора задач.Вычислительный процесс продолжаетсядо тех пор, пока на выходах всех тритгеров 6 не будут щясутствовать низкиепотенциалы. На выходе элемента ИЛИ18 будет низкий потенциал, в результатечего прекращается подача счетных импулЬсов с выхода генератора 15 через эле- Омент 16 совпадения на информационныевходы элементов И 4 и 7.С выхода триггера 19 высокий потенциал подается и на управляемый входшифратора 14, который обеспечивает по; 15явление высокого потенциала на одном или нескольких иэ И своих выходов, которые соответствуют максимальному коду, храняшемуся на одноименном счетчике 8. На вхОд шифратора 14 коды со 20счетчиков 8 подаются через элементыИ 10, на управляемые входы которыхподается высокий потенциал с нулевыхвыходов триггеров 9, В результате нарегистре 12 устанавливается код, содержаший набор нулей и один нли несколькоединиц. Зтог код подается через выходные шины 22 на супервизор вычислительной системы (не показан), который выбирает для реализации очередную ту программу, для которой в соответствуюшемразряде регистра 12 имеется единица. При наличии в регистре 12 одновременно нескольких единиц супервизор выбирает Очередной ту программу для которой 35 номер разряда, содержащий единицу, наименьший.После выбора одной иэ программ набора для реализации в вычислительной системе супервизор записывает В соот 4 Оветствуюпщй номеру (например, 4 = 1;и )выбранной программы разряд регистра 11 единищ. В результате на выходе элемента 13 будет высокий потенциал,. по которому триггер 9 3 пеРе ходит в единичное состояние, подача ко.да со счет дпа 81 на входы шифратора 14 прекращается и на регистре 12 записыва Ьтся другой код, по которому супервизор выбирает нереализованные программы. Работа устройства прекрашается при появлении на регистре 12 нулевого кода.Таким образом, предлагаемое устройство эа счет введения новых элементов55 распределение набора Информацчонноэя занных задач по процессорам .вычисли тыьной системы, сушественно сокращаются аппаратные затраты (приблизитель