parallel-processing - 循环倾斜如何使循环可并行化？

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, Survey of Loop Transformation Techniques, Eric LaForest, March 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)。由于此转换保留了词典编排
依存关系的顺序，始终是合法的。将偏斜因子1应用于
上面的内部循环产生以下代码:

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的依赖关系则由外部循环承载。
互换倾斜的循环边界不再简单明了:每个循环都必须
考虑到另一个循环的上下限。