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

4 4i 41

00

10

15

20

1 1444808

Изобретение относится к вычислительной технике и может быть использовано в качестве диспетчера для распределения заданий процессорам в многопроцессорной вмчислительной системе (МВС) класса ОКМД при вертикальном распараллеливании последовательных программ.

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

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

Устройство (фиг. 1) содержит блок 1 выбора кода, группу из k (k - разрядность адреса команда) элементов И 2, две группы изkэлементов И 3 25 каждая, группу из k элементов ИЛИ 4, блок 5 памяти, две группы по р (р - число элементов вектора конфигурации МВС) элементов ИСКЛОЧАЮЩЕ ИЛИ 6, группу из р элементов ИЛИ 7, группу из р элементов И 8, информационный ВЫХ0Д 9 устройства, информационные , входы ID-12 устройства, информационный выход 13 устройства, управляющие входы 14, 15 устройства. Блок 5 памяти (фиг. 2) включает п групп из m элементов И 16, группу из п элементов И 17, п регистров 18, п групп из р эле ментов И 19, группу из (п-2) элементов ИЛИ 20, группу из (п-2) элементов И-НЕ 21 и элемент ИЛИ 22. БЛОК 1 выбора кода (фиг, 3) включает грзшпу из k элементов I-ITO-HE 23, группу из k ячеек 24 анализа разрядов, каждая ячейка состоит из п узлов 25 поразрядного переноса (п - максимальное число адресов, поступающих на блок 1), в состав каждого из которых входят элементы ИЛИ 26 и И 27,и элемент И-НЕ 28.

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

При вьтолнении последовательной программы на вход ,10 устройства поступает адрес очередной команды в

30

35

40

45

50

состоянии (, соответствующие процессорам элементы вектора конфигурации МВС равны 1), или переходят в пассивное состояние (соответствующие элементы вектора конфигурации МБС равны О). Если перехода в программе требует хотя бы один процессор, то адрес первой команды (в обратном коде), вызванной переходом в программе, поступает на вход 12 устройства, в противном случае выполняется очередная команда. В результате наличия на входах 10 и 12 адресов команд блок 1 производит сравнение их значений и выбирает наименьшее значение адреса. Б результате на информационном выходе блока 1 появляется код минимального адреса команды, пред назначенного дпя выполнения, а больший по значению адрес команды запоминается в блоке 5 памяти и в соот- в етствии с ним запоминается состояние процессоров, требующее выполнения данной команды. Как только значение адреса очередной команды, поступающей на вход 10, станет равным адресу хранимой в блоке 5 памяти, с блока 5 поступает значение вектора конфигурации МВС. В результате процес соры, треб тощие выполнения данной команды, переводятся в активное состояние. Далее процесс выполнения програм мы продолжается аналогично.

Рассмотрим более подробно работу устройства.

В исходном состоянии в блоке 5 памяти находится нулевая информация. На вход 10 устройства поступает обратный, код адреса очередной команды, при наличии команды перехода в МВС происходит анализ состояния процессорного поля. Если хотя бы один процессор требует вьшолнения перехода в программе (i-й элемент вектора конфигурации МВС равен единице), то в центральном процессоре МВС (на схеме не показано) формируется адрес первой команды участка программы, которую необходимо выполнить i-му процессору. Сформированный адрес команды в обратном коде поступает на вход 12 устройства. Адрес первой команды для а-го процессора и адрес

обратном коде. Если, предьодущей коман-55 очередной команды поступают на входы

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

0

5

0

5 0

5

0

5

0

состоянии (, соответствующие процессорам элементы вектора конфигурации МВС равны 1), или переходят в пассивное состояние (соответствующие элементы вектора конфигурации МБС равны О). Если перехода в программе требует хотя бы один процессор, то адрес первой команды (в обратном коде), вызванной переходом в программе, поступает на вход 12 устройства, в противном случае выполняется очередная команда. В результате наличия на входах 10 и 12 адресов команд блок 1 производит сравнение их значений и выбирает наименьшее значение адреса. Б результате на информационном выходе блока 1 появляется код минимального адреса команды, предназначенного дпя выполнения, а больший по значению адрес команды запоминается в блоке 5 памяти и в соот- в етствии с ним запоминается состояние процессоров, требующее выполнения данной команды. Как только значение адреса очередной команды, поступающей на вход 10, станет равным адресу хранимой в блоке 5 памяти, с блока 5 поступает значение вектора конфигурации МВС. В результате процессоры, треб тощие выполнения данной команды, переводятся в активное состояние. Далее процесс выполнения программы продолжается аналогично.

Рассмотрим более подробно работу устройства.

