Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.arch.embedded > #29368

Re: FFT Speeds

Show all headers | View raw

On 01/04/2020 20:20, Rick C wrote:
> On Wednesday, April 1, 2020 at 12:32:27 PM UTC-4, Clive Arthur wrote:
>> On 01/04/2020 04:53, Rick C wrote:
>>
>> <snipped>
>>>
>>> Personally I much prefer coding FPGAs in HDL than mucking about with the complexities of trying to get a sequentially executing CPU to appear to be processing in parallel.
>>
>> Probably a dumb question, I'm no FPGA expert, but for a fixed-point FFT,
>> could one use multiple shift and add multipliers instead of one fast
>> hardware multiplier?  Roughly how many shift-add multipliers could you
>> fit in the same space as a fast multiplier?
>>
>> I use a 128 point FFT for a comms system, and a dsPIC handles this
>> quickly enough with it's two hardware multipliers and ancillary logic,
>> but I've wondered if an FPGA with lots of parallel shift-add multipliers
>> might be quicker.
>>
>> In my application, I can't use FPGAs with inbuilt processors or multipliers.
> 
> Ok, sometimes I don't completely follow what people have posted.  

That's because it's not my field and I don't know the correct form of words.

> By shift and add multiplier I assume you mean a single adder that is used sequentially to generate a multiply in N clocks?

Yes.
> 
> I can't think why you would use such a multiplier if you need many of them to do the job.  I'm not an expert on multiplier design, but I believe a modified Booth's algorithm is not only faster but more compact.  The logic is a bit involved but someone explained to me how it uses fewer computations, but I completely forget the details.

The last time I used a hardware multiplier outside a CPU it was made 
with TTL chips and wire wrapped.  A Wallace tree IIRC taken from a big 
orange Texas databook.  My experience is somewhat limited.

> It's almost certain that multiple multipliers of any type could be faster... for some situations.  A 128 point (complex/real?, xx bit?, fixed/float) FFT is not very large, so not a huge amount of computations.  If you split the work you need to consider the time to offload the data and return the results.  A friend many years ago told me about evaluating an attached array processor on his PDP 11/70 in grad school.  The calcs were fast, but the I/O speed was slow enough it was faster on the CPU.
> 
> I expect this is real time work so you might want to stream the data into the FPGA and do more processing there.  I would be looking at the problem as by default work being done on the FPGA and offloading to a CPU the parts that are harder to do in an FPGA like network connectivity, etc.  Many of my designs have no CPU.
> 
> Take a look at the iCE5LP series from Lattice.  2 or 4 DSP blocks with 1100, 2048 or 3520 logic cells (LUT4s + FF) and 8 or 16 kB block RAM in a 0.5 mm pitch, 7 x 7 mm, 48 pin QFN.  A nice part for many small designs.
> 
> Can you explain why you can't use the built in multipliers?  I get not wanting to use a CPU, but a multiplier is a multiplier whether you construct it or it's already in the FPGA.
> 
There is a possible future requirement to run at high temperatures and 
in a very high vibration space-constrained environment.  This limits the 
size of the FPGA and the package type in practice to say something with 
20k gates - the actual part numbers known to work is confidential, but 
they won't be the latest greatest.

It had occurred to me that, as the FFT needs lots of complex 
multiplications, these could be done using lots of smaller simple 
shift-add multipliers instead of one large 'normal' multiplier - and for 
all I know, that's the way an expert would do it.  But only if the 
speed/size trade off worked.

-- 
Cheers
Clive

Back to comp.arch.embedded | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

FFT Speeds Rick C <gnuarm.deletethisbit@gmail.com> - 2020-03-30 12:11 -0700
  Re: FFT Speeds David Brown <david.brown@hesbynett.no> - 2020-03-30 21:50 +0200
    Re: FFT Speeds Stef <stef33d@yahooI-N-V-A-L-I-D.com.invalid> - 2020-03-31 09:33 +0200
  Re: FFT Speeds dalai lamah <antonio12358@hotmail.com> - 2020-03-31 16:14 +0200
    Re: FFT Speeds Clifford Heath <no.spam@please.net> - 2020-04-01 12:07 +1100
      Re: FFT Speeds Paul Rubin <no.email@nospam.invalid> - 2020-03-31 18:41 -0700
        Re: FFT Speeds Clifford Heath <no.spam@please.net> - 2020-04-01 13:40 +1100
          Re: FFT Speeds Rick C <gnuarm.deletethisbit@gmail.com> - 2020-03-31 20:53 -0700
            Re: FFT Speeds Clifford Heath <no.spam@please.net> - 2020-04-01 18:45 +1100
            Re: FFT Speeds Clive Arthur <cliveta@nowaytoday.co.uk> - 2020-04-01 17:32 +0100
              Re: FFT Speeds Rick C <gnuarm.deletethisbit@gmail.com> - 2020-04-01 12:20 -0700
                Re: FFT Speeds Clive Arthur <cliveta@nowaytoday.co.uk> - 2020-04-02 09:40 +0100
                Re: FFT Speeds Rick C <gnuarm.deletethisbit@gmail.com> - 2020-04-02 02:00 -0700
                Re: FFT Speeds upsidedown@downunder.com - 2020-04-02 12:50 +0300
              Re: FFT Speeds Richard Damon <Richard@Damon-Family.org> - 2020-04-02 08:02 -0400
                Re: FFT Speeds Rick C <gnuarm.deletethisbit@gmail.com> - 2020-04-02 11:16 -0700
                Re: FFT Speeds Tauno Voipio <tauno.voipio@notused.fi.invalid> - 2020-04-02 21:33 +0300
                Re: FFT Speeds Rick C <gnuarm.deletethisbit@gmail.com> - 2020-04-02 12:39 -0700
                Re: FFT Speeds Paul Rubin <no.email@nospam.invalid> - 2020-04-02 20:33 -0700
                Re: FFT Speeds Rick C <gnuarm.deletethisbit@gmail.com> - 2020-04-02 20:43 -0700
                Re: FFT Speeds upsidedown@downunder.com - 2020-04-03 09:34 +0300
                Re: FFT Speeds Rick C <gnuarm.deletethisbit@gmail.com> - 2020-04-03 01:29 -0700
                Re: FFT Speeds David Brown <david.brown@hesbynett.no> - 2020-04-03 12:23 +0200
                Re: FFT Speeds Clifford Heath <no.spam@please.net> - 2020-04-03 21:48 +1100
                Re: FFT Speeds Rick C <gnuarm.deletethisbit@gmail.com> - 2020-04-03 10:38 -0700
                Re: FFT Speeds Clive Arthur <cliveta@nowaytoday.co.uk> - 2020-04-04 11:50 +0100
                Re: FFT Speeds David Brown <david.brown@hesbynett.no> - 2020-04-03 09:12 +0200
                Re: FFT Speeds Rick C <gnuarm.deletethisbit@gmail.com> - 2020-04-03 01:30 -0700
                Re: FFT Speeds David Brown <david.brown@hesbynett.no> - 2020-04-03 12:39 +0200
          Re: FFT Speeds Paul Rubin <no.email@nospam.invalid> - 2020-04-01 10:43 -0700
            Re: FFT Speeds Clifford Heath <no.spam@please.net> - 2020-04-02 13:26 +1100
      Re: FFT Speeds Phil Hobbs <pcdhSpamMeSenseless@electrooptical.net> - 2020-04-01 17:27 -0400

csiph-web