Best approach to parallelize BW and FW algorithms

Question

I have implemented the BW and FW algorithms to solve L and U triangular matrix. The algorithm that I implement run very fast in a serial way, but I can not figure out if this is the best method to parallelize it. I think that I have taken into account every possible data race (on alpha), am I right?

void solveInverse (double **U, double **L, double **P, int rw, int cw) {
    double **inverseA = allocateMatrix(rw,cw);
    double* x = allocateArray(rw);
    double* y = allocateArray(rw);
    
    double alpha;
    
    //int i, j, t;
    
    // Iterate along the column , so at each iteration we generate a column of the inverse matrix
    for (int j = 0; j < rw; j++) {
        
        // Lower triangular solve Ly=P
        y[0] = P[0][j];
        #pragma omp parallel for reduction(+:alpha)
        for (int i = 1; i < rw; i++) {
            alpha = 0;
            for (int t = 0; t <= i-1; t++)
                alpha += L[i][t] * y[t];
            y[i] = P[i][j] - alpha;
        }

        // Upper triangular solve Ux=P
        x[rw-1] = y[rw-1] / U[rw-1][rw-1];
        #pragma omp parallel for reduction(+:alpha)
        for (int i = rw-2; (i < rw) && (i >= 0); i--) {
            alpha = 0;
            
            for (int t = i+1; t < rw; t++)
                alpha += U[i][t]*x[t];
            x[i] = (y[i] - alpha) / U[i][i];
        }
        
        for (int i = 0; i < rw; i++)
            inverseA[i][j] = x[i];  
        }
    freeMemory(inverseA,rw);
    free(x);
    free(y);
}

After a private discussion with the user dreamcrash, we have come to the solution proposed in his comments, creating a couple of vector x and y for each thread that will work indipendently on a single column.

user_1366871 · Answer

After a discussion with the OP on the comments (that were removed afterwards), we both came to the conclusion that:

You do not need to reduce the alpha variable, because outside the first parallel region it is initialized again to zero. Instead, make the alpha variable private.

#pragma omp parallel for
for (int i = 1; i < rw; i++) {
    double alpha = 0;
    for (int t = 0; t <= i-1; t++)
        alpha += L[i][t] * y[t];
    y[i] = P[i][j] - alpha;
}

and the same applies to the second parallel region as well.

#pragma omp parallel for
for (int i = rw-2; (i < rw) && (i >= 0); i--) {
    double alpha = 0;
    for (int t = i+1; t < rw; t++)
        alpha += U[i][t]*x[t];
    x[i] = (y[i] - alpha) / U[i][i];
}

Instead of having one parallel region per j iteration. You can extract the parallel region to encapsulate the entire outermost loop, and use #pragma omp for instead of #pragma omp parallel for. Notwithstanding, although with this approach we reduced the number of parallel regions created from rw to only 1, the speedup achieved with this optimization should not be that significant, because an efficient OpenMP implementation will use a pool of threads, where the threads are initialized on the first parallel region but reused on the next parallel regions. Consequently, saving on the overhead of creating and destroying threads.

#pragma omp parallel
{
   for (int j = 0; j < rw; j++) 
   {
        y[0] = P[0][j];
        #pragma omp for
        for (int i = 1; i < rw; i++) {
            double alpha = 0;
            for (int t = 0; t <= i-1; t++)
               alpha += L[i][t] * y[t];
            y[i] = P[i][j] - alpha;
        }

        x[rw-1] = y[rw-1] / U[rw-1][rw-1];
        #pragma omp for
        for (int i = rw-2; (i < rw) && (i >= 0); i--) {
             double alpha = 0;
        
             for (int t = i+1; t < rw; t++)
                 alpha += U[i][t]*x[t];
             x[i] = (y[i] - alpha) / U[i][i];
        }
    
        #pragma omp for
        for (int i = 0; i < rw; i++)
           inverseA[i][j] = x[i];  
    }
}

I have shown you this code transformations so that you could see some potential tricks that you can use on other future parallelizations. Unfortunately, as it is that parallelization will not work.

Why?

Let us look at the first loop:

#pragma omp parallel for
for (int i = 1; i < rw; i++) {
    double alpha = 0;
    for (int t = 0; t <= i-1; t++)
        alpha += L[i][t] * y[t];
    y[i] = P[i][j] - alpha;
}

there is a dependency between y[t] being read in alpha += L[i][t] * y[t]; and y[i] being written in y[i] = P[i][j] - alpha;.

So what you can do instead is to parallelize the outermost loop (i.e., assign each column to the threads) and create separate x and y arrays for each thread so that there is no race-conditions during the updates/reads of those arrays.

#pragma omp parallel
{   
     double* x = allocateArray(rw);
     double* y = allocateArray(rw);

    #pragma omp for
    for (int j = 0; j < rw; j++) 
    {
        y[0] = P[0][j];
        for (int i = 1; i < rw; i++) {
            double alpha = 0;
            for (int t = 0; t <= i-1; t++)
               alpha += L[i][t] * y[t];
            y[i] = P[i][j] - alpha;
        }
        x[rw-1] = y[rw-1] / U[rw-1][rw-1];

        for (int i = rw-2; i >= 0; i--) {
             double alpha = 0;
             for (int t = i+1; t < rw; t++)
                 alpha += U[i][t]*x[t];
             x[i] = (y[i] - alpha) / U[i][i];
        }
        for (int i = 0; i < rw; i++)
           inverseA[i][j] = x[i];  
     }

    free(x);
    free(y);
}

Best approach to parallelize BW and FW algorithms

1 Answers