12
\$\begingroup\$

I have a particularly large signal processing transform that needs to be ported from matlab to VHDL. It definitely requires some kind of resource sharing. A bit of calculation gave me the following:

  • 512 ffts of 64-points
  • 41210 multiply-add operations

Considering the largest Virtex 6 FPGA has ~2000 DSP48E blocks, I know that I can resource-share in order to re-use the resources multiple times. Execution time isn't really an issue, the processing time can take relatively long in FPGA terms.

Looking at resource usage, using radix-2 lite architecture gets me 4dsp blocks/FFT operation = 2048 DSP blocks, a total of ~43k. biggest Virtex FPGA has 2k blocks, or 20 operations/mux.

Obviously including such large muxes into the fabric is also going to take up slices. Where do I find the upper end of this limit? I can't infinitely share the FPGA resources. Is 41210 multipliers too big? How do I calculate what is too big?

I've also looked at other resources (Slices, Brams, etc). Radix-2 Lite also gives 4 x 18k brams/fft = 2048 brams biggest Xilinx FPGA contains 2128 Brams. very borderline. I'm concerned that my design is just too big.


UPDATE:

Some more info on the design itself. I can't go into detail, but here is what I can give:

Initial conditions -> 512 ffts -> 40k multipliers ---------|----> output data to host 

                 ^------re-calculate initial conditions----|

output datarate spec: "faster than the matlab simulation"

calculations wise, this is where I am:

FFT stage: easy. I can implement 1/2/4/8 FFTs, store the results in SDRAM and access later. Relatively small, even if it takes long, it's ok. using radix-2 lite I can get 2 DSP48Es and 2 18k BRAMS/FFT. streaming gives 6 DSP48Es 0BRAMS/FFT. in either case, 64 point FFT is small in FPGA resource terms.

Multipliers: this is my problem. The multiplication inputs are taken from either lookup tables or FFT data. It really is just a whole bunch of multiply-adds. There isn't much to optimise. Not a filter, but has characteristics similar to a filter.

Considering resource sharing on the FPGA, maths works out as follows: One LUT-6 can be used as a 4-way mux. The formula for an N-way, M bit mux is as follows:

N*M/3 = number of luts, or N*M/12 = slices (4 LUTS/slice).

crunching the numbers for my implementation does not give good results. 90% of the virtix-6 family doesn't have enough slices to resource-share their DSPs in order to perform 40k operations.

\$\endgroup\$
  • \$\begingroup\$ The most efficient forms of resource sharing are partial serialization where you can access data by addressing memory. Of course, at an extreme of this you are back to a conventional stored-program processor - the lack of hard performance requirements starts to point back towards the flexibility of a software implementation perhaps running in a compute cloud. \$\endgroup\$ – Chris Stratton Dec 31 '12 at 15:45
  • 1
    \$\begingroup\$ This isn't part of your question, but in your resource calculation you didn't state what size operand. 512 FFTs x 64 points x how many bits? In an FPGA the operand size is totally up to you, so you have to consider it when working out the size of your problem. \$\endgroup\$ – The Photon Dec 31 '12 at 15:54
  • \$\begingroup\$ I don't know if you realized, but those big FPGAs are quite expensive. Some can be above $5k. Perhaps you should consider that as well, unless cost isn't an issue. \$\endgroup\$ – Gustavo Litovsky Dec 31 '12 at 17:54
  • 1
    \$\begingroup\$ Unfortunately beyond the sort-of alternate solution suggestions you got in the answers so far, I doubt if we can do to much more for you. I mean, you could make just one FFT core and run your 512 inputs through it one after the other, and obviously that would fit in even a fairly small FPGA. Somewhere between that and doing everything in parallel is the right balance of speed vs resources for your application...but it's hard for anyone but you to say where that balance should be. \$\endgroup\$ – The Photon Jan 1 '13 at 2:02
  • 1
    \$\begingroup\$ Do you have a budget number for this? Like Gustavo pointed out, high-end FPGAs are expensive, as is developing a PCB to sit them on. Whereas just doubling (or quadrupling or ...) the amount of compute hardware and continuing to use the existing, proven(?), Matlab code could probably meet the speed spec as given. \$\endgroup\$ – The Photon Jan 1 '13 at 17:07
8
\$\begingroup\$

I wonder if there is another way of looking at the problem?

