NTT transform at (AMD) GPU versus *lucas

[diep]

Originally Posted by fivemack

I spent a little while thinking about using CRT in this kind of context; the problem is that the individual primes need to be ==1 modulo the size of the transform, which makes them too big to handle with MMX-like techniques if the transform is of at all reasonable size. And the restriction gets worse if you also require the primes to have an appropriate root of two for doing the DWT.

(with all the 16-bit primes ==1 mod 256 you only get to store about 50k digits)

(with all the 24-bit primes ==1 mod 2^16 you could store 16 million digits, which isn't quite enough)

32-bit primes ==1 mod 2^24 are maybe more interesting, there are 24 of them (so the effective digit size is about 10^220), and probably a mulmodp on such a prime can be done slightly faster than for a general p. Doing lots and lots of parallel FFTs modulo different fixed small primes feels quite fitting for a GPU, but I'm not competent to quantify 'feels quite fitting'.

A message from the helpdesk reached my mailbox. I have explained it as good news. So 5 months after i bought a GPU i can now know that in theory the AMD gpu can multiply 24 x 24 bits == 48 bits within 2 instructions.

The least significant 32 bits are in a single unsigned integer and the top 16 bits idemdito.

That eats 2 cycles in short.

Now i hope they provide, as some AMD engineer proposed, a solution to add this to OpenCL, if that request is still in time for the next APP SDK. That might mean that APP SDK 2.5 also provides access to the top16 bits.

Right now only a slower instruction the 32x32 bits top 32 bits are there.

So it would be possible, garantuee until the door, to study a transform for the AMD gpu in opencl using 24 bits multiplications.

Now i must admit i didn't study this very well yet, i'm sure TheJudger did do that a lot better as he's using this for TF as well and the 72 bits is his fastest code there.

Adding Carry isn't so easy in AMD. Also it seems to me that using multiply-add is rather complicated as the low bits gives a 32 bits result rathre than 24 bits, so it will be impossible probably to get a throughput
of above 880Mhz * 1536 = 1.35 Tflop

With 24 bits multiplications it's possible however to emulate bigger numbers than 64 bits i'd argue. Up to 72 bits maybe is possible. Note that would still be rather slow 72 bits numbers. 48 bits would go a lot faster i'd guess.

This will require puzzling!

Of course in contradiction to 32 bits math where overflow to 33 bits is not possible, with all this 24 bits junk, in reality it's in an integer that has 8 bits left, so overflow is nearly impossible. So the full 48 or 72 bits can get used.

Karatsuba type shifting operations also more easy then.

Or maybe even 96 bits. 4 x 24 bits.

If we multiply 96 x 96 bits using 24 bits at a time, we need 9 multiplications using Karatsuba.

I'll generate a bunch of primes close to those limits.