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

Ё

Изобретение относится к вычислительной технике и может быть использовано в качестве диспетчера для распределения заданий процессорам в многопроцессорной вычислительной системе (МВС) класса МКМД при вертикальном распараллеливании программ. Цель изобретения - повышение быстродействия устройства, Устройство содержит каналы, а в каждом канале три группы элементов И, группу блоков элементов И, группы элементов НЕ, две группы триггеров. Устройство содержит группу элементов ИЛИ, блок выбгг,э заданий, счетчик, группу триггеров, элемент ИЛИ, элемент И, дешифратор. При освобождении любого процессора очередное задание распределяется сразу до окончания текущего задания. 2 ил.

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

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

На фиг. 1 представлена структурная схема устройства для распределения заданий процессорам; на фиг.2 - структурная схема блока выбора заданий.

Устройство (фиг.1) содержит каналы, в каждом из которых группа триггеров 1, группы триггеров 2, группу элементов И 3, группу элементов И 4, группу элементов НЕ 5, группу элементов И 6, группу блоков элементов И 7. Устройство содержит группу элементов ИЛИ 8, группы элементов И 9, 10,

группу триггеров 11, элемент ИЛИ 12, блок 13 выбора заданий, элемент И 14, счет-1ик 15, дешифратор 16, тактовый вход 17 устройства, вход опроса 18 устройства, сигнальные входы 19 устройства, информационные выходы 20 устройства, входы 21,22 бока 13, выхода 23, 24 блока 13.

Блок выбора заданий (фиг.2) содержит каналы 25, в каждом из которых триггеры 26 группы, группу элементов И 27, группу элементов И - НЕ 28, группу элементов И 29, блок выбора заданий содержит группу элементов ИЛИ 30, группу элементов ИЛИ 31 и узел 32 приоритета.

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

В исходном состоянии все триггеры находятся в нулевом состоянии. Первоначально в матрицу триггеров 1 заносится

сх го

VI

00

информация о топологии пройденных путем (установочные входы на схеме не показаны). В триггеры 2 заносится информация аналогичная, за исключением информации о последних вершинах. По управляющему сигналу, который поступает на вход 17, я триггеры 11 заносится информация о свободных процессорах по гходам 19 устройства. Если свободен хотя бы один процессор, то единичный сигнал, пройдя через элемент ИЛИ 12, подается на элемент Иг 14 и на группу элементов И 9. На вход 18 устройства подается управляющий сигнал, частота которого больше иастоты управляющего сигнала, который подается на вход 17 устройства. Единичный сигнал с выхода элемента И 14 подается на счетчик 15 и г него на дешифратор 16, с выхода дешифратсла сигналы подаются на первые входы элементов И группу 6. На вторые входы этих .элементов подается информация с триггеров 1. Единичные сигналы с триггеров 1 проводит через элементы И б, элементы ИЛИ 8, элементы И 9 и подаются на входы блока 1Я.

Блок 13 работает следующим образом.

Сигналы, поступающие на входы 21 бло ка, проходят через узел 32, который выделяет один сигнал. Выделенный поступает на вход элемента И группы 27. На второй вход элемента поступает сигнал с соответствующего триггера 11. Если триггер 11 находится в единичном состоянш/:, го сигнал с узла 32 поступает на вход установки в 1 триггера 26 группы. Если триггер 11 находится в нулевом состоянии, то сигнал проходит через элементы И - НЕ 28 и И 29 групп для установки следующего трип ера 26 группы. Сигнал с выхода триггера 26 группы поступает на входы элементов ИЛИ 31 и ИЛИ 30 групп. С выхода элементов ИЛИ 31 группы единичный сигнал поступает на вход установки в О соответствующего триггера 11. Это говорит о том, что процессор начал обработку соответствующей вершины. Одновременно сигнал с выхода элемента ИЛИ 30 группы поступает на элементы НЕ 5. С выхода элементов НЕ 5 сигнал подается на вход элемента И 4 группы. На вторые входы элементов И 4 группы подаются сигналы с инверсных выходов триггеров 1. С выхода элемента И 4 группы сигнал поступает на вход установки в О триггера 2 группы. С выхода триггеров 2 группы сигнал подается на входы управления блоков 7, который разрешает прохождение единичных сигналов с остальных триггеров 1, Сброс триггера 2 свидетельствует об окончании обработки соответствующей вершины.

Ф о р м у ji ,1 о f р е т е н и я

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

что. с целью повышения быстродействия, устройство содержит дешифратор, а в каждом канале вторую -руппу триггеров, три группч элементов И и группу элементов НЕ, причем прямое выход ка кдо о триггера первой группы Кс1жг.ого канала соединен с первым BXIV JM одноименного элемента И первой группы свое--о кана/:а, выходы эле- Л первой грулпь- КАЖДОЮ канала соединены с входами

одноименного блика ;v .чментов И, второй вход каждого элемента 1 первой группы во все каналах соединен с. одноименным выходом дешифратор-, входы которого соединены с выходам , счетчика, счетный вход

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

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

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

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

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

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

e элементы НЕ группы с первыми входами -элементов И третьей группы, в каждом канале выход элемента И второй группы сое- д/1нен с входом сбрбса эдноименного триггера первой груг.пы, инверсный выход триггера первой группы, кроме пьгледнего.

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

LJL щш

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

ijfeL

-а, Чг

-щ

Пг ft

Яя fety

Физ./

Zip 23р &,fy #р

u-i

U7