В исходном состоянии в блоке 5 памяти находится нулевая информация. На вход 10 устройства поступает обратный, код адреса очередной команды, при наличии команды перехода в МВС происходит анализ состояния процессорного поля. Если хотя бы один процессор требует вьшолнения перехода в программе (i-й элемент вектора конфигурации МВС равен единице), то в центральном процессоре МВС (на схеме не показано) формируется адрес первой команды участка программы, которую необходимо выполнить i-му процессору. Сформированный адрес команды в обратном коде поступает на вход 12 устройства. Адрес первой команды для а-го процессора и адрес

5 очередной команды поступают на входы

10 и 12 блока 1, на остальные входы из блока 5 поступает нулевая информация „

314

Блок 1 работает следуюп1им образом В первый момент в блоке 1 анализируются старрдае разряды всех кодов. Если хотя бы один из старших разрядов кодов равен единице, на выходе элемента ИЛИ-НЕ 23к появляется низкий потенциал (код 0), который соответствует значению старшего разряда максимального кода и является одновременно сигналом запрета при анализе остальных разрядов кодов, старшие раряды которых равны нулю. Эти сигналы формируются на выходах элементов ИЛИ

26и nocTynaJOT на входы элементов И 27. Те коды, старшие разряды которых равны 1, проходят через элементы И

27ячейки 24|. Если старшие разряды всех чисел равны О, на выходе элемента ИЛИ-НЕ 23 формируется 1, которая равна старшему разряду максимального кода и поступает на выход блока 1. Кроме того, она обеспечивает разрешение на прохождение остальных разрядов всех кодов через элемен

ТЫ ячейки 24|, Аналогичным образом анализируются вторые по старшинству разряды всех кодов и т.д., в результате чего на выходах узлов 25

1

25,... ,25„, формируется позиционный код номера максимального кода, на выходе блока 1 устанавливается позиционный номер или номера (в случае двух или более равных максимальных значений). Если на все входы блока 1 поступают только нули (низкие потенциалы), то с выходов элементов ИЛИ- НЕ 23 на входы элемента И-НЕ 28 подаются высокие потенциалы. В результате, с выхода элемента И-НЕ 28 низкий потенциал поступает на вход элементов И 27, следовательно, на выходе элемента И 27 будут низкие потенциалы. Сигналы с первого узла 25,, блока 1 поступают на управляющие входы элементов ИЗ,,...,ИЗц, а с второго уз- ла 25/J, - на управляющие входы элементов ИЗ,,. ..,И32,. Остальные сигналы с выходов блока 1 постзшают на соответствующие входы элементов И 17, 19 блока 5 памяти.

Кроме того, с выходов элементов ИЛИ-НЕ 23 на выход блока 1 поступает значение кода, который из блока 1 поступает на выход 9 устройства.При поступлении на входы блока 1 адресов команд на выход 9 устройства поступает адрес команды, которую необходимо выполнить. Б зависимости от значе

ния

адресов команд на первом или втором выходе устройства появляется высокий потенциал, которьпХ поступает на входы элементов И 3,...,3 или И3у,,, . . ,3,соответственно. Если на первом выходе блока 1 высокий потенциал, то адрес первой команды для i-ro процессора через элементы ИЛИ 4

поступает на информационные входы элементов И 16,,...,16ц.

Одновременно с поступлением на входы устройства адресов команд через вход 11 устройства на элементы

ИСКЛЮЧАЮЩЕЕ ИЛИ 6 поступает значение вектора конфигурации МВС,

Высокий потенциал с первого выхода блока 1 поступает на входы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 6р,,. .. ,6 р . В результате на входы элементов ИЛИ

7,7р с выходов элементов ИСКЖ)-

ИЛИ 6р,,...,6р поступает инвертированное значение вектора конфигурации МВС.

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

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

На входы элементов И16,, ... ,И16 поступает адрес команды, на входы элементов И 16,, ...16,, поступает

