GCD测试 - 测试循环语句之间的依赖关系

Question

我理解的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，c=2,d=0和GCD(a,c)=2和(d-b)是-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); 
    } 
} 

Answer 1

虽然下标可以非线性化，但GCD测试很容易直接应用。在你的榜样，下标对是[1+2*i + 20*j]和[2+20*i + 2*j]，所以我们正在寻找一个整数解方程

1 + 2*i + 20*j = 2 + 20*i' + 2*j' 

花事，我们得到

2*i - 20*i' + 20*j - 2*j = 1 

计算所有系数的GCD， 2，-20，20和-2，看看它是否除以常数。在这种情况下，GCD是2.由于2不等于1，所以不存在依赖关系。

Answer 2

“易”的方式在嵌套循环的情况下适用GCD是只在阵列本身multidemsional例应用它;即原始源代码使用多个下标而不是已经线性化的表达式。当然，如果你可以“回转换”这些线性化的下标，那么你将拥有相同的效果。

一旦你将这个问题作为一个多重问题来解决，那么你可以简单地应用GCD测试“按维度”。如果任何维度都不显示依赖关系，那么您可以停止并声明整个多重约束下标序列没有依赖关系。

关键当然是，作为多维索引问题的投射为您提供了很好的属性，即在各个索引值和相应的索引表达式元组之间存在一对一的映射关系。没有这个问题就更难了。

这是我在70年代在ASC Fortran矢量化编译器中采用的方法，它运行得非常好，特别是与非方向下标分析结合使用时，可以用于非不相交情况。 GCD测试本身是不够的，但它确实为您提供了一种相对便宜的方式，可以在分析过程中尽早做出决定，在那种情况下可以避免更昂贵的依赖性分析。