Parallelel If-else loop with break openmp

Question

I would like to know if there is a way to parallelize this piece of code in openmp. This loop needs to find next element that must be analyzed in another algorithm. So this loop analyze two vectors visited and used, if it finds an element that is visited but not used, next is equal to k and exit from loop setting k equal to dimension+1, if there aren't elements visited and not used, loop try to find elements not visited and not used and set next=k.

It's important that the statments inside else if don't break loop because there can be element visited in vectors.

for (k=0;k<dimension;k++){
    if (visited[k] == 1 && used[k]==0){
        next = k;
        fail =0;
        k=dimension+1;
     }

    else if (visited[k] == 0 && used[k]==0) {
        next = k;
        fail = 1;
    }

}

How Can I parallelize it with pragma omp for?

Isn't it a case of adding an omp directive before the for-loop? Reference: link — Simon Bosley

Jens Gustedt Jens Gustedt · Accepted Answer · 2014-02-20T10:28:55

Such code is not trivial to parallelize.

First you'd have to get rid of your implicit break, in resetting k.

Then you'd have to make vectors for your next and fail variables, and store your partial results in there.

Now your loop can be paralellized, since there are no interdependencies any more, only that your results now are vectors that you still have to analyse.

To analyse the result vectors you'd have to do prefix computations on them to find the first index i, if any, where fail[i] is 0 and take next[i] as the result.

All of this can be done, but nothing says a priori that you will have a speedup by that. This would much depend on the probability in which your different cases appear.

Parallelel If-else loop with break openmp

1 Answers