并行处理-循环偏斜如何使循环可并行化

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的依赖性由外部循环携带。请注意交换偏斜的循环边界不再简单：每个循环必须考虑另一个循环的上限和下限。