Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Parallel OpenMP loop with break statement

I know that you cannot have a break statement for an OpenMP loop, but I was wondering if there is any workaround while still the benefiting from parallelism. Basically I have 'for' loop, that loops through the elements of a large vector looking for one element that satisfies a certain condition. However there is only one element that will satisfy the condition so once that is found we can break out of the loop, Thanks in advance

for(int i = 0; i <= 100000; ++i)   {     if(element[i] ...)      {           ....           break;       }    } 
like image 610
Jeanno Avatar asked Mar 20 '12 19:03

Jeanno


People also ask

How do I break a loop in OpenMP?

OpenMP does not provide a mechanism to break out of a parallel loop. However, you can use a Boolean value, or flag, to enable an iteration of the loop to indicate that the solution has been found. The Concurrency Runtime provides functionality that enables one task to cancel other tasks that have not yet started.

Can you parallelize a while loop?

In addition, it is common for while loops to check for a condition using last iteration's result. This is called Read-after-Write or true-dependency and cannot be parallelized.

What is Nowait clause in OpenMP?

The nowait clause overrides any synchronization that would otherwise occur at the end of a construct. It can also specify that an interoperability requirement set includes the nowait property. If the construct includes an implicit barrier, the nowait clause specifies that the barrier will not occur.


2 Answers

See this snippet:

volatile bool flag=false;  #pragma omp parallel for shared(flag) for(int i=0; i<=100000; ++i) {         if(flag) continue;     if(element[i] ...)     {           ...           flag=true;     } } 

This situation is more suitable for pthread.

like image 58
yyfn Avatar answered Sep 18 '22 16:09

yyfn


You could try to manually do what the openmp for loop does, using a while loop:

const int N = 100000; std::atomic<bool> go(true); uint give = 0;  #pragma omp parallel {     uint i, stop;      #pragma omp critical     {         i = give;         give += N/omp_get_num_threads();         stop = give;          if(omp_get_thread_num() == omp_get_num_threads()-1)             stop = N;     }        while(i < stop && go)     {         ...         if(element[i]...)         {             go = false;         }         i++;     } } 

This way you have to test "go" each cycle, but that should not matter that much. More important is that this would correspond to a "static" omp for loop, which is only useful if you can expect all iterations to take a similar amount of time. Otherwise, 3 threads may be already finished while one still has halfway to got...

like image 42
Haatschii Avatar answered Sep 19 '22 16:09

Haatschii