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

4

00 Ч

сх

О5

со

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

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

На чертеже изображена схема устройства.

Устройство содержит группу входов 1-4 кода задания устройства, одно- вибратор 5, шифратор 6 условий запуска, группу элементов И 7, группу выходов 8 кода вектора микропрограммы устройства, вход 9 опроса устройства, элемент И 10,-регистр 11 сдвига, регистр 12 готовности, триггер 13 квитанции, элемент ИЛИ-НЕ 14, группу элементов И 15, элемент И 16, элемент ИЛИ-НЕ 17, элемент 18 задержки, одновибратор 19, группу одновиб раторов 20,. выход 21 подтрерждения начала обслуживания устройства, элемент 22 задержки, группу входов 23 количества свободных процессоров устройства, регистр 24 готовности процессоров, п 1еобразователь 25 числа единиц в двоичный код, группу выходов 26 устройства.

Перед началом работы устрой ства регистры сдвига 11 и готовности 12 содержат во всех разрядах логические О триггер 13 квитанции находится в нулевом состоянии, регистр 24 готовности процессоров содержит код, единичные разряды которого соответствуют свободным процессорам многопроцессорной системы, которой управляет данное устройство на выходах преобразователя 25 числа единиц в двоичный код, двоичный код, соответствующий количеству свободных процессоров Мей входе опроса 9 логический О, который запирает элемент И 10, на выходе элемен- .та ИЛИ-НЕ 14 логическая I, которая подготавливает прохождение квитанции триггера 13 квитанции через элемент И 16 и запирает элемент ИЛИ-НЕ 17, используемый как схема И, управляемая логическими нулями, что выключает генератор импульсов, состоящий из элемента ИПИ-НЕ 17, одновибрато- ра 19, элемента 22 задержки, на входе сдвига регистра 11 сдвига логический О,-элемент 1В задержки выдает на выход 21 устройства логический О, на (N-«-l )-м выходе шифратора условий запуска 6 произвольньп сигнал (0-1 ). на выходе одновибратора 3 лгический О, который, поступая ня вторые входы группы элементов И 7, запирает элементы И этой группы, все элементы И 15 группы заперты логическими О регистра 11 сдвига, подаваемыми на первые входы элементов И 15 группы, что не позволяет группе од- новибраторов 20 вьфабатьшать импульсы,

0 В первый момент времени работы устройства на группу входов 1 устройства поступает код операции КОП, на группу входов 2 поступает код типа операции ТОП, характеризующий типы

5 операндов (операнды-матрицы, операн- ды-вектора, операнды-матрица/вектор, операндьг-матрица/скаляр и т.д.), на группы входов 3 и 4 поступают коды - размеры матриц-операндов, соответ0 ствующие операнду большей размерности. Формат адреса, поступающего на вход шифратора б условий запуска, имеет следующий вид:

25

КОП

топ m п сб

30

По сформированному адресу выбирается код варианта реализации макрокоманды, имеющей следующий формат:

ВМ МЧи

где (М - код, в котором количество единиц равно количеству

необходимых процессоров; ВМ - вектор микропрограммы,

реализующей макрокоманду для устройства управления процессоров;

Р - бит подтверждения неравенства.

В следующий момент времени tp на вход 9 опроса подается логическая

1. Если в этот момент кол гчество единиц в коде н меньше количества единиц в коде р , что бит Р содержит нуль и в устройстве ничего не происходит до тех пор , пока процессоры, выставляя сигналы Свободен на входы 23 устройства, не установят в регистре 24 готовности процессоров такой код, что количество единиц в .коде jWcg, станет больше или равно ко- личеству единиц в коде «м. В этом случае бит Р содержит единицу, которая пропускается через элемент И 10, а также инициирует выработку единичного импульса одновибратором 5. Единим 1

ньй нмиульс, выр-чботанный одновибряf ic

тором 5, открывает все элементы И 7 группы. Код с количеством единиц из регистра 24 готовности процессоров переписывается в регистр 2 готовности. После этого изменение сигналов на группе входов устройства не влияет на работу устройства.

Изменение сигнала на вьпсоде эле- мента И 10 с О в 1 устанавливает триггер 13 квитанции в 1 и квитанция с выхода триггера 13 квитанции через элемент И 16 поступает на вход записи регистра 11 сдвига. Изменение сигнала на входе записи регистра 11 сдвига с О на 1 переписывает ко

С с первого по Ы-й выходов шифра- )ра 6 условий запуска в регистр i1 сдвига. Так как весовой код |Чн в ре- гистре сдвига не равен нулю, элемент ИЛИ-НЕ 14 вырабатывает на своем выходе логический О. Код открьша- ет те элементы И группы элементов И 15, которые соответствуют разрядам кода |Иц , содержащим единицы.

