循环倾斜如何使循环可并行化? [英] How is Loop skewing making loop parallelizable?
问题描述
我正在阅读有关循环转换技术的信息，并且我很难理解循环偏斜如何使一个循环可并行化.这里有两个循环，第一个循环和第二个循环，两者之间有什么区别?他们两个都依赖于i和j的先前迭代，是什么使第二个循环可并行化?还是为什么我们可以在第二个而不是第一个上进行互换?他们两个都依赖于i和j
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];
}
}
推荐答案
我对此并不满意，我只是为您设置了格式并从其他来源复制了它，希望对您有所帮助
[来源: ECE 1754，环路变换技术概述，Eric LaForest，3月19日，2010]
[source: ECE 1754, Survey of Loop Transformation Techniques, Eric LaForest, March 19, 2010]
这与两次执行迭代之间的距离有关，首先，一个外循环和内循环之间的距离为1，因此它们之间存在依赖性.
It is all about the distance between a two executive iterations, in the first the distance is 1 between one outer loop and inner loop, so there is a dependency between them.
循环歪斜完全按照它说的去做:它歪斜了内部循环的执行 相对于外部的如果内部循环依赖于外部循环，从而阻止其并行运行，则此功能很有用.例如，以下代码的依赖项向量为{(1，0)，(0，1)}.两个循环都不能并行化 因为它们每个都带有依赖项.简单地交换循环只会 交换包含依赖项的索引，什么也没做.
Loop skewing does exactly what it says: it skews the execution of an inner loop relative to an outer one. This is useful if the inner loop has a dependence on the outer loop which prevents it from running in parallel. For example, the following code has a dependency vector of {(1, 0),(0, 1)} .Neither loop can be parallelized since they each carry a dependency. Simply interchanging the loops would merely interchange the indices holding the dependencies, accomplishing nothing.
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应用于 上面的内部循环产生以下代码:
Loop skewing is implemented by adding the index of the outer loop, times some skewing factor f, to the bounds of the inner loop and subtracting the same value from all the uses of the inner loop index. The subtraction keeps the indices within the new loop bounds, preserving the correctness of the program. The effect on the inner loop iterations is to shift their position in the array forwards by f relative to the current outer loop, increasing the dependency distance to the outer loop in the same manner. In other words, given a dependency vector (a, b), skewing transforms it to (a, f a + b). Since this transformation preserves the lexicographic order of the dependencies, it is always legal. Applying a skew factor of one to the above inner loop yields the following code:
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)}，如以下代码所示:
This new code executes in the same manner, but with dependencies of {(1, 1),(0, 1)}. Both loops still carry a dependency. However, interchanging the loops at this point yields a dependence vector {(1, 0),(1, 1)}, as shown in the following code:
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的依赖关系则由外部循环承载. 互换倾斜的循环边界不再简单明了:每个循环都必须 考虑到另一个循环的上下限.
The inner loop can now be parallelized since it has now no loop-carried dependency on j, and the dependency to i is carried by the outer loop.Note that interchanging skewed loop bounds is no longer straightforward: each loop must take into account the upper and lower bounds of the other loop.
这篇关于循环倾斜如何使循环可并行化?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
