How to know if the loops can be parallelized for multithreading with the help of openmp?-CodePudding

I have a nested loop. i would like to know if the outer and the inner loops can be parallelized with the help of openmp?

for (col = n-1; col >= 0; col--) {
    x[col] /= A[col][col];
    for (row = 0; row < col; row  )
        x[row] -= A[row][col] * x[col];
}

I think the outer loop can be paralelized as the inner loop depends only on the fixed value of the the column or col.

CodePudding user response：

A sufficient condition (but not necessary!) of parallelizability is

for each value of the loop variable
only array locations with that index are changed.

In such a case iterations i1 and i2 can not write in conflicting locations, therefore the writes can be done in any order, therefore in parallel.

In your code the inner loop satisfies that condition; your outer does not. That's because the inner loop writes a whole bunch of indices, and not just [col]. So two different col values will all write to identical locations. You can sometimes fix that with an atomic directive, but that's 1. not good for performance 2. not even possible in your particular case because of the non-associativity of the operations you're doing.