0

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 ?
8
  • There's an excellent article here covering several techniques for multi-threading prime calculation. Apr 2, 2014 at 8:58
  • @OldCurmudgeon I'll take a look and hope it'll fit with C++, thanks. Apr 2, 2014 at 9:22
  • @OldCurmudgeon That link looks like it's only about Fibonacci. Oct 8, 2021 at 14:22
  • There are a number of algorithms which are substantially faster than the Sieve of Eratosthenes. Some are at least an order of magnitude faster. However, the main blockage would be how you represent integers. Oct 8, 2021 at 16:16
  • @BobDalgleish, that's interesting. Could you give some reference for this?
    – gnasher729
    Oct 10, 2021 at 15:07

1 Answer 1

2

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.

6
  • "the most probable distribution of primes." I'm 99% sure there is no such thing more precise than the prime number theorem which just states how (in)frequently they appear as the numbers get larger, but other than that you have to test every number in the vicinity for primality. Oct 10, 2021 at 6:48
  • @whatsisname infrequency is the same as frequency. "but other than that you have to test every number in the vicinity for primality." - that's not a "probable" distribution, that's the "actual" distribution. I was talking about a "guess" for the distribution of primes. I'm very sure that exists, but we can find out for sure - math.stackexchange.com/questions/4273186/… Oct 10, 2021 at 23:16
  • 1
    JWTanner comments on Math: The number of primes up to xis approximately x / (ln x) Oct 10, 2021 at 23:21
  • That number of primes is the formula for the prime number theorem, which is what I mentioned. Oct 11, 2021 at 4:45
  • There is an older answer for this - math.stackexchange.com/questions/642775/… Oct 11, 2021 at 23:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.