OPENMP - Parallelize Schwarz algorithm with preconditions

Question

I need to parallelize the Schwarz algorithm right bellow but I do not know how to deal with the precondition and the fact there are nested loops. I have to use OpenMP or MPI.

void ssor_forward_sweep(int n, int i1, int i2, int j1, int j2, int k1, int k2, double* restrict Ax, double w)
{
#define AX(i,j,k) (Ax[((k)*n+(j))*n+(i)])

int i, j, k;
double xx, xn, xe, xu;

for (k = k1; k < k2; ++k) {
   for (j = j1; j < j2; ++j) {
      for (i = i1; i < i2; ++i) {
         xx = AX(i,j,k);
         xn = (i > 0)   ? AX(i-1,j,k) : 0;
         xe = (j > 0)   ? AX(i,j-1,k) : 0;
         xu = (k > 0)   ? AX(i,j,k-1) : 0;
         AX(i,j,k) = (xx+xn+xe+xu)/6*w;
      }
   }
}
#undef AX
}

Taking account that each loop use values from the loop before, how to parallelize this function to get the best time.

I already tried to parallelize loops two by two or by splitting in blocks (like Stencil Jacobi 3D) but without success...

Thank you very much !

user_5809597 · Answer

Unfortunately, the inter-loop data dependency limits the amount of parallelism you can obtain in your nested loops.

You can use tasks with dependences, which will be the easiest approach. OpenMP runtime library will take care of the scheduling and you focus only on your algorithm. Another good side is that there is no synchronization at the end of any loop, but only between dependent parts of the code.

#pragma omp parallel
#pragma omp single
for (int k = 0; k < k2; k += BLOCK_SIZE) {
  for (int j = 0; j < j2; j += BLOCK_SIZE) {
    for (int i = 0; i < i2; i += BLOCK_SIZE) {
      #pragma omp task depend (in: AX(i-1,j,k),AX(i,j-1,k),AX(i,j,k-1)) \
                       depend (out: AX(i,j,k))
      // your code here
    }
  }
}

Tasks are sometimes a bit more expensive than parallel loops (depending on workload and synchronization granularities), so another alternative is the wavefront parallelization pattern, which basically transforms the iteration space so that the elements in the inner loop are independent between each other (so you can use parallel for there).

If you want to either approach, I strongly suggest you to turn your algorithm into a blocking one: unroll your 3-nested loops to do the computation in two stages:

Iterate among fixed sized sized blocks/cubes (let's call your new induction variables ii, jj and kk).
For each block, call the original serial version of your loop.

The goal of blocking is to increase the granularity of the parallel part, so that the parallelization overhead is not as noticeable.

Here is some pseudocode for the blocking part:

#define min(a,b) ((a)<(b)?(a):(b))
// Inter block iterations
for (int kk = 0; kk < k2; kk += BLOCK_SIZE) {
  for (int jj = 0; jj < j2; jj += BLOCK_SIZE) {
    for (int ii = 0; ii < i2; ii += BLOCK_SIZE) {

      // Intra block iterations
      for (int k = kk; k < min(k2,k+BLOCK_SIZE); k++) {
        for (int j = jj; j < min(j2,j+BLOCK_SIZE); j++) {
          for (int i = ii; i < min(i2,i+BLOCK_SIZE); i++) {
              // Your code goes here
          }
        }
      }

    }
  }
}

In the case of the wavefront parallelization, the last step is turning the outer loops (inter block iterations) into a wavefront, so that you iterate over the elements that are not dependent between each other. In 3D iteration spaces, it is basically a diagonal plane that advances from (0,0,0) to (i2,j2,k2). Something like the one highlighted in red, in the image below.

I'm going to put an example of the 2D wavefront, because it is easier to understand.

#define min(a,b) ((a)<(b)?(a):(b))
#pragma omp parallel
for (int d = 1; d < i2+j2; d++ ) {
    int i = min(d,i2) - 1;
    int j = 0;
    // Iterations in the inner loop are independent
    // Implicit thread barrier (synchronization) at the end of the loop
    #pragma omp for
    for ( ; i >= 0 && j < min(d,j2); i--, j++) {
      // your code here
    }
}

OPENMP - Parallelize Schwarz algorithm with preconditions

1 Answers