Page 1 of 1

Compute Parallel within a Loop-Iteration

PostPosted: Mon Jul 23, 2012 12:22 am
by nullspace
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

Re: Compute Parallel within a Loop-Iteration

PostPosted: Tue Jul 24, 2012 1:58 am
by nullspace
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.

Re: Compute Parallel within a Loop-Iteration

PostPosted: Tue Jul 24, 2012 4:30 am
by MarkB
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).

Re: Compute Parallel within a Loop-Iteration

PostPosted: Tue Jul 24, 2012 4:41 am
by nullspace
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.