Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Повышение размерности массивов для разбиения циклов
Если в графе информационных связей есть контур, то ни перестановка операторов, ни введение временных переменных, как в предыдущем примере, не помогают, и какая-нибудь дуга будет вести «снизу-вверх». Некоторые контуры, образованные вхождениями переменной, не зависящей от счетчика цикла, можно разорвать заменой этой переменной новым массивом, зависящим от счетчика цикла. Следует отметить, что такое преобразование («расщепление скаляров») предполагает дополнительный расход памяти.
Пример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 Конец примера.
|
Последнее изменение этой страницы: 2019-05-17; Просмотров: 417; Нарушение авторского права страницы