llrCUDA

[msft]

Hi ,mdettweiler

Originally Posted by mdettweiler

Cool! That easily covers the k-ranges tested by many of the larger projects (NPLB, RPS, PrimeGrid, even TPS to some degree).

But too slow.
1000065*2^390927-1 is prime! Time : 11376.660 sec.
3*2^303093+1 is prime! Time : 514.715 sec.
3*2^164987-1 is prime! Time : 42.509 sec.
1000065*2^220897-1 is prime! Time : 3059.852 sec.
39*2^113549+1 is prime! Time : 84.064 sec.
3*2^414840-1 is prime! Time : 210.427 sec.
9999*2^458051+1 is prime! Time : 1842.025 sec.
1000065*2^390927-1 is prime! Time : 11376.660 sec.

[mdettweiler]

Originally Posted by msft

Hi ,mdettweiler

But too slow.
1000065*2^390927-1 is prime! Time : 11376.660 sec.
3*2^303093+1 is prime! Time : 514.715 sec.
3*2^164987-1 is prime! Time : 42.509 sec.
1000065*2^220897-1 is prime! Time : 3059.852 sec.
39*2^113549+1 is prime! Time : 84.064 sec.
3*2^414840-1 is prime! Time : 210.427 sec.
9999*2^458051+1 is prime! Time : 1842.025 sec.
1000065*2^390927-1 is prime! Time : 11376.660 sec.

Hmm, indeed. Interesting that the test timings get dramatically worse as k increases...any idea why that is?

BTW, how does it do on composites? As an example you may want to try it with this known residue (found and doublechecked with CPU LLR 3.8.4):

2303*2^251634-1 is not prime.  Res64: 99B680F2A92ECC27  Time : 991.0 sec.
2303*2^251634-1 is not prime.  LLR Res64: 99B680F2A92ECC27  Time : 96.922 sec.

(Note that the second of the above two results is more indicative of how long it takes to do this test on a typical CPU. The first test was done on one of NPLB's LLRnet servers with an old, rather slow machine, from the looks of it.)

[Jean Penné]

Hi,

Here are some precision about how llrpi works, related to the size of k :

- For k's up to 22 bits large (defined by MAXKBITS constant), IBDWT is used, so, the FFT length is optimal, and the modular reduction is free.

- For larger k's, up to 36 bits on WIN 32, 45 bits on Linux, Zero padded FFT is used, and the modular reduction is done by the "modred()" function.

- For still larger k's, or if the base is not two, generic modular reduction is used, which requires three multiplications in place of one...

I suggest you set -oDebug=1 to see the details about the time consumed in multiplications, normalization and modular reduction.

Congrat for your nice work and Best Regards,

Jean

[msft]

Hi ,mdettweiler
We need something.

Hi ,Jean Penné
Thank you information,

3*2^414840-1 is prime! Time : 209.799 sec.
3*2^303093+1 is prime! Time : 107.206 sec.
3*2^164987-1 is prime! Time : 42.285 sec.
39*2^113549+1 is prime! Time : 30.923 sec.
3*2^414840-1 is prime! Time : 209.799 sec.

[frmky]

Starting Lucas Lehmer Riesel prime test of 2303*2^251634-1
Using real irrational base DWT, FFT length = 65536
V1 = 4 ; Computing U0...done.
2303*2^251634-1 is not prime.  LLR Res64: 99B680F2A92ECC27  Time : 112.600 sec.

However, to get this I had to modify gwpnumi.cu, set_fftlen(), to remove the checks fftdwt > fftzpad and bpw < 5.0. The values of these parameters are fftdwt = 65536, fftzpad = 32768, and bpw = 4.83979, so in version 0.34, both these checks fail and zero-padded rational base DWT, which runs about 20x slower, is used.

Edit: A second run:

./llrCUDA -d -q1000065*2^390927-1
Starting Lucas Lehmer Riesel prime test of 1000065*2^390927-1
Using real irrational base DWT, FFT length = 131072
V1 = 5 ; Computing U0...done.
1000065*2^390927-1, iteration : 40000 / 390927 [10.23%].  Time per iteration : 0.627 ms
1000065*2^390927-1 is prime!  Time : 246.393 sec.

Of course Jean Penné can now tell me what I have broken by doing this.

Edit 2: And a Proth test:

./llrCUDA -d -q9999*2^458051+1   
Starting Proth prime test of 9999*2^458051+1
9999*2^458051+1 is prime!  Time : 313.916 sec.

[Ken_g6]

I also notice that v0.34 is only about half as fast as v0.16 when testing 5*2^1282755+1. Any chance of reintroducing that code for certain values of K or something?

[msft]

Originally Posted by Ken_g6

I also notice that v0.34 is only about half as fast as v0.16 when testing 5*2^1282755+1. Any chance of reintroducing that code for certain values of K or something?

Yes.Not Yet.
Now I try Riesel Prime test tuning.
Deng Xiaoping say "Let some people get rich first."

[frmky]

And a larger number where the GPU shines...

./llrCUDA -d -q938237*2^3752950-1
Starting Lucas Lehmer Riesel prime test of 938237*2^3752950-1
Using real irrational base DWT, FFT length = 1048576
V1 = 4 ; Computing U0...done.
938237*2^3752950-1 is prime!  Time : 10740.747 sec.

[msft]

Hi ,frmky

Originally Posted by frmky

And a larger number where the GPU shines...

modred(),generic_modred() need Parallel code.

[henryzz]

Originally Posted by frmky

And a larger number where the GPU shines...

./llrCUDA -d -q938237*2^3752950-1
Starting Lucas Lehmer Riesel prime test of 938237*2^3752950-1
Using real irrational base DWT, FFT length = 1048576
V1 = 4 ; Computing U0...done.
938237*2^3752950-1 is prime!  Time : 10740.747 sec.

How long would that take on a pc?

[msft]

Originally Posted by Ken_g6

I also notice that v0.34 is only about half as fast as v0.16 when testing 5*2^1282755+1. Any chance of reintroducing that code for certain values of K or something?

Recognize this problem.
llrpi380devsrc.zip change FFT length.