循環展開來實現並行

Question

在一次演講我的教授給了我們以下循環：

for (int i = 0; i < 100; i++) { 
    a[i] = a[i] + b[i]; 
    b[i + 1] = c[i] + d[i]; 
} 

他循環迭代之間指出的依賴，因爲線三組在接下來的迭代中使用的值第2行（設置b[i+1]，在下一次迭代中變爲b[i]）。因此我們不能並行運行循環的每次迭代。

然後，他給了我們這個展開的版本：

a[1] = a[1] + b[1]; 
for (int i = 0; i < 98; i++) { 
    b[i+1] = c[i] + d[i]; 
    a[i+1] = a[i] + b[i]; 
} 
b[99] = c[99] + d[99]; 

他聲稱，循環的每次迭代現在可以並行運行。我看到的問題是第3行設置在第4行的下一次迭代中將變爲b[i]，因此我們仍然不能並行運行每個迭代。

我說得對嗎？如果是這樣，是否有一個正確展開版本的第一個循環，每個迭代可以並行化？

Answer 1

我猜你寫錯了你的教授給出的展開版本。要等同於第一算法，它應該這樣寫：

a[0] = a[0] + b[0]; 
for (int i=0 ; i<99 ; ++i) { 
    b[i+1] = c[i] + d[i]; 
    a[i+1] = a[i+1] + b[i+1]; 
} 
b[100] = c[100] + d[100]; 

在這個版本中，你可以看到，依賴性問題已經一去不復返了。