GCD 测试 - 测试循环语句之间的依赖关系
我理解 GCD 如何在一个简单的例子中工作，如下所示：
for(i=1; i<=100; i++)
{
X[2*i+3] = X[2*i] + 50;
}
我们首先将其转换为以下形式： X[a*i + b] 和 X[c*i + d]
a=2、b=3 code>、c=2、d=0 和 GCD(a,c)=2 和 (db) > 是-3。由于 2 不能整除 -3，因此不可能存在依赖关系。
但是我们如何在双重嵌套循环上进行 GCD 测试？
例如：
for (i=0; i<10; i++){
for (j=0; j<10; j++){
A[1+2*i + 20*j] = A[2+20*i + 2*j);
}
}
I understand how the GCD works on a trivial example as below:
for(i=1; i<=100; i++)
{
X[2*i+3] = X[2*i] + 50;
}
we first transform it into the following form:X[a*i + b] and X[c*i + d]
a=2, b=3, c=2, d=0 and GCD(a,c)=2 and (d-b) is -3. Since 2 does not divide -3, no dependence is possible.
But how can we do this GCD test on a doubly nested loop?
For example:
for (i=0; i<10; i++){
for (j=0; j<10; j++){
A[1+2*i + 20*j] = A[2+20*i + 2*j);
}
}
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
虽然下标可以去线性化，但 GCD 测试很容易直接应用。在您的示例中，下标对是
[1+2*i + 20*j]和[2+20*i + 2*j]，所以我们寻找方程的整数解重新排列，我们得到
计算所有系数 2、-20、20 和 -2 的 GCD，并查看它是否能整除该常数。在本例中，GCD 为 2。由于 2 不能整除 1，因此不存在依赖性。
While the subscripts can be delinearized, the GCD test is simple to apply directly. In your example, the subscript pair is
[1+2*i + 20*j]and[2+20*i + 2*j], so we're looking for an integer solution to the equationRearranging, we get
Compute the GCD of all the coefficients, 2, -20, 20, and -2, and see if it divides the constant. In this case, the GCD is 2. Since 2 doesn't divide 1, there's no dependence.
在嵌套循环情况下应用 GCD 的“简单”方法是仅在数组本身是多重数组的情况下应用它；即，原始源代码使用多个下标而不是已经线性化的表达式。当然，如果您可以“反向变换”这些线性化下标，那么您将获得等效的结果。
一旦您将问题转化为多维问题，那么您可以简单地应用 GCD 测试“逐个维度”。如果任何维度显示不存在依赖性，那么您可以停止并声明整个多维下标序列不存在依赖性。
当然，关键是转换为多维索引问题为您提供了一个很好的属性，即各个索引值和相应的索引表达式元组之间存在一对一的映射。如果没有这个，问题就更难了。
这是我在 70 年代在 ASC Fortran 向量化编译器中采用的方法，效果非常好，特别是与非不相交情况的定向下标分析结合使用。 GCD 测试本身确实不够，但它确实为您提供了一种相对便宜的方法，可以在分析中做出早期决策，从而避免更昂贵的依赖性分析。
The "easy" way to apply GCD in the nested loop case is to apply it only in cases where the arrays themselves are multidemsional; i.e., the original source code uses multiple subscripts rather than already linearized expressions. Of course if you can "back transform" these linearized subscripts then you'll have the equivalent.
Once you've cast the problem as a multidemsional problem then you may simply apply the GCD test "dimension by dimension". If any dimension shows no dependence then you can stop and declare there is no dependence for the entire multidemsional subscripting sequence.
The key of course is that casting as a multidimensional indexing problem gives you the nice property that there's a one-to-one mapping between individual index values and the corresponding index expression tuples. Without this the problem is harder.
This is the approach I took in the ASC Fortran vectorizing compiler back in the 70's and it worked pretty well, particularly used in conjunction with directional subscript analysis for the non disjoint case. The GCD test by itself is really not sufficient, but it does give you a relatively inexpensive way of making an early decision in your analysis in those cases where you then can avoid the more expensive dependence analysis.