Break a parallel loop

General OpenMP discussion

Break a parallel loop

Postby jgpallero » Fri May 11, 2012 3:56 pm

Hello:

I have a for loop from which I need to break out under some circumstances. I know that break sentence can not be used to break ot for a loop in OpenMP. Surfing the net I have found the web http://www.thinkingparallel.com/2007/06 ... in-openmp/ in which a trick is explained in order to perform a behavior similar to break (actually not break out the loop before it reaches the end). Consider this simple example (adapted from the one in the posted blog) that checks the existence of the number 1 in a vector:

Code: Select all
int avanti=0;
#pragma omp parallel for default(none) shared(avanti,N,A) private(i)
for(i=0;i<N;i++)
{
#pragma omp flush(avanti)
    if(avanti)
    {
#pragma omp critical(checkIfOne)
{
        if(A[i]==1)
        {
            avanti = 0;
#pragma omp flush(avanti)
        }
}
    }
}


My question is: is neccesary to use flush() in both places before the if(avanti) and after the avanti=0? I think that only after avanti=0 is sufficient. Is flush() correctly used after avanti=0, or can be changed its place by the optimization options of the compiler? Which is in your opinion the correct way to simulate the break behavior in an OpenMP for loop?

Thanks
jgpallero
 
Posts: 11
Joined: Fri May 11, 2012 1:47 am

Re: Break a parallel loop

Postby MarkB » Mon May 14, 2012 12:12 pm

jgpallero wrote:My question is: is neccesary to use flush() in both places before the if(avanti) and after the avanti=0? I think that only after avanti=0 is sufficient. Is flush() correctly used after avanti=0, or can be changed its place by the optimization options of the compiler?


The flush before the if(avanti) is certainly necessary to prevent the compiler reading the value from registers.
Flushes cannot be reordered with respect to writes/reads to variables in the list on the flush directive.
MarkB
 
Posts: 428
Joined: Thu Jan 08, 2009 10:12 am

Re: Break a parallel loop

Postby MarkB » Tue May 15, 2012 1:53 am

Actually, I'm very reluctant to advocate the use of flush, so here's a flush-free solution:

Code: Select all
   
int abort=0;
#pragma omp parallel default(none) shared(abort,N,A)
{
    int done = 0;
    int i = omp_get_thread_num();
    int nthreads = omp_get_num_threads();

    while (!done)
    {
    #pragma omp critical(checkIfOne)
       {
            if(A[i]==1)
            {
                abort = 1;
            }
            i += nthreads;
            done = (i >= N) || abort;
       }
    }
}


This is equivalent to schedule(static,1), so if you want another schedule you would need to modify the code accordingly.
MarkB
 
Posts: 428
Joined: Thu Jan 08, 2009 10:12 am

Re: Break a parallel loop

Postby jgpallero » Thu May 17, 2012 2:19 am

MarkB wrote:
jgpallero wrote:My question is: is neccesary to use flush() in both places before the if(avanti) and after the avanti=0? I think that only after avanti=0 is sufficient. Is flush() correctly used after avanti=0, or can be changed its place by the optimization options of the compiler?


The flush before the if(avanti) is certainly necessary to prevent the compiler reading the value from registers.
Flushes cannot be reordered with respect to writes/reads to variables in the list on the flush directive.


But when the loop begins the value of 'avanti' is the same as in its declaration int avanti=0; so the first time all threads read avanti=0. If one of them checks A[i]==1, 'avanti' is changed to avanto=1 and the flush() inside the if(A[i]==1) sets the new value to all 'avanti' private copie for each thread, so in the next step of the loop 'avanti' is updated and I think that the first flush() is not neccessary. Of course, probably I'm wrong, but I don't understand why.

On the other hand, is planned for OpenMP 4.0 or future versions any system for breaking loops in the 'natural' way of using break; sentence?

Thanks
jgpallero
 
Posts: 11
Joined: Fri May 11, 2012 1:47 am

Re: Break a parallel loop

Postby MarkB » Thu May 17, 2012 3:02 am

But when the loop begins the value of 'avanti' is the same as in its declaration int avanti=0; so the first time all threads read avanti=0. If one of them checks A[i]==1, 'avanti' is changed to avanto=1 and the flush() inside the if(A[i]==1) sets the new value to all 'avanti' private copie for each thread, so in the next step of the loop 'avanti' is updated and I think that the first flush() is not neccessary. Of course, probably I'm wrong, but I don't understand why.


