Life was throwing stones at me, so I turned to the parallel world for a sweet, simple and sexy adventure. Little did I know, that I will get hit by another revolting, wrecking boulder. Let me elaborate!
We have all met prime numbers in life. My adventure started off with a lucid attempt to write a code snippet that counts the number of prime numbers in a range. The vanilla approach involves finding factors of each number; counting primes as you iterate. But who likes vanilla? I wanted chocolate or strawberry!
There are plenty of fancy algorithms for primality testing - of which the I chose Miller-Rabin. Its is based on Fermat's theorem that states that if p is prime, then, ap-1 = 1(mod p) for any integer less than p.
Me : So, all I have to do is check if that condition is satisfied for all a.
The wiser me: But wait, how is that better from my vanilla method?
Me : Then, maybe I do it for just one such a.
The wiser me : But what if I am unlucky enough to select an a that satisfies on coincidence?
Me : Oh! I get it , I have to choose a small number of such a and deal with the error.
The wiser me : *rolls eyes* Finally!
As you pretty much guessed, asomething huge is pretty knotty to compute. There are tricks such as modular exponentiation, splitting into powers of 2 etc... that our prudent mathematicians have discovered. Let us take a moment to say arigato! Exploiting all such clever techniques, I proudly came up with a working version of prime.c. It was no child's play, especially for someone who can only see, not look!
Get to the parallelism already!
Broadly thinking, I could come up with two ways in which parallelism can be benefitted from.
Finally, a Mr.Robert Reed opened my eyes with this. rand() was the culprit! I was using rand() to pick those 'a' s and as it turns out, rand() is not thread-safe. Hence, all those calls to rand() were being done in serial. Added with the overhead of creating those threads, my parallel code was bound to be slower.
Moral of the story: Do not assume that you can parallelise anything and everthing; and also by the way, rand() is not always thread safe.
All relevant code and logs wills be found here. Happy coding in a parallel world! 😊
We have all met prime numbers in life. My adventure started off with a lucid attempt to write a code snippet that counts the number of prime numbers in a range. The vanilla approach involves finding factors of each number; counting primes as you iterate. But who likes vanilla? I wanted chocolate or strawberry!
There are plenty of fancy algorithms for primality testing - of which the I chose Miller-Rabin. Its is based on Fermat's theorem that states that if p is prime, then, ap-1 = 1(mod p) for any integer less than p.
Me : So, all I have to do is check if that condition is satisfied for all a.
The wiser me: But wait, how is that better from my vanilla method?
Me : Then, maybe I do it for just one such a.
The wiser me : But what if I am unlucky enough to select an a that satisfies on coincidence?
Me : Oh! I get it , I have to choose a small number of such a and deal with the error.
The wiser me : *rolls eyes* Finally!
As you pretty much guessed, asomething huge is pretty knotty to compute. There are tricks such as modular exponentiation, splitting into powers of 2 etc... that our prudent mathematicians have discovered. Let us take a moment to say arigato! Exploiting all such clever techniques, I proudly came up with a working version of prime.c. It was no child's play, especially for someone who can only see, not look!
Get to the parallelism already!
Broadly thinking, I could come up with two ways in which parallelism can be benefitted from.
- Parallelising the test for the numbers themselves
- Given a number, parallelising the test for the trials ( the a we spoke about earlier)
Finally, a Mr.Robert Reed opened my eyes with this. rand() was the culprit! I was using rand() to pick those 'a' s and as it turns out, rand() is not thread-safe. Hence, all those calls to rand() were being done in serial. Added with the overhead of creating those threads, my parallel code was bound to be slower.
Moral of the story: Do not assume that you can parallelise anything and everthing; and also by the way, rand() is not always thread safe.
All relevant code and logs wills be found here. Happy coding in a parallel world! 😊
No comments:
Post a Comment