c - OpenMP:在 while 循环中并行化 for 循环

Question

我正在实现一种算法，使用力导向来计算图形布局。我想添加 OpenMP 指令来加速某些循环。看了一些类(class)后，根据自己的理解加了一些OpenMP指令。代码已编译，但不会返回与顺序版本相同的结果。

我想知道您是否愿意看一下我的代码并帮助我找出我的 OpenMP 版本出了什么问题。

请在此处下载文件: http://www.mediafire.com/download/3m42wdiq3v77xbh/drawgraph.zip

如您所见，我想要并行化的代码部分是:

unsigned long graphLayout(Graph * graph, double * coords, unsigned long maxiter) 

特别是这两个消耗大量计算资源的循环:

/* compute repulsive forces (electrical: f=-C.K^2/|xi-xj|.Uij) */      
  for(int j = 0 ; j < graph->nvtxs ; j++) { 
    if(i == j) continue;
    double * _xj = _position+j*DIM;
    double dist = DISTANCE(_xi,_xj);        
    // power used for repulsive force model (standard is 1/r, 1/r^2 works well)
    // double coef = 0.0; -C*K*K/dist;       // power 1/r
     double coef = -C*K*K*K/(dist*dist); // power 1/r^2 
    for(int d = 0 ; d < DIM ; d++) force[d] += coef*(_xj[d]-_xi[d])/dist;
  }

/* compute attractive forces (spring: f=|xi-xj|^2/K.Uij) */
  for(int k = graph->xadj[i] ; k < graph->xadj[i+1] ; k++) {
    int j =  graph->adjncy[k]; /* edge (i,j) */ 
    double * _xj = _position+j*DIM;
    double dist = DISTANCE(_xi,_xj);            
    double coef = dist*dist/K;
    for(int d = 0 ; d < DIM ; d++) force[d] += coef*(_xj[d]-_xi[d])/dist;   
  }

提前感谢您提供的任何帮助!

Answer 1

您的代码中存在数据竞争，例如，在执行 maxmove = nmove; 或 energy += nforce2; 时。在任何多线程代码中，您不能写入线程共享的变量，直到您使用原子访问(#pragma omp atomic read/write/update)或直到您同步对此类变量的访问显式(临界区、锁)。首先阅读一些关于 OpenMP 的教程，你的代码有更多问题，例如

if(nmove > maxmove) maxmove = nmove;

即使是原子操作，这一行通常也不起作用(你必须使用所谓的比较和交换原子操作来解决这个问题)。这里更好的解决方案是让每个线程计算其局部最大值，然后将其缩减为全局最大值。