FPGA based FFT - Could it work?

[LaurV]

Originally Posted by chris2be8

you loaded one operand (I'll call it A) into them, then fed the other operand (B) in a word at a time and it multiplied that word of B by each word of A and summed with the previous result

in single clock cycles (actually called heart-beats, each "clock" is in fact two close pulses, like a heart, systolic and diastolic). They are still used sometimes, there is a huge theory behind of them, the process is called, you guessed, "systolic" calculus. From the "heart" stuff.

In fact, this hardware would work wonderful for LA phase of the NFS, just imagine millions of small shift/split registers doing Gauss elimination, they are very good at doing that! (well... yeah, I've heard some gossips about the "rarefied air" inside of those matrices, and better algorithms that we use, block, lanczos, whatever foreign names they are called...)

[jasonp]

Originally Posted by LaurV

block, lanczos, whatever foreign names they are called...)

Lanczos was Hungarian, so less foreign than the rest of us :)

[LaurV]

We knew that. We don't like Hungarians, Lanczos, Gerbicz, strange people, their algorithms are always faster than ours...

[Madpoo]

Originally Posted by airsquirrels

Does anyone on here actually work with FPGAs or design ASICs? Or are we all just speculating from our related field experience?

I did some work on Xilinx FPGA's a LONG time ago (back in college... we're talking 1993'ish. The software to design were far from modern convenience levels, and we were all learning the basics of it in the first place, which made for a very stressful (and educational) time.

All we built was a basic CPU (just 4 bit) that could do a few simple ops.

Glad I took the time to learn, but whew... I'm sure to be good at it you really have to make it a career.

[Prime95]

Originally Posted by ewmayer

Not quite so fast with regard to the exact 100-bits-plus product using FMA, young Jedi. :)

I have modpow routines based on that approach as a build option in my TF code for both Intel CPUs (starting with Haswell) and nVidia GPUs, though note on the latter this approach runs 10-20x slower than one based on multiword 32-bit integer math.

The reason using the FMA hardware to compute 106-bit products is slower than you state above is twofold:

[1] Each such basic product needs 2 MULs (one can be just ordinary mul, the other must needs be an fma, though AFAIK both instructions use the same hardware on Intel and probably most every modern FMA-supporting processor);

[2] The two output "halves" will typically need to be properly normalized with respect to whatever base one is using for one's multiword math.

Also added AVX2-based modmul routines based on capability
of FMA-double math to exactly compute 106-bit product of 53-bit signed inputs via the sequence

[input doubles x,y]
double hi = x*y;
double lo = FMA(x,y, -hi);
double hh,cy;

This still needs normalization to properly split the resultant significant bits across lo,hi,
e.g. in a base-2^52 signed-int multiword context:

hh = DNINT(hi*TWO52FLINV); // This part remains in hi...
cy = FMA(hh ,-TWO52FLOAT,hi); // hi - hh*2^52 is 'backward carry' from hi into lo, needed for proper base-normalization
lo += cy;
hi = hh;

Thus the cost of each 100+ - bit product is 1 ADD, 2 MUL, 2 FMA, 1 DNINT. (We assume/hope the negations are free).[/code]
I.e. 4 floating MULs per double-word product. Still very attractive on Haswell+, especially since the supported vector widths keep increasing, whereas the legacy 64x64 ==> 128-bit MUL (and the low-half-only variant, IMUL) remain stuck in scalar-only mode.

Interesting, I think we can improve on this. I've mocked up some code using 2 doubles to emulate the square-mod step in 70-bit TF (code should work up to at least 100-bit factors). The operation count is quite a bit less than my TF code that represents factors as three 30-bit integers. If this pans out, it could even help mfaktc.

We don't need the normalization steps described above. For example, if we are multiplying two 40-bit numbers and want two 40-bit results, do this:

hi = mul (a, b);
hi &= mask_out_lower_13_bits;
lo = fma (a, b, -hi);

The above works only if we know the top bit of each 40-bit input is on. If we can't rely on this, then this should work

hi = fma (a, b, 2^80);
hi -= 2^80
lo = fma (a, b, -hi);

Unfortunately, this produces a 53-bit hi and 27-bit low. But this should produce two 40-bit results:

hi = fma (a, b, 2^93);
hi -= 2^93
lo = fma (a, b, -hi);

[ewmayer]

Originally Posted by Prime95