Playing off your estimation of 512 FFT operations (64 point each) and 42k MAC operations... I presume this is what you need for one pass through the algorithm?

Now you have found an FFT core using 4 DSP units ... but how many clock cycles does it take per FFT? (throughput, not latency)? Let's say 64, or 1 cycle per point. Then you have to complete those 42k Mac operations in 64 cycles - perhaps 1k MACs per cycle, with each MAC handling 42 operations.

Now it is time to look at the rest of the algorithm in more detail : identify not MACs but higher level operations (filtering, correlation, whatever) that can be re-used. Build cores for each of these operations, with reusability (e.g. filters with different selectable coefficient sets) and soon you may find relatively few multiplexers are required between relatively large cores...

Also, is any strength reduction possible? I had some cases where multiplications in loops were required to generate quadratics (and higher). Unrolling them, I could iteratively generate them without multiplication : I was quite pleased with myself the day I built a Difference Engine on FPGA!

Without knowing the application I can't give more details but some such analysis is likely to make some major simplifications possible.

Also - since it sounds as if you don't have a definite platform in mind - consider if you can partition across multiple FPGAs ... take a look at this board or this one which offer multiple FPGAs in a convenient platform. They also have a board with 100 Spartan-3 devices...

(p.s. I was disappointed when the software guys closed this other question - I think it's at least as appropriate there)

Edit : re your edit - I think you are starting to get there. If all the multiplier inputs are either FFT outputs, or "not-filter" coefficients, you are starting to see the sort of regularity you need to exploit. One input to each multiplier connects to an FFT output, the other input to a coefficient ROM (BlockRam implemented as a constant array).

Sequencing different FFT operations through the same FFT unit will automatically sequence the FFT outputs past this multiplier. Sequencing the correct coefficients into the other MPY input is now "merely" a matter of organising the correct ROM addresses at the correct time : an organisational problem, rather than a huge headache of MUXes.

On performance : I think Dave Tweed was being needlessly pessimistic - the FFT taking n*log(n) operations, but you get to choose O(n) butterfly units and O(logN) cycles, or O(logN) units and O(n) cycles, or some other combination to suit your resource and speed goals. One such combination may make the post-FFT multiply structure much simpler than others...

\$\endgroup\$
  • \$\begingroup\$ An FFT implemented with a single hardware butterfly is going to require NlogN clock cycles to complete; for 512 points, that would be 256*8 butterflies, or 2048 clocks. That means that the 41210 (or 32768?) MACs would only require 8-10 hardware multipliers to get done in the same amount of time. \$\endgroup\$ – Dave Tweed Jan 1 '13 at 16:04
  • \$\begingroup\$ I mean, 16-20 multipliers. \$\endgroup\$ – Dave Tweed Jan 1 '13 at 16:12
  • \$\begingroup\$ Sorry, I just realized I got that backwards. The indiivdual FFTs are 64 points, so the single-butterfly implementation will require 32*5 = 160 clocks. The MACs can then be done with 200-250 hardware multipliers. \$\endgroup\$ – Dave Tweed Jan 1 '13 at 16:23
  • \$\begingroup\$ this is what stumps me. How can xilinx design a core capable of doing 16k/32k ffts that require 400k multiply-add operations (NlogN) and yet I'm struggling with my 41k? there must be a way! \$\endgroup\$ – stanri Jan 1 '13 at 16:31
  • \$\begingroup\$ @Dave : I believe you mean 160 multiplications, not 160 cycles, surely? There is nothing quite so inherently serialised in an FFT... \$\endgroup\$ – Brian Drummond Jan 1 '13 at 19:55
2
\$\begingroup\$

If this problem doesn't have hard realtime constraints, and it sounds like it doesn't — you just want it to run "faster", then it seems like it might be quite amenable to acceleration on one or more GPUs. There are several software libraries that make this a relatively straightforward proposition, and this would be about an order of magnitude easier than going straight to custom FPGA hardware.

Just Google for "GPU-enabled library" or "GPU-accelerated library" to get started.

\$\endgroup\$
  • \$\begingroup\$ Interestingly enough, i mentioned GPUs to the client when i heard about this project, and he wasn't interested. \$\endgroup\$ – stanri Jan 1 '13 at 1:43
  • \$\begingroup\$ @StaceyAnneRieck: Did he say why? \$\endgroup\$ – Dave Tweed Jan 1 '13 at 2:10
  • \$\begingroup\$ He didn't really say why, just that he had looked into it before an using an FPGA seemed like less work, apparently. I'm going to have to bring it up again. \$\endgroup\$ – stanri Jan 1 '13 at 5:51
  • \$\begingroup\$ @stanri: Even if you do ultimately end up in an FPGA implementation, it seems to me that GPU might be a good way to "breadboard" the overall system architecture. Do you have (and could you share?) some sort of high-level dataflow graph for the algorithm, and can you give us an idea of the amount of data involved? Without answers to questions like these, it's going to be really hard to give you anything other than very generic advice. \$\endgroup\$ – Dave Tweed Jan 1 '13 at 12:28
  • \$\begingroup\$ It's actually a very very simple algorithm, it's just the scale that makes it so complicated. Basically as follows: initial conditions -> 512 ffts in parallel -> 32768 multiply operations on FFT output -> adjust initial conditions -> rinse and repeat \$\endgroup\$ – stanri Jan 1 '13 at 15:48
1
\$\begingroup\$

It's possible to use an specialized hardware or an FPGA (or even a CPLD) to greatly accelerate certain kinds of math operations. The key thing to bear in mind when trying to design hardware (circuitry or FPGA logic) to accelerate math operations is to figure out what order data will need to go into and out of your device. A device with an efficient I/O layout may offer much better performance than one with an inefficient layout, even if the latter device requires much more circuitry.

I haven't tried working out a hardware-assist design for an FFT, but one I have looked at is hardware assistance for large multiply operations (as might be used for RSA encryption). Many microcontrollers, even those with special fast-multiplication hardware, are not terribly efficient at such operations because they require a lot of register shuffling. Hardware which was designed to minimize register swapping could achieve much better performance with multi-precision multiplication operations, even if the hardware itself wasn't as sophisticated. For example, hardware which can perform a pipelined 16xN multiplication two bits at a time (shifting in two lower bits of multiplcand, and shifting out two upper bits of result) may achieve better performance than hardware which can perform an 8x8 multiply in one cycle, even though the former may take less circuitry (and, by virtue of pipelining, have a shorter critical data path). The key is to figure out what the "inner loop" of the necessary code will look like, and figure out if there are any inefficiencies that can easily be eliminated.

\$\endgroup\$
  • \$\begingroup\$ What kinds of operations are particularly suited to this form of optimisation? I've edited the question above to detail a bit more about the nature of the multiply operation. Hardware-assist design sounds really interesting! \$\endgroup\$ – stanri Jan 1 '13 at 16:35
0
\$\begingroup\$

How little of an issue us execution time?

This really seems like a situation where you should really implement a soft-MCU, a FPGA with an integrated hard-MCU, or even a separate MCU device, and serialize all your operations.

Assuming you have the execution time, doing your FFTs in software will be both far easier to debug, and probably far simpler to design too.

\$\endgroup\$
  • 1
    \$\begingroup\$ Doing heavy computation in a soft core CPU on an FPGA is silly; if you are going to do the computation in a stored program architecture (something that should be considered), due it on high performance/dollar hard cpu(s) where you don't pay the speed penalty of flexible logic over comparable-fab-generation hard logic. \$\endgroup\$ – Chris Stratton Dec 31 '12 at 21:21
  • \$\begingroup\$ @ChrisStratton - Good point. Added an additional note to that effect. \$\endgroup\$ – Connor Wolf Dec 31 '12 at 21:25
  • 1
    \$\begingroup\$ Even the built in hard-CPUs are not going to hold a candle to commodity conventional processors/GPUs for software-based tasks, and will cost drastically more. \$\endgroup\$ – Chris Stratton Dec 31 '12 at 21:26
  • \$\begingroup\$ @ChrisStratton - I thought the most common integrated hard-CPU architectures was either ARM or POWER? In that case, it basically is a commodity CPU. \$\endgroup\$ – Connor Wolf Dec 31 '12 at 21:30
  • 1
    \$\begingroup\$ Given your other FPGA question, building the FPGA board is likely to be a learning experience that will cost quite a bit more than estimated. I think the thing to do at this point would be to give the client some hard price/performance numbers from trial compute cloud runs (which could eventually become purchased hardware), vs some idea of the higher price and much higher risk of the FPGA effort. \$\endgroup\$ – Chris Stratton Jan 2 '13 at 15:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.