How can I parallize using pthread

[menayah]

Hi all,

How can i parallize this code in pthread?

for(round=1;round<=16;round++)
{
Expansion(mid, 17 - round - 1, left);
Expansion(mid, round - 1, right);
round++;
Expansion(right, 17 - round - 1, mid);
Expansion(left, round - 1,mid);

}

Whereby each loop depend on the previous result from the first loop...

Thanks & Regards

[drl]

Hi.

If you mean by:

Whereby each loop depend on the previous result from the first loop...

first being previous, then in general, parallel calculation essentially becomes serial calculation. There are some constructions that allow parallelization even though the form appears recursive. See Automatic parallelization - Wikipedia, the free encyclopedia for an example.

We can't tell exactly what depends on what in your code because you have buried it in function calls. However, I find that the work involved in parallelization is rarely worth the time (well, my time, anyway). If an optimizing compiler can't figure it out, I probably couldn't get it right.

If this is for increasing speed, then loop unrolling could give you a little speed-up on some architectures, but the code would need to be more exposed for the compiler to see it.

Still, don't despair, it's possible that an expert will stop here and give you better and more insightful advice. This would be definitely the case if this is an academic exercise for you to learn pthreads (I'm guessing here -- I haven't used any of the gritty, detailed features for the reason mentioned above).

Best wishes ... cheers, drl

[Cabhan]

So, if each iteration of the loop requires all previous iterations to have been completed, then it seems to me that you cannot run the iterations in parallel. This is, in fact, exactly what optimizing/parallelizing compilers try to do: they detect if loop iterations depend on each other, and if not, they add threads.

So, is anything parallelizeable here? Well, depending on how complicated the Expansion() function is (and assuming, of course, that the Expansion() calls are not dependent on each other), there might be something to be gained in parallelizing those calls.

If all that you want to do is see an example of a parallelizeable loop for practice, here's a fairly trivial one:

int i;
int powers_of_2[10];

/* calculate the first 10 powers of 2 */
for(i = 0; i < 10; i++)
    powers_of_2[i] = pow(2, i);

I've done some work with writing massively parallel code, and while it's very cool, it can be difficult to get your algorithm into the appropriate form for parallelization, and it tends to only be worth it for extremely large data sets. If you're doing this for practice, then good luck, but if you're doing it for production, you might want to step back and decide if it's worth it.

[menayah]

Thank you both for the reply...

Drl: "If this is for increasing speed, then loop unrolling could give you a little speed-up on some architectures, but the code would need to be more exposed for the compiler to see it."

You are right, this is wat im doing now, i have done loop unrolling but i need additional help regarding thread wait...

im working with 2 threads currenlty, while both threads are running in one point Both threads need to update a value ( same as counter ) which im using mutix for that, But I need the final counter value to be used in the 2 threads...

Example ( thread 1 and thread 2 reads counter value then do some process then both will update counter then both should read the final counter value then procces)

How do I solve it in a proper why ?
Using Condition signal and wait should be great But both threads are using the same Function Expansion. Cuz as far as i read cond_wait and Cond_signal is placed by different functions.

A temporary solution for 2 threads that i have done shown below but its CPU cycle consuming cuz its using While loop.

// wait for both threads to reach the same point so they can read an updated value from both of them

if ( thread_id == 0 )
while ((t0_round > t1_round) && (t0_round != 0))
{
if (t0_round <= t1_round) break;
}
else
while ((t1_round > t0_round) && (t1_round != 0))
{
if (t1_round <= t0_round) break;
}