Например, Бобцов

МЕТОД ОБЪЕДИНЕНИЯ И РАЗДЕЛЕНИЯ ЦИКЛИЧЕСКИХ УЧАСТКОВ ПОСЛЕДОВАТЕЛЬНЫХ НАСЛЕДУЕМЫХ ПРОГРАММ

60 Д. Б. Борзов, С. А. Дюбрюкс, В. С. Титов
УДК 681.3

Д. Б. БОРЗОВ, С. А. ДЮБРЮКС, В. С. ТИТОВ
МЕТОД ОБЪЕДИНЕНИЯ И РАЗДЕЛЕНИЯ ЦИКЛИЧЕСКИХ УЧАСТКОВ ПОСЛЕДОВАТЕЛЬНЫХ НАСЛЕДУЕМЫХ ПРОГРАММ

Предложен метод объединения/разделения циклических участков последовательных наследуемых программ, позволяющий объединять тела циклов и получать более длинные линейные участки, подлежащие последующему распараллеливанию. На основе данных о внутренней структуре программы проанализированы возможности ее эквивалентного преобразования к виду, позволяющему выполнять параллельно часть задач, назначенных ранее для последовательного выполнения.

Ключевые слова: распараллеливание, программа, объединение, разделение, цикл, линейка, участок, метод.

В настоящее время все большее распространение получает использование большого количества процессоров (до нескольких сотен) для решения поставленных задач [1]. В то же время значительная часть задач остается последовательными [2], в связи с этим для повышения производительности необходимо назначать на разные процессоры отдельные части одной задачи. Очевидно, что различные подзадачи при этом должны оставаться независимыми без потери логики исходного алгоритма, в связи с чем необходимо выявлять независимые подалгоритмы внутри последовательных программ. Значительная часть современных алгоритмов состоит из циклических участков [3], на обработку которых используется ощутимая часть ресурсов вычислительной системы.
В настоящей статье предложен метод объединения и разделения циклических участков последовательных исполняемых программ, развиваются идеи, представленные в работах [4, 5].
Предлагаемый метод позволяет объединять циклы с целью получения более длинных линейных участков для их последующего распараллеливания, а также сокращения количества операций приращения счетчиков циклов и проверок условий выхода из них. Метод основан на объединении тел смежных циклов последовательной наследуемой программы, операторы которых имеют одинаковый уровень вложенности.
Введем исходные обозначения.

1. Множество операторов задается массивом

M=

mij

,
N ×5

где

i=N

— порядковые

номера операторов, N — общее число операторов.

2. ∀j = 1, Emi1 = NopN , где Nop — порядковые номера элементов массива М, i = 1, N .

3. ∀j = 2, Emi2 = VN , где V — уровень вложенности i-го оператора, i = 1, N . 4. ∀j = 3, Emi3 = CbegN , где Сbeg — начальное значение счетчика цикла, в который

вложен i-й оператор, i = 1, N .

5. ∀j = 4, Emi4 = CendN , где Cend — конечное значение счетчика цикла, в который

вложен i-й оператор, i = 1, N .

6. ∀j = 5, Emi5 = CnN , где Cn — порядковые номера циклов, i = 1, N .
На первом этапе при использовании метода осуществляются поиск и выделение на описанном массивом M фрагменте программы участка из циклов, подлежащих объедине-

ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2

Метод объединения и разделения циклических участков последовательных программ 61

нию. Операторы, составляющие тела этих циклов, должны иметь одинаковый уровень вло-
женности.
Рассмотрим более подробно данный этап на примере следующего алгоритма. Счетчик
Сt используется для подсчета числа операторов, составляющих выделяемый участок программы, переменная Level используется для перебора возможных значений уровня вложенности от первого до максимального для всего фрагмента программы значения LevMax, переменная Copy2 используется для копирования нижней границы искомого участка, i и k являются вспомогательными переменными.
1. Level=1. 2. i=1. 3. Если V(i)=Level, то Сt=1; A(Сt)=M(i); LowSide=i (иначе п. 9). 4. k=i+1. 5. Если V(k)=Level, то Сt= Сt+1; A(Сt)=M(k) (иначе п. 8). 6. k=k+1. 7. Если k=N, то п. 8 (иначе п. 5). 8. Если Сt>1, то Сopy2= LowSide; переход на 2 этап (иначе п. 10). 9. i=i+1. 10. Если i=N, то п. 11 (иначе п. 3). 11. Level=Level+1. 12. Если Level>LevMax, то конец (иначе п. 2).

Данные о

выделенных

участках

заносятся во

вспомогательный

массив

A=

aij

,
N×5

имеющий одинаковую структуру с массивом М.

Опишем работу приведенного алгоритма на следующем примере. Пусть дан массив М с

числом операторов N = 9, где максимальное значение уровня вложенности V равно 2 (табл. 1).

Таблица 1

Nop

V

Cbeg

Cend

Cn

1 0 1 12 0

2 1 1 15 1

3 1 1 20 2

4 1 1 20 2

5 1 1 12 3

6

0

13 15

0

7

1

13 15

4

8

2

16 20

5

9

0

16 20

0

