Материалы представленные на сайте исключительно с целью ознакомления пользователям Интернета и не преследуют коммерческих целей или нарушение авторских прав.
© 2018 - 2024
Это преобразование заменяет цикл
DO 99 I=1,N
99 ТЕЛОЦИКЛА(I)
на фрагмент программы
DO 99 I=1,M
99 ТЕЛОЦИКЛА(I)
DO 88 I=1,N-M
88 ТЕЛОЦИКЛА(I+M)
Это же преобразование может выглядеть и по-другому, как замена цикла
DO 99 I=1,N
99 ТЕЛОЦИКЛА(I)
на фрагмент программы
DO 99 I=1,M
99 ТЕЛОЦИКЛА(I)
DO 88 I=M+1,N
88 ТЕЛОЦИКЛА(I)
(Здесь не выполнена канонизация второго цикла в результирующем фрагменте).
Результирующий фрагмент программы должен быть в операторных скобках. Это важно для того случая, если бы исходный цикл был телом некоторого другого объемлющего цикла или под действием условного оператора.
Расщепление цикла используется как вспомогательное преобразование. Например, если цикл состоит из 100 итераций и надо сделать ему 3-кратную развертку, то этот цикл следует разделить на два: у одного 99 итераций, а у другого - 1.
Пример 86. Цикл
DO 99 I=1,100
99 X(I)=Y(I-1)
эквивалентен фрагменту программы
DO 99 I=1, 99, 3
X(I)=Y(I-1)
X(I+1)=Y(I)
99 X(I+2)=Y(I+1)
DO 88 I=100,100
88 X(I)=Y(I-1)
Конец примера.
Теорема 43 . Предположим, что в одномерном цикле
DO 99 I=1,N
99 ТЕЛОЦИКЛА(I)
есть зависимые индексные переменные, у которых в индексных выражениях коэффициенты при счетчиках цикла имеют разные знаки: X(a*I+N1) и X(N+N2-b*I). Тогда в результате расщепления пространства итераций цикла в точке M = (N+N2-N1)/(a+b) получатся два цикла, в каждом из которых исходные вхождения не связаны зависимостью (информационная зависимость стала между циклами).
Расщепление описывается во многих работах [43], [26], [100].
При выполнении расщепления следует контролировать соблюдение корректности. При копировании тела цикла не должно появиться двух операторов с одинаковыми метками. Оба результирующих цикла следует взять в операторные скобки и, если у заголовка исходного цикла была метка, то эта метка должна быть перенесена к открывающей скобке. Расщепление может выполняться, если исходный цикл содержит более одной итерации, либо, если допускаются циклы с нулевым количеством операций.
При расщеплении одномерного цикла не меняется порядок выполнения операций, поэтому, если у цикла единственный выход по завершении всех итераций, указанных в заголовке, расщепление является эквивалентным преобразованием.
6.3.5 Разрыв итераций, гнездование цикла
и подобные им преобразования
Разрыв итераций (strip mining) - это преобразование [20, с. 37], которое заменяет цикл
DO 99 I=1,N
99 ТЕЛОЦИКЛА(I)
на следующий фрагмент программы
DO 99 I=1,N//h
DO 99 J=1,h
99 ТЕЛОЦИКЛА(h*(I-1)+J)
DO 88 I=1,N-(N//h)*h
88 ТЕЛОЦИКЛА((N//h)*h+I)
Если N делится на h, то разрыв итераций выглядит более просто. Это преобразование заменяет цикл
DO 99 I=1,N
99 ТЕЛОЦИКЛА(I)
на следующий цикл
DO 99 I=1,N,h
DO 99 J=1,h
99 ТЕЛОЦИКЛА(I+J-1)
Гнездование цикла похоже на разрыв итераций и заменяет цикл
DO 99 I=1,N
99 ТЕЛОЦИКЛА(I)
на следующий фрагмент программы
DO 99 J=1,h
DO 99 I=1,N//h
99 ТЕЛОЦИКЛА(I+(J-1)*(N//h))
DO 88 I=1,N-(N//h)*h
88 ТЕЛОЦИКЛА((N//h)*h+I)
Если N константа и не делится нацело на h, то ко второму циклу полученного фрагмента программы можно применить раскрутку цикла.
Метка последнего оператора тела цикла должна остаться только у оператора последней копии тела цикла. Если ТЕЛОЦИКЛА(I) содержит помеченные операторы, то в копиях тела цикла метки должны вводиться новые (вместе со ссылками на эти метки). Ввиду этого требования удобно, чтобы последним оператором тела цикла был CONTINUE (в языке FORTRAN) и, чтобы не было меток у операторов без необходимости.
Результирующий фрагмент программы должен быть в операторных скобках. Это важно для того случая, в котором исходный цикл был телом некоторого другого объемлющего цикла или под действием условного оператора.
Не должно быть операторов выхода из цикла EXIT, BREAK.
Теорема 44 . Разрыв итераций и гнездование цикла являются равносильными преобразованиями.
Доказательство вытекает из того, что эти преобразования не меняют порядка выполнения операций.
Отличие этих преобразований в том, что у первого преобразования заранее задан размер внутреннего цикла, а размер внешнего зависит еще и от длины исходного, а во втором преобразовании - наоборот. Первое преобразование может быть целесообразно для компьютеров, параллельно обрабатывающих векторы фиксированной длины h. Второе преобразование может быть целесообразно при выполнении программы на компьютере типа MIMD с количеством процессоров h.
К преобразованиям «разрыв итераций» и «гнездование цикла» можно присовокупить еще два, на них похожих. Первое из них меняет цикл
DO 99 I=1,N
99 ТЕЛОЦИКЛА(I)
на следующий фрагмент программы
DO 99 I=1,h
DO 99 J=1,N//h
99 ТЕЛОЦИКЛА(h*(J-1)+I)
DO 88 I=1,N-(N//h)*h
88 ТЕЛОЦИКЛА((N//h)*h+I)
а второе - на следующий
DO 99 J=1,N//h
DO 99 I=1,h
99 ТЕЛОЦИКЛА(J+(I-1)*(N//h))
DO 88 I=1,N-(N//h)*h
88 ТЕЛОЦИКЛА((N//h)*h+I)
Эти преобразования равносильны не всегда. Если в теле цикла есть два вхождения некоторой переменной, которые обращаются к одной и той же ячейке памяти на итерациях I1 и I2, и выполняются условия I1<I2 и (I2 mod h) < (I1 mod h) то первое преобразование не равносильно. (Для второго цикла в этом рассуждении следует h заменить выражением N//h).
Пример 87. Замена цикла
DO 99 I=1,128
99 X(I)= 3*X(I-1)
на следующий фрагмент программы равносильна.
DO 99 I=1,8
DO 99 J=1,16
99 X(16*(I-1)+J)=3*X(16*(I-1)+J-1)
Конец примера.
Пример 88. Замена цикла
DO 99 I=1,128
99 X(I)= 3*X(I-1)
на следующий фрагмент программы
DO 99 I=1,8
DO 99 J=1,16
99 X(8*(J-1)+I)=3*X(8*(J-1)+I-1)
не равносильна. Действительно, если до выполнения цикла все элементы массива X равны 1, то после выполнения исходного цикла X(9)=3**8, а после выполнения результирующего - X(9)=3.
Конец примера.
Пример 89. Замена цикла
DO 99 I=1, 129
99 X(I)= 3*X(I-8)
на следующий фрагмент программы равносильна
DO 99 I=1, 8
DO 99 J=1, 16
99 X(8*(J-1)+I)=3*X(8*(J-1)+I-8)
X(129)= 3*X(129-8)
По поводу всех четырех преобразований следует отметить, что, поскольку в них копируется тело цикла, надо следить за тем, чтобы не возникло двух операторов с одинаковыми метками.
Конец примера.
Теорема 45 . Предположим, что в теле цикла для любой переменной и любых двух ее вхождений, которые обращаются к одной и той же ячейке памяти на итерациях I1 и I2 соответственно, не выполняются одновременно условия:
· хотя бы одно из этих вхождений является генератором,
· I1<I2
· (I2 mod h) < (I1 mod h).
Тогда первое преобразование равносильно.
Доказательство. Если к исходному и результирующему фрагментам программ применить раскрутку циклов, то полученные линейные участки программ будут отличаться перестановкой операторов. Теперь остается только вспомнить условие эквивалентности перестановки операторов.
Рассмотренное преобразование может быть применено к распараллеливанию на MIMD архитектуру. Это преобразование иногда позволяет некоторые рекуррентные зависимости сосредоточить внутри отдельных процессоров и этим самым уменьшить количество межпроцессорных пересылок.
Условие равносильности второго преобразования формулируется аналогично.
Развертка цикла
Развертка цикла [45] кратности h заменяет цикл
DO 999 I = 1, N
999 ТЕЛОЦИКЛА(I)
на следующий фрагмент программы
DO 888 I = 1, N, h
ТЕЛОЦИКЛА(I)
ТЕЛОЦИКЛА(I+1)
........................
888 ТЕЛОЦИКЛА(I+h-1)
N2 = N mod h //остаток от деления числа N на h.
DO 777 I = N-N2+1, N
777 ТЕЛОЦИКЛА(I)
Если N – константа, которая делится нацело на h, то второй цикл и стоящий перед ним оператор присваивания можно опустить.
Если N константа и не делится нацело на h, то ко второму циклу полученного фрагмента программы можно применить раскрутку цикла.
Метка последнего оператора тела цикла должна остаться только у оператора последней копии тела цикла. Если ТЕЛОЦИКЛА(I) содержит помеченные операторы, то в копиях тела цикла метки должны вводиться новые (вместе со ссылками на эти метки). Ввиду этого требования удобно, чтобы последним оператором тела цикла был CONTINUE и, чтобы не было без необходимости помеченных операторов.
Результирующий фрагмент программы должен быть в операторных скобках. Это важно для того случая, если бы исходный цикл был телом некоторого другого объемлющего цикла или под действием условного оператора.
Не должно быть операторов выхода из цикла EXIT, BREAK.
Теорема 46. Пусть тело цикла содержит операторы присваивания, логические или блочные условные операторы, операторы безусловного перехода GOTO (но не вычислимый GOTO языка ФОРТРАН!) или другие операторы цикла. Тогда развертка цикла, выполненная по описанным выше правилам, является эквивалентным преобразованием.
Доказательство вытекает из того, что при развертке цикла не меняется порядок выполнения операций. Следует проконтролировать лишь соблюдение корректности. Для более строго доказательства следует сделать раскрутки исходного и результирующего циклов.
Пример 90. Цикл
DO 99 I = 1, 100
99 X(I) = A(I+1)+K(I)-X(I-1)
эквивалентен следующему
DO 99 J = 1, 50
I = 2*J
X(I-1) = A(I)+K(I-1)-X(I-2)
99 X(I) = A(I+1)+K(I)-X(I-1)
Конец примера.
Пример 91. Цикл
DO 99 I = 1, 100
DO 88 J = 1, 40
88 B(J) = K(I)*X(J)
99 X(I) = A(I+1)+B(I)-X(I-1)
эквивалентен следующему
DO 99 I = 1, 100, 2
DO 77 J = 1, 40
77 B(J) = K(I)*X(J)
X(I) = A(I+1)+B(I)-X(I-1)
DO 88 J = 1, 40
88 B(J) = K(I+1)*X(J)
99 X(I+1) = A(I+2)+B(I+1)-X(I)
(Следует обратить внимание на изменение метки в заголовке и последнем операторе первого вложенного цикла)
Конец примера.
6.3.7 Расщепление вершин
(Введение временных массивов)
Это преобразование позволяет перенаправлять в программных циклах дуги антизависимости (дуги, направленные снизу вверх становятся направленными сверху вниз). Суть преобразования в том, чтобы какое-нибудь вхождение присвоить новой переменной и заменить этой переменной.
Пример 92. В следующем цикле есть дуга антизависимости от вхождения A(I+1) к первому вхождению A(I). Отметим, что эту дугу нельзя устранить перестановкой операторов тела цикла местами (такая перестановка нарушит равносильность программы ввиду наличия дуги потоковой зависимости между двумя вхождениями A(I)).
DO 111 I = 1, N
A(I) = B(I)+C(I)
D(I) = (A(I)+A(I+1))/2.
111 CONTINUE
Данный цикл равносилен следующему
DO 111 I = 1, N
ATEMP(I) = A(I+1)
A(I) = B(I)+C(I)
D(I) = (A(I)+ATEMP(I))/2.
111 CONTINUE
После выполнения данного преобразования можно цикл разбить на части (чему мешала прежде дуга антизависимости, ведущая «снизу-вверх»).
Конец примера.
Алгоритм. Находим в графе информационных связей дугу антизависимости. Если начальная вершина этой дуги не является источником в подграфе информационных связей, соответствующем данному фрагменту программы (телу цикла), то данная дуга антизависимости неустранима.
Иначе,
1) вводим временный одномерный массив, длина которого равна длине преобразуемого цикла (вставляем в программу оператор описания массива real ATEMP(N) )
2) в начале тела цикла вставляем оператор присваивания, левой частью которого является вхождение нового массива, у которого индексное выражение состоит только из счетчика цикла, а правой частью этого оператора присваивания является вхождение, соответствующее начальной вершине рассматриваемой дуги антизависимости
3) вхождение, соответствующее начальной вершине рассматриваемой дуги антизависимости, заменяем на левую часть нового оператора.
Пример 93.
DO 111 I = 3, N
A(I) = B(I-2)+C(I)
B(I) = (A(I)+A(I+1))/2
111 CONTINUE
Данный цикл равносилен следующему
DO 111 I = 3, N
ATEMP(I) = A(I+1)
BTEMP(I) = B(I)
A(I) = B(I-2)+C(I)
BTEMP(I) = (A(I)+ATEMP(I))/2
111 CONTINUE
Конец примера.
6.3.8 Растягивание скаляров
(Повышение размерности массива)
Это преобразование состоит в замене скалярной переменной массивом, зависящим от счетчика цикла, в который переменная входит. Растягивание скаляров иногда позволяет избавиться от некоторых информационных зависимостей в цикле. [20, с. 32].
Пример 94. Данный цикл
DO 111 I = 1, 100
A = B(I)+C(I)
D(I) = A/2
111 CONTINUE
эквивалентен следующему
dimention AA[100]
DO 111 I = 1, 100
AA(I) = B(I)+C(I)
D(I) = AA(I)/2
111 CONTINUE
Два вхождения переменной A в исходном цикле связаны двумя встречными дугами информационной зависимости. После замены переменной на массив AA дуга антизависимости исчезла и осталась только дуга истинной информационной зависимости.
Конец примера.
Алгоритм выполнения замены переменной на массив выглядит следующим образом.
Находим в теле цикла генератор, не зависящий от счетчика цикла. Будем считать для определенности, что имя этого генератора A, а имя счетчика цикла – I. Подбираем не использованное в данной программе имя для нового массива - предположим, что таким именем является AA. Заметим, что в теле цикла может быть несколько генераторов A. Предположим, что тело цикла состоит только из операторов присваивания. Тогда заменим все вхождения до первого генератора A на AA(I), а все вхождения A , начиная с первого генератора, – на AA(I+1). В начало программы следует вставить оператор описания массива AA. Перед заголовком цикла следует поставить оператор присваивания
AA(1)=A.
Если у заголовка цикла была метка, то ее надо передать вставленному перед заголовком оператору присваивания.
Если в теле цикла нет вхождения переменной A, как генератора, то после цикла следует вставить оператор
A=AA(I)
(в фортране после выполнения цикла значение счетчика сохраняется) или оператор
A=AA(N)
где N - последнее значение счетчика цикла.
В противоположном случае (если в теле цикла есть генератор переменной A) после цикла должен быть вставлен оператор
A=AA(I+1)
или
A=AA(N+1)
соответственно.
Теорема 47 . Пусть в теле цикла есть только операторы присваивания. Тогда описанная выше процедура замены переменной массивом равносильна.
Доказательство. Заменим исходный и результирующий циклы их раскрутками (напомним, что раскрутка - всегда эквивалентное преобразование). Теперь следует доказать эквивалентность полученных линейных участков. Но эти линейные участки могут быть получены один из другого переименованием.
Разбиение цикла
Наибольшее время работы программы отнимают циклически повторяющиеся участки. Поэтому в оптимизирующих и распараллеливающих компиляторах наиболее распространены преобразования циклов. Разбиение цикла - одно из наиболее важных преобразований, которое может быть использовано при распараллеливании программ на практически все типы параллельных компьютеров: векторные, конвейерные, MIMD, SIMD и т.д.
Суть разбиения цикла состоит в том, чтобы заменить цикл, в теле которого много операторов присваивания, на эквивалентный фрагмент программы из нескольких циклов, в телах которых меньше операторов. При распараллеливании зачастую большой цикл не может быть эффективно отображен на архитектуру суперкомпьютера (например, из-за нехватки ресурсов). В этом случае есть надежда, что после разбиения хотя бы некоторые из результирующих циклов смогут быть параллельно вычислены.
Иногда для оптимизации работы с памятью рассматривается разбиение цикла по именам (fission by name) [20, с. 36] – здесь одна и та же переменная не может встречаться в различных результирующих циклах. Понятно, что частота применения этого варианта преобразования весьма ограничена.
Не всякий цикл можно разбить непосредственно. Иногда для этого следует применить вспомогательные преобразования. Такие преобразования тоже включены в данную работу. Добавлены также преобразования, в которых разбиение является составной частью. С помощью вспомогательных преобразований разбиение цикла позволяет получить и частичную векторизацию цикла [20, с. 66-77].
Разбиение кратных циклов очевидным образом сводится к разбиению одномерных. Иногда вместо термина «разбиение» используется термин «разрезание» или «распределение» [26].
Разбиение цикла заменяет цикл
DO 333 I = 1, N
S1
..........
Sk
S(k+1)
..........
Sm
333 CONTINUE
на фрагмент программы, состоящий из последовательности двух циклов
DO 111 I = 1, N
S1
..........
Sk
111 CONTINUE
DO 222 I = 1, N
S(k+1)
..........
Sm
222 CONTINUE
Условия применения:
1) каждый из фрагментов программы S1,...,Sk и S(k+1),...,Sm имеет один вход и один выход. В частности:
1.1. ни один из операторов S(k+1),...,Sm не находится в зоне действия какого либо условного оператора из множества S1,...,Sk. (т.е. выполнение или невыполнение этого оператора не зависит от значения логического выражения условного оператора)
1.2. ни один из операторов S(k+1),...,Sm не находится в теле цикла, заголовок которого во множестве S1,...,Sk
1.3. всякий оператор goto из множества S1,...,Sk (или S(k+1), ..., Sm) указывает на метку оператора из этого же множества.
2) не существует такой дуги графа информационных связей (v1,v2), что v1 принадлежит Si, k+1=<i=<m, v2 принадлежит Sj, 1=<j=<k.
Результирующий фрагмент программы должен быть в операторных скобках. Это важно для того случая, если бы исходный цикл был телом некоторого другого объемлющего цикла или под действием условного оператора.
Теорема 48 . Если условия применения выполнены, то разбиение циклов является эквивалентным преобразованием.
Доказательство. Обозначим для краткости LOOPBODY1 фрагмент программы из операторов S1,...,Sk и LOOPBODY2 - S(k+1), ..., Sm. Тогда разбиение цикла состоит в замене цикла
DO 99 I
LOOPBODY1(I)
LOOPBODY2(I)
99 Continue
на фрагмент программы
DO 77 I
LOOPBODY1(I)
77 Continue
DO 99 I
LOOPBODY2(I)
99 Continue
Пусть счетчик цикла I пробегает последовательность итераций I1,I2,...,In. Раскрутка исходного цикла имеет следующий вид
LOOPBODY1(I1)
LOOPBODY2(I1)
LOOPBODY1(I2)
LOOPBODY2(I2)
.......................... (30)
LOOPBODY1(In)
LOOPBODY2(In)
Результирующий фрагмент после раскрутки циклов примет следующий вид
LOOPBODY1(I1)
LOOPBODY1(I2)
...........................
LOOPBODY1(In)
LOOPBODY2(I1) (31)
LOOPBODY2(I2)
............................
LOOPBODY2(In)
Поскольку не существует дуг информационной зависимости из LOOPBODY2(Ik) в LOOPBODY1(Im) при k>=m, с помощью эквивалентных перестановок операторов можно из (30) получить (31) (перестановки операторов описаны в [20, с.12]).
Пример 95. Цикл
DO 99 I = 1, 100
X(I) = A(I+1)
K(I) = X(I+1)
99 CONTINUE
НЕ эквивалентен следующему фрагменту программы
DO 99 I = 1, 100
X(I) = A(I+1)
99 CONTINUE
DO 88 I = 1, 100
K(I) = X(I+1)
88 CONTINUE
Конец примера.
Слияние циклов
Данное преобразование заменяет фрагмент программы, состоящий из двух подряд написанных циклов с одинаковыми заголовками, одним циклом (loop fusion) [20, с. 36].
Это преобразование является обратным к разбиению циклов.
Условие выполнения: если после выполнения преобразования получается цикл, который можно, сохраняя равносильность, разрезать на две части, получив исходный фрагмент, то данное преобразование равносильно.
Кроме того, есть ограничение, связанное с синтаксической корректностью. В исходной программе не должно быть переходов на заголовок второго цикла, поскольку в этом случае в результирующей программе этот переход исчезнет или возникнет недопустимый синтаксисом переход извне во внутрь цикла. И еще, при взятии в операторные скобки обоих исходных циклов должна получаться программа эквивалентная исходной. Это условие может не выполняться, если первый из исходных циклов является телом некоторого третьего объемлющего цикла, а второй исходный цикл – не является.
Пример 96. Фрагмент программы
DO 99 I = 1, 100
IF Y(I)<0 goto 99
K(I) = X(I-1)
99 CONTINUE
DO 88 I = 1, 100
X(I) = A(I+1)
88 CONTINUE
эквивалентен следующему
DO 88 I = 1, 100
IF Y(I)<0 goto 99
K(I) = X(I-1)
99 CONTINUE
X(I) = A(I+1)
88 CONTINUE
Конец примера.
Дата: 2018-12-21, просмотров: 552.