mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Hardware > GPU Computing

Reply
 
Thread Tools
Old 2010-06-11, 15:19   #177
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

3·2,083 Posts
Default

Hi msft,

Having observed the development effort of this CUDA LL testing application over time, I see that it's already faster than Prime95 on a modern CPU and as such represents a significant speedup for GIMPS once it's distributed more widely. However, I can't help but wonder how hard it would be to modify this program to utilize the Lucas-Lehmer-Riesel test--it is a very small modification of the Lucas-Lehmer test that allows it to test numbers of the form k*2^n-1, a.k.a. Riesel primes, versus LL's 2^n-1. As you can see from the Wikipedia pages linked here, the two tests differ only in their starting value: for LL it is always 4, whereas for LLR it is determined by a dynamic formula based on the value of k.

I co-adminstrate the "No Prime Left Behind" project (which can be found in the "Prime Search Projects" section of this forum) along with Gary Barnes (who goes by gd_barnes on this forum), a project which tests k*2^n-1 numbers for primality. The other day we were discussing GPUs and the recent advances in LL testing, and were thinking how big a boost it would be for NPLB (and all the other myriad projects that search Riesel primes) if this application could be modified for the LLR test. Neither of us have any CUDA programming knowledge, and thus wouldn't be able to make the code changes ourselves. However, we would be willing to help test such an application if it was developed. Gary said that he would be willing to purchase a reasonably fast CUDA-capable GPU for the purposes of testing such a CUDA LLR application if progress was begun on development of such; I could then (via remote access to his system) assist in debugging and verifying the accuract of the application. NPLB has tons of residuals from the various LLR tests we've done, so we'd have plenty of material with which to doublecheck the GPU's accuracy.

Note that the tests NPLB is doing are much smaller than GIMPS's: mostly for n<1M, with some between 1M and 2M. Other projects test higher n, though usually no higher than 10M at the max. (Since k is a variable for Riesel primes, and they don't have all the handy factoring "shortcuts" available for Mersenne numbers, needless to say, Riesel primes haven't been advanced nearly as far in terms of n yet.) This translates into smaller FFTs, usually less than 100K, that would be primarily used in such an LLR program.

Would you (or anyone else here with CUDA experience) be interested in embarking on such an effort? I estimate that the code change to MacLucasFFTW to make it do LLR tests would be rather trivial; perhaps more consuming would be the optimization of the smaller FFTs most commonly used in the program. However, since such optimization would take place within the FFT library itself as opposed to the LLR-specific code, such improvements would benefit the LL test application as well.

Thanks,
Max
mdettweiler is offline   Reply With Quote
Old 2010-06-11, 19:11   #178
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

16ED16 Posts
Default

Max, if you look at the end of the llr 3.8 thread you will see that Jean is developping llr to be half way there to using cuda. He will be using the same or very similar(there was also not mention of mac) fft library I think but a non-CUDA version.

Another option would be to rip the llr code(working out the starting value etc.) from LLR and adding it into the CUDA program we have here. That would be a lot of the work done. We would have to ask permission of course but I am pretty certain that he would support it.

edit: i seem to remember that primegrid have developed a CUDA sieve that might be helpful to NPLB. they might be willing to help make a CUDA llr.

Last fiddled with by henryzz on 2010-06-11 at 19:14
henryzz is offline   Reply With Quote
Old 2010-06-11, 19:32   #179
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

23·32·29 Posts
Default

Changing the starting value is easy. Changing the modulus in each iteration may be more involved?

Last fiddled with by frmky on 2010-06-11 at 19:33
frmky is online now   Reply With Quote
Old 2010-06-11, 20:19   #180
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

3·2,083 Posts
Default

Quote:
Originally Posted by henryzz View Post
Max, if you look at the end of the llr 3.8 thread you will see that Jean is developping llr to be half way there to using cuda. He will be using the same or very similar(there was also not mention of mac) fft library I think but a non-CUDA version.

Another option would be to rip the llr code(working out the starting value etc.) from LLR and adding it into the CUDA program we have here. That would be a lot of the work done. We would have to ask permission of course but I am pretty certain that he would support it.

edit: i seem to remember that primegrid have developed a CUDA sieve that might be helpful to NPLB. they might be willing to help make a CUDA llr.
Ah, I forgot about Jean's mention of that. However, I was thinking that it might simply be easier to modify this program; after all, as frmky said, it's easy enough to change the starting value the program uses, which AFAIK is the only difference between LL and LLR. I expect that would be easier even than trying to integrate Jean's existing LLR code with this code's CUDA FFT library.

