Compute Parallel within a Loop-Iteration

General OpenMP discussion

Compute Parallel within a Loop-Iteration

Postby nullspace » Mon Jul 23, 2012 12:22 am

Hi!

I already parallized my first few loops for an interesting math/mechanics algorithm. Right now, I am standing before a more intesting piece of code which I want to parallelize. The problem is that I (as far as I understood) encountered a race condition.

Basically, I cannot resolve this race condition. However, I want to split up every iteration of the loop into multiple threads which each compute different things.

Let me write the programm structure in some simplified pseudo code:
Code: Select all
/* Initialize */
N[N-1]  = 1;
M1[N-1] = 0;
M2[N-1] = 0;

/* Loop */
for ( i = N-2 ; i => 0 ; i-- )
{   
    M1[i] = computeM1(M1[i+1], N[i+1]);
    M2[i] = computeM2(M2[i+1], N[i+1]);
   
    N[i] = computeN(M1[i],M2[i],N[i+1]);
}

Is it possible to have one thread computing M1[i], another one computing M2[i] and when they both are finished N[i] should be computed by an already waiting third thread. Then head on to the next iteration. Over and over again until the loop is finished.

I'd also want to create the threads before the loop to keep the administrative times as low as possible.

Is this possible? If yes, which openMP directives will I need?

Thanks alot and kind regards,
yours Roland
nullspace
 
Posts: 3
Joined: Thu Jul 19, 2012 10:54 pm

Re: Compute Parallel within a Loop-Iteration

Postby nullspace » Tue Jul 24, 2012 1:58 am

Hi Again!

My first try:
/* Initialize */
N[N-1] = 1;
M1[N-1] = 0;
M2[N-1] = 0;

/* Loop */
#pragma omp parallel num_threads(3) private(i) default(shared)
for ( i = N-2 ; i => 0 ; i-- )
{
#pragma omp barrier
switch ( omp_get_thread_num() )
{
case 0:
M1[i] = computeM1(M1[i+1], N[i+1]);
break;
case 1:
M2[i] = computeM2(M2[i+1], N[i+1]);
break;
}
#pragma omp barrier
if ( omp_get_thread_num() = 2 )
{
N[i] = computeN(M1[i],M2[i],N[i+1]);
}
}

Unfortunately, it is not very performant. Is there a more efficient way to parallelize this problem ?
Or is my problem not well suited for parellelization ?

Regards, Roland

PS: Sorry, tabs for readability dont seem to work.
nullspace
 
Posts: 3
Joined: Thu Jul 19, 2012 10:54 pm

Re: Compute Parallel within a Loop-Iteration

Postby MarkB » Tue Jul 24, 2012 4:30 am

Your problem really isn't suited to parallelisation! Apart from being able to compute M1[i] and M2[i] at the same time, the dependencies prevent any additional parallelism. I can't really see any way to improve your solution, except to observe that there's no real need for the third thread: the computation of N[i] might as well be done by thread 0 (or thread 1).
MarkB
 
Posts: 450
Joined: Thu Jan 08, 2009 10:12 am
Location: EPCC, University of Edinburgh

Re: Compute Parallel within a Loop-Iteration

Postby nullspace » Tue Jul 24, 2012 4:41 am

Thanks for your answer!

It could probably have worked if the computation of M1 and M2 would consume alot of time. However, as it turned out, they are (un)fortunately less complex than I've expected.

The positive side effect: I learned a lot about openMP the last days and I really like it.
nullspace
 
Posts: 3
Joined: Thu Jul 19, 2012 10:54 pm


Return to Using OpenMP

Who is online

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