OpenMP C並行化算法

Question

在「使用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很多

迎接斯特普

Answer 1

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

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

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

Answer 2

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

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和變化只是列，這意味着你的內存訪問將是連續的。

Answer 3

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