Why this piece of parallelized code with OpenMP is not working well?

user_15984349 0
Viewed 105

I am trying to parallelize this piece of C code with OpenMP:

for (i = 0; i < openSetSize; i++) {
    tmpF = arrayCells[openSet[i]].f;
    if (tmpF <= arrayCells[openSet[best]].f && tmpF <= arrayCells[bestPath[0]].f){
        isThereBest = true;
        best = i;
    }
}

I tried this way:

#pragma omp parallel {
            
    int best_private = 0;
    #pragma omp for nowait
    for (int i = 0; i < openSetSize; i++) {
        double tmpF = arrayCells[openSet[i]].f;
        if (tmpF <= arrayCells[openSet[best_private]].f && tmpF <= arrayCells[bestPath[0]].f) {
            isThereBest = true;
            best_private = i;
        }
    }
            
    #pragma omp critical
    {
        if(best_private > best){
            best = best_private;
        }
    }
}

but the performance are not satisfactory at all (much more time spent with the omp version).

Does anyone have better hints? Or do know where I am wrong? Thank you so much

openmp parallel-processing multithreading c
1 Answers

The only problem I see is that all threads are writing to the shared variable isThereBest.

The simplest solution would be to you give every thread its own private version of the variable, just like you did with the variable best:

#pragma omp parallel
{
    bool isThereBest_private = false;
    int best_private = 0;

    #pragma omp for nowait
    for (int i = 0; i < openSetSize; i++) {
        double tmpF = arrayCells[openSet[i]].f;
        if (tmpF <= arrayCells[openSet[best_private]].f && tmpF <= arrayCells[bestPath[0]].f) {
            isThereBest_private = true;
            best_private = i;
        }
    }

    #pragma omp critical
    {
        if ( isThereBest_private ) {
            isThereBest = true;
        if ( best_private > best ) {
            best = best_private;
        }
    }
}

However, a cleaner solution would be to use the reduction clause instead, which makes the entire omp critical construct redundant:

#pragma omp parallel for reduction(||:isThereBest) reduction(max:best)
for (int i = 0; i < openSetSize; i++) {
    double tmpF = arrayCells[openSet[i]].f;
    if (tmpF <= arrayCells[openSet[best]].f && tmpF <= arrayCells[bestPath[0]].f) {
        isThereBest = true;
        best = i;
    }
}

Using the reduction clause instead of an omp critical construct will likely also improve performance.

user_121494710
Related