Is it possible to parallelize this for loop?

Question

I was given some code to paralellize using OpenMP and, among the various function calls, I noticed this for loop takes some good guilt on the computation time.

  double U[n][n];
  double L[n][n];
  double Aprime[n][n];
  for(i=0; i<n; i++) {
    for(j=0; j<n; j++) {
      if (j <= i) {
          double s;
          s=0;
          for(k=0; k<j; k++) {
            s += L[j][k] * U[k][i];
          } 
          U[j][i] = Aprime[j][i] - s;
      } else if (j >= i) {
          double s;
          s=0;
          for(k=0; k<i; k++) {
            s += L[j][k] * U[k][i];
          }
          L[j][i] = (Aprime[j][i] - s) / U[i][i];
      }
    }

However, after trying to parallelize it and applying some semaphores here and there (with no luck), I came to the realization that the else if condition has a strong dependency on the early if (L[j][i] being a processed number with U[i][i], which may be set on the early if), making it, in my oppinion, non-parallelizable due to race conditions.

Is it possible to parallelize this code in such a manner to make the else if only be executed if the earlier if has already completed?

Answer 1

Before trying to parallelize things, try simplification first.

For example, the if can be completely eliminated.

Also, the code is accessing the matrixes in a way that causes worst cache performance. That may be the real bottleneck.

Note: In update #3 below, I did benchmarks and the cache friendly version fix5, from update #2, outperforms the original by 3.9x.

I've cleaned things up in stages, so you can see the code transformations.

With this, it should be possible to add omp directives successfully. As I mentioned in my top comment, the global vs. function scope of the variables affects the type of update that may be required (e.g. omp atomic update, etc.)

---

For reference, here is your original code:

double U[n][n];
double L[n][n];
double Aprime[n][n];

for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
        if (j <= i) {
            double s;

            s = 0;
            for (k = 0; k < j; k++) {
                s += L[j][k] * U[k][i];
            }
            U[j][i] = Aprime[j][i] - s;
        }
        else if (j >= i) {
            double s;

            s = 0;
            for (k = 0; k < i; k++) {
                s += L[j][k] * U[k][i];
            }
            L[j][i] = (Aprime[j][i] - s) / U[i][i];
        }
    }
}

---

The else if (j >= i) was unnecessary and could be replaced with just else. But, we can split the j loop into two loops so that neither needs an if/else:

// fix2.c -- split up j's loop to eliminate if/else inside

double U[n][n];
double L[n][n];
double Aprime[n][n];

for (i = 0; i < n; i++) {
    for (j = 0; j <= i; j++) {
        double s = 0;
        for (k = 0; k < j; k++)
            s += L[j][k] * U[k][i];
        U[j][i] = Aprime[j][i] - s;
    }

    for (; j < n; j++) {
        double s = 0;
        for (k = 0; k < i; k++)
            s += L[j][k] * U[k][i];
        L[j][i] = (Aprime[j][i] - s) / U[i][i];
    }
}

---

U[i][i] is invariant in the second j loop, so we can presave it:

// fix3.c -- save off value of U[i][i]

double U[n][n];
double L[n][n];
double Aprime[n][n];

for (i = 0; i < n; i++) {
    for (j = 0; j <= i; j++) {
        double s = 0;
        for (k = 0; k < j; k++)
            s += L[j][k] * U[k][i];
        U[j][i] = Aprime[j][i] - s;
    }

    double Uii = U[i][i];

    for (; j < n; j++) {
        double s = 0;
        for (k = 0; k < i; k++)
            s += L[j][k] * U[k][i];
        L[j][i] = (Aprime[j][i] - s) / Uii;
    }
}

---

The access to the matrixes is done in probably the worst way for cache performance. So, if the assignment of dimensions can be flipped, a substantial savings in memory access can be achieved:

// fix4.c -- transpose matrix coordinates to get _much_ better memory/cache
// performance

double U[n][n];
double L[n][n];
double Aprime[n][n];

for (i = 0; i < n; i++) {
    for (j = 0; j <= i; j++) {
        double s = 0;
        for (k = 0; k < j; k++)
            s += L[k][j] * U[i][k];
        U[i][j] = Aprime[i][j] - s;
    }

    double Uii = U[i][i];

    for (; j < n; j++) {
        double s = 0;
        for (k = 0; k < i; k++)
            s += L[k][j] * U[i][k];
        L[i][j] = (Aprime[i][j] - s) / Uii;
    }
}

---

UPDATE:

In the Op's first k-loop its k<j and in the 2nd k<i don't you have to fix that?

Yes, I've fixed it. It was too ugly a change for fix1.c, so I removed that and applied the changes to fix2-fix4 where it was easy to do.

---

UPDATE #2:

These variables are all local to the function.

If you mean they are function scoped [without static], this says that the matrixes can't be too large because, unless the code increases the stack size, they're limited to the stack size limit (e.g. 8 MB)

Although the matrixes appeared to be VLAs [because n was lowercase], I ignored that. You may want to try a test case using fixed dimension arrays as I believe they may be faster.

Also, if the matrixes are function scope, and want to parallelize things, you'd probably need to do (e.g.) #pragma omp shared(Aprime) shared(U) shared(L).

The biggest drag on cache were the loops to calculate s. In fix4, I was able to make access to U cache friendly, but L access was poor.

I'd need to post a whole lot more if I did include the external context

I guessed as much, so I did the matrix dimension swap speculatively, not knowing how much other code would need changing.

I've created a new version that changes the dimensions on L back to the original way, but keeping the swapped versions on the other ones. This provides the best cache performance for all matrixes. That is, the inner loop for most matrix access is such that each iteration is incrementing along the cache lines.

In fact, give it a try. It may improve things to the point where parallel isn't needed. I suspect the code is memory bound anyway, so parallel might not help as much.

// fix5.c -- further transpose to fix poor performance on s calc loops
//
// flip the U dimensions back to original

double U[n][n];
double L[n][n];
double Aprime[n][n];

double *Up;
double *Lp;
double *Ap;

for (i = 0; i < n; i++) {
    Ap = Aprime[i];
    Up = U[i];

    for (j = 0; j <= i; j++) {
        double s = 0;
        Lp = L[j];
        for (k = 0; k < j; k++)
            s += Lp[k] * Up[k];
        Up[j] = Ap[j] - s;
    }

    double Uii = Up[i];

    for (; j < n; j++) {
        double s = 0;
        Lp = L[j];
        for (k = 0; k < i; k++)
            s += Lp[k] * Up[k];
        Lp[i] = (Ap[j] - s) / Uii;
    }
}

Even if you really need the original dimensions, depending upon the other code, you might be able to transpose going in and transpose back going out. This would keep things the same for other code, but, if this code is truly a bottleneck, the extra transpose operations might be small enough to merit this.

---

UPDATE #3:

I've run benchmarks on all the versions. Here are the elapsed times and ratios relative to original for n equal to 1037:

orig: 1.780916929 1.000x
fix1: 3.730602026 0.477x
fix2: 1.743769884 1.021x
fix3: 1.765769482 1.009x
fix4: 1.762100697 1.011x
fix5: 0.452481270 3.936x

Higher ratios are better.

Anyway, this is the limit of what I can do. So, good luck ...