8

I am reading about loop tranformation techniques and i have a very hard time understanding how does loop skewing makes a loop parallelizable Here are are two loops, the initial one and the seconde one, what is the difference betwwen the two ? The two of them depends on previous iteration on both i and j, what make the second loop parallisable ? Or why can we make the interchange on the second one and not the first one ? Both of them have dependencies on i and 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];
            }
        }
4

1 回答 1

4

我对此没有任何功劳，我只是为您格式化并从其他来源复制它，希望对您有所帮助

[来源：ECE 1754，循环变换技术调查，Eric LaForest，2010 年 3 月 19 日]

这完全是关于两次执行迭代之间的距离，在第一次中，一个外循环和内循环之间的距离为 1，因此它们之间存在依赖关系。

循环倾斜正如它所说的那样：它使内部循环的执行相对于外部循环倾斜。如果内部循环依赖于阻止它并行运行的外部循环，这将很有用。例如，下面的代码有一个依赖向量 {(1, 0),(0, 1)} 。这两个循环都不能并行化，因为它们都带有一个依赖项。简单地交换循环只会交换持有依赖关系的索引，什么都不做。

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

循环倾斜是通过将外部循环的索引乘以一些倾斜因子 f 到内部循环的边界并从内部循环索引的所有使用中减去相同的值来实现的。减法将索引保持在新的循环范围内，从而保持程序的正确性。对内循环迭代的影响是将它们在数组中的位置相对于当前外循环向前移动f ，以相同的方式增加与外循环的依赖距离。换句话说，给定一个依赖向量 (a, b)，倾斜将其转换为 (a, fa + b)。由于此转换保留了依赖项的字典顺序，因此它始终是合法的。对上述内部循环应用 1 的偏斜因子会产生以下代码：

do i = 2, n-1
do j = 2+i, m-1+i
a[i,j-i] =
(a[i-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[i-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 的依赖由外部循环携带。请注意，交换倾斜循环边界不再简单：每个循环都必须考虑上和另一个循环的下限。

于 2014-09-22T21:52:20.390 回答