Fast Mersenne Testing on the GPU using CUDA

Andrew Thall · 2010-12-07, 15:15

I'd like to announce the implementation of a Lucas-Lehmer tester, gpuLucas, written in CUDA and running on Fermi-class NVidia cards. It's a full implementation of Crandall's IBDWT method and uses balanced integers and a few little tricks to make it fast on the GPU.

Example timing: demonstrated primality of M_42643801 in 57.86 hours, at a rate of 4.88 msec per Lucas product. This used a DWT runlength of 2,359,296 = 2¹⁸*3², taking advantage of good efficiency for CUFFT runlengths of powers of small primes. Maximum error was 1.8e-1.

gpuLucas has been tested on GTX 480 and Tesla 2050 cards; there's actually very little difference in runtimes between the two...fears of a performance hit due to slow floating point on the 480 are bogus---it's a wicked fast card for the GPGPU stuff; you get an additional 32 CUDA cores in place of the faster double precision, and it's clocked much faster than the Tesla. The Tesla only really shines when you overclock the heck out of it; I ran it up to 1402 Mhz for the above test, at which point it is 15-20% faster than the GTX for the big Mersenne numbers. (It depends on the FFT length, though, and when the greater number of processors on the GTX are offset by slower double precision, which is only used in the FFTs anyway.)

Finishing off a paper on the topic, and will post a pre-print here in a week or so. I'll make the code available publicly as well, and maybe set up a tutorial webpage if folks are interested and if time permits.

msft · 2010-12-07, 20:14

Hi ,Andrew Thall
Congratulations !

TimSorbet · 2010-12-07, 20:39

When they use the same FFT lengths, how does the speed of this program compare to MacLucasFFTW? In any case, the flexibility of having non-power-of-2 FFTs makes it a very attractive choice compared to MacLucasFFTW.

CRGreathouse · 2010-12-07, 22:47

Quote:

Originally Posted by Andrew Thall

Finishing off a paper on the topic, and will post a pre-print here in a week or so. I'll make the code available publicly as well, and maybe set up a tutorial webpage if folks are interested and if time permits.

I'd love to see those if/when you get to them.

Uncwilly · 2010-12-08, 00:50

A verification run in 3 days!?!?!

Brain · 2010-12-08, 00:57

We are very interested. I would buy a GTX 460 just for running your program. ;-) Verification in 3 days? Wow. What would CUDALucas have needed?

msft · 2010-12-08, 01:21

Quote:

Originally Posted by Brain

What would CUDALucas have needed?

9.04 (ms/iter) / 4.88 (msec) * 57.86 (hours) = 107.2 (hours)

ixfd64 · 2010-12-08, 02:04

I'm usually a bit leery when a brand new user makes such a bold claim; after all, we do get a fair share of trolls and cranks here (for example, someone recently claimed to have written an OpenCL-enabled siever but following up after his second post).

However, I am 99% sure that this is legit because the OP in this thread seems to know what he is talking about. If the "gpuLucas" really works as claimed, it will greatly benefit the GIMPS community.

Mathew · 2010-12-08, 02:14

http://andrewthall.org/

ixfd64 · 2010-12-08, 02:52

Quote:

Originally Posted by Mathew Steine

http://andrewthall.org/

This is the real deal, then!

No offense to msft, but it looks like that CUDALucas just got owned!

msft · 2010-12-08, 03:17

Quote:

Originally Posted by ixfd64

No offense to msft, but it looks like that CUDALucas just got owned!

I can change name to "YLucas" ,"Y" is my Initial.

2010-12-07, 15:15	#1
Andrew Thall Dec 2010 2³ Posts	Fast Mersenne Testing on the GPU using CUDA I'd like to announce the implementation of a Lucas-Lehmer tester, gpuLucas, written in CUDA and running on Fermi-class NVidia cards. It's a full implementation of Crandall's IBDWT method and uses balanced integers and a few little tricks to make it fast on the GPU. Example timing: demonstrated primality of M_42643801 in 57.86 hours, at a rate of 4.88 msec per Lucas product. This used a DWT runlength of 2,359,296 = 2¹⁸*3², taking advantage of good efficiency for CUFFT runlengths of powers of small primes. Maximum error was 1.8e-1. gpuLucas has been tested on GTX 480 and Tesla 2050 cards; there's actually very little difference in runtimes between the two...fears of a performance hit due to slow floating point on the 480 are bogus---it's a wicked fast card for the GPGPU stuff; you get an additional 32 CUDA cores in place of the faster double precision, and it's clocked much faster than the Tesla. The Tesla only really shines when you overclock the heck out of it; I ran it up to 1402 Mhz for the above test, at which point it is 15-20% faster than the GTX for the big Mersenne numbers. (It depends on the FFT length, though, and when the greater number of processors on the GTX are offset by slower double precision, which is only used in the FFTs anyway.) Finishing off a paper on the topic, and will post a pre-print here in a week or so. I'll make the code available publicly as well, and maybe set up a tutorial webpage if folks are interested and if time permits.

2010-12-07, 20:39	#3
TimSorbet Account Deleted "Tim Sorbera" Aug 2006 San Antonio, TX USA 11·389 Posts	When they use the same FFT lengths, how does the speed of this program compare to MacLucasFFTW? In any case, the flexibility of having non-power-of-2 FFTs makes it a very attractive choice compared to MacLucasFFTW. Last fiddled with by TimSorbet on 2010-12-07 at 20:40

2010-12-08, 00:57	#6
Brain Dec 2009 Peine, Germany 101001011₂ Posts	Sounds great We are very interested. I would buy a GTX 460 just for running your program. ;-) Verification in 3 days? Wow. What would CUDALucas have needed? Last fiddled with by Brain on 2010-12-08 at 00:58

2010-12-08, 02:04	#8
ixfd64 Bemusing Prompter "Danny" Dec 2002 California 3·7²·17 Posts	I'm usually a bit leery when a brand new user makes such a bold claim; after all, we do get a fair share of trolls and cranks here (for example, someone recently claimed to have written an OpenCL-enabled siever but following up after his second post). However, I am 99% sure that this is legit because the OP in this thread seems to know what he is talking about. If the "gpuLucas" really works as claimed, it will greatly benefit the GIMPS community. Last fiddled with by ixfd64 on 2010-12-08 at 02:06

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
mfaktc: a CUDA program for Mersenne prefactoring	TheJudger	GPU Computing	3624	2023-02-15 18:56
Do normal adults give themselves an allowance? (...to fast or not to fast - there is no question!)	jasong	jasong	35	2016-12-11 00:57
Find Mersenne Primes twice as fast?	Derived	Number Theory Discussion Group	24	2016-09-08 11:45
TPSieve CUDA Testing Thread	Ken_g6	Twin Prime Search	52	2011-01-16 16:09
Fast calculations modulo small mersenne primes like M61	Dresdenboy	Programming	10	2004-02-29 17:27

2010-12-07, 20:14	#2
msft Jul 2009 Tokyo 610₁₀ Posts	Hi ,Andrew Thall Congratulations !

2010-12-08, 00:50	#5
Uncwilly 6809 > 6502 """"""""""""""""""" Aug 2003 101×103 Posts 31×353 Posts	A verification run in 3 days!?!?!

2010-12-08, 02:14	#9
Mathew Nov 2009 350₁₀ Posts	http://andrewthall.org/