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

Если в графе информационных связей есть контур, то ни перестановка операторов, ни введение временных переменных, как в предыдущем примере, не помогают, и какая-нибудь дуга будет вести «снизу-вверх». Некоторые контуры, образованные вхождениями переменной, не зависящей от счетчика цикла, можно разорвать заменой этой переменной новым массивом, зависящим от счетчика цикла. Следует отметить, что такое преобразование («расщепление скаляров») предполагает дополнительный расход памяти.

 

Пример 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 все генераторы не зависят от счетчика цикла и предположим, что в этом фрагменте нет истинных циклически порожденных зависимостей. Тогда:

  1. Если нет дуг графа информационных связей ведущих в фрагмент FRAG2 из фрагментов FRAG1 и FRAG3 , то исходный цикл равносилен следующему

 

FRAG2(N)

DO 333 I = 1, N

FRAG1(i)

FRAG3(i)

333 CONTINUE

 

  1. Если нет дуг графа информационных связей ведущих из фрагмента FRAG2 в фрагменты FRAG1 и FRAG3 , то исходный цикл равносилен следующему

 

DO 333 I = 1, N

FRAG1(i)

FRAG3(i)

333 CONTINUE

FRAG2(N)

 

Доказательство. Заметим, что данное преобразование может быть сведено к двум: к разрезанию цикла, а, затем, к удалению заголовка. Рассмотрим, подробно первый случай, а второй может быть рассмотрен аналогично.

Поскольку нет дуг графа информационных связей ведущих в фрагмент FRAG2 из фрагментов FRAG1 и FRAG3 , то исходный цикл с помощью разрезания (и предварительной перестановки фрагментов) может быть преобразован к следующему равносильному фрагменту:

 

DO 222 I = 1, N

FRAG2(i)

222 CONTINUE

DO 333 I = 1, N

FRAG1(i)

FRAG3(i)

333 CONTINUE

 

Поскольку в фрагменте FRAG2 , который является телом цикла 222, все генераторы не зависят от счетчика цикла и в этом фрагменте нет истинных циклически порожденных зависимостей, заголовок цикла можно удалить, а вместо счетчика цикла подставить его последнее значение N. В результате получиться описанный в формулировке теоремы фрагмент.

Пример 112.  Цикл

   DO 99 I = 1, 100

   X = A+1

   K(I) = X

 99 CONTINUE

эквивалентен следующему фрагменту программы

   X = A+1

    DO 99 I = 1, 100

    K(I) = X

99 CONTINUE

Конец примера.

 

Пример 113.  Цикл

    DO 99 I = 1, 100

   X = A+X

   K(I) = X

99 CONTINUE

не эквивалентен следующему фрагменту программы

   X = A+X

DO 99 I = 1, 100

  K(I) = X

 99 CONTINUE

Конец примера.

 

Пример 114. Цикл

   DO 99 I = 1, 100

   K = K+1

   X(K) = B

99 CONTINUE

не эквивалентен следующему фрагменту программы

   X(K) = B

  DO 99 I = 1, 100

  K = K+1

99 CONTINUE

Конец примера.

 

  Пример 115. Цикл

  DO 99 I = 1, 100

  IF (A(I)<B(I)) goto 33

  X(K) = 1

33 Y(I) = 0

99 CONTINUE

не эквивалентен следующему фрагменту программы

   X(K) = 1

DO 99 I = 1, 100

IF (A(I)<B(I)) goto 33

33 Y(I) = 0

99 CONTINUE

Конец примера.

 

Пример 116. Цикл

   DO 99 I = 1, 100

   X = A+X

   K = B(I)+7

99 CONTINUE

эквивалентен следующему фрагменту программы

   DO 99 I = 1, 100

   X = A+X

99 CONTINUE

K = B(100)+7

Конец примера.

 

Пример 117. Цикл

   DO 99 I = 1, 100

   X = A(I)+X

   K = B(I)+X

99 CONTINUE

эквивалентен следующему фрагменту программы

    DO 99 I = 1, 100

   X = A(I)+X

99 CONTINUE

    K = B(100)+X

Конец примера.

 

Пример 118. Цикл

   DO 99 I = 1, 100

   K = B(I)+X

   X = A(I)+X

99 CONTINUE

не эквивалентен следующему фрагменту программы

   DO 99 I = 1, 100

   X = A(I)+X

99 CONTINUE

  K = B(100)+X

Конец примера.

 

Пример 119. Цикл

   DO 99 I = 1,N

   K = B+X

   X = A(I)+X

99 CONTINUE

не эквивалентен следующему фрагменту программы

   K = B+X

   DO 99 I = 1,N

   X = A(I)+X

99 CONTINUE

поскольку существует дуга истинной зависимости от второго

оператора к первому.

Конец примера.

 

Пример 120. Цикл

     DO 99 I = 1,N

     K = B+X

     X = A(I)

99 CONTINUE

не эквивалентен следующему фрагменту программы

    DO 99 I = 1,N

     X = A(I)+X

99 CONTINUE

     K = B+X

поскольку существует дуга антизависимости от первого оператора ко второму.

Конец примера.

 

Пример 121. Цикл

    DO 99 I = 1,N

    K = B+X

    X = С*4

    T(I)= A(I)+X

99 CONTINUE

эквивалентен следующему фрагменту программы

     K = B+X

     X = С*4

     DO 99 I = 1,N

     T(I)= A(I)+X

99 CONTINUE

Конец примера.

 

Дата: 2018-12-21, просмотров: 322.