The OpenMP memory model is quite tricky to get your head around! The flush after the write does not update other threads' temporary views of memory. Threads that subsequently read the value must do a flush first to make sure they are reading the value from memory, and not from their own temporary view. In practice, this translates to making sure the compiler really does do loads and stores of the variable, instead of keeping it in registers.

On the other hand, is planned for OpenMP 4.0 or future versions any system for breaking loops in the 'natural' way of using break; sentence?


Sorry, no, there are no plans for such a feature. I think one objection would be that there is no way to make the set of iterations which would be executed in the parallel case the same as the sequential case (or even deterministic).
MarkB
 
Posts: 428
Joined: Thu Jan 08, 2009 10:12 am

Re: Break a parallel loop

Postby jgpallero » Thu May 17, 2012 3:14 am

MarkB wrote:
But when the loop begins the value of 'avanti' is the same as in its declaration int avanti=0; so the first time all threads read avanti=0. If one of them checks A[i]==1, 'avanti' is changed to avanto=1 and the flush() inside the if(A[i]==1) sets the new value to all 'avanti' private copie for each thread, so in the next step of the loop 'avanti' is updated and I think that the first flush() is not neccessary. Of course, probably I'm wrong, but I don't understand why.


The OpenMP memory model is quite tricky to get your head around! The flush after the write does not update other threads' temporary views of memory. Threads that subsequently read the value must do a flush first to make sure they are reading the value from memory, and not from their own temporary view. In practice, this translates to making sure the compiler really does do loads and stores of the variable, instead of keeping it in registers.

On the other hand, is planned for OpenMP 4.0 or future versions any system for breaking loops in the 'natural' way of using break; sentence?


Sorry, no, there are no plans for such a feature. I think one objection would be that there is no way to make the set of iterations which would be executed in the parallel case the same as the sequential case (or even deterministic).


In this last case I was thinking too in a way to check errors in a parallel loop. Imagine the serial code:

Code: Select all
for(i=0;i<N;i++)
{
    errorFlag = SomeFunction(someData);
    //check for errors
    if(errorFlag==isReallyAnError)
    {
        printf("Hey guy, an error occurs inside the for loop!\n");
        break;
    }
}


This is a normal way I use to break a loop when an error with some function occurs (or changing the break for a return sentence). I think that I could use a similar piece of code as in my first example in this thread, but it could be complicated in some cases if some allocation and free memory are implied.
jgpallero
 
Posts: 11
Joined: Fri May 11, 2012 1:47 am

Re: Break a parallel loop

Postby MarkB » Thu May 17, 2012 4:27 am

MarkB wrote:Sorry, no, there are no plans for such a feature.


Actually, this not correct, sorry! There are discussions about supporting a cancel construct to allow user termination of parallel regions and worksharing constructs.
MarkB
 
Posts: 428
Joined: Thu Jan 08, 2009 10:12 am

Re: Break a parallel loop

Postby jgpallero » Thu May 17, 2012 4:36 am

MarkB wrote:
MarkB wrote:Sorry, no, there are no plans for such a feature.


Actually, this not correct, sorry! There are discussions about supporting a cancel construct to allow user termination of parallel regions and worksharing constructs.


Mmmm... this sounds good, very good. As a user, I support the motion! :) As I said in my previous post, I think this feature valuable above all for termination of loops related to catch errors and similar.

Exist any roadmap about 4.0 version

Thanks
jgpallero
 
Posts: 11
Joined: Fri May 11, 2012 1:47 am

Re: Break a parallel loop

Postby MarkB » Thu May 17, 2012 6:41 am

jgpallero wrote:Exist any roadmap about 4.0 version


There's some information in the SC11 presentations linked from here: http://openmp.org/wp/resources/
MarkB
 
Posts: 428
Joined: Thu Jan 08, 2009 10:12 am

Re: Break a parallel loop

Postby chameleon » Thu May 17, 2012 1:06 pm

MarkB wrote:
On the other hand, is planned for OpenMP 4.0 or future versions any system for breaking loops in the 'natural' way of using break; sentence?

Sorry, no, there are no plans for such a feature. I think one objection would be that there is no way to make the set of iterations which would be executed in the parallel case the same as the sequential case (or even deterministic).

It is very simple:
break from thread A signals all other threads and pause on barrier after loop.
All other threads, when arrive in a line "#pragma omp thread_can_die_here_safely" die safely.
chameleon
 
Posts: 8
Joined: Mon Jan 23, 2012 6:37 pm

Next

Return to Using OpenMP

Who is online

Users browsing this forum: Exabot [Bot], Google [Bot], Yahoo [Bot] and 7 guests

cron