Today we will test how fast we can check if a large number ( 19 digit ) is prime. I written a classical sequential algorithm and an Aparapi parallel version and here are the results:
There is a massive 50X improvement over the sequential algorithm and a very good 14X improvement over the parallel version run on CPU. I don't know why we didn't see the same 40X improvement like in the previous 2 algorithm but 14X is still very good.
The sequential version just checks each number for 3 to sqrt(n) if it divides n.
The parallel version splits the interval [3, sqrt(n)] in 128*1028 equal intervals and the number from each interval are checked by a " GPU thread " ( I'am not sure what is the right terminology for this ).
Probably you wonder why 128*1028 intervals? I tested with different number of interval and this offered the best performance, this is probably caused by the fact the GPU is very efficient in switching between and allocating resources to threads and a larger number of threads will maximize the resource utilization ( this is just my empirical explanation )
Results ( spreadsheet ) and Java code
No comments:
Post a Comment