Циклы с нелинейной рекуррентностью
Поможем в ✍️ написании учебной работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Пусть 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, просмотров: 279.