20160927, 16:35  #1 
"Curtis"
Sep 2016
Fort Collins, CO
10_{10} Posts 
New GPU accelerated sieve of Eratosthenes
Hey guys,
I just put the code online (https://github.com/curtisseizert/CUDASieve) for a sieve that I've been working on that could perhaps be useful to other people. It contains an implementation of Tomás Oliveira e Silva's bucket algorithm, so it doesn't slow down horrendously at higher ranges. I've verified the output in various intervals up to 2^58, but there are kinks that need to be ironed out above that. I'm somewhat new to this type of thing, but I am interested in making this useful to other people, so if there is some way that I can do that, let me know. Oh, and I'm looking forward to checking this forum out. Maybe soon I'll be able to accomplish my life goal of understanding Hardy and Wright. Curtis 
20160928, 00:12  #2 
"Curtis"
Feb 2005
Riverside, CA
5166_{10} Posts 
Curtis
What number forms does it handle, in what formats? Curtis 
20160928, 00:46  #3 
"Curtis"
Sep 2016
Fort Collins, CO
1010_{2} Posts 
It's actually just a humble sieve of Eratosthenes.

20160928, 01:25  #4 
"Ben"
Feb 2007
2×11×163 Posts 
Not so humble though... it is quite fast. Here are some timings on Curtis's github site compared to the top of the line cpu sieves (running single threaded on my haswell i3 laptop)
Code:
range yafu 1.35beta primesieve cseizert 2^40  2^40 + 2^30 0.581 0.598 0.137 2^50  2^50 + 2^30 1.19 0.939 0.143 0  10^10 2.26 3.02 0.168 0  10^12 375 524 13.1 Nice work Curtis! Last fiddled with by bsquared on 20160928 at 01:27 Reason: formatting and range column edits 
20160928, 05:11  #5 
"Curtis"
Sep 2016
Fort Collins, CO
2×5 Posts 
Thanks Ben! It is indeed memory access, specifically to the list of sieving primes, that is slowing it down the most. Higher ranges are on their way, and I'll have to take a look at yafu.

20160929, 06:49  #6 
Jan 2008
France
1046_{8} Posts 
Impressive results, congratulation
Talking about sieves, did anyone see this: http://www.scientificamerican.com/ar...primenumbers/ New Take on an Ancient Method Improves Way to Find Prime Numbers Harald Helfgott has reduced the memory requirements for sieving. I wonder if this has any practical impact. Can't wait to read the article. 
20160929, 13:51  #7  
Aug 2006
3×1,993 Posts 
Quote:


20160929, 15:04  #8 
"Curtis"
Sep 2016
Fort Collins, CO
10_{10} Posts 
As of last night I got the top of the usable range up to 2^642^35! I'm pretty happy about that. I had been stymied by the fact that an intermediate value in a calculation was being stored in a 32 bit register, and this intermediate would hit a maximum of about 2^34.5. Since changing a single 32 to a 64 in the code (blah!), I haven't found any examples of ranges where the output is less than a complete list of only prime numbers in that interval. I'm working on automating correctness tests today so that I can make sure of this while I'm asleep.
The method in that article would be intersesting interesting possibility. My library access at the university I recently graduated from was revoked a couple weeks ago otherwise I would see if the abstracts of this meeting had been published. I've been thinking about feasibility of trying to tackle the challenge of moving this sieve into ranges above 64 bits, but among other things, the amount of memory required for this implementation would go through the roof pretty quickly. Actually, you'd hit 8 GB of memory necessary to hold the data set at about 2^68, so it really would not be worth it. It seems like, with my knowledge anyway, it would be best to partially sieve with, for example, all the primes up to 2^30 and then use some primality test to cross off the rest of the composites. Obviously, this is not a new idea. That said, there are more important things in this project as well as in my life in general than getting this sieve above 2^64. Thanks for the love on the results guys! Very encouraging. I will say that it's kind of cheating to compare GPU results to CPU ones, especially if the latter are based on a single thread. But hey, I'll take it! 
20161027, 05:55  #9  
"Gang aft agley"
Sep 2002
2×1,877 Posts 
Quote:
Quote:
Quote:
I found some pdf slides in Spanish from this Google+ post slides (57 slides) Quote:
Last fiddled with by only_human on 20161027 at 06:34 Reason: found some pdf slides. Removed "/view" from slide URL  I think my browser appended that. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Sieve of Eratosthenes  bhelmes  Number Theory Discussion Group  43  20180313 01:04 
Hardware accelerated LL Testing  TObject  Hardware  32  20130509 18:17 
Thinking of a new project: Sieve of Eratosthenes  XYYXF  Computer Science & Computational Number Theory  91  20130119 12:19 
Sieve of Eratosthenes  Raman  Programming  4  20090119 17:12 
Sieve of Eratosthenes  jchein1  Homework Help  6  20070827 13:51 