FPGA based FFT - Could it work?

[paulunderwood]

I played with a Xilinx spartan 6 dev board (10 MHz?). If anything it teaches you to code well. Unless you design some FFT circuits using the given multipliers are almost useless for huge integer calculations.

[a1call]

Precisely so,
I have used a CPU-less FPGA in a past job to design a NDT module.
I have this way-on-the-backburner/dream project to create a module that would perform arbitrary-precision calculations which would entail designing external memory and from-the-scratch programming to perform the arbitrary precision calculation, It is a Herculean-task,

ETA, OTOH, You could design a very specialized/efficient system without the PC's OS overhead.

[xilman]

Originally Posted by retina

Digging ditches is also a career in itself. But amateurs can also partake in the fun if they wish.

If you want a fantastic ditch dug quickly, hire a professional. If you want to spend no money and lots of time farting about with a shovel to create a ditch that does its job only under a narrow range of special conditions then you can do it yourself.

[drkirkby]

Originally Posted by kriesel

Go for it.
It took only seconds online to find:

https://www.intel.com/content/www/us.../overview.html

https://www.ebay.com/sch/i.html?_fro...board&_sacat=0

I know they are around, but the cheap boards don't have enough power to do anything very useful. They don't have enough RAM for a start to hold an FFT.

However, I could see this could make a student project, with perhaps the possibility of a university getting a decent FPGA development board free from Xilinx, Intel etc.

[xilman]

Originally Posted by retina

Digging ditches is also a career in itself. But amateurs can also partake in the fun if they wish.

If you want a fantastic ditch dug quickly, hire a professional. If you want to spend no money and lots of time farting about with a shovel to create a ditch that does its job only under a narrow range of special conditions then you can do it yourself.

And learning about how to dig ditches.

Don't underestimate the value of self-education.

[kriesel]

Originally Posted by drkirkby

I know they are around, but the cheap boards don't have enough power to do anything very useful. They don't have enough RAM for a start to hold an FFT.

Try crawling before sprinting or flying. One TF kernel. Small ram requirements, and much less herculean than attempting FFT based PRP or P-1 implementation.
Or stop advocating someone else should do it.
Getting an FPGA to do better than a mass produced gpu driven by finely honed GIMPS software seems a tall order.

[mackerel]

Is trying to use FPGAs to implement FFTs the best way forward? By that I mean, is there some other algorithm that might work more efficiently on FPGA by taking better advantage of what the hardware can do?

I wish I had the understanding, but through observation it is often said on this forum that GPUs are the best way currently. Yet for relatively smaller prime finding on Primegrid, CPUs mostly running LLR are the choice. Attempts at GPU usage for smaller prime finding have not resulted in good performance relative to CPU. It is a scaling problem? The exception is genefer, which works great on GPUs even with relatively smaller sizes, although it is limited to generalised fermat. Whatever the method behind it, I wonder if it could be expanded to other prime types. So swinging it back to this thread, would something other than implementing FFTs work better on FPGA?

To answer this I think you'd need to have decent skills in mathematics, software and hardware. I don't fit in any of those categories.

[paulunderwood]

FPGAs usually have several, sometimes scores, of (say) 48x48 bit multipliers which can all be harnessed. I am not sure about the existence of floating point units.

Another thing to take into account is the clock frequency of the FPGA. The higher the clock the more they cost.

I'll let someone more knowledgeable chip in...

ps here is a not too technical paper with many references that might be illuminating.

[preda]

Originally Posted by mackerel

Is trying to use FPGAs to implement FFTs the best way forward? By that I mean, is there some other algorithm that might work more efficiently on FPGA by taking better advantage of what the hardware can do?

I wish I had the understanding, but through observation it is often said on this forum that GPUs are the best way currently. Yet for relatively smaller prime finding on Primegrid, CPUs mostly running LLR are the choice. Attempts at GPU usage for smaller prime finding have not resulted in good performance relative to CPU. It is a scaling problem? The exception is genefer, which works great on GPUs even with relatively smaller sizes, although it is limited to generalised fermat. Whatever the method behind it, I wonder if it could be expanded to other prime types. So swinging it back to this thread, would something other than implementing FFTs work better on FPGA?

