Как перекос петли делает петлю параллелизируемой?

Я читаю о методах преобразования петель, и мне очень трудно понять, как перекосы петель делают петлю параллелизируемой здесь есть две петли, начальная и вторая, в чем разница между ними ? Два из них зависят от предыдущей итерации как от i, так и от j, что делает второй цикл параллельным ? Или почему мы можем сделать обмен на втором, а не на первом ? Оба они имеют зависимости от i и j 

for(int i =2; i < 5; i++){
            for(int j =2; j < 5; j++){
                A[i][j] = A[i-1][j] + A[i][j-1];
            }
        }
for(int i =2; i < 5; i++){
            for(int j =2+i; j < 5+i; j++){
                A[i][j-i] = A[i-1][j-i] + A[i][j-1-i];
            }
        }
1 5
parallel-processing skew nested-loops

1 ответ:

У меня нет никакой заслуги в этом, я просто отформатировал его для вас и скопировал из другого источника, и я надеюсь, что это поможет вам

[Источник: ЕСЕ 1754, обзор методов преобразования петель, Эрик Лафорест, 19 марта 2010 г.]

Все дело в расстоянии между двумя исполнительными итерациями, в первой расстояние равно 1 между одним внешним циклом и внутренним циклом, поэтому между ними существует зависимость.

Перекос петли делает именно то, что он говорит: он искажает выполнение внутреннего цикла относительно внешнего. Это полезно, если внутренняя петля имеет зависимость от внешней петли, которая не позволяет ей работать параллельно. Например, следующий код имеет вектор зависимостей типа {(1, 0),(0, 1)} .Ни один цикл не может быть распараллелен так как каждый из них несет в себе зависимость. Просто замена петель будет просто обменивайтесь индексами, содержащими зависимости, ничего не добиваясь.

do i = 2, n-1
do j = 2, m-1
a[i,j] =
      (a[a-1,j] + a[i,j-1] + a[i+1,j] + a[i,j+1]) / 4
end do
end do

Перекос цикла реализуется путем добавления индекса внешняя петля, раз несколько смещение коэффициента f к границам внутреннего контура и вычитание того же значения от всех видов использования индекса внутреннего цикла. Вычитание удерживает индексы в пределах новый цикл ограничивает, сохраняя корректность программы. Влияние на внутренний цикл итераций заключается в смещении их положения в массиве вперед на f относительно к текущему внешнему контуру, увеличивая расстояние зависимости до внешнего контура точно так же. Другими словами, учитывая вектор зависимости (a, b), перекос преобразует его в (a, f a + b). Так как эта трансформация сохраняет лексикографическую порядок зависимостей, он всегда легален. Применение коэффициента перекоса, равного единице, к приведенный выше внутренний цикл дает следующий код: 

do i = 2, n-1
do j = 2+i, m-1+i
a[i,j-i] =
(a[a-1,j-i] + a[i,j-1-i] + a[i+1,j-i] + a[i,j+1-i]) / 4
end do
end do

Этот новый код выполняется таким же образом, но с зависимостями {(1, 1),(0, 1)}. Оба цикла все еще несут зависимость. Однако обмен петлями в этой точке дает вектор зависимости{(1, 0),(1, 1)}, как показано в следующий код: 

do j = 4, m+n-2
do i = max(2, j-m+1), min(n-1, j-2)
a[i,j-i] =
(a[a-1,j-i] + a[i,j-1-i] + a[i+1,j-i] + a[i,j+1-i]) / 4
end do
end do

Внутренний цикл теперь можно распараллелить, так как он теперь не имеет зависимости от J, а зависимость от i переносится внешним циклом.Обратите внимание, что взаимозаменяемость перекошенных границ цикла больше не является простой: каждый цикл должен примите во внимание верхнюю и нижнюю границы другого цикла.

2