Page 1 of 1

### Compute Parallel within a Loop-Iteration

Posted: 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

### Re: Compute Parallel within a Loop-Iteration

Posted: 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
{
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

Posted: 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).

### Re: Compute Parallel within a Loop-Iteration

Posted: Tue Jul 24, 2012 4:41 am