的OpenMP：循環結轉依賴

Question

我想用C實現一個簡單的累計總和++代碼如下：

x[0] = 0; 
for (k=1;k<100; k++) 
    x[k] = x[k-1] + x[k]; 

在此site，實現被記錄下來，以消除過度依賴環路矣。該代碼應該是這樣的兩個線程：

x[0] = 0; 
x[49] = 74; //pre calculated 
//the outer loop is parallelized (two instances) 
#pragma omp parallel for private(m,k) 
    for(m=0;m<2;m++) { 
    for (k=m*49+1; k<m*50+50; k++) { 
     x[k] = x[k-1] + x[k]; 
    } 
    } 

問題是，我仍然可以看到這裏的循環進位的依賴性（並行運行兩個線程，但一個來自另一個需要數據）。

有人可以在這裏添加一些解釋嗎？消除這種依賴的最好方法是什麼？

Answer 1

由於x[49]的值已經存在，因此不需要再次計算：您可以跳過k = 0和k = 49的迭代。這就是爲什麼循環展開爲兩個嵌套循環。

但是，那裏似乎有錯誤。應該只有內循環的循環進位依賴性，並且它應該跨越外循環的迭代進行傳播。這是因爲極限未正確定義：

• 隨着m = 0，k = 1 .. 48（你已經得到0和49）。
• With m = 1，k = 50 ..99（同樣，你已經有49！）。

因此，循環應留有如下所示：

for(m = 0; m < 2; m++) { 
    for (k=m*49+1; k<m*51+49; k++) { 
    x[k] = x[k-1] + x[k]; 
    } 
} 

如果改變除了是：

x[k+1] = x[k] + x[k+1]; 

它可以簡化有點您的下限。 ..

for(m = 0; m < 2; m++) { 
    for (k=m*50; k < m*51+48; k++) { 
    x[k+1] = x[k] + x[k+1]; 
    } 
}