OpenMP C並行化算法

在「使用OpenMP」一書中，C是一個錯誤的內存訪問的例子，我認爲這是我試圖平行化高斯算法的主要問題。OpenMP C並行化算法

的例子看起來是這樣的：

k= 0 ;  
for(int j=0; j<n ; j++) 
    for(int i = 0; i<n; i++) 
     a[i][j] = a[i][j] - a[i][k]*a[k][j] ;

所以，我不明白爲什麼這會導致糟糕的內存訪問。在C中，二維數組按行存儲，並且在每一步中都會將新行從內存複製到緩存。

我想找到一個解決方案，但我沒有得到一個很好的加速。我的嘗試效果很小。

有人可以給我一個提示我可以做什麼嗎？

最簡單的方法是交換for循環，但我想按列方式執行。

第二次嘗試：

for(int j=0; j<n-1 ; j+=2) 
    for(int i = 0; i<n; i++) 
    { 
    a[i][j] = a[i][j] - a[i][k]*a[k][j] ; 
    a[i][j+1] = a[i][j+1] - a[i][k]*a[k][j+1] ; 
    }

沒有有所作爲的。

第三次嘗試：

for(int j=0; j<n ; j++) 
{ 
    d= a[k][j] ; 
    for(int i = 0; i<n; i++) 
    { 
    e = a[i][k] ; 
    a[i][j] = a[i][j] - e*d ; 
    } 
}

THX很多

迎接斯特普

來源

2011-02-24 Stepp

您是否試過交換'for'循環的順序？ – 2011-02-24 17:57:57

是的，我認爲，但這不會是意圖的解決方案。 btw謝謝大家的快速回復！ – Stepp 2011-02-24 18:46:45

使用平板陣列代替，例如：

#define A(i,j) A[i+j*ldA] 

for(int j=0; j<n ; j++) 
{ 
    d= A(k,j) ; 
    ... 
}

來源

2011-02-24 18:05:33 Anycorn

它有什麼區別？二維數組實際上是長扁平數組。 – Andrey 2011-02-24 18:07:13

@Andrey它使得列主要佈局變得更容易。二維數組在很多層面上都很難看。 – Anycorn 2011-02-24 18:09:18

試過這個......加速是一樣的。沒有區別。 – Stepp 2011-02-24 18:43:41

你的循環順序會導致緩存錯過每次迭代，正如你所指出的那樣出。所以，只要將循環語句的順序：

for (int i = 0; i < n; i++)  // now "i" is first 
    for (int j = 0; j < n; j++) 
     a[i][j] = a[i][j] - a[i][k]*a[k][j];

這將解決該行中a和變化只是列，這意味着你的內存訪問將是連續的。

來源

2011-02-24 18:12:40 chrisaycock

Thx，這將是最簡單的方法來解決這個問題，但我希望它能夠以列方式工作。 – Stepp 2011-02-24 18:42:42

此內存訪問問題僅與CACHE使用情況不相關，而與Openmp相關。爲了充分利用緩存，您應該訪問連續的內存位置。還請記住，如果兩個或更多線程訪問相同的內存區域，則可能會出現「虛假剪切」問題，迫使緩存不必要地重新加載。例如：
http://software.intel.com/en-us/articles/avoiding-and-identifying-false-sharing-among-threads/

來源

2011-02-24 21:55:59 GBBL

OpenMP C並行化算法

回答

相關問題