环路偏移如何使循环可并行化？

Question

我正在阅读有关循环变换技术的内容，但我很难理解循环偏移如何使循环可并行化。这里有两个循环，初始循环和第二个循环，它们之间有什么区别？它们都依赖于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];
            }
        }

- user2133558

Answer 1

我没有为此做出贡献，只是为您格式化并从另一个来源复制了它，希望它能帮助到您

[来源：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, f a + 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 的依赖关系由外层循环承载。请注意，交换偏斜的循环边界不再是直接的：每个循环必须考虑到另一个循环的上限和下限。

- mmain

---

谢谢您的评论，我已经更新了答案，并附上了原始来源的链接。我不想让提问者感到困惑，所以为他提取了必要的信息。 - mmain