Разработка и реализация методов потокового анализа распараллеливаемых программ в Преобразователе программ СБкЗ_ПП

Пример

было

do i=2, n-1

a[i] = a[i] + a[i - 1] * a[i + 1]

end do

стало

do i = 2, n-2, 2

a[i] = a[i] + a[i - 1] * a[i + 1]

a[i + 1] = a[i + 1] + a[i] * a[i + 2]

end do

if (mod(n-2,2) = 1) then

a[n-1] = a[n-1] + a[n-2] * a[n]

end if

В примере №9 показаны все три варианта улучшений. Количество переходов уменьшилось в два раза потому, что две итерации выполняются перед проверкой и переходом в начало цикла. Параллелизм увеличен за счет того, что второе присваивание может быть выполнено в то время, как выполняется первое и обновлялись переменные цикла. Если элементы массива привязаны к регистрам, то это увеличит эффективность, поскольку в теле цикла a[i] и a[i+1] используются два раза. В этом случае данные будут загружены в регистры не три, а два раза за итерацию. Если процессор содержит соответствующие инструкции, разворачивание позволяет скомбинировать несколько операций по загрузке данных в регистры в одну. Конструкция if в конце называется эпилогом цикла и должна быть сгенерирована, когда неизвестно на этапе компиляции будет ли совпадать количество итераций с фактором разворачивания u. Если u > 2, то эпилог цикла - есть сам цикл.

Преимущество разворачивания циклов в том, что оно может применяться к любому циклу и может быть выполнено как на высоком, так и на низком уровне. Некоторые компиляторы выполняют, так называемое сворачивание циклов, перед разворачиванием потому, что программы часто содержат циклы, которые были развернуты вручную. Большинство компиляторов для высокопроизводительных процессоров разворачивают как минимум самый внутренний цикл гнезда циклов. Разворачивание внешнего цикла не настолько универсальная процедура потому, что предполагает генерацию копий внутренних циклов. Иногда компилятор может комбинировать эти копии, собирая их в ту же структуру, которая наблюдалась в тексте исходного кода. Такое комбинирование называется развернуть-и-сжать (unroll-and-jam).

Неформальное контекстное условие

Участком экономии в данном случае является цикл For, тело которого состоит из последовательности операторов

Схема

Здесь Y - цикл For. У него есть начальная граница - E₁, конечная граница - E₂, шаг E₃ и тело - B. Причём D - представление тела цикла Y в виде последовательности операторов.

Информационные условия:

тело цикла B не содержит операторов, не зависимых от параметра цикла;

результаты X не влияют на параметр цикла;

фактор разворачивания u должен быть меньше либо равен E₂-1.

Формальное контекстное условие

< Y, E₁, E₂, E₃, B,D, U>(

FragClass(Y)=Dfor &

FragClass(E₁)=Dexpr & FragClass(E₂)=Dexpr &

FragClass(E₃)=Dexpr & FragClass(U)=Dexpr &

FragClass(B)=Dbody & FragClass(D)=Dsch &

E₁=For(Y) & E₂=Until(Y) & E₃=Step(Y) & B=Body(Y) &

D=Sch(B) Ч X<D Ч Not(Par(Y) A(X) = ) &

Eval(U, null, null) <= Eval(U, -, 1)

).

Неформальное описание трансформации

В зависимости от фактора разворачивания u:

1. Копируем оператор X u раз c инкрементированным значением начальной границы E1 для каждой копии (i_u=i_u-1 + 1);

2. Конечную границу E2 уменьшаем на u;

3. Шаг цикла E3 увеличиваем на u;

4. Если u > 2, то создаём после цикла Y условный оператор, условие которого имеет вид mod(E2-u, u) = 1, а ветка then состоит из оператора Х c декрементированным значением E1.

Формальное описание трансформации

Покрывает пункты 2, 3, 4 неформального описания трансформации.



< Y, E₁, E₂, E₃, B,D, U>(

FragClass(Y₁) = Dfor &

FragClass(C₁) = Dif &

FragClass(X₁) = Dsch &

FragClass(X₂) = Dsch &

c = Новые идентификаторы (Var, Int) &

E₁₁ = NewExpr(c) &

Eval(E₁₁, ,) = Eval(Until(Y), -, U) &

E₁₂ = NewExpr(c) &

Eval(E₁₂) = Eval(Step(Y), +, U) &

For(Y₁) = ? (For(Y)) &

Until(Y₁) = ? (E₁₁) &

Step(Y₁) = ? (E₁₂) &

Par(Y₁) = Par(Y) &

If(C₁) = MakeExpr(MakeExpr(E₂, -, U), mod, U), =, 1) &

X₁ = ZamFrag(X, Par(Y), Eval(Until(Y), -, 1)) &

Sch(Thcn(C1)) = ? (X₁) &

If(Eval(U, ,) > 2, X₂ = Y₁||С₁, X₂ = Y₁), Y => X₂).

Характеристическая функция

Формула стратегии

Элементы потокового анализа Конец /Развертка цикла/

7. Шелушение, или разгрузка цикла

Бекон 6.3.5 (28)

0.127 августа 2006

Описание

Объединение двух циклов при совпадении верхней или нижней границ итераций. Тело цикла с большим количеством итераций попадает в тело цикла с меньшим количеством итераций. Оставшиеся итерации выполняются отдельно

Пример

было

Do i = 2, n

b[i] = b[i] + b[2]

end do

do all i = 3, n

a[i] = a[i] + c

end do all

стало

if (2 <= n) then

b[2] = b[2] + b[2]

end if

do all i=3, n

b[i] = b[i] + b[2]

a[i] = a[i] + c

end do all

Неформальное контекстное условие

Данное ОП можно применить при выполнении следующих условий:

· если два цикла выполняются последовательно друг за другом;

· либо верхние границы заданы константами (значения констант отличается на 1), а нижние переменными, причём совпадающими, либо наоборот;

· Шаги обоих циклов константы и совпадают;

· выполнение операторов одного цикла не влияет на результат выполнения операторов другого цикла;

· аргументы тела одного из циклов не должны пересекаться(совпадать) с результатами тела другого цикла;

результаты тел обоих циклов не должны пересекаться.

Формальное контекстное условие

