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

 

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

СОЮЗ СОВЕТСКИХ

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

РЕСПУБЛИК (51)s G 06 F 9/46, 15/20

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4675559/24 (22) 11.04.89 (46) 23.05,91. Бюл, %19 (72) А.А.Есетов, А,А,Чупринов и В.А.Титов (53) 681.325 (088.8) (56) Авторское свидетельство СССР

N 1275464, кл. G 06 F 15/20, 1986.

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

N 1444808, кл. G 06 F 15/20, 1987. (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ

ЗАДАНИЙ (57) Изобретение относится к вычислительной технике и может быть использовано в качестве диспетчера для распределения заданий процессорам в многопроцессорной

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

ОКМД при вертикальном распараллеливании последовательных программ.

Цель изобретения — оптимизация процесса распараллеливания.

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

Устройство для распределения заданий (фиг.1) содержит матрицу 1 орграфа, входы

21 данных, элементы И 3, первую группы из и элементов ИЛИ 4, пятую и вторую группы блоков элементов И 5, 6, группу из п элементов ИЛИ-НЕ 7, группу из и информационных регистров 8, первую и вторую группу блоков элементов ИЛИ 9, 10, группу из и адресных регистров 11, шестую и седьмую, БАХ 1651 284 А1 вычислительной системе (МВС) класса

ОКМД при вертикальном распараллеливании последовательных неструктурированных программ. Цель изобретения оптимизация процесса распараллеливания путем использования оптимального расписания выполнения последовательных неструктурированных программ на МВС класса ОКМД. Устройство для распределения заданий содержит блок выбора максимального кода, по шесть блоков элементов

И и ИЛИ, семь групп блоков элементов И, две группы блоков элементов ИЛИ, информационные и адресные регистры, дешифратор, группу элементов ИЛИ вЂ” Н Е, сдвигающий регистр. 2 ил, третью и первую группы блоков элементов

И 12 — 15, третий и первый блоки элементов

ИЛИ 16 и 17, сдвигающий регистр 18, группу

19 кодовых входов устройства, четвертую группу блоков элементов И 20, четвертый блок элементов ИЛИ 21, дешифратор 22, блок 23 выбора максимального кода, первый блок элементов И 24, второй блок элементов ИЛИ 25, второй и третий блоки элементов И 26 и 27, пятый блок элементов

ИЛИ 28, пятый и шестой блоки элементов И

29 и 30, шестой блок элементов ИЛИ 31, четвертый блок элементов И 32, входы 33—

37, выходы 38 и 39. Блок 23 выбора максимального кода содержит элемент И вЂ” НЕ 45, группу элементов ИЛИ вЂ” HE 401, 402,...,40р, где р — число разрядов в кодах, группу ячеек

411, 412,...,41р анализа оазрядов, каждая ячейка состоит из узлов 4211 4212. 422р подразрядного переноса, в состав каждого из которых входят элементы ИЛИ 43 и И 44.

1651284

40

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

На входы 19 устройства поступают номера вершин управляющего графа последо-, . вательной программы, определяющие оптимальную последовательность выполнения программы. Каждая вершина графа идентифицирует линейный участок программы, последней командой которой является команда перехода, Через входы 2л поступает информация о топологии графа программы. При наличии связи по управлениЮ между l-й и j-й вершинами на вход 2ii устройства поступает высокий потенциал, в противном случае — низкий. В первом (К+ 1)-м разряде регистра 18 находится единица. На регистре 8 находится код 11, „.; 1, а на регистре 111 — адрес первой команды программы.

Для выбора очередной вершины на входы 331 и 332 устройства подаются сигналы, в результате которых на 1-м выходе регистра

18 появляется высокий потенциал, который поступает на входы группы элементов И 20.

В результате код номера вершины с входа

19 через элементы И 20 и ИЛИ 21 поступает на входы дешифратора 22 с i-го выхода группы элементов И 141 и 15I, В результате с выходов регистра 11I через элементы И 15. и ИЛИ 17 адрес команды (первоначально адрес первой команды программы, соответствующей начальной вершине графа) поступает на выход 39 устройства.

С выходов регистра 8 через элементы

ИЛИ 9, И 14 и ИЛИ 16 на выход 38 устройства поступает вектор конфигурации МВС, соответствующий адресу команды, находящемуся на выходе 39 устройства (первоначально все элементы вектора конфигурации

MBC равны единице).

При выполнении последней команды очередного участка программы формируются адреса следующих команд. Если последней командой очередного участка программы, идентифицированного вершиной графа была команда условного перехода, то на входы 34 и 35 устройства поступают адреса команд, сформированных по результатам выполнения команды условного перехода, а на входы 36 и 37 устройства — значения элементов векторов конфигурации МВС, соответствующие поступившим адресам команд, Если последней командой очередного участка программы была команда безусловного перехода, то на вход 34 устройства поступает адрес команды, сформированный после окончания выполнения команды безусловного перехода, а на вход 35 устройства — код

111, ..., 1. Одновременно на вход 36 устроиства поступают значения элементов вектора конфигурации МВС, соответствующие адресу команды, поступающей на вход 34. Поступившие адреса команд анализируются блоком 23.

Блок 23 работает следующим образом, В первый момент анализируются старшие разряда кодов поступивших адресов команд. Если хотя-бы один из старших разрядов кодов равен единице, на выходе элемента ИЛИ вЂ” НЕ 40р появляется низкий потенциал (код О), который соответствует сигналу запрета при анализе старшего разряда второго кода, который равен нулю. Зти сигналы фомируются на выходах элементов

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

44, Тот код, старший разряд которого равен

1, проходит через элемент И 44 ячейки 42р.

Если старшие разряды всех кодов j)GBHLI нулю, на выходе элемента ИЛИ вЂ” НЕ 40р формируется 1, благодаря чему обеспечивается разрешение на прохождение остальных разрядов всех кодов через элементы ячейки 42р. Аналогичным образом анализируются вторые по старшинству разряды всех кодов и т,д., в результате чего на выходах узлов 42», 4221 формируется позиционный код номера минимального кода адреса команды (в данном случае низкий потенциал соответствует минимальному коду), который поступает на входы группы элементов