I wasn't aware that PrimeGrid had a CUDA sieve. Does it work for k*b^n+-c numbers, or only for one of their other types of searches (AP26, etc.)?
Quote:
Originally Posted by frmky View Post
Changing the starting value is easy. Changing the modulus in each iteration may be more involved?
Hmm, I didn't think of that. How much harder do you think it would be?
mdettweiler is offline   Reply With Quote
Old 2010-06-12, 11:42   #181
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

4,813 Posts
Default

As for CUDA-enabled sieves, I have been pointed to Ken_g5 ppsieve.

I compiled it under both Linux and Windows, but I had problems passing an ABC(D) file to it.

Anybody here having hints?

Luigi
ET_ is offline   Reply With Quote
Old 2010-06-13, 08:42   #182
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

5,869 Posts
Default

Quote:
Originally Posted by ET_ View Post
As for CUDA-enabled sieves, I have been pointed to Ken_g5 ppsieve.

I compiled it under both Linux and Windows, but I had problems passing an ABC(D) file to it.

Anybody here having hints?

Luigi
Yes thats the one http://www.primegrid.com/forum_thread.php?id=1737
henryzz is offline   Reply With Quote
Old 2010-06-13, 13:20   #183
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

4,813 Posts
Default

Quote:
Originally Posted by henryzz View Post
Maybe I made errors while explainig...

I correctly compiled and run ppsieve on Linux.

I don't need the file with the factors.

I need a siever like the one I downloaded from Ken's page, able to read and update an ABC(D) file, because the version I have just can't (or has hidden parameters I can't see).

That's why I asked for help.

Luigi
ET_ is offline   Reply With Quote
Old 2010-06-13, 13:34   #184
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

16ED16 Posts
Default

Quote:
Originally Posted by ET_ View Post
Maybe I made errors while explainig...

I correctly compiled and run ppsieve on Linux.

I don't need the file with the factors.

I need a siever like the one I downloaded from Ken's page, able to read and update an ABC(D) file, because the version I have just can't (or has hidden parameters I can't see).

That's why I asked for help.

Luigi
Do you mean you need a program that produces files you can feed to ppsieve?
If so try googling srsieve.
henryzz is offline   Reply With Quote
Old 2010-06-14, 12:34   #185
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

4,813 Posts
Default

Quote:
Originally Posted by henryzz View Post
Do you mean you need a program that produces files you can feed to ppsieve?
If so try googling srsieve.
No...

Issue 1:

I have a correct ABCD file, produced by FermFact.
The file is correct, as pfgw reads it with no problem.

When I feed ppsieve with that ABCD file, ppsieve says it can't recognize the file.
---

Issue 2:

When I try to run ppsieve from scratch, all I can get is a "factors" file. No ABC or D file.

Luigi
ET_ is offline   Reply With Quote
Old 2010-06-14, 12:39   #186
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

3·2,083 Posts
Default

Quote:
Originally Posted by ET_ View Post
No...

Issue 1:

I have a correct ABCD file, produced by FermFact.
The file is correct, as pfgw reads it with no problem.

When I feed ppsieve with that ABCD file, ppsieve says it can't recognize the file.
---

Issue 2:

When I try to run ppsieve from scratch, all I can get is a "factors" file. No ABC or D file.

Luigi
I believe ppsieve only works with k*2^n+-1 numbers (base 2 Riesel/Proth) [Issue 1] and it's designed to continue sieves already started with a program like srsieve, not start a fresh sieve [Issue 2].
mdettweiler is offline   Reply With Quote
Old 2010-06-14, 12:54   #187
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

113158 Posts
Default

Quote:
Originally Posted by mdettweiler View Post
I believe ppsieve only works with k*2^n+-1 numbers (base 2 Riesel/Proth) [Issue 1] and it's designed to continue sieves already started with a program like srsieve, not start a fresh sieve [Issue 2].
Thank you, so Issue 2 is cleared

As for k*2^n+/-1, they are quite the numbers I'm sieving as possible Fermat factors...

Luigi
ET_ is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Don't DC/LL them with CudaLucas LaurV Data 131 2017-05-02 18:41
CUDALucas / cuFFT Performance on CUDA 7 / 7.5 / 8 Brain GPU Computing 13 2016-02-19 15:53
CUDALucas: which binary to use? Karl M Johnson GPU Computing 15 2015-10-13 04:44
settings for cudaLucas fairsky GPU Computing 11 2013-11-03 02:08
Trying to run CUDALucas on Windows 8 CP Rodrigo GPU Computing 12 2012-03-07 23:20

All times are UTC. The time now is 06:41.

Fri May 7 06:41:47 UTC 2021 up 29 days, 1:22, 0 users, load averages: 2.61, 2.29, 2.19

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.