значение векторй конфигурации МВС. При наличии адресов на j-x (,...,n/ регистрах 18 на входы соответствующих элементов ИЛИ 20 поступают коды адресов. В результате с выходов элементов ИЛИ 20 j высокие потенциалы поступают на соответствующие входы элементов И-НЕ 21j (,b-l,...,2) регистров 18. В результате на выходах элементов И-НЕ 21j появляются низкие

потенциалы, которые поступают на входы j-x групп элементов И 16. А так

как на регистре 18 отсутствует ий- формация, то через элемент ИЛИ 20 н вход элемента И-НЕ 21, поступает низкий потенциал. В результате с выхода элемента И-НЕ 21 высокий потенциал поступает на входы второй группы элементов И 16. Следовательно, при подаче на вход 14 устройства высокого потенциала - сигнала записи, который поступает на входы элементов И 16, происходит сдвиг информации с регистра 18 на регистр IS, состояние остальных регистров 18 не

изменяется из-за наличия низкого потенциала на входах элементов И 16, а информация, поступившая на входы первой группы элементов И 16, поступает на регистр 18,, Для поиска требуемой информации с инверсных выходов регистров 18 значения адресов команд поступают на выход блока 5 памяти. При считывании значения вектора конфигурации МВС на входы соответствующих элементов И 19 поступает сигнал считывания, в результате на выход блока 5 памяти поступает значение вектора конфигурации МВС. Дпя сброса считанной информации на входы элементов И 17 поступает сигнал сброса. В результате с выхода элемента И 17 высокий потенциал поступает на вход соответствующего регистра 18 и устанавливает его в нулевое состояние. При необходимости одновременного счи- тьшания более одного вектора конфигурации МВС одновременно на входы не

менты И 19,,...,19р поступает на соответствующие входы элементов ИЛИ 7, на которые через вход 11 устройства и элементы ИСКЛЮЧАЮЩЕЕ ИЛИ бр.., б рпоступает значение вектора конфигурации МВС, соответствующее очередной команде. В результате на выходе элементов ИЛИ 7 появляется значение вектора конфигурации МВС, которое поступает на входы элементов И 8, При выборке очередной команды на вьг- поление на вход 15 поступает сигнал запроса, который поступает на входы элементов И 8 и 2. В результате на выход 9 устройства с блока 1 через элементы И 2 подается адрес очередной команды, а на выход 13 устройства через элементы И 8 поступает

значение вектора конфигурации НВС. Следовательно, процессоры, требующие выполнения данного участка программы, активны. Процесс распределения заданий процессорам МВС продолжается

Изобретение относится к вычислительной технике и может быть использовано в качестве диспетчера для распределения заданий процессорам в многопроцессорной вычислительной системе класса ОКМД при вертикальном распараллеливании последовательных программ. Цель изобретения - расширение класса решаемых задач за счет возможности распределения заданий процессорам в многопроцессорной вычислительной системе при вертикальном распараллеливании последовательных программ. Устройство для распределения заданий содержит блок выбора кода, четыре группы элементов И, две группы элементов ИСКЛЮЧАЮЩЕЕ . ИЛИ, две группы элементов ИЛИ и блок памяти. Цель достигается введением двух групп элементов ИЛИ, двух групп элементов ИСКЛЮЧАКЦЕЕ ИЛИ и блока памяс $ ти с соответствующими связями. ф-лы, 3 ил. I з.п. (Л

логично.

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

30

скольких групп элементов И 19 поступа-25 до окончания вьшолнения программы ана- ют высокие потенциалы и происходит одновременное считывание нескольких векторов конфигурации МВС. При поступлении на входы элементов И 17 сигнала сброса происходит одновременный сброс считанной информации с соответствующих регистров 18. В результате нескольких регистров 18 оказываются в нулевом состоянии. При необходимости записи очередной информации происходит сдвиг содержимых регистров 18 до первого свободного регистра 18.

Таким образом, при поступлении в блок 5 памяти на входы элементов И160 ,..., 16 адреса команды, а на входы элементов И (б,- т значения вектора конфигурации МВС и при наличии сигнала записи на входах элементов И 16,..., 6п, происходит запись поступившей информации на регистр 18j. Б процессе поступления адресов очередных команд на вход 10 устройства в блоке 1 происходит сравнение адреса команды, поступающей с инверсного выхода регистра 18 блока 5 Пс1мяти на вход блока 1 , и адреса очередной команды. При совпадении значений адресок команд на третьем выходе блока 1 появляется высокий потенциал, который поступает на входы элементов И 17, 19, ,...,19р. В результате значение вектора конфигурации МВС с регистра 18, через эле1. Устройство для распределения заданий, содержащее блок выбора кода и четыре группы элементов И, причем выходы элементов И первой группы образуют первый информационный выход

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

40 системе при вертикальном распараллеливании последовательных программ, в него введены две группы элементов ИЛИ, две группы элементов ИСКЛЮЧА10- РЩЕ ИЛИ и блок памяти, причем первые

45 входы элементов И второй группы соединены с соответствующими разрядами первого адресного входа команды блока выбора кода и образуют первый информационный вход устройства, пер50 -вые входы элементов И третьей группы соединены с соответствующими разрядами второго адресного входа команды блока выбора кода и образуют второй информационный вход устройства, вто55 рые входы элементов И третьей группы соединены с первым управляющим выходом блока выбора кода и первыми входами элементов ИСКЛЮЧАЮЩЕЕ ИЛИ первой группы, вторые входы которых

логично.

до оконча

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

до окончания вьшолнения программы ана

до окончания вьшолнения программы ана-

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

системе при вертикальном распараллеливании последовательных программ, в него введены две группы элементов ИЛИ, две группы элементов ИСКЛЮЧА10- РЩЕ ИЛИ и блок памяти, причем первые

входы элементов И второй группы соединены с соответствующими разрядами первого адресного входа команды блока выбора кода и образуют первый информационный вход устройства, первые входы элементов И третьей группы соединены с соответствующими разрядами второго адресного входа команды блока выбора кода и образуют второй информационный вход устройства, вторые входы элементов И третьей группы соединены с первым управляющим выходом блока выбора кода и первыми входами элементов ИСКЛЮЧАЮЩЕЕ ИЛИ первой группы, вторые входы которых

соединечы с первыми входами элементов ИСКЛ)ЧА10ЩЕЕ Ш1И второй группы и образуют третий информационный вход уст- ройства, вторые входы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ второй группы соединены с вторым управляющим выходом блока выбора кода и вторыми входами элементов И второй группы соответственно, выходы которых соединены соответ- ю первой группы (,...,k, k - ственно с первыми входами элементов разрядность адреса команды), входы ИЛИ первой группы, вторые входы кото- значения вектора конфигурации блока рых соединены с выходами элементов И соединены соответственно с вторыми третьей группы, информационные выхог входами (1,р)-х элементов И первой ды блока выбора кода соединены соот- 15 группы (,..,,т), выходы элеменветственно с первыми входами элементов И четвертой группы, вторые входы которых, соединены с вторыми входами элементов И первой группы, входом

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

И второй группы, выходы которых соединены соответственно с входами сброса J-X регистров (,2,,..,п),пря 25 мые выходы р-х разрядов которых соединены соответственно с первыми входами элементов И третьей группы, прямые выходы 1-х разрядов п-1 регистров соединены соответственно с вторыми

входы разрядов адреса команды которо- ЗО входами (t,l)-x элементов И первой го соединены соответственно с выхода- группы (,...jn), прямые выходы

1-х разрядов z-ro регистра (,.,,, n-l) соединены с соответствующими входами Ъ-го элемента ИЛИ группы (Ъ 1,...,п-2), прямые выходы 1-х разрядов п-го регистра соединены с соот- ветствзтощими входами элемента ИЛИ, прямой выход которого соединен с первыми входами элементов И-НЕ группы.

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

ми элементов ИЛИ первой группы, выходы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ первой группы соединены соответственно с входами значения вектора конфигурации блока памяти, вторые входы элементов И первой группы соединены соответственно с выходами элементов ИЛИ второй группы, первые входы ко35

торых соединены соответственно с выхо-до а инверсный выход - с третьими входани (n,m)-x элементов И первой груп пы, третьи входы (z,m)-x элементов И первой группы соединены соответственно с выходами Ъ-х элементов И-НЕ 45 группы, выходы Ъ-х элементов ИЛИ группы соединены с соответствующими входами d-x элементов И-НЕ (а.Ъ,Ъ-1, Ъ-2,...,2), управляющие входы блока соединены соответственно с вторыми входами элементов И второй и третьей групп, выходы элементов И третьей группы соединены с информационными выходами данных блока.

дами элементов ИСКЛЮЧАВЩЕЕ ИЛИ второй группы, р входов которых соединены с информационными выходами данных соответствующих разрядов блока памяти (р - число элементов вектора конфигурации), выходы элементов И четвертой группы являются вторым информационным выходом устройства,

п элементов И, группу из п-2 элементов И-HF, р« п элемент ов И третьей группы, группу из п-2 эл;ементов ИЛИ и элемент ИЛИ, причем вход записи блока соединен с первыми входами элементов И первой группы, входы адреса команды блока соединены соответственно с вторыми входами (l,l)-x элементов И первой группы соединены с соответствующими разрядами п регистров, инверсные выходы 1-х разрядов которых соединены с выходами адреса

35

а инверсный выход - с третьими входани (n,m)-x элементов И первой группы, третьи входы (z,m)-x элементов И первой группы соединены соответственно с выходами Ъ-х элементов И-НЕ группы, выходы Ъ-х элементов ИЛИ группы соединены с соответствующими входами d-x элементов И-НЕ (а.Ъ,Ъ-1, Ъ-2,...,2), управляющие входы блока соединены соответственно с вторыми входами элементов И второй и третьей групп, выходы элементов И третьей группы соединены с информационными выходами данных блока.

яз-нуЛтЗу вжтИ

ici ftySjroSy Lf

SJIOKO r

СэяенемтЛ

«4

CSMfWHOIOt MfHJHtS

K6todylS Н$ызго9ан j -fOtOHOJ .

«V Ш

1{3йенемти НЯН. 7t

I g;

4

3 Фиг.

fft-f}3JO }s,.

ffjtMOt iгг

Кп-му вгоду блока 1

К эдененту УЖ