И 24, 26, 27, 29, 30 и 32. Если на все входы блока 23 поступают только нули (низкие потенциалы), тос выходов элементов ИЛИ вЂ” НЕ

40 на входы элемента И вЂ” НЕ 45 подаются высокие потенциалы, В результате с выхода элемента И вЂ” НЕ 45 низкий потенциал поступает на входы элементов И 44 узлов 42», 42 <. Следовательно, на выходе элементов И

44 будут низкие потенциалы. Кроме того, в результате анализа кодов адресов команд с инверсных выходов элементов ИЛИ вЂ” НЕ 40 на входы групп элементов И 13 поступает код большего адреса команды.

На входы групп элементов И 6 через группу элементов И 24 (И 26), ИЛИ 25 поступает код меньшего адреса команды, а на входы групп элементов И 5 через группы элементов И 27 (И 29) и ИЛИ 28 поступают значения элементов вектора конфигурации

МВС, соответствующие коду меньшего адреса команды. Кроме того, на входы групп элементов И 12 через rpyhny элементов И 30 (И 32) и ИЛИ 31 поступают значения элементов вектора конфигурации МВС, соответствующие коду большего адреса команды.

Высокий потенциал с i-го выходы дешифратора 22 поступает на входа элементов И 3 (-й строки матрицы. Если на входе 2 высокий потенциал, то с выходов соответствуюi 651284

15

45 элементов И 3 первой строки матрицы 1. Ц

55 щих элементов И 3iI высокие потенциалы поступают на вход соответствующих элементов ИЛИ 4, В результате с прямых выходов элементов ИЛИ 4 высокие потенциалы подаются на входы групп элементов И 5, 6I, 121 131 и на синхровходы регистров 8, 11, а низкие потенциалы с их инверсных выходов поступают на входы групп элементов И 5i и

6 (I = i+1, 1+2,;.„и). Следовательно, через группы элементов И 5m и 6m ИЛИ 9m и 10m на входы регистров 8«и 11«(m = мин)) с выходов группы элементов ИЛИ 28 и ИЛИ

25 соответственно поступают значения элементов вектора конфигурации MBC и код меньшего адреса команды, Одновременно на входы элементов ИЛИ 9i с выходов второй ступени регистра 8 поступают значе-ния элементов вектора конфигурации МВС, если они были записаны ранее.

С выходов групп элементов И 6m адрес команды поступает на входы элементов

ИЛИ вЂ” HE 7. В результате низкий потенциал с его выхода поступает на входы группы элементов И 12m и 13m и запрещает прием на регистры 8m и 11m информации, соответствующей большему адресу команды. Если

I-я вершина имеет связь с двумя вершинами графа, то с выхода элемента ИЛИ 4„+, (где

m+z — номер второй вершины графа, имеющей связь с l-й вершиной) высокий потенциал поступает на входы групп элементов И

12m+z, 13m+z а так как на выходе элемента

ИЛИ вЂ” HE 7m+z высокий потенциал, то значения элементов вектора конфигурации MBC и соответствующий им больший адрес командчереэ группы элементов И 12«+, 13m+z, ИЛИ 9«+z и 10«+ поступают на регистры

