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

 

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

СО103 СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК (19) (11) 44 08 А1 (51) 4 G 06 F 15/20

В, f4

Е, f

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

Н А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21 ) 4 2541 1 2/24-24 (22) 08.04,87 (46) 15.12.88. Бюл. Ф 46 (72) А.А.Есетов, А.А.Чупринов, A.À.ØåëoìåíöåB, А.С.Липницкий, А.А.Семенович, В.М.Кузьмицкий и Г,М.Шпаковский (53) 681.325(088.8) (56) Авторское свидетельство СССР

N 1283764, кл . Г 06 F 15/20, 1985 .

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

Ф 1275464, кл. Г 06 F 15/20, 1985. (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ ЗАДАНИЙ (57) Изобретение относится к вычислительной технике и может быть использовано в качестве диспетчера для распределения заданий процессорам в многопроцессорной вычислительной системе класса ОНЯ при вертикальном распараллеливании последовательных программ. Цель изобретения — расширение класса решаемых задач за счет возможности распределения заданий процессорам в многопроцессорной вычислительной системе при вертикальном распараллеливании последовательных программ. Устройство для распределения заданий содержит блок выбора кода, четыре группы элементов И, две группы элементов ИСКЛ10ЧА1ОЩЕЕ . ИЛИ, две группы элементов ИЛИ и блок памяти. Цель достигается введением двух групп элементов ИЛИ, двух групп элементов ИСКЛМЧАИ1ЕЕ ИЛИ и блока памя( ти с соответствующими связями. 1 s,ï. флы 3 ил, T

С:

1444808

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

В исходном состоянии в блоке 5 памяти находится нулевая информация.

На вход 10 устройства поступает об40 ратный,код адреса очередной команды, при наличии команды перехода в

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

Ф процессору. Сформированный адрес команды в обратном коде поступает на вход 12 устройства. Лдрес первой команды для i-ro процессора и адрес н- 55 очередной команды поступают на входы

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

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

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

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

Устройство (фиг. 1) содержит блок 1 выбора кода, группу из k (k— разрядность адреса команды) элементов И 2, две группы из k элементов И 3 каждая, группу из k элементов ИЛИ 4, блок 5 памяти, две группы по р (р— число элементов вектора конфигурации

МВС) элементов ИСКЛ10ЧАЮЩЕЕ ИЛИ 6, группу из р элементов ИЛИ 7, группу из р элементов И 8, информационный выход 9 устройства, информационные входы 1.0-12 устройства, информационный выход 13 устройства, управляющие входы 14, 15 устройства. Блок 5 памяти (фиг. 2) включает и групп из m элементов И 1 6, группу из и элементов И 17, п регистров 18, и групп из р элементов И 19, группу из (и-2) элементов ИЛИ 20, группу из (и-2) элементов И-НЕ 21 и элемент ИЛИ 22.

Блок 1 выбора кода (фиг. 3) включает группу из k элементов ИЛИ-НЕ 23, группу из k ячеек 24 анализа разрядов, каждая ячейка состоит из и узлов 25 поразрядного переноса (и — ма симальное число адресов, поступающих на блок 1), в состав каждого из кото рых входят элементы ИЛИ 26 и И 27,и элемент -HE 28.

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

При выполнении последовательной программы на вход 10 устройства поступает адрес очередной команды н обратном коде . Если предыдущей кома дой была команда условного перехода, то по результатам анализа условия процессоры или остаются в активном состоянии (соответствующие процессорам элементы вектора конфигурации

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

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

10 остальных разрядов кодов, старшие раз15

35

50

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

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

26 и поступают на нходы элементов И

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

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

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

И 27, следовательно, на выходе элемента И 27 будут низкие потенциалы.

Сигналы с первого узла 25„ блока 1 поступают на управляющие входы элементов ИЗ,,...,ИЗ„, а с второго узла 25, — на управляющие входы элементов ИЗ„„,...,ИЗ к, Остальные сигналы с выходов блока 1 поступают на соответствующие входы элементов И 17, 19 блока 5 памяти.

Кроме того, с выходов элементов

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

40 ния адресов команд на первом или ВТо ром выходе устройства появляется высокий потенциал, которьп<, поступает на входы элементов И 3,,...,З„или

ИЗ „„.,3, „соответственно. Если на первом выходе блока 1 высокий потенц1<ал, то адрес первой команды для

i-ro процессора через элемент< ИЛИ 4 поступает на информационные входы элементов И 16<,...,16„, Одновременно с поступлением на нходы устройства адресов команд через вход 11 устройства на элементы

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

Высокий потенциал с первого выхода блока 1 поступает на входы элементов

ИСКЛЮЧАЮЩЕЕ ИЛИ 6 „,...,6 . В результате на входы элементов ИЛИ

7,,...,7< с выходов элементов ИСКЛЮЧАЮ!

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

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

На входы элементов И!6 ...,,И16« поступает адрес команды, на входы элементов И 16„„,...,16,„ поступает значение вектора конфигурации МВС.

При наличии адресов на j-x (j=l и, регистрах 18 на входы соответствующих элементов ИЛИ 20 поступают коды адресов. В результате с выходов элементов ИЛИ 20 высокие потенциалы по1 ступают на соответствующие входы элементов И-НЕ 21

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

35 устройства о т л и ч а ю щ е е с я

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

4р системе при вертикальном распараллеливании последовательных программ, в него введены две группы элементов

ИЛИ, две группы элементов HCKJ_#_×A10ЩЕЕ ИЛИ и блок памяти, причем первые

45 входы элементов И второй группы соединены с соответствующими разрядами первого адресного входа команды блока выбора кода и образуют первый информационный вход устройства, пер5п .вые входы элементов И третьей группы соединены с соответствующими разрядами второго адресного входа команды блока выбора кода и образуют второй информационный вход устройства, вторые входы элементов И третьей группы соединены с первым управляющим выходом блока выбора кода и первыми входами элементов ИСКЛЮЧА1ОШЕЕ ИЛИ первой группы, вторые входы которых изменяется из-за наличия низкого потенциала на входах элементов И 16, а информация, поступившая на входы первой группы элементов И 16, поступает на регистр 18 . Для поиска требуемой информации с инверсных выходов .регистров 18 значения адресов команд поступают на выход блока 5 памяти.

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

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

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

И!6,...,16„ адреса команды, а на входы элементов И 16„+,,...,16 значения вектора конфигурации МВС и при наличии сигнала. записи на входах элементов И 16, ° ...16 происходит запись поступившей информации на регистр 18 . В процессе поступления адресов очередных команд на вход 10 устройства в блоке 1 происходит сравнение адреса команды, поступающей с инверсного выхода регистра 18 блока

5 памяти на вход блока l и адреса очередной команды. При совпадении значений адресов команд на третьем выходе блока 1 появляется высокий потенциал, который поступает на входы элементов И 17, 19,, ° . °, 19р. В результате значение вектора конфигурации МВС с регистра 18, через эле4808 6 менты И 19, 19> поступает на соответствующие входы элементов ИЛИ 7, на которые через вход 11 устройства и элементы ИСКЛЮЧАЮЩЕЕ ИЛИ 6,».

6 поступает значение вектора конЯp фигурации МВС, соответствующее очередной команде. В результате на выходе элементов ИЛИ 7 появляется значение вектора конфигурации МВС, которое поступает на входы элементов И 8.

При выборке очередной команды на вьг поление на вход 15 поступает сигнал запроса, который поступает на входы элементов И 8 и 2, В результате на выход 9 устройства с блока 1 через элементы И 2 подается адрес очередной команды, а на выход 13 устройства через элементы И 8 поступает

2О значение вектора конфигурации МВС.

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

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

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

7 14448 соединены с первыми входами элементон

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

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

ИЛИ второй группы, первые входы которых соединены соответственно с выхо-4О дами элементов ИСХЛ10ЧАНЦЕЕ ИЛИ второй группы, р входов которых соединены с информационными выходами данных соответствующих разрядов блока памяти (р — число элементов вектора конфигурации), выходы элементов И четвертой группы являются вторым информационным выходом устройства.

2. Устройство по п. 1, о т л ич а ю щ е е с я тем, что блок па- 50 мяти содержит .п регистров, ие m элементов И первой группы (m — разрядность регистров), вторую группу из

08 8 и элементов И, группу из п-2 элементов И-HF., ум и элементов И третьей группы, групг у из и-2 элементов ИЛИ и элемент ИЛИ, причем вход записи блока соединен с первыми входами элементов И первой группы, входы адреса команды блока соединены соответственно с вторыми входами (1,1)-х элементов И первой группы (1=1,...,k, разрядность адреса команды), входы значения вектора конфигурации блока соединены соответственно с вторыми входами (1,р)-х элементов И первой группы (p=k+1,...,m), выходы элементов И первой группы соединены с соответствующими разрядами и регистров, инверсные выходы 1-х разрядов которых соединены с выходами адреса команды блока, вход сброса которого соединен с первыми входами элементов

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

1-х разрядов z-ro регистра (z=2 п-1) соединены с соответствующими входами Ъ-ro элемента ИЛИ группы (Ъ=

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

1444808

Ф гЛ

С а№ генту

Ф4

Сзмген л/юи

1444808