CUDA algorithms

[ET_]

ECM on graphics cards (Bernstein - Chen - Cheng - Lange - Yang)
GMP implementations on CUDA (Liu - Tong)
Multi-precision modular multiplication on GPU (Zhao)
The billion-Mulmod-per-second PC (Bernstein - Chen - Chen - Cheng - Hsiao - Lange - in - Yang)

If you can provide more links, maybe this thread is worth a "sticky" bit.

Luigi

[rogue]

How about OpenCL algorithms?

[jasonp]

For multiprecision arithmetic? The stuff you see here in the trial factoring on GPU section could well be all there is now.

[Christenson]

I make no claim to have this, but it seems to me that *IF* P-1 *could* benefit from GPU processing, that would be a significant benefit to GIMPS. I'd love to program it, but don't know if I can do it in a timely fashion.

I conjecture that a GPU implementation would also allow limits to be raised on numbers checked for Goldbach's conjecture by a few (3-4) orders of magnitude.

Finally, if ECM is efficient on GPUs, then it's useful bounds might well extend into the current DC range. Emotionally, I prefer factors to LL checks!

What about sieving for SNFS and GNFS (or even MPQS) on GPUs? I think that already exists....

[ET_]

Originally Posted by Christenson

I make no claim to have this, but it seems to me that *IF* P-1 *could* benefit from GPU processing, that would be a significant benefit to GIMPS. I'd love to program it, but don't know if I can do it in a timely fashion.

You are doing something big with mfaktc, please go ahead...
I'm using my spare time to study how to theorically work out something, and hope I'll have some guidelines by the time you'll release a Primenet enabled mfaktc...

Originally Posted by Christenson

I conjecture that a GPU implementation would also allow limits to be raised on numbers checked for Goldbach's conjecture by a few (3-4) orders of magnitude.

Why not Riemann Zeta function?

Originally Posted by Christenson

Finally, if ECM is efficient on GPUs, then it's useful bounds might well extend into the current DC range. Emotionally, I prefer factors to LL checks!

I think the main limitation for good ECM on GPUs is the memory constraint.
If (as it seems) EECM is less memory-hungry and more efficient in searching factors, then we may try to contact Bernstein's workgroup.

I'd like to know what Alex Kruppa thinks about it.

Originally Posted by Christenson

What about sieving for SNFS and GNFS (or even MPQS) on GPUs? I think that already exists....

Actually msieve uses GPU for polynomial selection. AFAIK, sieving on GFNS/SNFS implies heavy memory transfers, not a good characteristic for GPUs.

Luigi

[LaurV]

Assuming one has a Fermi (or two Fermi's ) with 3GB (each) or 6Gb (each, for Tesla's) and 384 bit bus for internal mem access (each). How would this influence the speed of P-1 and/or ECM? I would be willing to try, if any software available. No time and no knowledge to try to write my own. GPU's now are very different from the GPU's at the time when that papers were written. I don't believe the mem size or the mem access is a limitation anymore. When I run CudaLucas, the GPU's mem controller is anywhere between 30% and 40% busy, for a 95% GPU occupation, and when I run mfaktc (need 3 copies to max the GPU, i.e. to raise it to 95-98%) the mem controller is 1% busy. No joke. 1%! Here also there is a lot of place for improvement, I think. Like for example, use GPU for sieving too, and let the CPU free for other tasks. Contrary to CudaLucas, which does not need the CPU at all (almost) mfaktc is taking lots of CPU resources for sieving or whatever else, and meantime, GPU's mem is "wasted", sleeping, not used at all.

[ET_]

You put different ideas on the same message.

Originally Posted by LaurV

Assuming one has a Fermi (or two Fermi's ) with 3GB (each) or 6Gb (each, for Tesla's) and 384 bit bus for internal mem access (each). How would this influence the speed of P-1 and/or ECM?

No easy Brent-Suyama extension.
As for the speed, it all depends on both the algorithm and the level of parallelization.
I.E. Karatsuba multiplication has a better asymptotic efficiency than Montgomery multiplication, but the latter is much easier to parallelize.
FFT multiplication is asymptotically the fastest, but if you only rely on base 2 FFTs its benefical effects dim out.

Originally Posted by LaurV

I would be willing to try, if any software available. No time and no knowledge to try to write my own. GPU's now are very different from the GPU's at the time when that papers were written. I don't believe the mem size or the mem access is a limitation anymore.

It is.
You may have 6 GB memory, but threads that are allowed to use only 64K at a time. To feed the threads, much memory management should be done. Or use of global memory, with a slowdown of about 600x on accesses.

Originally Posted by LaurV

When I run CudaLucas, the GPU's mem controller is anywhere between 30% and 40% busy, for a 95% GPU occupation, and when I run mfaktc (need 3 copies to max the GPU, i.e. to raise it to 95-98%) the mem controller is 1% busy. No joke. 1%! Here also there is a lot of place for improvement, I think. Like for example, use GPU for sieving too, and let the CPU free for other tasks. Contrary to CudaLucas, which does not need the CPU at all (almost) mfaktc is taking lots of CPU resources for sieving or whatever else, and meantime, GPU's mem is "wasted", sleeping, not used at all.

Note that there are tasks that are better completed by CPUs, and other that are suited for GPUs.

Luigi

[axn]

Optimization of Primality Testing Methods by GPU

[axn]

Originally Posted by LaurV

Assuming one has a Fermi (or two Fermi's ) with 3GB (each) or 6Gb (each, for Tesla's) and 384 bit bus for internal mem access (each).

Are you talking in GIMPS context or generic P-1/ECM context (a la GMP-ECM)? The answers would differ based on the context.

[ET_]

Originally Posted by axn

Optimization of Primality Testing Methods by GPU

Thanks!

[ET_]

Another one:

Modular Reduction of Large Integers Using Classical, Barrett, Montgomery Algorithms

Not specifically CUDA-aware, but interesting, since TheJudger used Barrett algorithm for mfaktc...

Luigi