Sieve of Eratosthenes by Data parallel method

Question

I am trying to implement the Sieve of Eratosthenes problem by data parallel method using pthreads, but I am not able to figure out how does thread-1 on finding "2" is a prime number broadcast that to all the other threads and when all the other threads mark multiples of 2 they should wait again for the next prime. How will the multiple wait for the threads be implemented?

Answer 1

Before looking at the actual program constructs, you first need to get your algorithm right. I think you have a problem finding a function here because you do not have a proper algorithm for a parallel sieve.

For starters, a key criterium in parallel algorithms is the distribution of work across threads. If all threads did precisely the same, there would be no speedup at all. But it's entirely unclear here what the work distribution is.

I am not even certain that your threads should be waiting. That's inefficient; the best designs are those where all threads are performing work at all times.