В следующий момент времени логический О, выработанный элементом ИЛИ-НЕ 14, запирает элемент И 16 и отпирает схему И по нулям (элемент Ш1И-НЕ 17). Через интервал времени д на выходе элемента 18 задержки появляется логическая 1, которая сбрасывает триггер 13 квитанции в О, подготавливая его к выработке квитанции на новую заявку.

Логические 1, выработанные элементами И 15 группы, запускают соответствующие одновибраторы группы одновибраторов 20 и сбрасьшают разряды регистра 24 готовки процессоров, соответствующие совпавшим единицам разрядов регистров сдвига 11 и готовности 12.

В следующий момент времени единичные импульсы, выработанные группой одновибраторов 20, поступая на группу входов установки в О регистра 11 сдвига и группу входов установки в О регистра 12 готовности, устанавливают в регистре 11 сдвига код.

пл PHT-I (|Чн1-1 Ь i ПКиакс,,

- код, содержащийся в регистре 11 сдвига к началу момента времени tV

где

1

f

ffij - код, спдержатиися v регистре 1 2 Г)товности к гячалу момента време. i - текущий номер сдвиг п регистра 11 сдвига;

t-j - момент времени, соответствующий появлению на выходе одновибратра 19 i-ro импульса при обслуживании одной заявки N - максимальное количество

сдвигов в регистре 11 сдвига, за которое происходит выделение процессоров одной заявки.

В регистре 12 готовности устанавивается код jlicB-i

cв lcei- + (/ cй1-V §/U)

20

Логическая 1, сформированная на выходе элемента ИЛИ-НЕ 17, запускает 25 одновибратор 19, который вырабатывает единичньп импульс i сдвига.

В следующий момент времени ti- единичньш (1+1)-й импульс, выработанный одновибратором 19, сдвигает со- 30 держимое регистра 1I сдвига:

) 2 , где i + 1 определяет временной интервал

TI + ;

