Loop偏斜如何使循环可并行化？

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];
            }
        }

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, 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 的依赖由外部循环承载。请注意，交换倾斜循环边界不再简单：每个循环必须考虑上层循环和另一个循环的下界。