Interesting, I think we can improve on this. I've mocked up some code using 2 doubles to emulate the square-mod step in 70-bit TF (code should work up to at least 100-bit factors). The operation count is quite a bit less than my TF code that represents factors as three 30-bit integers. If this pans out, it could even help mfaktc.

We don't need the normalization steps described above. For example, if we are multiplying two 40-bit numbers and want two 40-bit results, do this:

hi = mul (a, b);
hi &= mask_out_lower_13_bits;
lo = fma (a, b, -hi);

The above works only if we know the top bit of each 40-bit input is on. If we can't rely on this, then this should work

hi = fma (a, b, 2^80);
hi -= 2^80
lo = fma (a, b, -hi);

Unfortunately, this produces a 53-bit hi and 27-bit low. But this should produce two 40-bit results:

hi = fma (a, b, 2^93);
hi -= 2^93
lo = fma (a, b, -hi);

True, there are definitely cycle savings to be had in contexts where the requirement for precise multiword base-normalization can be relaxed, which includes certain aspects of the modmuls used in TF.

More importantly, in the next-gen updates to the AVX-512 instruction coming in Cannonlake - specifically all architectures featuring the IFMA subest of instruction extensions to the AVX-512 Foundation instruction set - Intel is gifting us what promises to be at least a factor of 2 speedup, by implementing the base-2^52 double-wide product sequence I listed above (just with nonnegative-digits, i.e. the round-to-nearest replaced with a round-toward-minus-oo) in an unsigned integer form, via the VPMADD52[L|H]UQ instruction pair.

Although those instructions will be formally integer, I suspect they will share the same multiply hardware as double-float FMA. It would also be nifty if Intel tweaked its microcode engine to look for paired VPMADD52[L|H]UQ which take the same inputs in proximity in the instruction stream and in such cases do just a single wide hardware MUL to obtain both halves of the output (much the way the legacy 64x64 ==> 128-bit unsigned MUL instruction does things), but we won't know about that until the chips are out, I suppose.

[GP2]

Amazon AWS has just announced a new "F1" cloud instance type (FPGA). It is available in developer preview in the us-east-1 (N. Virginia) region.

More details here.

The specs say these are Xilinx UltraScale+ VU9P FPGAs

[airsquirrels]

So this is quite an old topic,

In the time between I’ve stretched my own legs and have moved into some more direct FPGA development, as the audio/video space tends to do.

Turns out I have a few quite nice devices in the lab for a bit ranging from high-end Virtex 6 and 7 boards, to Zynq, Kintex, and Virtex Ultrascale+ boards. All Xilinx kit here.

I’ve been trying to keep up on developments, but I’m afraid I’ve completely missed out on the PRP internals. Are those tests still using FFT based multiplication at the core?

What do you all think? If I was to take a “for fun and records” run of TF, LL, or PRP against one of the Ultrascale+ devices which would be most interesting?

[axn]

Originally Posted by airsquirrels

I’ve been trying to keep up on developments, but I’m afraid I’ve completely missed out on the PRP internals. Are those tests still using FFT based multiplication at the core?

Yes. PRP and LL uses the same squaremod FFT routines.

Originally Posted by airsquirrels

What do you all think? If I was to take a “for fun and records” run of TF, LL, or PRP against one of the Ultrascale+ devices which would be most interesting?

TF will be easiest to implement, so LL/PRP testing will be more interesting, I guess?

[GP2]

If you came up with some FPGA code it would be cool if it ran on those AWS f1 instances I mentioned earlier. They're available in the us-east-1 (N. Virginia), us-west-2 (Oregon) and eu-west-1 (Ireland) regions.

No idea if it would be cost-effective though, they seem a bit pricey so it all depends on how many iterations/sec the FPGA code could potentially crank out.

[airsquirrels]

Originally Posted by GP2

If you came up with some FPGA code it would be cool if it ran on those AWS f1 instances I mentioned earlier. They're available in the us-east-1 (N. Virginia), us-west-2 (Oregon) and eu-west-1 (Ireland) regions.

No idea if it would be cost-effective though, they seem a bit pricey so it all depends on how many iterations/sec the FPGA code could potentially crank out.

I have two development boards of basically the same chip as the F1 instances, although the general design should be able to be tiled across the available slices on must Xilinx FPGAs. No promises but I’ll give it a shot. Maybe Ernst has some more crazy custom bit-width algorithm ideas for me. Integers would be nice....