Если в графе информационных связей есть контур, то ни перестановка операторов, ни введение временных переменных, как в предыдущем примере, не помогают, и какая-нибудь дуга будет вести «снизу-вверх». Некоторые контуры, образованные вхождениями переменной, не зависящей от счетчика цикла, можно разорвать заменой этой переменной новым массивом, зависящим от счетчика цикла. Следует отметить, что такое преобразование («расщепление скаляров») предполагает дополнительный расход памяти.
Пример 104. В следующем гнезде циклов
DO 111 J = 1, N
DO 111 I = 1, N
A(I,J) = B(I)+ C(J)
C(J) = A(I+1,J)+B(I)
111 CONTINUE
после повышения размерности массива C внутренний цикл может быть разрезан с перестановкой операторов
DO 111 J = 1, N
CC(1,J)=C(J)
DO 222 I = 1, N
CC(I+1,J) = A(I+1,J)+B(I)
222 CONTINUE
DO 333 I = 1, N
A(I,J) = B(I)+ CC(I,J)
333 CONTINUE
C(J) = CC(N+1,J)
111 CONTINUE
Конец примера.
Переименование переменных
Если в теле цикла есть два генератора одной и той же переменной, то они могут создавать в графе ложные дуги зависимости и дуги выходной зависимости [20, с. 29]. Чтобы от этого избавиться иногда возможно часть вхождений переменной, включая один из генераторов, переименовать. Этим самым тело цикла может быть приведено к виду с однократным присваиванием, что важно для конвейеризации. Условия переименования приводятся в [100] .
Пример 105 ([ 20, с. 73]). В графе информационных связей программного цикла
DO 99 I = 5, 999
A(I) = D(I)
E(I) = A(I-2)+D(I)*C(I)
A(I-3) = F(I)+G(I)
D(I) = A(I-4)
B(I+1) = D(I)
99 CONTINUE
есть контур, проходящий через все операторы тела цикла. Такой цикл непосредственно нельзя разбить на меньшие (даже после какой-либо перестановки операторов) или векторизовать. После переименования переменной получим следующий фрагмент программы
DO 99 I = 5, 999
AA(I) = D(I)
E(I) = AA(I-2)+D(I)*C(I)
A(I-3) = F(I)+G(I)
D(I) = A(I-4)
B(I+1) = D(I)
99 CONTINUE
A(997)=AA(997)
A(998)=AA(998)
A(999)=AA(999)
В полученном фрагменте граф информационных связей бесконтурный - результирующий цикл можно разбивать или векторизовать.
Конец примера.
Инверсия цикла
Суть инверсии в изменении порядка вычисления итераций цикла на противоположный.
Если все итерации цикла независимы, то инверсия цикла является эквивалентным преобразованием.
Пример 106. Данный цикл
DO 99 i = 1, N
99 X(i) =A(i) * B(i)
равносилен следующему
DO 99 i = 1, N
99 X(N+1-i) =A(N+1-i) * B(N+1-i)
Инверсия является равносильным преобразованием не только для независимых циклов.
Пусть # – ассоциативная операция с нейтральным элементом $ и пусть задан одномерный цикл вида
DO 99 i = 1, N
99 X =A(i) # X
Инверсия этого цикла состоит в замене этого одномерного цикла на следующий фрагмент программы
Y = $
DO 99 i = 1, N
99 Y = Y # A(N-i+1)
X = Y # X
Если операция # еще и коммутативна, то инверсия состоит в замене исходного цикла на следующий
DO 99 i = 1, N
99 X =A(N-i+1) # X
Примерами ассоциативной и коммутативной операции # могут служить сложение, умножение, конъюнкция, дизъюнкция, максимум и минимум (двух чисел). Некоммутативной, но ассоциативной операцией является, например, произведение матриц. По поводу ассоциативности операций над числами с плавающей запятой следует отдельно удостовериться в достаточной точности при округлениях.
Инверсия цикла меняет информационный граф программы и этим самым может привести к возможности распараллеливания изначально не распараллеливаемый фрагмент программы.
Пример 107. Решетчатый граф программы следующего нетесного гнезда циклов содержит путь, проходящий через все вершины этого графа. Это не позволяет одновременно вычислять никакие две итерации этого фрагмента программы.
DO 88 i = 1, N
DO 99 j = 1, i-1
99 H(N-i+1) = H(N+i-1) - A(N-i+1,N-i+j+1)* H(N-i+j+1)
88 H(N-i+1) = H(N+i-1)/A(N-i+1,N-i+1)
Если сделать инверсию вложенного цикла, то решетчатый граф программы измениться и его можно будет распараллеливать.
DO 88 i = 1, N
DO 99 j = 1, i-1
99 H(N-i+1) = H(N+i-1) - A(N-i+1,N-j+1)* H(N-j+1)
88 H(N-i+1) = H(N+i-1)/A(N-i+1,N-i+1)
Заметим, что программа данного примера представляет собой решение системы линейных алгебраических уравнений с треугольной матрицей.
Конец примера.
Пример 108. В данном цикле есть циклически порожденная антизависимость и он не может быть инвертирован.
DO 99 j = 1, N
99 H(j) = A(j)* H(j+1)
Пример 109. В данном цикле все итерации независимы и он может быть инвертирован. Циклически независимая зависимость не препятствует инверсии.
DO 99 j = 1, N
99 H(j) = A(j)* H(j)
Конец примера.
Пример 110. В данном цикле есть истинная информационная зависимость, и он не может быть инвертирован.
DO 99 j = 1, N
99 H(j) = A(j)* H(j-1)
Конец примера.
Пример 111. В данном цикле выполняется ассоциативная операция дробнолинейное преобразование, и этот цикл может быть инвертирован.
DO 99 j = 1, N
99 H = A(j)* H +B(j)/ C(j)*H+D(j)
Конец примера.
Вынос оператора из цикла
Данное преобразование заменяет цикл
DO 333 I = 1, N
S1
..........
S(k-1)
Sk
S(k+1)
..........
Sm
333 CONTINUE
на следующий фрагмент программы
Sk
DO 333 I = 1, N
S1
..........
S(k-1)
S(k+1)
..........
Sm
333 CONTINUE
Теорема 51 . Пусть тело исходного цикла состоит из трех фрагментов, каждый из которых имеет один вход и один выход.
DO 333 I = 1, N
FRAG1(i)
FRAG2(i)
FRAG3(i)
333 CONTINUE
Пусть в фрагменте FRAG2 все генераторы не зависят от счетчика цикла и предположим, что в этом фрагменте нет истинных циклически порожденных зависимостей. Тогда:
FRAG2(N)
DO 333 I = 1, N
FRAG1(i)
FRAG3(i)
333 CONTINUE
DO 333 I = 1, N
FRAG1(i)
FRAG3(i)
333 CONTINUE
FRAG2(N)
Доказательство. Заметим, что данное преобразование может быть сведено к двум: к разрезанию цикла, а, затем, к удалению заголовка. Рассмотрим, подробно первый случай, а второй может быть рассмотрен аналогично.
Поскольку нет дуг графа информационных связей ведущих в фрагмент FRAG2 из фрагментов FRAG1 и FRAG3 , то исходный цикл с помощью разрезания (и предварительной перестановки фрагментов) может быть преобразован к следующему равносильному фрагменту:
DO 222 I = 1, N
FRAG2(i)
222 CONTINUE
DO 333 I = 1, N
FRAG1(i)
FRAG3(i)
333 CONTINUE
Поскольку в фрагменте FRAG2 , который является телом цикла 222, все генераторы не зависят от счетчика цикла и в этом фрагменте нет истинных циклически порожденных зависимостей, заголовок цикла можно удалить, а вместо счетчика цикла подставить его последнее значение N. В результате получиться описанный в формулировке теоремы фрагмент.
Пример 112. Цикл
DO 99 I = 1, 100
X = A+1
K(I) = X
99 CONTINUE
эквивалентен следующему фрагменту программы
X = A+1
DO 99 I = 1, 100
K(I) = X
99 CONTINUE
Конец примера.
Пример 113. Цикл
DO 99 I = 1, 100
X = A+X
K(I) = X
99 CONTINUE
не эквивалентен следующему фрагменту программы
X = A+X
DO 99 I = 1, 100
K(I) = X
99 CONTINUE
Конец примера.
Пример 114. Цикл
DO 99 I = 1, 100
K = K+1
X(K) = B
99 CONTINUE
не эквивалентен следующему фрагменту программы
X(K) = B
DO 99 I = 1, 100
K = K+1
99 CONTINUE
Конец примера.
Пример 115. Цикл
DO 99 I = 1, 100
IF (A(I)<B(I)) goto 33
X(K) = 1
33 Y(I) = 0
99 CONTINUE
не эквивалентен следующему фрагменту программы
X(K) = 1
DO 99 I = 1, 100
IF (A(I)<B(I)) goto 33
33 Y(I) = 0
99 CONTINUE
Конец примера.
Пример 116. Цикл
DO 99 I = 1, 100
X = A+X
K = B(I)+7
99 CONTINUE
эквивалентен следующему фрагменту программы
DO 99 I = 1, 100
X = A+X
99 CONTINUE
K = B(100)+7
Конец примера.
Пример 117. Цикл
DO 99 I = 1, 100
X = A(I)+X
K = B(I)+X
99 CONTINUE
эквивалентен следующему фрагменту программы
DO 99 I = 1, 100
X = A(I)+X
99 CONTINUE
K = B(100)+X
Конец примера.
Пример 118. Цикл
DO 99 I = 1, 100
K = B(I)+X
X = A(I)+X
99 CONTINUE
не эквивалентен следующему фрагменту программы
DO 99 I = 1, 100
X = A(I)+X
99 CONTINUE
K = B(100)+X
Конец примера.
Пример 119. Цикл
DO 99 I = 1,N
K = B+X
X = A(I)+X
99 CONTINUE
не эквивалентен следующему фрагменту программы
K = B+X
DO 99 I = 1,N
X = A(I)+X
99 CONTINUE
поскольку существует дуга истинной зависимости от второго
оператора к первому.
Конец примера.
Пример 120. Цикл
DO 99 I = 1,N
K = B+X
X = A(I)
99 CONTINUE
не эквивалентен следующему фрагменту программы
DO 99 I = 1,N
X = A(I)+X
99 CONTINUE
K = B+X
поскольку существует дуга антизависимости от первого оператора ко второму.
Конец примера.
Пример 121. Цикл
DO 99 I = 1,N
K = B+X
X = С*4
T(I)= A(I)+X
99 CONTINUE
эквивалентен следующему фрагменту программы
K = B+X
X = С*4
DO 99 I = 1,N
T(I)= A(I)+X
99 CONTINUE
Конец примера.
Дата: 2018-12-21, просмотров: 512.