Пусть f – нелинейная обратимая (относительно суперпозиции) функция одного переменного. Тогда в следующем цикле рекуррентная зависимость не линейная.
DO 99 I = k+1, N (37)
99 X(I) = f-1(A1(I)*f(X(I-1))+A2(I)*f(X(I-2))+…+Ak(I)*f(X(I-k)) +A0(I))
Несложно заметить, что элементы массива Y(I) = f(X(I)), I = 1,2,…N образуют последовательность с линейной рекуррентной зависимостью. Такая замена переменных сводит распараллеливание этого цикла к предыдущему случаю.
DO 88 I = 1, k
88 Y(I) = f(X(I))
DO 99 I = k+1, N
99 Y(I) = A1(I)*Y(I-1)+A2(I)*Y(I-2)+…+Ak(I)*Y(I-k) +A0(I)
DO 77 I = k+1, N
77 X(I) = f-1(Y(I))
Пример 132. Рекуррентный цикл
DO 99 I = 3, N
99 X(I) =exp( A1(I)*ln(X(I-1))+A2(I)*ln(X(I-2))+A0(I) )
равносилен следующему фрагменту программы
Y(1) = ln(X(1))
Y(2) = ln(X(2))
DO 99 I = 3, N
99 Y(I) = A1(I)*Y(I-1)+A2(I)*Y(I-2)+…+Ak(I)*Y(I-k) +A0(I)
DO 77 I = 3, N
77 X(I) = exp(Y(I))
Пример 133. Рекуррентный цикл
DO 99 I = 3, N
99 X(I) = 
равносилен следующему фрагменту программы
Y(1) = X(1)2
Y(2) = X(2)2
DO 99 I = 3, N
99 Y(I) = A(I)*Y(I-1)+B(I)*Y(I-2)+1/I
DO 77 I = 3, N
77 X(I) = 
Рекуррентные циклы, не имеющие эффективного распараллелливания.
В формулах (35) вместо xn-1 одновременно для всех n можно подставить
xn-1 = f( xn-2 , xn-3 ,…, xn-k-1 ) . (38 ) (10)
Получиться
xn = f( f( xn-2 , xn-3 ,…, xn-k-1 ) , xn-2 ,…, xn-k ) (39 ) (11)
Теперь, используя обе формулы (11) и (10), можно одновременно вычислять xn и xn-1 . Казалось бы, этим самым, процесс вычисления рекуррентной последовательности ускоряется вдвое. Но такое ускорение возможно лишь тогда, когда время вычисления функции (11) такое же, как и (10). Непосредственное вычисление (11) ровно вдвое дольше вычисления (10) и сводит на нет подстановку. Если в (11) можно провести преобразования и получить в правой части функцию вида (10), как это происходит для линейных рекуррентных зависимостей, то желаемое ускорение было бы достигнуто, исключая затраты на преобразования (11) к виду (10). Это возможно для линейных и описанных выше дробно-линейных функций, а также для циклов вида (37).
Следующий рекуррентный цикл нельзя эффективно распараллелить, (если функцию cos(x) не заменить более удобной интерполирующей функцией)
DO 99 I = 2, N
99 X(I) = cos(X(I-1))
В работе [99] исследуется возможность распараллеливания рекуррентных циклов, содержащих условный оператор.
ТЕСТЫ ПО ТЕОРИИ ПРЕОБРАЗОВАНИЯ ПРОГРАММ
Подстановка
Пример 134. Равносильны ли фрагменты?
10 X(K) = A(I+1)
20 B = X(K)
10 X(K) = A(I+1)
20 B = A(I+1)
Пример 135. Равносильны ли фрагменты?
10 X(K) = A(I+1)
15 A(I+1) = 1
20 B = X(K)
10 X(K) = A(I+1)
15 A(I+1) = 1
20 B = A(I+1)
Пример 136. Равносильны ли фрагменты?
10 X(K) = A(I+1) + B
20 B = X(K)
10 X(K) = A(I+1)
20 B = A(I+1) + B
Пример 137. Равносильны ли фрагменты?
10 X(K) = A(I+1) + B
20 X(K) = X(K)
10 X(K) = A(I+1)
20 X(K) = A(I+1) + B
Пример 138. Равносильны ли фрагменты?
goto 77
..................
T = 5
77 A = T+E
B = 2*T
goto 77 THEN
.....................
T = 5
77 A = 5+E
B = 2*5
Пример 139.
goto Sm
..................
S1 X(K) = A+B
X(K) = 1
A = T+E
Sm B = 0*X(K) +C
равносилен ?
goto Sm
..................
S1 X(K) = A+B
X(K) = 1
A = T+E
Sm B = 0*(A+B) +C
Пример 140.
10 IF (C<0)
15 X(K) = A(I+1)
20 B = X(K)
равносилен ?
10 IF (C<0)
15 X(K) = A(I+1)
20 B = A(I+1)
Пример 141. Фрагмент программы
10 X(K) = A(I+1)
15 X(K) = 1
20 B = X(K)
равносилен ?
10 X(K) = A(I+1)
15 X(K) = 1
20 B = A(I+1)
Пример 142. Фрагмент программы
10 X(K) = A(I+1)
15 K = 1
20 B = X(K)
равносилен ?
10 X(K) = A(I+1)
15 K = 1
20 B = A(I+1)
Пример 143. Фрагмент программы
X(K) = A(I+1)
I = 1
B = X(K)
равносилен ?
X(K) = A(I+1)
I = 1
B = A(I+1)
Перестановка
Пример 144. Фрагмент программы
10 X(K) = A(I+1)
15 A(I+1) = 1
равносилен ?
10 A(I+1) = 1
15 X(K) = A(I+1)
Пример 145. Фрагмент программы
10 X(K) = A(I+1)
15 A(I) = 1
равносилен ?
10 A(I) = 1
15 X(K) = A(I+1)
Пример 146. Фрагмент программы
10 X(K) = A(I+1)
15 K = 1
равносилен ?
10 K = 1
15 X(K) = A(I+1)
Пример 147. Фрагмент программы
10 IF (C<0)
15 L = A(I+1)
20 B = X(K)
равносилен ?
10 IF (C<0)
20 B = X(K)
15 L = A(I+1)
Пример 148. Фрагмент программы
IF (C<0)
L = A(I+1)
B = X(K)
Равносилен?
B = X(K)
IF (C<0)
L = A(I+1)
Пример 149. Фрагмент программы
DO 10 K=1,N
Y(K) = C
10 X(K) = A(I+1)
C = 1
равносилен ?
DO 10 K=1,N
Y(K) = C
C = 1
10 X(K) = A(I+1)
Пример 150. Фрагмент программы
K = X+1
goto 99
K = I-1
99 A = K
равносилен ?
K = X+1
K = I-1
goto 99
99 A = K
Пример 151. Фрагмент программы
С = 1
goto 99
……………..
88 С = 2
99 A = K
равносилен ?
С = 1
goto 99
…………………
99 A = K
88 С = 2
Пример 152. Фрагмент программы
write(F,10)
write(F,20)
равносилен ?
write(F,20)
write(F,10)
Пример 153. Фрагмент программы
write(F1,10)
write(F2,20)
равносилен ?
write(F2,20)
write(F1,10)
Пример 154. Фрагмент программы
DO 99 I = 1, N
X(I) = A(I+1)
K(I) = X(I-1)
99 CONTINUE
равносилен ?
DO 99 I = 1, N
K(I) = X(I-1)
X(I) = A(I+1)
99 CONTINUE
Пример 155. Фрагмент программы
DO 99 I = 1, N
X(I) = A(I+1)+B(I)
K(I) = X(I-1)+B(I)
99 CONTINUE
равносилен ?
DO 77 I = 1, N
K(I) = X(I-1)+B(I)
77 CONTINUE
DO 88 I = 1, N
X(I) = A(I+1)+B(I)
88 CONTINUE
Пример 156. Данный фрагмент программы
K = I+1
B = X+3
A = 5*Y
L = 3*J
равносилен ?
K = I+1
A = 5*Y
B = X+3
L = 3*J
Пример 157. Фрагмент программы
10 X(K) = A(I+1)
15 I = 1
равносилен?
10 I = 1
15 X(K) = A(I+1)
Пример 158. Фрагмент программы
DO 10 K=1,N
C = 1
Y(K) = C
10 CONTINUE
равносилен следующему?
DO 10 K=1,N
Y(K) = C
C = 1
10 CONTINUE
Пример 159 Фрагмент программы
DO 10 K=1,N
C(K) = 1
Y(K) = C(K)
10 CONTINUE
равносилен следующему ?
DO 10 K=1,N
Y(K) = C(K)
C(K) = 1
10 CONTINUE
Пример 160. Фрагмент программы
DO 10 K=1,N
C(K) = 1
Y(K) = C(K+1)
10 CONTINUE
равносилен следующему ?
DO 10 K=1,N
Y(K) = C(K+1)
C(K) = 1
10 CONTINUE
Пример 161. Фрагмент программы
X = I+1
K = I-1
равносилен следующему ?
K = I-1
X = I+1
Пример 162. Фрагмент программы
K = X+1
K = I-1
равносилен следующему ?
K = I-1
K = X+1
Пример 163. Фрагмент программы
T = A+B
X = T+C
Y = T-C
write(Y)
равносилен следующему ?
T = A+B
Y = T-C
write(Y)
Пример 164. Фрагмент программы
DO 99 I = 1, N
IF (X > N) goto 88
T = I*A
X = T+C
Y = T-C
99 write(Y)
равносилен следующему ?
DO 99 I = 1, N
IF (X > N) goto 88
T = I*A
Y = T-C
99 write(Y)
Пример 165. Фрагмент программы
IF (X > N)
D = T+C
T = I*A
Y = T-C
99 write(Y)
равносилен следующему ?
IF (X > N)
T = I*A
Y = T-C
99 write(Y)
Вынос выражений
Пример 166. Фрагмент программы
X = A+B+C
Y = A+B-C
равносилен следующему ?
T = A+B
X = T+C
Y = T-C
Пример 167. Фрагмент программы
X = A+B+C
A = 1
Y = A+B-C
равносилен следующему
T = A+B
X = T+C
A = 1
Y = T-C
Пример 168. Фрагмент программы
X = A+I+1
Y = A-I-1
равносилен следующему ?
T = I+1
X = A+T
Y = A-T
Пример 169. Фрагмент программы (Алгоритм Флойда построения матрицы кратчайших расстояний графа)
DO 77 K = 1, N
DO 77 J = 1, N
DO 77 I = 1, N
IF ( A(I,J) > A(I,K)+A(K,J) )
A(I,J) = A(I,K)+A(K,J)
77 CONTINUE
равносилен следующему ?
DO 77 K = 1, N
DO 77 J = 1, N
DO 77 I = 1, N
T = A(I,K)+A(K,J)
IF ( A(I,J) > T )
A(I,J) = T
77 CONTINUE
Пример 170. Фрагмент программы
IF ( X > 0 ) THEN
A = C+D+E
B = 2*(C+D)
равносилен следующему ?
T = C+D
IF ( X > 0 ) THEN
A = T+E
B = 2*T
Пример 171. Фрагмент программы
IF ( X > 0 ) THEN
A = C+D+E
B = 2*(C+D)
равносилен следующему ?
IF ( X > 0 ) THEN
T = C+D
A = T+E
B = 2*T
Переименование переменных
Пример 172. Линейный участок программы
A = A+C
A = A+B
C = 3*A
A = A+A+C
write(A)
эквивалентен следующему?
A = A+C
AA = A+B
C = 3*AA
A = AA+AA
write(A)
Пример 173. Линейный участок программы
A = A+C
A = A+B
777 C = 3*A
A = A+A+C
write(A)
эквивалентен следующему?
A = A+C
AA = A+B
777 C = 3*AA
A = AA+AA
write(A)
Пример 174. Фрагмент программы
A = B+C
IF K>0
A = A+B
ENDIF
C = 3*A
эквивалентен следующему фрагменту?
A = B+C
IF K>0
AA = A+B
ENDIF
C = 3*AA
Пример 175. Цикл
DO 99 I = 1, 100
X(I) = A(I+1)+X(I)
K(I) = X(I+1)+X(I)
IF K(I)>0 GOTO 100
X(I) = B(I)*X(I)
99 CONTINUE
преобразуется к циклу?
DO 99 I = 1, 100
XX(I) = A(I+1)+X(I)
K(I) = X(I+1)+XX(I)
IF K(I)>0 GOTO 100
X(I) = B(I)*XX(I)
99 CONTINUE
Пример 176. Цикл
DO 99 I = 1, 100
X(I) = A(I+1)+X(I)
K(I) = X(I+1)+X(I)
X(I) = B(I)*K(I)
99 CONTINUE
преобразуется к циклу?
DO 99 I = 1, 100
XX(I) = A(I+1)+X(I)
K(I) = X(I+1)+XX(I)
X(I) = B(I)*K(I)
99 CONTINUE
Пример 177. Цикл
DO 99 I = 1, 100
X(I) = A(I+1)+X(I-1)
K(I) = X(I+1)+X(I)
X(I) = B(I)*K(I)
99 CONTINUE
преобразуется к фрагменту программы?
DO 99 I = 1, 100
XX(I) = A(I+1)+X(I-1)
K(I) = X(I+1)+XX(I)
X(I) = B(I)*K(I)
99 CONTINUE
Пример 178. Цикл
DO 99 I = 5, 100
X(I-1) = A(I+1)+X(I-1)
K(I) = X(I-1)+X(I-3)
X(I) = B(I)*K(I)
99 CONTINUE
преобразуется к фрагменту программы?
XX(2)=X(2)
XX(3)=X(3)
DO 99 I = 5, 100
XX(I-1) = A(I+1)+X(I-1)
K(I) = XX(I-1)+XX(I-3)
X(I) = B(I)*K(I)
100 CONTINUE
Пример 179. Цикл
DO 99 I = 5, 100
X(I) = B(I)*K(I)
K(I) = X(I-1)+X(I-3)
X(I-1) = A(I+1)+X(I-1)
99 CONTINUE
эквивалентен фрагменту программы?
XX(2)=X(2)
XX(3)=X(3)
DO 99 I = 5, 100
X(I) = B(I)*K(I)
K(I) = X(I-1)+XX(I-3)
XX(I-1) = A(I+1)+X(I-1)
99 CONTINUE
Пример 180. Цикл
DO 99 I = 5, 100
X(I) = B(I)*K(I)
K(I) = X(I-1)+X(I-3)
X(I-1) = A(I+1)+X(I-1)
99 CONTINUE
преобразуется к эквивалентному фрагменту программы
XX(4)=X(4)
DO 99 I = 5, 100
XX(I) = B(I)*K(I)
K(I) = XX(I-1)+X(I-3)
X(I-1) = A(I+1)+XX(I-1)
99 CONTINUE
X(100) = XX(100)
Канонизация циклов
Пример 181. Для цикла
DO 99 I = 5,100
99 X = A(I)+X
канонический вид будет?
Пример 182. Для цикла
DO 99 I = 5,100,10
99 X = A(I)+X
канонический вид будет следующий?
Пример 183. Для цикла
DO 99 I = K-1,N,2
if (A(I)<X) goto 99
K = B+X
99 X = A(I)+X
канонический вид будет?
Развертка цикла.
Пример 184. Цикл
DO 99 I = 1, 100
X(I) = A(I+1)
K(I) = X(I-1)
99 CONTINUE
эквивалентен?
DO 99 I = 1, 100, 2
X(I) = A(I+1)
K(I) = X(I-1)
X(I+1) = A(I+2)
K(I+1) = X(I)
99 CONTINUE
Пример 185. Цикл
DO 99 I = 1, 100
99 X(I) = A(I+1)
эквивалентен?
DO 99 I = 1, 100, 3
X(I) = A(I+1)
X(I+1) = A(I+2)
99 X(I+2) = A(I+3)
X(100) = A(101)
Пример 186. Цикл
DO 99 I = 1, N
99 X(I) = A(I+1)+K(I)-X(I-1)
эквивалентен?
DO 99 I = 1, N, 2
X(I) = A(I+1)+K(I)-X(I-1)
99 X(I) = A(I+1)+K(I)-X(I-1)
Пример 187. Цикл
DO 99 I = 1, 100
A(I) = B(I)*C(I)
99 X(I) = A(I+1)+K(I)-X(I-1)
заменять циклом?
DO 99 I = 1, 100, 2
A(I) = B(I)*C(I)
99 X(I) = A(I+1)+K(I)-X(I-1)
A(I+1) = B(I+1)*C(I+1)
99 X(I+1) = A(I+2)+K(I+1)-X(I)
Пример 188. Цикл
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)
Пример 189. Цикл
DO 99 I = 1, 100
IF A(I)<0 THEN GOTO 99
B(I) = K(I)*X(I)
99 X(I) = A(I+1)+K(I)-X(I-1)
эквивалентен следующему ?
DO 99 J = 1, 100, 2
IF A(I)<0 THEN GOTO 99
B(I) = K(I)*X(I)
X(I) = A(I+1)+K(I)-X(I-1)
IF A(I+1)<0 THEN GOTO 99
B(I+1) = K(I+1)*X(I+1)
99 X(I+1) = A(I+2)+K(I+1)-X(I)
Пример 190. Цикл
DO 99 I = 1, 100
IF A(I)<0 THEN GOTO 99
B(I) = K(I)*X(I)
99 X(I) = A(I+1)+K(I)-X(I-1)
эквивалентен следующему ?
DO 99 J = 1, 100, 2
IF A(I)<0 THEN GOTO 77
B(I) = K(I)*X(I)
77 X(I) = A(I+1)+K(I)-X(I-1)
IF A(I+1)<0 THEN GOTO 99
B(I+1) = K(I+1)*X(I+1)
99 X(I+1) = A(I+2)+K(I+1)-X(I)
Пример 191. Цикл
DO 99 I = 1, 100
IF A(I)<0 THEN GOTO 77
B(I) = K(I)*X(I)
99 X(I) = A(I+1)+K(I)-X(I-1)
эквивалентен следующему ?
DO 99 J = 1, 100, 2
IF A(I)<0 THEN GOTO 77
B(I) = K(I)*X(I)
X(I) = A(I+1)+K(I)-X(I-1)
IF A(I+1)<0 THEN GOTO 77
B(I+1) = K(I+1)*X(I+1)
99 X(I+1) = A(I+2)+K(I+1)-X(I)
Пример 192. Цикл
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)
Раскрутка цикла.
Пример 193. Цикл
DO 99 I = 3, 5
99 X(I) = A(I+1)+K(I)-X(I-1)
корректно заменять следующим образом на фрагмент программы ?
99 X(3) = A(4)+K(3)-X(2)
99 X(4) = A(5)+K(4)-X(3)
99 X(5) = A(6)+K(5)-X(4)
Пример 194. Цикл
DO 99 I = 1, 2
DO 88 J = 1, 40
88 B(J) = K(I)*X(J)
99 X(I) = A(I+1)+B(I)-X(I-1)
эквивалентен следующему фрагменту ?
DO 88 J = 1, 40
88 B(J) = K(1)*X(J)
99 X(1) = A(2)+B(1)-X(0)
DO 88 J = 1, 40
88 B(J) = K(2)*X(J)
99 X(2) = A(3)+B(2)-X(1)
6.5.8 Разрыв итераций, гнездование цикла и подобные им преобразования
Пример 195. Замена цикла
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)=X(16*(I-1)+J-1)
Пример 196. Замена цикла
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)=X(8*(J-1)+I-1)
Пример 197. Замена цикла
DO 99 I=1,128
99 X(I)= 3*X(I-8)
на следующий фрагмент программы эквивалентна?
DO 99 I=1,8
DO 99 J=1,16
99 X(8*(J-1)+I)=X(8*(J-1)+I-8)
Пример 198. Замена цикла
K=1
DO 99 I=1,128
K=K+2
99 X(K)= 3*X(I-1)
на следующий фрагмент программы эквивалентна?
K=1
DO 99 I=1,8
DO 99 J=1,16
K=K+2
99 X(K)=X(8*(J-1)+I-1)
Расщепление цикла
Пример 199. Почему замена цикла
DO 99 I=1,100
99 X(I)=Y(I-1)
на фрагмент программы
DO 99 I=1,64
99 X(I)=Y(I-1)
DO 88 I=64,100
88 X(I)=Y(I-1)
равносильна?
Пример 200. Почему замена цикла
DO 99 I=1,100
99 X(I)=Y(I-1)
на фрагмент программы
DO 99 I=1,64
99 X(I)=Y(I-1)
DO 99 I=65,100
99 X(I)=Y(I-1)
равносильна?
6.5.10 Расщепление вершин (Введение временных массивов)
Пример 201.
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
Пример 202.
DO 111 J = 1, N
DO 111 I = 3, N
A(I) = B(I-2,I+J-2)+C(I)
B(I,J) = (A(I)+A(I+1))/2
111 CONTINUE
Данный цикл равносилен следующему?
DO 111 J = 1, N
DO 111 I = 3, N
ATEMP(I) = A(I+1)
BTEMP(I) = B(I,J)
A(I) = B(I-2,I+J-2)+C(I)
BTEMP(I) = (A(I)+ATEMP(I))/2
111 CONTINUE
Пример 203.
J = 1
DO 111 I = 3, N
J=J+1
A(I,J) = B(I-2,I+J-2)+C(I)
B(I,J) = (A(I,J)+A(I+1,J))/2
111 CONTINUE
Данный цикл равносилен следующему?
J = 1
DO 111 I = 3, N
ATEMP(I) = A(I+1,J)
BTEMP(I) = B(I,J)
J=J+1
A(I,J) = B(I-2,I+J-2)+C(I)
BTEMP(I) = (A(I,J)+ATEMP(I))/2
111 CONTINUE
Пример 204. Данный цикл
DO 111 I = 1, N
A = B(I)+C(I)
D(I) = A/2
111 CONTINUE
эквивалентен следующему ?
dimention AA[100]
DO 111 I = 1, N
AA(I) = B(I)+C(I)
D(I) = AA(I)/2
111 CONTINUE
Пример 205. Данный цикл
DO 111 I = 1, N
D(I) = A/2
A = B(I)+C(I)
111 CONTINUE
эквивалентен следующему?
dimention AA[100]
DO 111 I = 1, N
D(I) = AA(I)/2
AA(I) = B(I)+C(I)
111 CONTINUE
Пример 206. Данный цикл
DO 111 I = 1, N
D(I) = A/2
A = B(I)+C(I)
111 CONTINUE
эквивалентен следующему?
dimention AA[100]
AA(1)=A
DO 111 I = 1, N
D(I) = AA(I)/2
AA(I+1) = B(I)+C(I)
111 CONTINUE
Пример 207. Данный цикл
DO 111 J = 1, N
DO 111 I = 1, M
A(J) = B(I,J)+C(I)
D(I,J) = A(J)/2
111 CONTINUE
эквивалентен следующему?
dimention AA[100]
DO 111 J = 1, N
DO 111 I = 1, M
AA(I,J) = B(I,J)+C(I)
D(I,J) = AA(I,J)/2
111 CONTINUE
Разбиение цикла
Пример 208. Цикл
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
Пример 209. Цикл
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
Пример 210. Цикл
DO 99 I = 1, 100
X(I) = A(I+1)
K(I) = X(I+1)
99 CONTINUE
эквивалентен следующему фрагменту программы?
DO 99 I = 1, 100
K(I) = X(I+1)
99 CONTINUE
DO 88 I = 1, 100
X(I) = A(I+1)
88 CONTINUE
Пример 211. Цикл
DO 99 I = 1, 100
K(I) = X(I-1)
A(I) = B(I)
X(I) = A(I+1)+K(I)
Y(I) = K(I+1)
99 CONTINUE
эквивалентен следующему фрагменту программы?
DO 66 I = 1, 100
66 Y(I) = K(I+1)
DO 77 I = 1, 100
K(I) = X(I-1)
77 X(I) = A(I+1)+K(I)
DO 88 I = 1, 100
88 A(I) = B(I)
Пример 212.. Фрагмент программы
DO 88 I = 1, 100
X(I) = A(I+1)+A(I-1)
A(I)=X(I+1)*5
88 CONTINUE
эквивалентен следующему?
DO 88 I = 1, 100
TEMP(I) = A(I+1)
A(I)=X(I+1)*5
X(I) = TEMP(I)+A(I-1)
88 CONTINUE
Пример 213. Фрагмент программы
DO 99 I = 1, 100
IF Y(I)<0 goto 99
K(I) = X(I-1)
99 X(I) = A(I+1)
эквивалентен следующему?
DO 999 I = 1, 100
IF Y(I)<0 goto 99
K(I) = X(I-1)
999 CONTINUE
DO 88 I = 1, 100
99 X(I) = A(I+1)
88 CONTINUE
Пример 214. Фрагмент программы
DO 88 I = 1, 100
DO 99 J = 1, 50
K(I,J) = X(I-1)*B(J)
99 X(I) = A(I+1)
A(I)=C(I)*5
88 CONTINUE
эквивалентен следующему?
DO 88 I = 1, 100
DO 99 J = 1, 50
K(I,J) = X(I-1)*B(J)
88 CONTINUE
DO 77 I = 1, 100
99 X(I) = A(I+1)
A(I)=C(I)*5
77 CONTINUE
Пример 215. Фрагмент программы
DO 88 I = 1, 100
DO 99 J = 1, 50
K(I,J) = X(I-1)*B(J)
99 X(I) = A(I+1)
A(I)=C(I)*5
88 CONTINUE
эквивалентен следующему?
DO 99 I = 1, 100
DO 99 J = 1, 50
K(I,J) = X(I-1)*B(J)
99 X(I) = A(I+1)
DO 88 I = 1, 100
A(I)=C(I)*5
88 CONTINUE
Пример 216. Фрагмент программы
DO 88 I = 1, 100
DO 99 J = 1, 50
K(I,J) = X(I-1)*B(J)
99 X(I) = A(I+1)
A(I)=C(I)*5
88 CONTINUE
эквивалентен следующему?
DO 88 I = 1, 100
DO 44 J = 1, 50
44 K(I,J) = X(I-1)*B(J)
DO 55 J = 1, 50
55 X(I) = A(I+1)
A(I)=C(I)*5
88 CONTINUE
Пример 217. Фрагмент программы
DO 88 I = 1, 100
DO 99 J = 1, 50
K(I,J) = X(I+1)*B(J)
99 X(I) = A(I+1)
A(I)=C(I)*5
88 CONTINUE
эквивалентен следующему?
DO 88 I = 1, 100
DO 44 J = 1, 50
44 K(I,J) = X(I+1)*B(J)
DO 55 J = 1, 50
55 X(I) = A(I+1)
A(I)=C(I)*5
88 CONTINUE
Пример 218.. Фрагмент программы
DO 88 I = 1, 100
X(I) = A(I+1)+A(I-1)
A(I)=X(I+1)*5
88 CONTINUE
эквивалентен следующему?
DO 88 I = 1, 100
TEMP(I) = A(I+1)
A(I)=X(I+1)*5
X(I) = TEMP(I)+A(I-1)
88 CONTINUE
Пример 219.
DO 111 I = 1, N
A(I) = B(I)+ sin C(I+1)
C(I) = A(I+1)+B(I)
111 CONTINUE
эквивалентен следующему?
DO 111 I = 1, N
TEMP(I)=C(I+1)
111 C(I) = A(I+1)+B(I)
DO 222 I = 1, N
A(I) = B(I)+ sinTEMP(I)
222 CONTINUE
Пример 220..Цикл
DO 99 I = 1, N
99 X(I) = C(I)*exp(D(I)*X(I-1)+E(I)) + A(I)*B(I)
можно заменить фрагментом программы ?
DO 88 I = 1, N
88 T(I) = A(I)*B(I)
DO 99 I = 1, N
99 X(I) = C(I)*exp(D(I)*X(I-1)+E(I)) + T(I)
Пример 221. Цикл
DO 111 I = 1, N
A(I) = B(I)+ C
C = A(I+1)+B(I)
111 CONTINUE
эквивалентен следующему фрагменту программы?
CC(1)=C
DO 222 I = 1, N
CC(I+1) = A(I+1)+B(I)
222 CONTINUE
DO 111 I = 1, N
A(I) = B(I)+ CC(I)
111 CONTINUE
C = CC(N)
Пример 222. В следующем гнезде циклов
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
эквивалентен?
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
Пример 223.
DO 111 I = 1, N
A(I) = B(I)+ C(I)
C(I+1) = A(I)+B(I)
111 CONTINUE
Эквивалентен?
A(1) = B(1)+ C(1)
C(2) = A(1)+B(1)
DO 222 I = 2, N
A(I) = B(I)+ A(I-1)+B(I-1)
222 CONTINUE
DO 333 I = 2, N
C(I+1) = A(I)+B(I)
333 CONTINUE
Пример 224. Цикл
DO 111 I = 1, N
A(I) = B(I)+ C(I)
B(I) = 5*A(I)
C(I+1) = A(I)+B(I)
D(I+1) = A(I)*D(I)+C(I+1)
111 CONTINUE
эквивалентен следующему фрагменту программы?
A(1) = B(1)+ C(1)
B(1) = 5*A(1)
C(2) = A(1)+B(1)
D(2) = A(1)*D(1)+C(2)
DO 222 I = 2, N
A(I) = B(I)+ A(I-1)+B(I-1)
B(I) = 5*A(I)
222 CONTINUE
DO 333 I = 2, N
C(I+1) = A(I)+B(I)
D(I+1) = A(I)*D(I)+C(I+1)
333 CONTINUE
Пример 225. Цикл
DO 111 I = 1, N
A(I) = B(I)+ C+D(I-1)+D(I+1)
D(I) = 2*A(I)
C = A(I+1)+B(I)
111 CONTINUE
эквивалентен следующему фрагменту программы?
CC(1)=C
DO 444 I = 1, N
CC(I+1) = A(I+1)+B(I)
444 CONTINUE
DO 333 I = 1, N
TEMP(I) = D(I+1)
333 CONTINUE
DO 222 I = 1, N
D(I) = 2*(B(I)+ CC(I)+D(I-1))
222 CONTINUE
DO 111 I = 1, N
A(I) = B(I)+ CC(I) + D(I-1)+TEMP(I)
111 CONTINUE
C = CC(N)
Пример 226. Фрагмент программы
DO 88 I = 1, 100
DO 99 J = 1, 50
K(I,J) = X(I+1)*B(J+1)
99 B(J) = A(I+1)
88 CONTINUE
эквивалентен следующему?
DO 66 I = 1, 100
DO 66 J = 1, 50
77 K(I,J) = X(I+1)*B(J+1)
66 CONTINUE
DO 55 I = 1, 100
DO 55 J = 1, 50
99 B(J) = A(I+1)
55 CONTINUE
Пример 227. Фрагмент программы
DO 88 I = 1, 100
IF A(I)>1 THEN GOTO 88
K(I) = X(I+1)*B(I+1)
B(I) = A(I)
88 CONTINUE
эквивалентен следующему?
DO 66 I = 1, 100
IF A(I)>1 THEN GOTO 66
K(I) = X(I+1)*B(I+1)
66 CONTINUE
DO 77 I = 1, 100
IF A(I)>1 THEN GOTO 77
B(I) = A(I)
77 CONTINUE
Пример 228. Фрагмент программы
DO 88 I = 1, 100
IF A(I)>1 THEN GOTO 88
A(I) = X(I+1)*B(I+1)
B(I) = A(I)
88 CONTINUE
эквивалентен следующему?
DO 66 I = 1, 100
IF A(I)>1 THEN GOTO 88
A(I) = X(I+1)*B(I+1)
66 CONTINUE
DO 77 I = 1, 100
IF A(I)>1 THEN GOTO 88
B(I) = A(I)
77 CONTINUE
Слияние циклов
Пример 229. Фрагмент программы
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 99 I = 1, 100
IF Y(I)<0 goto 99
X(I) = A(I+1)
K(I) = X(I-1)
99 CONTINUE
Пример 230. Фрагмент программы
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
Пример 231. Фрагмент программы
IF Y<0 goto 77
DO 99 I = 1, 100
K(I) = X(I-1)
99 CONTINUE
77 DO 88 I = 1, 100
Z(I) = A(I+1)
88 CONTINUE
эквивалентен следующему циклу?
IF Y<0 goto 77
DO 99 I = 1, 100
K(I) = X(I-1)
Z(I) = A(I+1)
99 CONTINUE
Пример 232. Фрагмент программы
IF (Y<0)
DO 99 I = 1, 100
K(I) = X(I-1)
99 CONTINUE
DO 88 I = 1, 100
Z(I) = A(I+1)
88 CONTINUE
эквивалентен следующему циклу?
IF Y<0
DO 99 I = 1, 100
K(I) = X(I-1)
Z(I) = A(I+1)
99 CONTINUE
Пример 233. Фрагмент программы из двух циклов
DO 99 I = 1, 100
A(I) = B(I)+C(I)
99 CONTINUE
DO 88 I = 1, 100
D(I) = A(I+1)
88 CONTINUE
эквивалентен следующему циклу?
DO 99 I = 1, 100
A(I) = B(I)+C(I)
D(I) = A(I+1)
99 CONTINUE
Вынос оператора из цикла
Пример 234. Цикл
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
Пример 235. Цикл
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
Пример 236. Цикл
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
Пример 237. Цикл
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
Пример 238. Цикл
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
Пример 239. Цикл
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
Пример 240. Цикл
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
Пример 241. Цикл
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
Пример 242. Цикл
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
Пример 243. Цикл
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
Пример 244. Цикл
DO 99 I = 1,N
A(I) = B(I)+Y
X = A(I)
99 CONTINUE
эквивалентен следующему фрагменту программы?
DO 99 I = 1,N
A(I) = B(I)+Y
99 CONTINUE
X = A(N)
Пример 245. Цикл
DO 99 I = 1,N
A = B(I)+A
X = A
99 CONTINUE
эквивалентен следующему фрагменту программы
DO 99 I = 1,N
A = B(I)+A
99 CONTINUE
X = A
Инверсия цикла.
Пример 246. может быть инвертирован?
DO 99 j = 1, N
99 H(j) = A(j)* H(j+1)
Пример 247. может быть инвертирован?
DO 99 j = 1, N
99 H(j) = A(j)* H(j)
Пример 248. может быть инвертирован. ?
DO 99 j = 1, N
99 H(j) = A(j)* H(j-1)
Пример 249. этот цикл может быть инвертирован?
DO 99 j = 1, N
99 H = A(j)* H +B(j)/ C(j)*H+D(j)
Пример 250.
DO 111 I = 1, N
A(I) = B(I)+C(I)
D(I) = A(I+1)/2.
111 CONTINUE
Можно распараллелить?
DO ALL 111 I = 1, N
A(I) = B(I)+C(I)
D(I) = A(I+1)/2.
111 CONTINUE
В следующих примерах будем предполагать, что архитектура позволяет одновременно выполнять одну операцию «+» и одну «*».
Пример 251. Как оптимально сгруппировать операторы
DO 99 I = 1, N
X(I) = A(I)+B(I)
A(I) = C(I)+D(I).
Y(I) = X(I)*Z(I)
V(I) = A(I)*U(I).
W(I) = C(I)*D(I)
B(I) = Z(I)+D(I).
99 CONTINUE
Пример 252. будем предполагать, что архитектура позволяет одновременно выполнять одну операцию «+» и одну «*». Как оптимизировать?
DO 99 I = 1, N
X(I) = A(I)+B(I)
Y(I) = X(I)*D(I).
99 CONTINUE
Пример 253. будем предполагать, что архитектура позволяет одновременно выполнять одну операцию «+» и одну «*». Как оптимизировать?
DO 77 I = 1, N
X(I) = A(I)+B(I)
Y(I) = С(I)-D(I).
77 CONTINUE
DO 99 I = 1, N
Z(I) = A(I)*B(I)
T(I) = X(I)*Z(I).
99 CONTINUE
Пример 254. Цикл
DO 99 I=1,N
DO 99 J=1,N
99 B(I,J)= (B(I,J)+B(J,I))/2
эквивалентен следующему фрагменту программы?
DO 77 I=1,N
DO 77 J=1,I-1
77 B(I,J)= (B(I,J)+B(J,I))/2
DO 88 I=1,N
DO 88 J=I,N
88 B(I,J)= (B(I,J)+B(J,I))/2
Пример 255 . Цикл
DO 99 I=1,N
DO 99 J=1,N
99 B(I,J)= (B(I,J)+B(J,I))/2
эквивалентен следующему фрагменту программы?
DO 88 I=1, N
DO 88 J=I, N
88 B(I,J)= (B(I,J)+B(J,I))/2
DO 77 I=1, N
DO 77 J=1, I-1
77 B(I,J)= (B(I,J)+B(J,I))/2
Пример 256 . Цикл
DO 99 J=1,N1
DO 99 I=1,N2
DO 99 K=1,N3
X(I)=A(I,J)-K
99 B(I,J,K)=X(I-1)
эквивалентен следующему фрагменту программы?
DO 99 J=1,N1
DO 99 K=1,N3
X(1)=A(1,J)-K
B(1,J,K)=X(0)
DO 99 I=2,N2
X(I)=A(I,J)-K
99 B(I,J)=A(I-1,J)-K
Переименование массивов
Пример 257 . Двойной цикл
Do 444 I = 3,100
Do 444 J = 3,100
X(I-1,J+2) = ...
... = X(I,J)+X(I-2,J)
X(I+1,J-1) =
444 CONTINUE
эквивалентен фрагменту программы?
DO 111 J = 3,100
111 XX(1,J) = X(1,J)
DO 112 J = 3,4
112 XX(2,J) = X(1,J)
Do 444 I = 3,100
Do 444 J = 3,100
XX(I-1,J+2) = ...
... = X(I,J)+XX(I-2,J)
X(I+1,J-1) =
444 CONTINUE
DO 555 J = 3,100
555 X(2,J+2) = XX(2,J+2)
DO 666 J = 3,100
666 X(3,J+2) = XX(3,J+2)
DO 777 I= 3,100
777 X(I-1,100) = XX(I-1,100)
DO 888 I = 3,100
888 X(I-1,101) = XX(I-1,101)
DO 999 I= 3,100
999 X(I-1,102) = XX(I-1,102)
Рекуррентные циклы
Пример 258. Рекуррентный цикл
DO 99 I = 3, N
99 X(I) =exp( A1(I)*ln(X(I-1))+A2(I)*ln(X(I-2))+A0(I) )
равносилен следующему фрагменту программы ?
Y(1) = ln(X(1))
Y(2) = ln(X(2))
DO 99 I = 3, N
99 Y(I) = A1(I)*Y(I-1)+A2(I)*Y(I-2)+ A0(I)
DO 77 I = 3, N
77 X(I) = exp(Y(I))
Пример 259. Рекуррентный цикл
DO 99 I = 3, N
99 X(I) =
равносилен следующему фрагменту программы ?
Y(1) = X(1)2
Y(2) = X(2)2
DO 99 I = 3, N
99 Y(I) = A(I)*Y(I-1)+B(I)*Y(I-2)+1/I
DO 77 I = 3, N
77 X(I) =
Дата: 2018-12-21, просмотров: 397.