<Y1,Y2,E1,E2,O1,O2,B1,B2>(FragClass(Y1)=Dfor & FragClass(Y2)=Dfor & FragClass(O1)=Dexpr & FragClass(O2)=Dexpr & FragClass(E1)=Dexpr & FragClass(E2)=Dexpr & FragClass(S1)=Dexpr & FragClass(S2)=Dexpr & FragClass(B1)=Dbody & FragClass(B2)=Dbody &O1 = For(Y1) & O2 = For(Y2) & E1 = Until(Y1) & E2 = Until(Y2) & S1 = Step(S1) & S2 = Step(S2) & B1 = Body(Y1) & B2 = Body(Y2) &

<(Y1,Y2) & ((Left(O1) = Const & Left(O2) = Const & Calc(O1, -, O2) = 1 & Left(E1) = Var & Left(E2) = Var & LeftExpr(E1) = LeftExpr(E2)) Or (Left(E1) = Const & Left(E2) = Const & Calc(E1, -, E2) = 1 & Left(O1) = Var & Left(O2) = Var & LeftExpr(O1) = LeftExpr(O2))) & Left(S1) = Const & Left(S2) = Const & Eval(S1) = Eval(S2) & (R(Y1) R(Y2) = ) & (A(B1) R(B2) = ) & (R(B1) R(B2) = ) >)

Неформальное описание трансформации

Создаем условие IF для выноса одной итерации, если O1 и O2 - константы тогда левая часть выражения минимум из O1 и O2, а правая часть выражения максимум из O1 и O2. Тело IF есть тело цикла с минимальной начальной константой.

Создаем цикл FOR такой что, если O1 и O2 - константы, O1 и O2 отличаются на 1, E1 и E2 переменные, E1 = E2, S1 = S2 тогда FOR = объединение B1 и B2, O' = максимум из O1 и O2, E' = E1, S' = S1.

Пояснения Y1 - DFOR - определение цикла, Y2 - DFOR - определение цикла, O1 - DEXPR - начальное условие цикла Y1, O2 - DEXPR - начальное условие цикла Y2, E1 - DEXPR - конечное условие цикла Y1, E2 - DEXPR - конечное условие цикла Y2, B1 - DBODY - тело цикла Y1, B2 - DBODY - тело цикла Y2, IF1 - DIF - условие If, FOR1 - DFOR - новый цикл.

Формальное описание трансформации



!<Y1,Y2,E1,E2,O1,O2,B1,B2>

(

CASE1 = iif( Type(Left(O1)) = Const & Type(Left(O1)) = Const, true, false) &

FragClass(IF_EXPR) = DEXPR &

Op(IF_EXPR) = '<=' &

Left(IF_EXPR) = iif(CASE1,

iif(eval(O1)<eval(O2), Left(O1), Left(O2)),

iif(eval(E1)<eval(E2), Left(E1), Left(E2))) &

Right(IF_EXPR) = iif(CASE1,

iif(eval(O1)<eval(O2), Left(O2), Left(O1)),

iif(eval(E1)<eval(E2), Left(E2), Left(E1))) &

FragClass(IF_THEN) = DBODY &

SCH(IF_THEN) = iif(CASE1,

iif(eval(O1) < eval(O2), SCH(B1), SCH(B2)),

iif(eval(E1) > eval(E2), SCH(B1), SCH(B2)))

FragClass(IF1) = DIF &

IF(IF1) = IF_EXPR &

THEN(IF1) = IF_THEN &

FragClass(FOR1) + DFOR &

FOR(FOR1) = iif(CASE1, iif(eval(B1) > eval(B2), B1, B2), B1 )&

BEGIN(FOR1) = iif(CASE1, iif(eval(O1) < eval(O2), O1, O2), O1 ) &

UNTIL(FOR1) = iif(CASE1, E1, iif(eval(E1) < eval(E2), E1, E2) ) &

STEP(FOR1) = STEP(Y1) &

BODY(FOR1) = SCH(B1) || SCH(B2)

)

Характеристическая функция

Формула стратегии

Элементы потокового анализа Конец /Разгрузка цикла/

8. Нормализация цикла

Бекон 6.3.6 (28)

0.127 августа 2006

Описание

Нормализация преобразует все циклы так, что индексная переменная инициализируется единицей (или нулем) и увеличивается на 1 для каждой итерации. Такое преобразование предоставляет возможность для слияния и упрощает анализ зависимостей между циклами, как показано в примере №11 . Нормализация помогает выявить, какие циклы являются кандидатами для расслаивания с последующим слиянием. Наиболее важным использованием нормализации является разрешение компьютеру применять тест для анализа индексов массивов, многие из которых требуют нормализованных итерационных границ

Пример

было

do i = 1,n

a[i] = a[i] + c

end do

do i = 2, n+1

b[i] = a[i-1] * b[i]

end do

стало

do i = 1, n

a[i] = a[i] +c

end do

do i = 1, n

b[i+1] = a[i] * b[i+1]

end do

Возможны варианты реализации для подвыражений.

В постановке для операторов, просто.

Неформальное контекстное условие

Участком экономии в данном случае является цикл For, тело которого состоит из последовательности операторов.

Y - цикл. У цикла есть свои границы: Е1 - начальная граница, Е2 - конечная граница, Е3 - шаг цикла. B - тело цикла. E1 не равно 1

Формальное контекстное условие

<Y,E1,E2,E3,B,D,X1,X2>(FragClass(Y)=Dfor & FragClass(B)=Dbody & FragClass(E1)=Dexpr & FragClass(E1)=Dexpr & FragClass(E2)=Dexpr & FragClass(E3)=Dexpr & ParDO(Y)=True & E1 = For(Y) & E2 = Until(Y) & E3 = Step(Y) & B = Body(Y) & Eval(E1, null, null) <> 1)

Неформальное описание трансформации

Значение верхней границы переходит в значение верхней границы+значение нижней границы, значение нижней границы переходит в 1

Формальное описание трансформации

<Y,E1,E2,E3,B,D,X1,X2>(Eval(Е2, null, null) = Eval(E2, +, E1), E1=>1)

Характеристическая функция

Формула стратегии

Элементы потокового анализа

Конец /Нормализация цикла/

Вариант 2

1. обмен циклов

Бэкон 6.2.1 (16), Никитин _

0.115 октября 2006

Описание

Преобразование состоит в перестановке местами каких-либо двух циклов в тесно вложенном гнезде циклов. В частности, всегда можно переставлять рядом стоящие циклы, имеющие по всем зависимостям тип ParDo. После перестановки свойство РаrDo сохраняется у обоих циклов. Если возможна перестановка 1-го цикла с k-ым и 1-ый цикл имеет тип РаrDо, то после перестановки тип РаrDо будет иметь k-ый цикл. Пусть самый внешний цикл имеет тип РаrDо по всем зависимостям. Его всегда можно переставить со вторым циклом. Новый второй цикл будет также иметь тип РаrDо по всем зависимостям. Поэтому его можно переставить с третьим циклом и т. д. Это означает, что любой цикл РаrDо всегда можно поставить в тесно вложенном гнезде на любое более глубокое место. При этом свойство РаrDо сохраняется. В противоположность этому, в общем случае переставлять внутренний цикл РаrDо "наружу" нельзя.

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