35 t-j -4: TT+{ t-i+j .

При этом генератор, состоящий из элемента ИЛИ-НЕ 17, одновибратора 19 элемента 22 задержки, введен в режим генерации импульсов. Период колеба40 НИИ генератора

Tj : Тг 2

45

50

где- t QAj - длительность задержки элемента 22 задержки; 20 - длительность импульса, выработанного одновибратором. Если на выходе элемента 18 задержки выработан единичный импульс, то триггер 13 квитанции устанавливается в О. Длительность задержки элемента 18 задержки

Г1Л57Т%

длительность задержки распространения сигнала от первого входа записи регистра I1 сдвига до входа элемента 19 задержки.

5

Устройство приняло заявку, чему соответствует единичный импульс на выходе 21 устройства,и оно готово к приему следующей. Далее логические 1, выработанные элементами И 15 группы, запускают соответствующие одновибраторы группы одновибраторов 20. Далее в устройстве происходят изменения, описанные выше и приводящие к выработке импульсов сдвига на выходе одновибратора 19.. Такие циклы продолжаются до тех пор, пока в регистре сдвига не окажется нулевой код, При этом элемент. ИЛИ-НЕ 14 вырабатьгоает 1, которая срьгеает колебания генератора и открывает элемент И 16, Если до этого момента поступила новая заявка на обслуживание и т.е. бит Р , то записанная в триггер 13 квитанции 1 пр пускатеся на выход 21 устройства. Устройство начинает.,обслуясивать новую заявку.

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

Устройство для распределения заданий процессорам, содЕржаи(ее N-разряд ный регистр сдвига (N - коли шство процессоров), первый и второй одно- вибраторы, К-разрядный регистр готовности, первый и второй элементы И, триггер квитанции, первый и второй элементы задержки, N-paзpядньri регистр готовности процессоров, первую и вторую группы из Ы элементов И, группу из N одновибраторов, npH -ieM группа входов установки в 1 регистра готовности процессоров является группой входов готовности процессоров- устройства, выход i-ro разряда (i I,N) регистра готовности процессоров соединен с первым входом i-ro элемента И первой группы, выход которого соединен с 1-м входом группы входов установки в регистра готовности, выход i-ro разряда которого соединен с первым входом i-ro элемента И второй группы, выход i-ro одновибратора группы соединен с i-м входом группы входов установки в О регистра сдвига и i-м входом группы входов установки в О регистра готовности,выход i-ro разряди регистра сдвига соединен с вторым входом i-ro элемента И второй группы, отличающееся тем, что, г

636

целью попьтгения быстродействия уст- , ройства, в него введены шифратор условий запуска, преобразователь

числа единиц в двоичный код, первый и второй элементы ШТИ-НЕ, причем группа входов кодов задания устройства является первой группой входов шифратора условий запуска,

первая группа выходов которого является первой группой выходов устро.й- cтвa,i-й выход шифратора условий запуска соединен с i-м входом группы входов установки в 1 регистра сдвига, (ГГ+О-й выход шифратора условий запуска соединен с входом первого одновибратора и первым входом первого элемента И, второй вход которого является входом запуска устройства, вторые входы элементов И первой группы объединены между собой и соединены с выходом первого одновибратора, выход первого элемента И

соединен с входом установки в Г

триггера квитан1Ц и, выход которого соединен с первым входом второго элемента И, выход которого соединен с входом записи регистра сдвига и с входом первого элемента задержки, выход которого соединен с входом сброса триггера квитанции и является выходом устройства, выход i-ro разряда регистра сдвига соединен с i-м входом первого элемента IITOI-HE, которого соединен с вторым входом второго элемента И н с первым ходом второго элемента ИЛИ-НЕ, выход которого соединен с входом второго одновибратора, выход которого

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

группы соединен с входом i-ro одновибратора группы и с i -м входом группы входов установки в О регистра готовности процессоров, группа выходов которого соединена с группой входов преобразователя числа единиц в двоичный код количества свободных процессоров, группа выходов которого соединена с второй группой входов шифратора условий запуска, группа выходов регистра готовности процессоров является второй группой выходов устройства .

Изобретение относится к вычислительной технике и может быть использовано в многопроцессорных системах. Целью изобретения является повьшение быстродействия. Устройство для распределения заданий про,цессором содержит шифратор условий .запуска, регистр сдвига, регистр готовности, регистр готовности процессоров, преобразователь числа единиц в двоичньш код, триггер квитанции, два элемента И, двз элемента Ш1И-НЕ, два элемента задержки, два одновибратора, две группы из N элементов И, группу из К одновибра- торов. Устройство позволяет с по- .моя1ью шифратора условий запуска определить оптимальный вариант реализации алгоритма РОПТ как функш-п- от числа свободных процессоров jVcg, кода макрооперации, типа выполняемой операции, размеров матриц, над которыми проводятся макрооперации и при |Чсб г /Ч„ин I Мин определяется для каждого РОПТ таблицей истинности шифратора условий запуска, не простаивая, начать обслуживание заявки. 1 ил. i СЛ