OpenMP: Parallelize for loops inside a while loop

Question

I am implementing an algorithm to compute graph layout using force-directed. I would like to add OpenMP directives to accelerate some loops. After reading some courses, I added some OpenMP directives according to my understanding. The code is compiled, but don’t return the same result as the sequential version.

I wonder if you would be kind enough to look at my code and help me to figure out what is going wrong with my OpenMP version.

Please download the archive here: http://www.mediafire.com/download/3m42wdiq3v77xbh/drawgraph.zip

As you see, the portion of code which I want to parallelize is:

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

Particularly, these two loops which consumes alot of computational resources:

/* 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;   
  }

Thank you in advance for any help you can provide!

Daniel Langr · Accepted Answer · 2016-04-04 08:22:56Z

1

You have data races in your code, e.g., when doing maxmove = nmove; or energy += nforce2;. In any multi-threaded code, you cannot write into a variable shared by threads until you use an atomic access (#pragma omp atomic read/write/update) or until you synchronize an access to such a variable explicitly (critical sections, locks). Read some tutorial about OpenMP first, there are more problems with your code, e.g.

if(nmove > maxmove) maxmove = nmove;

this line will generally not work even with atomics (you would have to use so-called compare-and-exchange atomic operation to solve this). Much better solution here is to let each thread to calculate its local maximum and then reduce it into a global maximum.

edited Apr 4, 2016 at 8:22

answered Apr 4, 2016 at 8:13

Daniel Langr

24.2k3 gold badges55 silver badges110 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

OpenMP: Parallelize for loops inside a while loop

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related