Primes and multi-threading

Question

I use to compute primes using linear code which took a long time. As I've an 8 cores processor I thought about multi-threading.

At first I use to put a huge number of int in a vector then share the vector between the threads which takeout each number which is not a prime. The first thread processed the 1st/nthread part, the second processed the 2nd/nthread and so on. Which leads me to a resource issue due to concurrent access.

Then I tried to split the vector in nthread vectors to give one vector to each thread, removing concurrent access issue. But I'm not convinced that it's the best way to do it since processing the primes from 1 to 10 000 is faster than processing primes form 10 001 to 20 000.

• Is there a better way to take profit of the multi-threading ?
• If no, what is the best way to split vectors so the thread would take the same time ?

Answer 1

Option 1 - Probable distribution from a Math's forum

In order to distribute "fairly" upfront, you would need to understand the most probable distribution of primes. I suspect that there are good algorithms for doing that, but that would be quite academic. Such questions are best suited for a Math's forum to determine an algorithm to partition a search space in such decreasing sizes.

Option 2 - Smaller Blocks

A simpler ignorant approach would be to create smaller "blocks" of search space, and have the threads reserve the next block when they run out of work.

For example:

• The search space is fixed at: 1 - 20,000.
• There are 8 threads
• Block size is 1000
• A global NextBlock variable is set to 1.
• Each thread increments NextBlock by 1000 and reads the result (using a CPU atomic ADD operation).
• The result is the upper bound for that thread to complete.

You would then optimise the BlockSize according to trial and error. You might find that if you make the block size 1 the aggregate throughput is way too slow. If the block size is 2000, you might find 1 thread remaining for 200ns longer than the rest.

---

This is probably not a common real-world issue

By the way, usually you would be simply searching for "new" primes, not particularly searching within such a small range as you indicated. In this case, the search space might be chosen to take 1-min, then the Threads can use locking mechanisms to reserve the next "block".

Optimisation in the order of even 1 second of assymetric duty on CPUs feels like over-optimisation to me.