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

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

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

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

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

третью и первую группы блоков элементов И 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,

группу элементов ИЛИ-НЕ 40i. 40240Р,

где р - число разрядов в кодах, группу ячеек

411, 41241р анализа разрядов, каждая

ячейка состоит из узлов 42ц, 42i2....,422p подразрядного переноса, а состав каждого из которых входят элементы ИЛИ 43 и И 44.

(/

С

о о

к о Ј

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

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

Для выбора очередной вершины на входы 33i и 332 устройства подаются сигналы, в результате которых на i-м выходе регистра 18 появляется высокий потенциал, который поступает на входы группы элементов И 20. В результате код номера вершины с входа 19i через элементы И20|иИЛИ21 поступает на входы дешифратора 22 с i-ro выхода группы элементов И 14i и 15|. В результате с выходов регистра 11i через элементы И 15i и ИЛИ 17 адрес команды (первоначально адрес первой команды программы, соответствующей начальной вершине графа) поступает на выход 39 устройства.

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

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

блоком 23.

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

5 сигналы фомируются на выходах элементов ИЛИ 43 и поступают на входы элементов И 44. Тот код, старший разряд которого равен 1, проходит через элемент И 44 ячейки 42р. Если старшие разряды всех кодов равны

0 нулю, на выходе элемента ИЛИ-НЕ 40р формируется 1, благодаря чему обеспечивается разрешение на прохождение остальных разрядов всех кодов через элементы ячейки 42р. Аналогичным образом анализи5 руются вторые по старшинству разряды всех кодов и т.д., в результате чего на выходах узлов 42ц, 4221 формируется позиционный код номера минимального кода адреса команды (в данном случае низкий потенци0 ал соответствует минимальному коду), который поступает на входы группы элементов И 24, 26, 27, 29, 30 и 32. Если на все входы блока 23 поступают только нули (низкие потенциалы), то с выходов элементов ИЛИ-НЕ

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

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

5На входы групп элементов И 6 через

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

0 значения элементов вектора конфигурации МВС, соответствующие коду меньшего адреса команды. Кроме того, на входы групп элементов И 12 через группу элементов И 30 (И 32) и ИЛ И 31 поступают значения элемен5 тов вектора конфигурации МВС, соответствующие коду большего адреса команды. Высокий потенциал с i-ro выходы дешифратора 22 поступает на входа элементов И 3 1-й строки матрицы. Еслм на входе 2 высокий потенциал, то с выходов соответствующих элементов И 3ij высокие потенциалы поступают на вход соответствующих элементов ИЛИ Л В результате с прямых выходов элементов ИЛИ 4j высокие потенциалы подаются на входы групп элементов И 5, 6j, 12j, 13j и на синхровходы регистров 8j. 11, а низкие потенциалы с их инверсных выходов поступают на входы групп элементов И 5i и

6i (I i+1, I+2п). Следовательно, через

группы элементов И 5т и 6т, ИЛИ 9т и 10т на входы регистров 8т и 11т (т мин) с выходов группы элементов ИЛИ 28 и ИЛИ 25 соответственно поступают значения элементов вектора конфигурации МВС и код меньшего адреса команды. Одновременно на входы элементов ИЛИ 9| с выходов второй ступени регистра 8j поступают значе- - ния элементов вектора конфигурации МВС, если они были записаны ранее.

С выходов групп элементов И 6т адрес команды поступает на входы элементов ИЛИ-НЕ 7. В результате низкий потенциал с его выхода поступает на входы группы элементов И 12т и 13т и запрещает прием на регистры 8т и 11т информации, соответствующей большему адресу команды. Если i-я вершина имеет связь с двумя вершинами графа, то с выхода элемента ИЛИ 4m+z (где m+z - номер второй вершины графа, имеющей связь с 1-й вершиной) высокий потенциал поступает на входы групп элементов И 12m+z, 13m+z, а так как на выходе элемента 7m+z высокий потенциал, то значения элементов вектора конфигурации МВС и соответствующий им больший адрес команд через группы элементов И 12m+z. 13m+z. ИЛИ 9m+z и 10m+z поступают на регистры 8m+z и Hm+z соответственно. Для выполнения очередной вершины графа программы в соответствии с порядком их выполнения на входы 331. 332 устройства поступают сигналы, которые приводят к сдвигу единицы в регистре 18. В результате чего на выходах 38 и 39 устройства устанавливаются значения элементов вектора конфигурации МВС и первый адрес команды, выбранной на выполнение вершины графа программы. Далее процесс распределения заданий продолжается аналогичным образом до окончания выполнения всей программы.

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

Пример. Пусть последовательная программа задана циклическим орграфом. Матрица А смежности орграфа имеет вид

0110000000 0001100000 0000011000 0000000100

А 0000000100

0100000100 0010000010 0000000011 0000000001

00000000000

Порядок выполнения отдельных участков программы задан вектором Т 1. 3, 7, 6, 2, 4, 5, 8, 9, 10. После занесения исходной информации на входы 331 и 332 устройства

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

0 входа 19i через элементы И 20ь ИЛИ 21 поступает на входы дешифратора 22. С первого выхода которого высокий потенциал поступает на входы группы элементов И 14i и И 15i. Следовательно, с выхода регистра

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

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

0 Одновременно на входы 36 и 37 поступают соответствующие адресам команд значения элементов векторов конфигурации МВС. Высокий потенциал с первого выхода дешифратора 22 поступает на входы

5 элементов И 3 первой строки матрицы 1. В. результате чего на входы элементов ИЛИ 4 и ИЛИ 4з с входов 212 и 213 через элементы И 3i2 и И 313 поступают высокие потенциалы. Поступившие на входы блока 23 адреса

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

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

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

Высокий потенциал с выхода элемента ИЛИ 4з поступает на входы группы элемен- тов И 12з и 13з, в результате чего значения элементов вектора конфигурации МВС и адрес команды, соответствующие третьей вер- шине графа, соответственно через элементы ИЛИ 9з и 1бз поступают на соот- ветствующие регистры 8з и 11з. Прохождение информации, по третьей вершине графа на регистры 8з и 11з возможно благодаря наличию на входах элементов И 12 и 13з с выхода элемента ИЛИ-НЕ 7з высокого потенциала, который появляется на его входах за счет наличия низких потенциалов с выходов группы элементов И 6з, так как нз входы последнего с инверсного выхода элемента ИЛИ 42 поступает низкий потенциал.

Для выбора очередного участка программы на входы 331 VI 332 устройства подаются сигналы. В результате на втором информационном выходе регистра 18 появ- ляется высокий потенциал, который поступает на входы элементов И 20а, и код номера третьей вершины с входа 192 через элемент И 20а и ИЛИ 21 поступает на дешифратор 22. с третьего выхода которого высокий по- тенциал поступает на входы группы элементов И 14з и 15з, на вторые входы которых с регистра 11з и с регистра 8з через элементы ИЛИ 9з поступает информация о третьей вершине (адрес команды и значения эле- ментов tteKTOpa конфигурации МВС), которая черб З группу элементов ИЛИ 16 и 17 поступает на соответствующие выходы 39 и 38 устройства.

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

0 5

0 5 0 5

0 5 0

5

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

выход которого соединен с первыми входами элементов И i-й строки матрицы топологии орграфа, вторые входы которых являются входами данных устройства, выходы элементов И j-ro столбца матрицы топологии орграфа соединены с входами j-ro

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

,Я;

Я,

тов И пятой группы, выходы четвертого и шестого блоков элементов И соединены с входами шестого блока элементов ИЛИ, выход которого соединен с вторыми входами блоков элементов И шестой группы, выходы j-x блоков элементов И пятой и шестой групп соединены соответственно с вторым и третьим входами j-ro блока элементов ИЛИ первой группы, выход которого соединен с информационным входом j-ro информационного регистра и с первым входом j-ro блока элементов И третьей группы, выход которого соединен с j-м входом третьего блока элементов ИЛИ, выход которого является выходами вектора конфигурации устройства, выход j-ro элемента ИЛИ-НЕ группы соединен с третьим и вторым входами j-x блоков элементов И соответственно шестой и седьмой групп, выход 1-го блока элементов И седьмой группы соединен с вторым входом 1-го блока элементов ИЛИ второй группы, i-й выход дешифратора соединен с вторым и первым входами i-x блоков элементов И первой и третьей групп, третий выход блока выбора максимального кода соединен с вторыми входами блоков элементов И седьмой группы, вторые входы j-x блоков элементов И четвертой группы являются j-ми кодовыми входами устройства.

К элементам №6,U29,№0

К элементам

U2tt,

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

С 8хо$а Жс dxofa 35

фиг.1