CUDA integer FFTs

[airsquirrels]

Originally Posted by Prime95

A 4M FFT needs ~135 MB of bandwidth per iteration. A 4M FFT is 32MB of data requiring two passes over the data. Thus, 32MB read + 32MB write + 32MB read + 32MB write + somewhere between 5MB and 10MB of read-only sin/cos/weights data.

You’re right - I was only accounting for one pass. Of course I’m not sure how all the constants translate into integer based calculations, but constant in hardware are significantly faster than constants in software/CUDA.

[preda]

I'm personally very interested in how this turns out; I wish you all good luck.

I did try to implement a FGT (fast gallois transform) integer convolution in OpenCL/GCN, but somehow the performance was disappointing and I didn't investigate further. (I'm not sure what part of the blame goes to the compiler for generating poor integer code).

Just mentioning, a radically different integer approach for convolution is
"Nussbaumer convolution" described in Richard Crandall "Topics in Advanced Scientific Computation". This requires mostly integer additions! no multiplications, or constant tables. The drawback is in the memory access pattern, which is not fit for CPU or GPU architectures (low locality), but who knows may be OK for something different like FPGA.

Another drawback is that the "Nussbaumer convolution" naturally computes a negacyclic convolution, instead of a cyclic convolution that we need for mersenne modulo.

[bsquared]

Discussion on NN prime finding moved to here

[tServo]

Originally Posted by jasonp

I will probably get access to a compute capability 3.0+ Nvidia GPU in the near future, and have been toying with the idea of porting the integer FFT convolution framework I've been building off and on over the last few years to CUDA GPUs,

Do consumer GPUs still have their double precision throughput sharply limited, i.e. do the cards with 1:32 DP throughput vastly outnumber the server cards that do double precision faster? Using integer arithmetic on these cards has a shot at enabling convolutions that are faster than using cufft in double precision, if there is much more headroom on consumer GPUs for arithmetic compared to the memory bandwidth available. Are current double precision LL programs bandwidth limited on consumer GPUs even with the cap on double precision floating point throughput?

The latest source is here and includes a lot of stuff already, including optimizations for a range of x86 instruction sets.

Would there be interest in another LL tester for CUDA? I've never worked with OpenCL so CUDA is what I know.

Jason,
Just wondering if you have started this yet.
I have an interest in what you propose.

[jasonp]

Very basic stuff only; real life is swamping everything for the foreseeable future.

[kriesel]

Originally Posted by jasonp

The latest source is here and includes a lot of stuff already, including optimizations for a range of x86 instruction sets.

Would there be interest in another LL tester for CUDA? I've never worked with OpenCL so CUDA is what I know.

Yes, or PRP. With or without Jacobi check or Gerbicz check respectively (with preferred).
On NVIDIA, there's already CUDALucas and gpulucas for LL in CUDA, nothing via OpenCl; nothing yet on NVIDIA for PRP in CUDA or OpenCl. Neither LL program has the Jacobi check, which would be a nice addition.
Preda's contemplating addressing NVIDIA somehow with gpuOwL or a variant; avoiding duplication might be good.
A summary of current software available is described at http://www.mersenneforum.org/showthread.php?t=22450 and http://www.mersenneforum.org/showthread.php?t=23371

[jasonp]

In my mind the only reason to attempt something like this would be to speed up enough consumer grade GPUs to measurably increase the throughput of GIMPS. I've been toying with number theoretic FFTs off and on for almost 20 years now and it would be nice to find a real niche for them in a project like this.

[Prime95]

Originally Posted by jasonp

In my mind the only reason to attempt something like this would be to speed up enough consumer grade GPUs to measurably increase the throughput of GIMPS. I've been toying with number theoretic FFTs off and on for almost 20 years now and it would be nice to find a real niche for them in a project like this.

The last time I looked at CUDA, I think about 4 years ago, the problem is that 32x32 multiplies are limited to the DP throughput rate. Shifts are also severely limited. 32-bit adds run at full speed (as long as there is no carry propagation involved). Can your integer FFT algorithms take advantage of this scenario?

[jasonp]

There's some interesting reading on the subject here.

It's ironic that FFTs using Winograd's prime factor algorithm were developed in the 70s and 80s to optimally reduce the number of multiplications in FFTs, and suddenly after 30 years that really matters for integer FFTs where multiplies have lower throughput than anything else. A single modular multiply requires one high-half and two low-half integer multiplications when the prime modulus and the underlying arithmetic is chosen carefully.

I don't know if the overhead of an integer FFT using 30-bit prime moduli would swamp the savings in throughput from avoiding double precision floating point; my gut says the integer option would be faster on lower-end cards.

[airsquirrels]

I’m still interested in this for FPGAs

I happen to have ended up with exceptional access to a very large number of High end Xilinx FPGAs, and I would be more than happy to provide one or two on loan to anyone who has time or has a grad student to implement some GIMPS factoring or LL algorithms in them.

[Mysticial]

Originally Posted by jasonp

There's some interesting reading on the subject here.

It's ironic that FFTs using Winograd's prime factor algorithm were developed in the 70s and 80s to optimally reduce the number of multiplications in FFTs, and suddenly after 30 years that really matters for integer FFTs where multiplies have lower throughput than anything else. A single modular multiply requires one high-half and two low-half integer multiplications when the prime modulus and the underlying arithmetic is chosen carefully.

I don't know if the overhead of an integer FFT using 30-bit prime moduli would swamp the savings in throughput from avoiding double precision floating point; my gut says the integer option would be faster on lower-end cards.

Unfortunately, 30-bit primes won't be enough for LL unless you go Gaussian.

30-bit primes have enough roots-of-unity to do convolutions of around a billion bits, but you also need roots-of-two. And since there's no observable correlation between them, the longest transform length that you can do with 30-bit primes will probably only be around 2^16-ish.

More context here with 64-bit primes: http://www.mersenneforum.org/showthr...t=unity&page=4