В п. 1 алгоритма переменной Level присваивается значение 1, т.е. выполняются поиск и выделение групп операторов первого уровня вложенности. В п. 2 счетчику i операторов
присваивается значение 1. В результате значение первого элемента вектора V меньше значе-
ния переменной Level, поэтому содержимое счетчика i увеличивается на единицу (i=2). Так как значение второго элемента вектора V равно значению переменной Level, то счетчику Ct операторов образуемой группы присваивается значение 1, а нижней границе LowSide будущего участка — значение i: LowSide=2. Элемент 2 массива М копируется на место элемента 1 вспомогательного массива А. В п. 4 инициализируется вспомогательная переменная k=3. Зна-
чение третьего элемента вектора V равно значению переменной Level, поэтому содержание счетчика Ct увеличивается на единицу: Ct =2. В то же время элемент 3 массива М перемещается (копируется) на место второго элемента вспомогательного массива А. В п. 6 k=4. Так
как k меньше общего числа операторов, осуществляется переход к п. 5. Значение четвертого
элемента вектора V равно значению переменной Level, следовательно, Ct увеличивается на единицу: Ct =3. При этом элемент 4 массива М копируется на место элемента 3 вспомогательного массива А и k=5. Так как k1, то искомый участок выбран, значение его нижней границы (2) сохраняется в переменной Copy2, осуществляется переход к следующему этапу.
На втором этапе происходит объединение всех циклов выделенного участка в один с
минимальным значением счетчика Сbeg с последующим разделением оставшихся участков, затем — объединение по новому минимальному значению Сbeg среди счетчиков конца цикла c дальнейшим разделением и т.д., пока количество циклов объединения/разделения не станет
равным числу циклов на участке, уменьшенному на единицу.

Исходными данными этапа 2 являются массив A = aij N×5 (табл. 2), значение Ct счет-

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

циклов этого участка MaxNc, и его нижняя граница LowSide.

Таблица 2

Nop

V

Сbeg

Сend

Cn

2 1 1 15 1

3 1 1 20 2

4 1 1 20 2

5 1 1 12 3

Этап состоит из многоитерационной процедуры поиска минимума среди элементов Cend с последующей модификацией элементов Сbeg и Cn при объединении циклов участка и копирования информации, характеризующей операторы, при разделении циклов. Процесс пред-
ставляется следующим алгоритмом, в котором HighSide — верхняя граница участка, x — счетчик числа итераций объединения/разделения, Min — переменная для поиска минимума среди конечных значений счетчиков циклов, Copy1 — переменная для копирования значений границ участка, z — вспомогательная переменная:
1. HighSide=Ct; LowSide=1. 2. x=1. 3. Если х≠1, то HighSide=LowSide+1. 4. Min=Сend(LowSide). 5. z= LowSide+1. 6. Если Сend(z)=Min then Min= Сend(z). 7. z=z+1. 8. Если z>HighSide, то п. 9 (иначе п. 6). 9. Copy1= HighSide. 10. z= LowSide. 11. Если Сend(z)>Min, то Сend(z)=Min, Сbeg(z+Сt)=Min+1;
Nop(z+ Сt)= Nop(z)+ Сt; Cn(z)=x. 12. Cn(z+ Сt)= Cn(z); Copy1= Copy1+1. 13. z=z+1. 14. Если z>HighSide, то п. 14 (иначе п. 11). 15. LowSide= HighSide+1; HighSide=Сopy1. 16. x=x+1. 17. Если x= Max Nc–1, то переход на этап 3 (иначе п. 4). Рассмотрим работу данного алгоритма на примере выходных данных первого этапа, ко-
торые состоят из массива А (табл. 2), нижней границы LowSide=2, суммарного количества циклов участка MaxNc=3 и длины участка, равной значению счетчика Ct =4.
В п. 1 значению начальной верхней границы участка присваивается значение
HighSide= Ct =4 и нижней границы — LowSide=1, т.е. на первой итерации обработка ведется среди элементов а1,1—а4,1. В п. 2 счетчику х числа итераций присваивается начальное значение 1. На первой итерации модификация границ участка поиска минимума не производится,

ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2

Метод объединения и разделения циклических участков последовательных программ 63

за минимум принимается значение Cend(l)=15, соответствующее первому элементу массива А.

Значение нижней границы участка, увеличенное на единицу, присваивается счетчику z пере-

бора участка: z=2. Значение Cend(2) больше минимума, поэтому z увеличивается на единицу:

z=3. Так как значение z меньше верхней границы, элемент вектора Cend(3) сравнивается с ми-

нимумом. Значение Cend(3) больше минимума, поэтому содержание счетчика увеличивается и

становится равным четырем. Так как значение z равно верхней границе, элемент вектора

Cend(4) сравнивается с минимумом. Cend(4) больше минимума, следовательно, минимуму при-

сваивается значение Cend(4)=12. Далее z = 5 — что больше верхней границы, следовательно,

осуществляется переход к п. 9 и копируется значение верхней границы HighSide в перемен-

ную Copyl. В п. 10 счетчику z нижней границы перебора участка присваивается значение 1.

Так как Cend(l) больше минимума, то в п. 11 минимуму присваивается значение Cend(l), а эле-

мент массива А(1) копируется в элемент А(5), при этом происходит модификация значений

Cend(l)=Min=12; Сbeg(5)=Min+l=13, Cn(1)=1 и Cn(5)=4, а также увеличивается значение копии

верхней границы: Сору1=5. В п. 12 осуществляется приращение значения z: z=2; Так как z