|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
|
|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Распараллеливание рекуррентных циклов
Всякое вычисление членов рекуррентной последовательности
xn = f( xn-1, xn-2, …, xn-k ) ( 35 )
может быть описано с помощью программного цикла
DO 99 I = k+1, N 99 X(I) = f(X(I-1), X(I-2), …, X(I-k))
Если функция f линейна, то и рекуррентную последовательность и рекуррентный цикл называют линейными. Итак, линейный рекуррентный цикл имеет вид
DO 99 I = k+1, N X(I) = A1(I)*X(I-1)+A2(I)*X(I-2)+…+Ak(I)*X(I-k) +A0(I)
Выполнение этого цикла равносильно решению системы линейных уравнений с ленточной треугольной матрицей
В формуле ( 35 ) если xn является вектором, а f – линейное отображение, то в теле соответствующего программного цикла будет несколько операторов присваивания. В следующем примере по линейной рекуррентной формуле вычисляется пара массивов.
Пример 129.
DO 99 I = 2, N X(I) = A(I)*X(I-1)+B(I)*Y(I-1)+C(I) Y(I) = D(I)*X(I-1)+E(I)*Y(I-1)+F(I) ( 36 ) 99 CONTINUE
Выполнение такого цикла равносильно решению СЛАУ с блочной двухдиагональной матрицей.
Конец примера.
Пример 130. Выполнение следующего цикла равносильно решению СЛАУ с треугольной ленточной матрицей (вообще говоря, не блочной двухдиагональной).
DO 99 I = 2, N X(I) = A0(I)*X(I)+A1(I)*X(I-1)+…+Ak(I)*X(I-k)+ +B0(I)*Y(I)+B1(I)*Y(I-1)+ +Bk(I)*Y(I-k)+C(I) Y(I) = D0(I)*X(I)+D1(I)*X(I-1)+…+Dk(I)*X(I-k)+ +E0(I)*Y(I)+E1(I)*Y(I-1)+ +Ek(I)*Y(I-k)+F(I) 99 CONTINUE Конец примера.
Аналогичное утверждение можно сформулировать и для циклов с линейной рекуррентностью с большим количеством операторов присваивания.
Пример 131. В следующем цикле рекуррентно вычисляются не массивы, а простые переменные.
DO 99 I = 1, N X = A(I)*X+B(I)*Y+C(I) Y = D(I)*X+E(I)*Y+F(I) 99 CONTINUE
Такие переменные могут быть заменены массивами, после чего этот цикл становиться равносильным следующему фрагменту программы
XX(1) = X YY(1) = Y DO 99 I = 2, N+1 X(I) = A(I)*X(I-1)+B(I)*Y(I-1)+C(I) Y(I) = D(I)*X(I)+E(I)*Y(I-1)+F(I) 99 CONTINUE X = XX(N+1) Y = YY(N+1)
Если в теле цикла этого фрагмента выполнить подстановку вперед: во втором операторе присваивания вместо X(I) подставить правую часть первого оператора присваивания этого цикла – то цикл примет вид ( 36 ). Конец примера.
Циклы с нелинейной рекуррентностью Пусть 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 |
Последнее изменение этой страницы: 2019-05-17; Просмотров: 445; Нарушение авторского права страницы
