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/