GPU for NFS factoring?

[Stargate38]

Why hasen't NFS been implemented into a GPU program yet?

[xilman]

Originally Posted by Stargate38

Why hasen't NFS been implemented into a GPU program yet?

Because no-one has thought it worth doing. Why don't you do it?

[jasonp]

'NFS' needs a large collection of sub-algorithms, the majority of which don't benefit at all from running on a graphics card. What you likely are asking about is NFS sieving running on a graphics card, which nobody that I know of has attempted because the sieving process involves lots of read-modify-write operations to random locations in a very large memory array, which has big problems running in parallel.

Sieving is inherently sensitive to memory latency, not memory bandwidth. GPUs have tons of the latter but are terrible with the former.

[akruppa]

Bernstein and colleagues have a few papers on ECM on graphics cards for small numbers such as appear in the cofactorization of relation candidates in NFS sieving, see for example http://eecm.cr.yp.to/index.html

[henryzz]

How does EECM-MPFQ compare with GMP-ECM speed wise?

[akruppa]

Opps, overlooked that. Bernstein claims that EECM-MPFQ is faster, unsurprisingly, but I never tried it myself. Also, PZ and colleagues recently added the batch-ECM variant to GMP-ECM (of which I know nothing myself) which is faster than the old ECM. I don't know how that compares to EECM-MPFQ.

[R.D. Silverman]

Originally Posted by jasonp

'NFS' needs a large collection of sub-algorithms, the majority of which don't benefit at all from running on a graphics card. What you likely are asking about is NFS sieving running on a graphics card, which nobody that I know of has attempted because the sieving process involves lots of read-modify-write operations to random locations in a very large memory array, which has big problems running in parallel.

Sieving is inherently sensitive to memory latency, not memory bandwidth. GPUs have tons of the latter but are terrible with the former.

Allow me to point out that a GPU can be used effectively in combination with the primary CPU.

Two of the compute intensive tasks (as opposed to memory intensive)
are:

Computing the initial start points for this sieve.
This means computing an expression of the form (ax + b)/(cx + d) mod p
for each prime p in the factor base. The modular inverses are compute
(but not memory!) intensive.

Reconstructing the actual factorization of an identified smooth value
after the sieving is complete. This is trial division!

So, While the primary CPU is busy with sieving, the GPU can do these
much less memory intensive and much more compute intensive tasks.

Coordinate the primary CPU with the GPU; use them together. Each can
do what it does best.

[chris2be8]

I'm not sure which thread this belongs in, apologies is this is the wrong one.

The latest Cryptogram from Bruce Schneier includes a link to http://2012.sharcs.org/record.pdf which includes an article on GPU assembly language programming. I've not had time to do more than skim it yet, but it looks very interesting.

Some of the other papers also relate to CUDA programming as well.

Chris

[jasonp]

Originally Posted by R.D. Silverman

Allow me to point out that a GPU can be used effectively in combination with the primary CPU.

Note that unless the data starts and ends in the GPU's memory, the latency of data transfer needs to be added to the latency of performing auxiliary sieving computations. Running algorithms like P+-1 and ECM on big batches of small numbers is a natural fit to a GPU, but IMO trial factoring doesn't fit so well because resieving is a viable alternative and computing start points doesn't have enough arithmetic to justify the data transfer on and off the card.

It may be a win to combine calculating the start points and also sieving by vectors on a GPU, using a bucket or radix sort instead of updating a huge array of bytes randomly. But even in that case you'd need space on the card for every factor base entry and also for the intermediate results, and I think that would be a tight fit for large jobs even with 2GB of memory on the card.

[henryzz]

An interesting paper on qs on gpus. http://www.cs.bath.ac.uk/~mdv/course...on-2009-10.pdf
Possible and pehaps fast if optimised. However, NFS uses much more memory and that was a bit of a challenge with just qs considering the high latency.