To answer this I think you'd need to have decent skills in mathematics, software and hardware. I don't fit in any of those categories.

TF (trial factoring) does not use FFTs.

For primality testing Mersenne numbers, there is LL and PRP; the two are very similar from an implementation perspective. They both require squaring very large numbers, and that is done through FFTs. There's no avoiding FFTs for the bit-sizes we consider (let's say larger than 100M bits).

OTOH there is a wide range of choice about how to implement the FFT:
1. using complex numbers: based on some floating point format (e.g. DP), or on some fixed-point format.
2. using FGT (Fast Galois Transform), which is similar to complex arithmetic but using integers modulo a small prime.
3. using NTT (Number Theoretic Transform), which again involves modular arithmetic modulo a small prime.

(there is extensive discussion of these techniques in other threads).
And each of these choices has sub-variants and various tradeoffs.

What they have in common, is they all require a lot of multiplications. These multiplications, at some fundamental level, always come down to integer multipliers (even for floating point).

There is also a different technique, "Nussbaumer convolution", which does not require multiplication (using additions and shifts instead). It does not seem competitive on GPUs, but the situation may be different on FPGAs, I have no idea.

[mackerel]

Originally Posted by preda

OTOH there is a wide range of choice about how to implement the FFT:
1. using complex numbers: based on some floating point format (e.g. DP), or on some fixed-point format.
2. using FGT (Fast Galois Transform), which is similar to complex arithmetic but using integers modulo a small prime.
3. using NTT (Number Theoretic Transform), which again involves modular arithmetic modulo a small prime.

That's one of many gaps in my knowledge filled out. I had taken FFTs to be #1 in the above only (throw more FP64 at it), and thought #3 was something else entirely. I think #3 might be the one used in genefer, but I'm not 100% on that.

One other thought I had, and think I've mentioned in the past, is if we can do this, would it be beneficial to use number formats different than those currently available. For example, would it be beneficial overall (more efficient) if you could work on bigger data sizes vs more smaller ones, factoring in the hardware implementation cost. So unless there are fixed functionality blocks in FPGAs that have to be used, could this be an option?

[bsquared]

Originally Posted by mackerel

That's one of many gaps in my knowledge filled out. I had taken FFTs to be #1 in the above only (throw more FP64 at it), and thought #3 was something else entirely. I think #3 might be the one used in genefer, but I'm not 100% on that.

One other thought I had, and think I've mentioned in the past, is if we can do this, would it be beneficial to use number formats different than those currently available. For example, would it be beneficial overall (more efficient) if you could work on bigger data sizes vs more smaller ones, factoring in the hardware implementation cost. So unless there are fixed functionality blocks in FPGAs that have to be used, could this be an option?

I think you are asking, could you implement, say, FP128 and use that instead of FP64 as a building block for the FFT?

It's complicated. Fundamentally, you could implement anything you like, limited only by the logic cell capacity of the chip. Clock frequency, however, will be limited to the max possible fabric clock which is usually way slower than the hard-DSPs present on the chip. Also, the bigger the multiplier design gets, the harder it is to interconnect all of the logic, and the slower the clock will run.

The way to get around using relative slow reconfigurable logic is to use any hard DSPs the chip may have (most chips have some, expensive chips have lots), which run a lot faster. But they are limited in size; modern ones I think are around 25x18 bits. A few of these can be cascaded to get to around 36x36 or maybe 48x48 without compromising clock frequency, but beyond that the clock will slow way down again (crossing slice boundaries).

Add to all of that:
* integrating the small multipliers discussed above into a working IBDWT algorithm
* interfacing with memory, probably external, probably heirarchical (using on-chip block rams)
* considering several parallel designs or one huge one
* controllers to interface with the outside world (microblaze makes this easier than it used to be)
* probably lots more detail

Anyway, it would be a massive design effort and even with the biggest most expensive parts available, is questionable as to whether it could beat a nice gpu.

Even figuring out the answer to that question (could it beat a gpu) is maybe a master's thesis project scale question since it likely involves prototyping designs to figure out the max clock rates and size of many design variations to essential fill in the boxes of a large design-space matrix.