1

在“Using 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 中,二维数组按行存储,并且在每 i 步中,都会将新行从内存复制到缓存。

我正在尝试为此找到解决方案,但我没有得到很好的加速。我的尝试的影响很小。

有人可以给我一个提示我能做什么吗?

最简单的方法是交换 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 ;
  }
}

多谢

问候 Stepp

4

3 回答 3

0

此内存访问问题仅与 CACHE 使用有关,与 Openmp 无关。一般来说,要充分利用缓存,您应该访问连续的内存位置。还要记住,如果两个或多个线程正在访问同一个内存区域,那么您可能会遇到“错误剪切”问题,迫使缓存不必要地重新加载。参见例如: http:
//software.intel.com/en-us/articles/avoiding-and-identifying-false-sharing-among-threads/

于 2011-02-24T21:55:59.327 回答
0

改用平面数组,例如:

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

for( int j=0; j<n ; j++)
{  
  d= A(k,j) ;
  ...
}
于 2011-02-24T18:05:33.080 回答
0

正如您所指出的,您的循环顺序将在每次迭代时导致缓存未命中。所以只需交换循环语句的顺序:

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-24T18:12:40.150 回答