8m+z и 11«+ соответственно, Для выполнения очередной вершины графа программы в соответствии с порядком их выполнения на входы 33-<, 33 устройства поступают сигналы, которые приводят к сдвигу единицы в регистре 18. В результате чего на выходах

38 и 39 устройства устанавливаются значения элементов вектора конфигурации МВС и первый адрес команды, выбранной на выполнение вершины графа программы. Далее процесс распределения заданий продолжается аналогичным образом до окончания выполнения всей программы.

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

Матрица А смежности орграфа имеет вид

А = 0000000100

0000000011

0000000001

Порядок выполнения отдельных участков программы задан вектором Т = 1, 3, 7, 6, 2, 4, 5, 8, 9, 10. После занесения исходной информации на входы 331 и 332 устройства поступают сигналы, в результате чего на первом информационном входе регистра 18 появляется высокий потенциал, который поступает на входы группы элементов И 20I. В результате код номера первой вершины с входа 19> через элементы И 201, ИЛИ 21 поступает на входы дешифратора 22. С первого выхода которого высокий потенциал поступает на входы группы элементов И 14> и И 15>, Следовательно. с выхода регистра

11i через элементы И 15> и ИЛИ 17 адрес первой команды программы, соответствующей первой вершине графа, поступает на выход 39 устройства. Одновременно с выходов регистра 8i через элементы ИЛИ 9i, И

14I и ИЛИ 16 на выход 38 устройства поступают значения элементов вектора конфигурации МВС. Так как последней командой первого участка программы, соответствующей первой вершине графа, является команда условного перехода (первая вершина имеет две дуги), то в результате ее выполне ния на входы 34 и 35 поступают два адреса команд, сответствующие второй и третьей вершинам графа.

Одновременно на входы 36 и 37 поступают соответствующие адресам команд значения элементов векторов конфигурации M BC. Высокий потенциал с первого выхода дешифратора 22 поступает на входы результате чего на входы элементов ИЛИ 4 и ИЛИ 4з с входов 212 и 2 э через элементы

И 312 и И З з поступают высокие потенциалы. Поступившие на входы блока 23 адреса команд анализируются, в результате чего на входы групп элементов И 13 поступает адрес команды, соответствующий третьей вершине графа, так как данный участок программы расположен после участка. идентифицированного второй вершиной графа программы. Одновременно на входы групп элементов И 24, 27 и 32 поступают высокие, а на входы групп элементов И 26, 29 и 30 — низкие потенциалы с выходов блока 23. В результате на входы групп эле1651284

10

15 ства, первый вход адреса команд устройства соединен с первыми входами первого

30

ы

Для выбора очередного участка программы на входы 33> м 332 устройства подаются сигналы. В результате на втором информационном выходе регистра 18 появляется высокий потенциал, который поступает на входы элементов И 20р, и код номера третьей вершины с входа 19з через элемент

Й 20> и ИЛИ 21 поступает на дешифратор

22, с третьего выхода которого высокий потенциал поступает на входы группы элементов И 14з и 15з, на вторые входы которых с регистра 11з и с регистра Оз через элементы

ИЛИ 9з поступает информация о третьей вершине (адрес команды и значения элементов вектора конфигурации M В С), которая через группу элементов ИЛИ 16 и 17 поступает на соответствующие выходы 39 и

38 устройства. ментов И 6 и 5 соответственно-через элементы И 24 и 27 и ИЛИ 25 и 28 поступают коды адреса команды и значения элементов вектора конфигурации МВС, соответствующие второй вершине графа.

На входы групп элементов И 12 через элементы И 30 и ИЛИ 31 поступают значения элементов вектора конфигурации МВС, соответствующие третьей вершине графа программы. Высокий потенциал с выхода элемента ИЛИ 42 поступает на входы групп элементов И 52, И 62 и на синхровходы регистров 82 и 112, в результате чего значения элементов вектора конфигурации M BC и адрес команды, соответствующие второй вершине графа, соответственно через элементы ИЛИ 92 и 102 поступают на соответствующие регистры Bz и 112.

Высокий потенциал с выхода элемента

ИЛИ 4з поступает на входы группы элементов И 12з и 13з, в результате чего значения элементов вектора конфигурации MBC и адрес команды, соответствующие третьей вершине графа, соответственно через элементы ИЛИ 9з и 10з поступают на соответствующие регистры 8з и 11з. Прохождение информации i, по третьей вершине графа на регистры 8з и 11з возможно благодаря наличию на входах элементов И 12 и