Пример

было

Do i=1,n

do j=1,n

total[i]=total[i]+a[i,j]

end do

end do

стало

Do j=1,n

do i=1,n

total[i]=total[i]+a[i,j]

end do

end do



Неформальное контекстное условие

Участком экономии в данном случае является цикл For, тело которого состоит из другого цикла For, тело которого, в свою очередь, состоит из двух операторов.

Здесь Y1 - первый (внешний) цикл For, Y2 - второй (внутренний) цикл For. У каждого цикла есть свои начальные границы - E1 и T1, свои конечные границы - E3 и T3, свои шаги цикла E2 и T2 и свои тела циклов - B1 и B2. Причём Y2 является телом цикла Y1. D - представление тела внутреннего цикла Y2 в виде последовательности операторов, X1 и X2 - две части этой последовательности.

Информационные условия:

Любой цикл РаrDо всегда можно поставить в тесно вложенном гнезде на любое более глубокое место.

Формальное контекстное условие

< Y1, Y2, E1, E2, E3, T1, T2, T3, B1, B2, D, X1, X2>(

Класс_фрагмента (Y1)= Цикл_с_шагом &

Класс_фрагмента (Y2)= Цикл_с_шагом &

Класс_фрагмента (B1)= Программный_блок &

Класс_фрагмента (B2)= Программный_блок &

Класс_фрагмента (D)= Последовательность_операторов &

Класс_фрагмента (E1)= Выражение &

Класс_фрагмента (E2)= Выражение &

Класс_фрагмента (E3)= Выражение &

Класс_фрагмента (T1)= Выражение &

Класс_фрагмента (T2)= Выражение &

Класс_фрагмента (T3)= Выражение &

Класс_фрагмента (X1)= Присваивание &

Класс_фрагмента (X2)= Присваивание &

B1= Тело (Y1) & Первый_элемент_последовательности (B1)=Y2 &

Последний_элемент_последовательности (B1)=Y2 & B2= Тело(Y2) &

D= Дуга_последовательность_операторов (B2) & Первый_элемент_последовательности(D)= Первый_элемент_последовательности (X1) &

Последний_элемент_последовательности (D)= Последний_элемент_последовательности (X2) &

Тип_левой_части (E1){Const} & Тип_левой_части (E2){Const} & Тип_левой_части (E3){Const} & Тип_левой_части (T1){Const} & Тип_левой_части (T2){Const} & Тип_левой_части (T3){Const} &

Результатное множество (Выражение_справа (X1)) Аргументное множество (Выражение_слева (X2)) = &

Результатное множество (Выражение_слева (X1)) Аргументное множество (Выражение_справа (X1)) = &

Гнездо_циклов (Y1)=True &

(X1, X2, Y1) = false & (X2, X1, Y1) = false &

v1: Выражение & v1 < Выражение_слева (X1) & Символ_операции (v1) = NULL & Результат_есть_массив (Тип (Тип_левой_части (v1))) = true & Аргументное множество (Выражение_слева (X1)) \ Счетчик_цикла (Y1) \ Счетчик_цикла (Y2) \ Результатное множество (v1) =

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/



v3: Выражение & v3 < Выражение_справа (X2) & Символ_операции (v3) = NULL & Результат_есть_массив (Тип (Тип_левой_части (v3))) = true & Тип_левой_части (v3)= Тип_левой_части (v1) & Аргументное множество (Выражение_справа (X1)) \ Счетчик_цикла (Y1) \ Счетчик_цикла (Y2) \ Результатное множество (v3) =

Неформальное описание трансформации

Меняем все нижние и верхние границы циклов, а также их шаги местами. Также меняем местами счетчики циклов.

Формальное описание трансформации

< Y1, Y2, E1, E2, E3, T1, T2, T3, B1, B2> ( (E1Z,T1) & (E2Z,T2) & (E3Z,T3) & (T1Z,E1) & (T2Z,E2) & (T3Z,E3), i1= Счетчик_цикла (Y1) & i2= Счетчик_цикла (Y2), E1E1Z, E2E2Z, E3E3Z, T1T1Z, T2T2Z, T3T3Z, Счетчик_цикла (Y1)=i2, Счетчик_цикла (Y2)=i1)

Характеристическая функция

Формула стратегии

Элементы потокового анализа

Последовательность_операторов, Первый_элемент_последовательности, Последний_элемент_последовательности, Дуга_последовательность_операторов, Результатное множество,

Аргументное множество, Гнездо_циклов, , Результат_есть_массив

Конец / Обмен циклов /

2. Распределение цикла

Бэкон 6.2.7 (23)

Воеводин 417

0.127 августа 2006

Описание

Распределение циклов (также называемое расщеплением циклов или разделением циклов) разбивает гнездо циклов на несколько отдельных циклов. Каждый из новых циклов имеет тоже итерационное пространство, что и исходный цикл, но содержит подмножество операторов исходного цикла.

Это преобразование является обратным по отношению к преобразованию слияния циклов. Пусть задан некоторый цикл. Построим для него граф зависимостей. Допустим, что после переупорядочивания в теле цикла его можно представить в виде двух подряд идущих фрагментов, и нет ни одной Дуги, идущей из опорных пространств второго фрагмента в опорные пространства первого фрагмента. Тогда цикл можно представить в виде двух Подряд идущих циклических конструкций. Самые внешние циклы у них совпадают. Телом первого цикла является первый фрагмент, телом второго -- второй фрагмент. Если преобразуемый цикл имел тип РаrDо, то тип ParDo будут иметь оба внешних цикла преобразованной программы. Оба внешних цикла или один из них могут иметь тип РаrDо и в том случае, когда таковым не является преобразуемый цикл.

Пример

было

do i = 1, n

do j = 1, m

a[i] = a[i] + c

x[j] = x[j] + x[j]*10

end do

end do

стало

do all i = 1, n

a[i] = a[i] + c

end do

do j = 1, m

x[j] = x[j] + x[j]*10

end do

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

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

Неформальное контекстное условие

Участком экономии в данном случае является цикл For, тело которого состоит из другого цикла For, тело которого, в свою очередь, состоит из двух операторов.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Здесь Y1 - первый (внешний) цикл For, Y2 - второй (внутренний) цикл For. У каждого цикла есть свои начальные границы - E1 и T1, свои конечные границы - E3 и T3, свои шаги цикла E2 и T2 и свои тела циклов - B1 и B2. Причём Y2 является телом цикла Y1. D - представление тела внутреннего цикла Y2 в виде последовательности двух операторов, X1 и X2 - первый и второй оператор.

Информационные условия:

результаты X2 не влияют на X1

результаты X1 не влияют на X2

X1 и X2 не имеют общих результатов

Аргументное множество X2 не содержит переменную цикла Y1

Аргументное множество X1 не содержит переменную цикла Y2

Оба цикла имеют тип ParDO

Формальное контекстное условие

< Y1, Y2, E1, E2, E3, T1, T2, T3, B1, B2, D, X1, X2>(

Класс_фрагмента (Y1)= Цикл_с_шагом &

Класс_фрагмента (Y2)= Цикл_с_шагом &

Класс_фрагмента (B1)= Программный_блок &

Класс_фрагмента (B2)= Программный_блок &

Класс_фрагмента (D)= Последовательность_операторов &

Класс_фрагмента (E1)= Выражение &

Класс_фрагмента (E2)= Выражение &

Класс_фрагмента (E3)= Выражение &

Класс_фрагмента (T1)= Выражение &

Класс_фрагмента (T2)= Выражение &

Класс_фрагмента (T3)= Выражение &

Класс_фрагмента (X1)= Присваивание &

Класс_фрагмента (X2)= Присваивание &

B1= Тело (Y1) & Первый_элемент_последовательности (B1)=Y2 &

Последний_элемент_последовательности (B1)=Y2 & B2= Тело (Y2) &

D= Дуга_последовательность_операторов (B2) &

Первый_элемент_последовательности (D)=

Первый_элемент_последовательности (X1) &

Последний_элемент_последовательности (D)=

Последний_элемент_последовательности (X2) & Тип_левой_части

(E1){Const} &

Тип_левой_части (E2){Const} & Тип_левой_части (E3){Const} &

Тип_левой_части (T1){Const} & Тип_левой_части (T2){Const} &

Тип_левой_части (T3){Const} & Результатное множество ( X1)

Результатное множество (X2) = &

Аргументное множество ( X1) Счетчик_цикла (Y2) = &

Аргументное множество ( X2) Счетчик_цикла (Y1) = &

Гнездо циклов (Y1)=True & Гнездо циклов (Y2)=True &

(X1, X2, Y1) = false & (X2, X1, Y1) = false.

Неформальное описание трансформации

Гнездо из двух циклов разбиваем на два отдельных цикла

Формальное описание трансформации

< Y1, Y2, E1, E2, E3, T1, T2, T3, B1, B2, X1, X2>

(Класс_фрагмента (V1)={ Цикл_с_шагом } & Начальная_граница_цикла (V1)=( Начальная_граница_цикла (Y1)) & Конечная_граница_цикла (V1)= ( Конечная_граница_цикла (Y1)) & Шаг (V1)= ( Шаг (Y1)) & Счетчик_цикла (V1)= Счетчик_цикла (Y1) & Дуга_последовательность_операторов (Тело (V1))=(X1)) & & Класс_фрагмента (V2)={ Цикл_с_шагом } & Начальная_граница_цикла (V2)= ( Начальная_граница_цикла (Y2)) & Конечная_граница_цикла (V2)= ( Конечная_граница_цикла (Y2)) & Шаг (V2)= ( Шаг (Y2)) & Счетчик_цикла (V2)= Счетчик_цикла (Y2) & Дуга_последовательность_операторов (Тело (V2))=(X2) &Класс_фрагмента (Z1)={ Последовательность_операторов } & Z1=V1||V2, Y1Z1)

Характеристическая функция

Формула стратегии

Элементы потокового анализа

Конец /Распределение цикла/

3. Объединение циклов

Бэкон 6.3.3 (27)

Воеводин 416

0.127 августа 2006

Описание

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

Объединение позволяет свернуть гнездо циклов в один цикл с оригинальными индексными переменными, которые вычисляются с помощью другой индексной переменной. Объединение может улучшить распределение цикла при параллельных вычислениях и уменьшить итерационные переходы. Например, если n и m немного больше, чем количество процессоров P (см. пример №6), то ни одна итерация, равно как и внешний цикл не займет столько времени, с момента выполнения последних n-P итераций, как первые P. Объединение двух циклов гарантирует, что P итераций могут выполняться каждый раз за исключением последних (nm mod P) итераций, как показано в примере

Пример



было

do all i=1, n

do all j=1, m

a[i,j] = a[i,j] +c

end do all

end do all

стало

do all T=1, n*m

i = ((T-1) / m)*m + 1

j = MOD(T-1, m) + 1

a[i,j] = a[i,j] + c

end do all

Неформальное контекстное условие

Участком экономии в данном случае является непрерывная последовательность операторов, начинающаяся и заканчивающаяся циклом For. Между циклами могут стоять и другие операторы. У циклов должны совпадать обе границы и шаг цикла, переменные цикла могут иметь разные идентификаторы.

Схема

здесь D - последовательность операторов, Y1 и Y2 - два цикла For, являющиеся ее началом и концом соответственно, Y - последовательность операторов, возможно пустая, лежащая между ними. У каждого цикла есть свои начальные границы - E1 и T1, свои конечные границы - E3 и T3, свои шаги цикла E2 и Е2 и свои тела циклов - B1 и B2. Образы выражений E1 и Е1, E2 и T2, E3 и T3 соответственно должны совпадать.

Информационные условия:

Результаты E1, E2, E3, B1, Y не должны влиять на T1, T2, T3 или B2

Результаты B2 не должны влиять на B1 и Y

Формальное контекстное условие

<D, Y, Y1, Y2, E1, E2, E3, T1,T2,T3, B1,B2> (

Класс_фрагмента (D)= Последовательность_операторов &

Класс_фрагмента (Y1)= Цикл_с_шагом &

Класс_фрагмента (Y2)= Цикл_с_шагом &

Класс_фрагмента (Y)= Последовательность_операторов &

Класс_фрагмента (E1)= Выражение &

Класс_фрагмента (E2)= Выражение &

Класс_фрагмента (E3)= Выражение &

Класс_фрагмента (T1)= Выражение &

Класс_фрагмента (T2)= Выражение &

Класс_фрагмента (T3)= Выражение &

Класс_фрагмента (B1)= Программный_блок &

Класс_фрагмента (B2)= Программный_блок &

Первый_элемент_последовательности (D)=Y1 &

Последний_элемент_последовательности (D)= Y2 &

Y2<>Y1 & <(Y1, Y) & <(Y, Y2) &

Непрерывная_последовательность (D) &

Непрерывная_последовательность (Y) &

B1= Тело (Y1) &

B2= Тело (Y2)&

Обратная_польская_запись (E1)= Обратная_польская_запись (T1) &

Обратная_польская_запись (E2)= Обратная_польская_запись (T2) &

Обратная_польская_запись (E3)= Обратная_польская_запись (T3) &

(

(Результатное множество (E1) Результатное множество (E2) Результатное множество (E3) Результатное множество (B1) Результатное множество (Y))

( Аргументное множество (T1) Аргументное множество (T2) Аргументное множество (T3) Аргументное множество (B2)) )= &

Результатное множество (B2) (Аргументное множество (B1) Аргументное множество (Y))= ,

Гнездо циклов (Y1)=True &

Гнездо циклов (Y2)=True )

Неформальное описание трансформации

Тело цикла B1 заменяется на конкатенацию B1 и B2 c заменой в B2 всех вхождений параметра цикла Y2 на параметр цикла B1

цикл Y2 заменяется на Null

Гнездо из двух циклов разбиваем на два отдельных цикла

Формальное описание трансформации

<D, Y, Y1, Y2, E1, E2, E3, T1,T2,T3, B1,B2>(

Класс_фрагмента (B3)= Последовательность_операторов &

B3= (B1) ||

Zam(B2, Счетчик_цикла (Y2), Счетчик_цикла (Y1) ),

B1B3,

Y2 NULL)

Характеристическая функция

Формула стратегии

Элементы потокового анализа

Последовательность_операторов, Первый_элемент_последовательности, Последний_элемент_последовательности, Результатное множество, Аргументное множество, Гнездо_циклов, Обратная_польская_запись, Непрерывная_последовательность

Конец /Объединение циклов/

4. Распределение цикла

Бэкон 6.2.3 (20)

Воеводин 418

0.127 августа 2006

Описание

Распределение циклов (также называемое расщеплением циклов или разделением циклов) разбивает гнездо циклов на несколько отдельных циклов. Каждый из новых циклов имеет тоже итерационное пространство, что и исходный цикл, но содержит подмножество операторов исходного цикла.

Это преобразование является обратным по отношению к преобразованию слияния циклов. Пусть задан некоторый цикл. Построим для него граф зависимостей. Допустим, что после переупорядочивания в теле цикла его можно представить в виде двух подряд идущих фрагментов, и нет ни одной Дуги, идущей из опорных пространств второго фрагмента в опорные пространства первого фрагмента. Тогда цикл можно представить в виде двух Подряд идущих циклических конструкций. Самые внешние циклы у них совпадают. Телом первого цикла является первый фрагмент, телом второго -- второй фрагмент. Если преобразуемый цикл имел тип РаrDо, то тип ParDo будут иметь оба внешних цикла преобразованной программы. Оба внешних цикла или один из них могут иметь тип РаrDо и в том случае, когда таковым не является преобразуемый цикл.

Пример

было

do i = 1, n

do j = 1, n

a[i,j] = a[i-1,j+1] + 1

end do

end do

стало

do i = 1, n

do j = n, 1, -1

a[i,j] = a[i-1,j+1] + 1

end do

end do

исходное гнездо циклов: дистанционный вектор (1, -1) - перестановка недопустима

внутренний цикл инвертирован: вектор направлений (1, 1) - перестановка допустима

Неформальное контекстное условие

Участком экономии в данном случае является цикл For, тело которого состоит из последовательности операторов.

Y - цикл. У цикла есть свои границы: Е1 - начальная граница, Е2 - конечная граница, Е3 - шаг цикла. B - тело цикла. E3 = 1. E1>0.

Формальное контекстное условие

<Y,E1,E2,E3,B>(

Класс_фрагмента (Y)= Цикл_с_шагом &

Класс_фрагмента (B)= Программный_блок &

Класс_фрагмента (E1)= Выражение &

Класс_фрагмента (E1)= Выражение &

Класс_фрагмента (E2)= Выражение &

Класс_фрагмента (E3)= Выражение &

Гнездо циклов (Y)=True & E1 = Начальная_граница_цикла (Y) &

E2 = Конечная_граница_цикла (Y) & E3 = Шаг (Y) &

B = Тело (Y) & Значение (E1, null, null) > 0 &

Значение (E3, null, null) = 1 ).

Неформальное описание трансформации

Создаём Y'. Y' - это цикл For такой, что значения его начальной границы совпадают со значениями конечной границы цикла Y, значение конечной границы со значением начальной границы Y, а шаг цикла = -1.

Цикл Y переходит в цикл Y'.

Формальное описание трансформации

<Y,E1,E2,E3,B,D> ( (c: Новые идентификаторы (Var, Int)) &

Класс_фрагмента (Y')= Цикл_с_шагом & Счетчик_цикла (Y')= Счетчик_цикла (Y) & Дуга_последовательность_операторов (Тело (Y))=? Дуга_последовательность_операторов (Тело (Y'))& Начальная_граница_цикла (Y')=NewExp(C)& Начальная_граница_цикла (Y') =? (Конечная_граница_цикла (Y))& Конечная_граница_цикла (Y')=NewExp(C) & Конечная_граница_цикла (Y') =? (Начальная_граница_цикла (Y)) & Значение (Шаг (Y')=1),Y=>Y')

Характеристическая функция

Формула стратегии

Элементы потокового анализа

Конец /Распределение цикла/

5. Разбиение цикла

Бэкон 6.2.6 (22)

0.127 августа 2006

Описание

Разбиение цикла является многомерным обобщением послойного разбора. Разбиение цикла (также называемое блочным разбиением) в основном используется для улучшения повторного использования кэша (Qc) и представляет собой деление итерационного пространства на блоки и преобразования гнезда циклов для проведения итераций над этими блоками. Однако оно может использоваться для улучшения использования процессоров (на многопроцессорных машинах), регистров, TLB (Translation Lookaside Buffer - используется для преобразования линейных адресов в физические адреса), или размещения страниц памяти.

Ниже приведен пример №8 гнезда массивов, в котором матрице a присваивается транспонированная матрица b. Во внутреннем цикле (с итерационной переменной j) доступ к элементам массива b осуществляется максимальным шагом 1, в то время, как доступ к элементам массива a - с максимальным шагом n. Перестановка циклов в данном случае не поможет, т.к. после перестановки доступ к элементу массива b будет осуществляться с максимальным шагом n. Осуществляя дополнительные итерации над прямоугольными подпространствами итерационного пространства, как показано в примере, достигается полное использование кэша.

Пример

было

do i = 1, n

do j = 1, n

a[i,j] = b[j,i]

end do

end do

стало

do TI = 1, n, 64

do TJ = 1, n, 64

do i = TI, min(TI+63,n)

do j = TJ, min(TJ+63,n)

a[i,j] = b[j,i]

end do

end do

end do

end do

Неформальное контекстное условие

Участком экономии в данном случае является цикл For, тело которого состоит из другого цикла For, тело которого, в свою очередь, состоит из последовательности операторов. Здесь Y1 - первый (внешний) цикл For, Y2 - второй (внутренний) цикл For. У каждого цикла есть свои начальные границы - O1 и O2, свои конечные границы - E1 и E2, свои шаги цикла S1 и S2 и свои тела циклов - B1 и B2. Причём Y2 является телом цикла Y1. D - представление тела внутреннего цикла Y2 в виде последовательности операторов

Формальное контекстное условие

< Y1, Y2, B1, B2, O1, O2, E1, E2, S1, S2, D > (

Класс_фрагмента (Y1)= Цикл_с_шагом &

Класс_фрагмента (Y2)= Цикл_с_шагом &

Класс_фрагмента (B1)= Программный_блок &

Класс_фрагмента (B2)= Программный_блок &

Класс_фрагмента (D)= Последовательность_операторов &

Класс_фрагмента (O1)= Выражение &

Класс_фрагмента (E1)= Выражение &

Класс_фрагмента (S1)= Выражение &

Класс_фрагмента (O2)= Выражение &

Класс_фрагмента (E2)= Выражение &

Класс_фрагмента (S2)= Выражение &

B1= Тело (Y1) & Первый_элемент_последовательности (B1)=Y2 &

Последний_элемент_последовательности (B1)=Y2 & B2= Тело (Y2) &

D= Дуга_последовательность_операторов (B2) & Гнездо циклов (Y1)=True

Неформальное описание трансформации

Создаём Y1'. Y1' - это цикл For такой, что значения его начальной и конечной границы совпадают со значениями начальной и конечной границы цикла Y1 соответственно, а шаг цикла - увеличенный шаг цикла Y1. Создаём целочисленную переменную - счётчик цикла Y1 - V1. Телом цикла Y1' является цикл Y2'. Y2' - это цикл For такой, что значения его начальной и конечной границы совпадают со значениями начальной и конечной границы цикла Y2 соответственно, а шаг цикла - увеличенный шаг цикла Y2. Для него так же создаем целочисленную переменную, которая будет являться счётчиком цикла - V2. Внутри цикла Y2 создаём цикл Y3 c шагом 1, начальная граница которого совпадает с текущим значением V1, а конечная - min(V1 + (значение(S1) - 1), E1). Y3 - является телом цикла Y2'. Затем, уже внутри цикла Y3, создаём цикл Y4 так же c шагом 1. Начальная граница Y4 совпадает с текущим значением V2, а конечная - min(V2 + (значение(S2) - 1), E2). Y4 - является телом цикла Y3. Телом цикла Y4 - является последовательность операторов - D

Формальное описание трансформации

< Y1, Y2, B1, B2, O1, O2, E1, E2, S1, S2, D > ( (c: Новые идентификаторы (Var, Int)) &

Класс_фрагмента (Y1')= Цикл_с_шагом & Начальная_граница_цикла (Y1')=?( Начальная_граница_цикла (Y1)) & Конечная_граница_цикла (Y1')=?( Конечная_граница_цикла (Y1)) &

Шаг (Y1')= Значение (Шаг (Y1),+,NewExpr(c)) & V1=NewExpr(c) &

Класс_фрагмента (Y2')= Цикл_с_шагом & Начальная_граница_цикла (Y2')=?( Начальная_граница_цикла (Y2)) & Конечная_граница_цикла (Y2')=?( Конечная_граница_цикла (Y2)) &

Шаг (Y2')= Значение (Шаг (Y2),+,NewExpr(c)) & V2=NewExpr(c) &

Класс_фрагмента (Y3)= Цикл_с_шагом & Счетчик_цикла (Y3)=?(V1) & Начальная_граница_цикла (Y3)= Значение (V1) & Шаг (Y3)= Значение (1) &

Конечная_граница_цикла (Y3)=MakeExpr(MakeExpr(MakeExpr(Шаг (Y1),-,1),+,V1),min,E1) &

Класс_фрагмента (Y4)= Цикл_с_шагом & Счетчик_цикла (Y4)=?(V2) & Начальная_граница_цикла (Y4)= Значение (V2) & Шаг (Y4)= Значение (1) &

Конечная_граница_цикла (Y4)=MakeExpr(MakeExpr(MakeExpr(Шаг (Y2),-,1),+,V2),min,E2) &

Дуга_последовательность_операторов (Тело (Y1'))=?(Y2') & Дуга_последовательность_операторов (Тело (Y2'))=?(Y3) & Дуга_последовательность_операторов (Тело (Y3))=?(Y4) &

Дуга_последовательность_операторов (Тело (Y4))=?(Y4) || =?( Дуга_последовательность_операторов (Тело (Y2))), Y1 => Y1', Y2 => Y2' || Y3 | Y4 )

Характеристическая функция

Формула стратегии

Элементы потокового анализа

Конец /Разбиение цикла/

6. Развертка циклов

Бекон 6.3.1 (24)

0.127 августа 2006

Описание

Развёртка в точности копирует тело цикла некоторое количество раз, называемое фактором разворачивания (unrolling factor) u. Каждая итерация после этого будет состоять не из одного, а из u шагов. Выгода использования разворачивания циклов была изучена на нескольких различных архитектурах.

Развёртка может улучшить производительность посредством:

· уменьшения количества итераций и соответственно количество условных переходов;

· увеличения параллелизма инструкций;

улучшения использования регистров, кэша данных

Пример

было

do i=2, n-1

a[i] = a[i] + a[i - 1] * a[i + 1]

end do

стало

do i = 2, n-2, 2

a[i] = a[i] + a[i - 1] * a[i + 1]

a[i + 1] = a[i + 1] + a[i] * a[i + 2]

end do

if (mod(n-2,2) = 1) then

a[n-1] = a[n-1] + a[n-2] * a[n]

end if

В примере №9 показаны все три варианта улучшений. Количество переходов уменьшилось в два раза потому, что две итерации выполняются перед проверкой и переходом в начало цикла. Параллелизм увеличен за счет того, что второе присваивание может быть выполнено в то время, как выполняется первое и обновлялись переменные цикла. Если элементы массива привязаны к регистрам, то это увеличит эффективность, поскольку в теле цикла a[i] и a[i+1] используются два раза. В этом случае данные будут загружены в регистры не три, а два раза за итерацию. Если процессор содержит соответствующие инструкции, разворачивание позволяет скомбинировать несколько операций по загрузке данных в регистры в одну. Конструкция if в конце называется эпилогом цикла и должна быть сгенерирована, когда неизвестно на этапе компиляции будет ли совпадать количество итераций с фактором разворачивания u. Если u > 2, то эпилог цикла - есть сам цикл.

Преимущество разворачивания циклов в том, что оно может применяться к любому циклу и может быть выполнено как на высоком, так и на низком уровне. Некоторые компиляторы выполняют, так называемое сворачивание циклов, перед разворачиванием потому, что программы часто содержат циклы, которые были развернуты вручную. Большинство компиляторов для высокопроизводительных процессоров разворачивают как минимум самый внутренний цикл гнезда циклов. Разворачивание внешнего цикла не настолько универсальная процедура потому, что предполагает генерацию копий внутренних циклов. Иногда компилятор может комбинировать эти копии, собирая их в ту же структуру, которая наблюдалась в тексте исходного кода. Такое комбинирование называется развернуть-и-сжать (unroll-and-jam).

Неформальное контекстное условие

Участком экономии в данном случае является цикл For, тело которого состоит из последовательности операторов

Схема



Здесь Y - цикл For. У него есть начальная граница - E₁, конечная граница - E₂, шаг E₃ и тело - B. Причём D - представление тела цикла Y в виде последовательности операторов.

Информационные условия:

тело цикла B не содержит операторов, не зависимых от параметра цикла;

результаты X не влияют на параметр цикла;

фактор разворачивания u должен быть меньше либо равен E₂-1.

Формальное контекстное условие

< Y, E₁, E₂, E₃, B,D, U>(

Класс_фрагмента (Y)= Цикл_с_шагом &

Класс_фрагмента (E₁)= Выражение &

Класс_фрагмента (E₂)= Выражение &

Класс_фрагмента (E₃)= Выражение &

Класс_фрагмента (B)= Программный_блок &

Класс_фрагмента (D)= Последовательность_операторов &

Класс_фрагмента (U)= Выражение &

E₁= Начальная_граница_цикла (Y) &

E₂= Конечная_граница_цикла (Y) &

E₃= Шаг (Y) &

B= Тело (Y) &

D= Дуга_последовательность_операторов (B) Ч X<D Ч Not(Счетчик_цикла (Y) Аргументное множество (X) = ) &

Значение (U, null, null) <= Значение (U, -, 1)

)

Неформальное описание трансформации

В зависимости от фактора разворачивания u:

1. Копируем оператор X u раз c инкрементированным значением начальной границы E1 для каждой копии (i_u=i_u-1 + 1);

2. Конечную границу E2 уменьшаем на u;

3. Шаг цикла E3 увеличиваем на u;

4. Если u > 2, то создаём после цикла Y условный оператор, условие которого имеет вид mod(E2-u, u) = 1, а ветка then состоит из оператора Х c декрементированным значением E1.

Формальное описание трансформации

Покрывает пункты 2, 3, 4 неформального описания трансформации.

< Y, E₁, E₂, E₃, B,D, U>(

Класс_фрагмента (Y₁) = Цикл_с_шагом &

Класс_фрагмента (C₁) = Условный_оператор &

Класс_фрагмента (X₁) = Последовательность_операторов &

Класс_фрагмента (X₂) = Последовательность_операторов &

c = Новые идентификаторы (Var, Int) &

E₁₁ = NewExpr(c) &

Значение (E₁₁, ,) = Значение (Конечная_граница_цикла (Y), -, U) &

E₁₂ = NewExpr(c) &

v(E₁₂) = Значение (Шаг (Y), +, U) &

Начальная_граница_цикла (Y₁) = ? (Начальная_граница_цикла (Y)) &

Конечная_граница_цикла (Y₁) = ? (E₁₁) &

Шаг (Y₁) = ? (E₁₂) &

Счетчик_цикла (Y₁) = Счетчик_цикла (Y) &

Если (C₁) = MakeExpr(MakeExpr(E₂, -, U), mod, U), =, 1) &

X₁ = ZamFrag(X, Счетчик_цикла (Y), Значение (Конечная_граница_цикла (Y), -, 1)) &

Дуга_последовательность_операторов (То (C1)) = ? (X₁) &

Если (Значение (U, ,) > 2, X₂ = Y₁||С₁, X₂ = Y₁), Y => X₂).

Характеристическая функция

Формула стратегии

Элементы потокового анализа

Конец /Развертка циклов/

7. Шелушение, или разгрузка цикла

Бекон 6.3.5 (28)

0.127 августа 2006

Описание

Объединение двух циклов при совпадении верхней или нижней границ итераций. Тело цикла с большим количеством итераций попадает в тело цикла с меньшим количеством итераций. Оставшиеся итерации выполняются отдельно

Пример

было

Do i = 2, n

b[i] = b[i] + b[2]

end do

do all i = 3, n

a[i] = a[i] + c

end do all

стало

if (2 <= n) then

b[2] = b[2] + b[2]

end if

do all i=3, n

b[i] = b[i] + b[2]

a[i] = a[i] + c

end do all

Неформальное контекстное условие

Данное ОП можно применить при выполнении следующих условий:

· если два цикла выполняются последовательно друг за другом;

· либо верхние границы заданы константами (значения констант отличается на 1), а нижние переменными, причём совпадающими, либо наоборот;

· Шаги обоих циклов константы и совпадают;

· выполнение операторов одного цикла не влияет на результат выполнения операторов другого цикла;

· аргументы тела одного из циклов не должны пересекаться(совпадать) с результатами тела другого цикла;

результаты тел обоих циклов не должны пересекаться.

Формальное контекстное условие

<Y1,Y2,E1,E2,O1,O2,B1,B2>( Класс_фрагмента (Y1)= Цикл_с_шагом &

Класс_фрагмента (Y2)= Цикл_с_шагом &

Класс_фрагмента (O1)= Выражение &

Класс_фрагмента (O2)= Выражение &

Класс_фрагмента (E1)= Выражение &

Класс_фрагмента (E2)= Выражение &

Класс_фрагмента (S1)= Выражение &

Класс_фрагмента (S2)= Выражение &

Класс_фрагмента (B1)= Программный_блок &

Класс_фрагмента (B2)= Программный_блок &

O1 =Начальная_граница_цикла (Y1) & O2=Начальная_граница_цикла (Y2)&

E1 = Конечная_граница_цикла (Y1) & E2 = Конечная_граница_цикла (Y2) &

S1 = Шаг (S1) & S2 = Шаг (S2) &

B1 = Тело (Y1) & B2 = Тело (Y2) &

<(Y1,Y2) & ((Тип_левой_части (O1) = Const & Тип_левой_части (O2) = Const & Calc(O1, -, O2) = 1 & Тип_левой_части (E1) = Var & Тип_левой_части (E2) = Var & Левая_часть_выражения (E1) = Левая_часть_выражения (E2)) Or (Тип_левой_части (E1) = Const & Тип_левой_части (E2) = Const & Calc(E1, -, E2) = 1 & Тип_левой_части (O1) = Var & Тип_левой_части (O2) = Var & Левая_часть_выражения (O1) = Левая_часть_выражения (O2))) & Тип_левой_части (S1) = Const & Тип_левой_части (S2) = Const & Значение (S1) = Значение (S2) & (Результатное множество (Y1) Результатное множество (Y2) = ) & (Аргументное множество (B1) Результатное множество (B2) = ) & (Результатное множество (B1) Результатное множество (B2) = ) >)

Неформальное описание трансформации

Создаем условие IF для выноса одной итерации, если O1 и O2 - константы тогда левая часть выражения минимум из O1 и O2, а правая часть выражения максимум из O1 и O2. Тело IF есть тело цикла с минимальной начальной константой.

Создаем цикл FOR такой что, если O1 и O2 - константы, O1 и O2 отличаются на 1, E1 и E2 переменные, E1 = E2, S1 = S2 тогда FOR = объединение B1 и B2, O' = максимум из O1 и O2, E' = E1, S' = S1.



Формальное описание трансформации

!<Y1,Y2,E1,E2,O1,O2,B1,B2>

(

CASE1 = iif( Type(Тип_левой_части (O1)) = Const & Type(Тип_левой_части (O1)) = Const, true, false) &

Класс_фрагмента (IF_EXPR) = Выражение &

Op(IF_EXPR) = '<=' &

Тип_левой_части (IF_EXPR) = iif(CASE1,

iif(Значение (O1)< Значение (O2), Тип_левой_части (O1), Тип_левой_части (O2)),

iif(Значение (E1)< Значение (E2), Тип_левой_части (E1), Тип_левой_части (E2))) &

Right(IF_EXPR) = iif(CASE1,

iif(Значение (O1)< Значение (O2), Тип_левой_части (O2), Тип_левой_части (O1)),

iif(Значение (E1)< Значение (E2), Тип_левой_части (E2), Тип_левой_части (E1))) &

Класс_фрагмента (IF_THEN) = Программный_блок &

Дуга_последовательность_операторов (IF_THEN) = iif(CASE1,

iif(Значение (O1) < Значение (O2), Дуга_последовательность_операторов (B1), Дуга_последовательность_операторов (B2)),

iif(Значение (E1) > Значение (E2), Дуга_последовательность_операторов (B1), Дуга_последовательность_операторов (B2)))

Класс_фрагмента (IF1) = Условный_оператор &

Если (IF1) = IF_EXPR &

То (IF1) = IF_THEN &

Класс_фрагмента (FOR1) + Цикл_с_шагом &

Начальная_граница_цикла (FOR1) = iif(CASE1, iif(Значение (B1) > Значение (B2), B1, B2), B1 )&

Первый_элемент_последовательности (FOR1) = iif(CASE1, iif(Значение (O1) < Значение (O2), O1, O2), O1 ) &

Конечная_граница_цикла (FOR1) = iif(CASE1, E1,

iif(Значение (E1) < Значение (E2), E1, E2) ) &

Шаг (FOR1) = Шаг (Y1) &

Тело (FOR1) = Дуга_последовательность_операторов(B1) || Дуга_последовательность_операторов (B2)

)

Характеристическая функция

Формула стратегии

Элементы потокового анализа

Конец /Разгрузка цикла/

8. Нормализация цикла

Бекон 6.3.6 (28)

0.127 августа 2006

Описание

Нормализация преобразует все циклы так, что индексная переменная инициализируется единицей (или нулем) и увеличивается на 1 для каждой итерации. Такое преобразование предоставляет возможность для слияния и упрощает анализ зависимостей между циклами, как показано в примере №11 . Нормализация помогает выявить, какие циклы являются кандидатами для расслаивания с последующим слиянием. Наиболее важным использованием нормализации является разрешение компьютеру применять тест для анализа индексов массивов, многие из которых требуют нормализованных итерационных границ



Пример

было

do i = 1,n

a[i] = a[i] + c

end do

do i = 2, n+1

b[i] = a[i-1] * b[i]

end do

стало

do i = 1, n

a[i] = a[i] +c

end do

do i = 1, n

b[i+1] = a[i] * b[i+1]

end do

Возможны варианты реализации для подвыражений.

В постановке для операторов, просто.

Неформальное контекстное условие

Участком экономии в данном случае является цикл For, тело которого состоит из последовательности операторов.

Y - цикл. У цикла есть свои границы: Е1 - начальная граница, Е2 - конечная граница, Е3 - шаг цикла. B - тело цикла. E1 не равно 1

Формальное контекстное условие

<Y,E1,E2,E3,B,D,X1,X2>( Класс_фрагмента (Y)= Цикл_с_шагом &

Класс_фрагмента (B)= Программный_блок &

Класс_фрагмента (E1)= Выражение &

Класс_фрагмента (E1)= Выражение &

Класс_фрагмента (E2)= Выражение &

Класс_фрагмента (E3)= Выражение &

Гнездо циклов (Y)=True & E1 = Начальная_граница_цикла (Y) &

E2 = Конечная_граница_цикла (Y) & E3 = Шаг (Y) &

B = Тело (Y) & Значение (E1, null, null) <> 1)

Неформальное описание трансформации

Значение верхней границы переходит в значение верхней границы+значение нижней границы, значение нижней границы переходит в 1

Формальное описание трансформации

<Y,E1,E2,E3,B,D,X1,X2>( Значение (Е2, null, null) = Значение (E2, +,

E1), E1=>1)

Характеристическая функция

Формула стратегии

Элементы потокового анализа

Конец / Нормализация цикла /