How to parallelize nested loops correctly

Question

I am working with OpenMP to parallelize a scalar nested loop:

double P[N][N]; double x=0.0,y=0.0; for (int i=0; i<N; i++) { for (int j=0; j<N; j++) { P[i][j]=someLongFunction(x,y); y+=1; } x+=1; } 

In this cycle, it is important that the matrix P must be the same in both scalar and parallel versions:

All my possible trials failed ...

Answer 1

The problem is that you added the iteration dependencies to the iteration with:

 x+=1; y+=1; 

Therefore, since the code is standing right now, it is not parallelizable. Attempting to do this will result in incorrect results. (as you probably see)

Fortunately, in your case, you can directly calculate them without introducing this dependency:

 for (int i=0; i<N; i++) { for (int j=0; j<N; j++) { P[i][j]=someLongFunction((double)i, (double)N*i + j); } } 

Now you can try throwing the OpenMP pragma on this and see if it works:

 #pragma omp parallel for for (int i=0; i<N; i++) { for (int j=0; j<N; j++) { P[i][j]=someLongFunction((double)i, (double)N*i + j); } }