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測試本身是不夠的，但它確實爲您提供了一種相對便宜的方式，可以在分析過程中儘早做出決定，在那種情況下可以避免更昂貴的依賴性分析。