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

 

(72) Авторы изобретения

В А. Ти гов Ю П Афанасьев и Д, СKß„ó ð()ð . . (7) ) Заявитель

БИЬЛИОТИКА (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ ЗАДАНИЙ

ПРОБЕССОРАМ

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

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

Наиболее близким к предлагаемому является устройство дпя распределения заданий процессорам, содержашее матувтцу формирователей весов дуг, каждый из которых содержит трьптер и счетчик выход которого подключен к входу т1жггера, выход триттера каждого столбца матрицы формирователей весов дуг соединен с соответствукишп. входом перво2 го элемента И, генератор тактовых импульсов, блок управления в составе второго, элемента И схемы начального пуска, третьего элемента И, триггера, четвертый элемент И, и -разрядные регистр приоритетов, регистр выбранных sepusa„ пятых элементов И, камбинапионную схему, по числу столбцов матричной модели сети дополнительные тригтеры, шестые элементы И P2 ) .

Недостатком известных устройств является низкая надекность.

Цепь изобрегения - повышение надеж ности, Указанная цепь достигается тем, что в устройство дпя распредзтения заданий . процессорам, содержашее матричную модель сети, блок управления, первый вы ход которого подключен к управляющему входу шифратора, выходы которого сое динены с входами ри истра приоритета, входы кагорого являются выходами уст» ! ройства s подключены к первым входам элементов И первой грутты, вторые вхо

3 940 ды которых соединены с Выходами регистра выбранных вершин, входы которого явтяк гся входами устройства, выходы элементов И первой группы соединены с Входами трнггероВ первой группы, Вы ходы когорых подключены к первым,выходам элементов И второй группы, выходы которых соединены с информационными входами шифратора, первую г руппу счетчиков и третью грутпту элементов И, выходы которых подключены к входам счетчиков первой группы, выходы которых соединены с вторыми входами элементов И второй груцпы, ВЪедены вторая, группа триггеров, вторая группа счетчиков, четвертая группа элементов И и группа элементов ИЛИ-НЕ, входы которых соединены соответственно с выходами матричной модели сети, выходы элементов ИЛИ-HE группы подключены к первым входам элементов И четвертой группы, вторые входы которых соединены с первыми входами элементов И третьей группы и подключены к второму выходу блока управпения, выходы элементов И четвертой rpymIII подключены к входам счетчиков второй группы, выходы которых соединены с входами матричной модели сети и с входами туаптеров второй группы, выходы которых подключены к вторым входам элементов И третьей группы и к входам блока управления.

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

Устройство содержит матричную модель

1 сети в составе триггеров 2, по числу строк матрицы группу элементов ИЛИ HE

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 начального пуска, тригг ep 19, входы 20 и 21 и выход 22.

Первоначально в модель 1 заносится информация о топологии моделируемого гра а. При этом триггеры 2„. (1, *= 1; и ), которые являются формирователями дуг; устанавливаются в единичное сосгояние, если есть информационная

СВЯЗЬ ИЗ - -Ой ВЕРШИНЫ В J -Ю ВРРШИНУ.

Соответствуюший триггер 2.; определ"-." егся пересечением (-ой строки и j -го

IO столбца. Другие триггеры 2„, а также триггеры 6, 9 и 19, счетчики 8 находя*т ся в нулевом состоянии. В счетчики 5 соогветствукших вершин графа заносятс числа импульсов, дополняющие веса " °

1 вершин до полной емкости счетчиков.

После занесения исходной информации на входах элементов ИЛИ-НЕ 3, объединяющих выходы триггеров 2 в строках, ccîãветствуюшим конечным вершинам графа, о будут высокие потенциалы. Это объясняется тем, что в однонаправленном графе без циклов и петель конечные вершины не содержат выходящих ветвей, à следс вательно, все триггеры 2 в этой строке будут в нулевом состоянии.

Первоначально в устройстве происходит определение величин максимальных путей из данной вершины до конечной вершины графа, описывающего набор информационно-связанных задач. При этом с появлением пускового сигнале на входе 20 схемы 17 начального пуска импульсы с выхода генератора 15 поступают на входы элементов И 4 и 7, а далее на все счетчики 8, так как в исходном

35 состоянии все триггеры 6 находятся в нулевом состоянии, а управляемые входы элементов И 7 подключены к нулевым выходам триггеров 6. Кроме того, счетные импульсы поступают через элементы

4()

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

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

45 одноименного элемента И 4 будет высокий потенциал.

Огсчитев число импульсов, пропор циональное весу моделируемой верши50

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

164 4 ны, счетчик 5 переполняется, устанавливает в единичное состояние соответствующий триггер 6, а все триггеры 2 в пенном столбце матукчной модели - в нулевое состояние. Переброс триггера 6 в единичное состояние обеспечвает прекращение подачи счетных импульсов через элемент И 7 на вход регистрирующего счетчика 8, на котором фиксирует4 6 но, с точностью до одного триггера, на (И - И ) счетчиков, в которые заносятся числа импульсов, дапопняюшие aeca" вершин до полной емкости счетчиков) по сравнению с известным. Сокрашение аппаратных затрат в устройстве, выполняющем те же функции,привоиит к соответствующему увеличению на иежности устройства, Формула иэобрет ения

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

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

Источники информации, принятые во внимание при эксг.артизе

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

% 664175, кл, G06 F 15/20, 1976.

2. Авторское свидетельство СССР по заявке М 2886510/18-24, кл. 606 Г 15/20, 1979 (прототип), 5 94016 ся код максимального луги из данной вершины до конечной вершины графа информационно-связанного набора задач.

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

18 будет низкий потенциал, в результате чего прекрашается подача счетных импуль сов с выхода генератора 15 через элемент 16 совпадения на информационные входы элементов И 4 и 7.

С выхода триггера 19 высокий потенциал подается и на управляемый вход шифратора 14, который обеспечивает по-; 15 явление высокого потенциала на одном или нескольких иэ И своих выходов, которые соответствуют максимальному коду, храняшемуся на одноименном счетчике 8. На вход шифратора 14 коды со счетчиков 8 подаются через элементы

И 10, на управляемые входы которых подается высокий потенциал с нулевых выходов триггеров 9. В результате на регистре 12 устанавливается код, содер- 25 жаший набор нулей и один или несколько единиц. Зтсхг код подается через выход.ные шины 22 на супервизор вычислительной системы (не показан), который вы6HpaeT пп реализации o epennyro m rrpo- 3О грамму, дпя которой в соответствуюшем разряде регистра 12 имеется единица.

При наличии в регистре 12 одновременно нескольких единиц супервизор выбирает очередной ту прогр™у, дпя которой 35 номер разряда, содержаший единицу, наименьший.

После выбора одной иэ программ набора для реализации в вычислительной системе супервизор записывает в соот- 4О ветствуюпщй номеру (например, 4 = 1;и ) выбранной программы разряд регистра 11 едппцгу. В результате на выходе элемента 13 будет высокий по.тенциал, rro которому триггер, 9 g пер 45 ходит в единичное состояние, подача ко.да со счет пгка 81 на входы шифратора 14 прекрашается и на регистре 12 записыва

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

Работа устройства прекрашается при появлении на регистре 12 нулевого кода.

Таким образом, предпагаемое устройство эа счет введения новых элементов

55 распределение набора информац юинсь вя« занных задач по процессорам .вычисли тыьной системы, сушественно сокрашаются аппаратные затраты (прибпизитель