13з с выхода элемента ИЛИ-HE 7з высокого потенциала, который появляется на его входах за счет наличия низких потенциалов с выходов группы элементов И 6з, так как на входы последнего с инверсного выхода элемента ИЛИ 42 поступает низкий потенциал, Далее процесс распределения заданий процессором МВС продолжается аналогичным образом. Процесс распределения закан чивается после выполнения последней вершины графа программы, Формула изобретения

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

И, три блока элементов И, первую группу блоков элементов ИЛИ, три блока элементов ИЛИ, адресные и информационные регистры, причем выход i-го (i = 1, „„п, n— число процессоров) адресного регистра соединен с первым входом i-ro блока элементов И первой группы, выход которого соединен с соответствующим входом первого блока элементов ИЛИ, выход которого является выходом адреса команды устройблока элементов И и блока выбора максимального кода, первый выход которого соединен с первым входом второго блока элементов И, второй выход блока максимального кода соединен с вторым входом первого блока элементов И, выход которого соединен с первым входом второго блока элементов ИЛИ, второй вход адреса команды устройства соединен с вторыми входами блока выбора максимального кода и второго блока элементов И, выход которого соединен с вторым входом второго блока элементов ИЛИ, выход которого соединен с первыми входами блоков элементов И второй группы, выход )-ro информационного регистра соединен с первым входом i-го блока элементов ИЛИ первой группы, о тл и ч а ю щ е е с я тем, что, с целью оптимизации процесса распараллеливания путем использования оптимального расписания выполнения последовательных неструктурированных программ на многопроцессорной вычислительной системе класса ОКМД. в него введены матрица топологии орграфа иэ пхп элементов И, три группы блоков элементов И, вторая группа блоков элементов

ИЛИ, три блока элементов И, три блока элементов ИЛИ, сдвигающий регистр, дешифратор, группа элементов ИЛИ вЂ” НЕ, причем вход сдвига и синхронизирующий вход сдвигающего регистра являются соответственно входом сдвига и синхронизирующим входом устройства, i-й выход сдвигающего регистра соединен с i-м блоком элементов

И четвертой группы, выход которого соединен с соответствующим входом четвертого блока элементов ИЛИ, выход которого соединен с входом дешифратора, )-й (1 = 1, ..., и) выход которого соединен с первыми входами элементов И i-й строки матрицы топологии орграфа, вторые входы которых являются входами данных устройства, выходы элементов l4 j-m столбца матрицы топологии орграфа соединены с входами )-ro

1651284

10 элемента ИЛИ первой группы, прямой выход которого соединен с синхровходами j-ro адресного и информационного регистров. с вторым входом )-го блока элементов И второй группы и с первыми входами )-х блоков элементов И пятой, шестой и седьмой групп, инверсный выход)-го () =-1, 2, ..., и-1) элемента ИЛИ первой группы соединен с (J+1)-ми входами К-х (К = j+1, j+2, ...,n) блоков элементов И второй и пятой групп, выход J-ro блока элементов И второй группы соединен с входами )-го элемента ИЛИ вЂ” НЕ группы и с первым входом j-го блока элементов ИЛИ второй группы, выход которого соединен с информационным входом j-го адресного регистра, второй выход блока выбора максимального кода соединен с первыми входами третьего и четвертого блоков элементов И, первый выход блока выбора максимального кода соединен с первыми входами пятого и шестого блоков элементов И, первый вход вектора конфигурации устройства соединен с вторыми входами третьего и шестого блоков элементов И, второй вход вектора конфигурации устройства соединен с вторыми входами четвертого и пятого блоков элементов И, выходы третьего и пятого блоков элементов И соединены с входами пятого блока элементов ИЛИ, выход которого соединен с соответствующими входами блоков элементов И пятой группы, выходы четвертого и шестого блоков элементов И соединены с входами шестого блока элементов ИЛИ, выход которого соединен с вторыми входами

5 блоков элементов И шестой группы, выходы

j-x блоков элемен-ов И пятой и шестой групп соединены соответственно с вторым и третьим входами J-ro блока элементов

ИЛИ первой группы, выход которого соеди10 нен с информационным входом j-го информационного регистра и с первым входом)-го блока элементов И третьей группы, выход которого соединен с J-м входом третьего блока элементов ИЛИ, выход которого явля15 ется выходами вектора конфигурации устройства, выход j-го элемента ИЛИ-НЕ группы соединен с третьим и вторым входами j-x блоков элементов И соответственно шестой и седьмой групп, выход i-го блока

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

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

1651284 злю;жилаю с дхпо а _#_

Составитель Г. Пономарева

Техред M.Ìîðãåíòàë Корректор О . Кундрик

Редактор В. Данко

Производственно-издательский комбинат "Патент", r. Ужгород, ул.Гагарина, 101

Заказ 1607 Тираж 417 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5