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

Groups > comp.arch.embedded > #29369

Re: FFT Speeds

Show all headers | View raw

On Thursday, April 2, 2020 at 4:40:42 AM UTC-4, Clive Arthur wrote:
> 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.

No, I think your terminology is good, I just don't recall exactly what things mean from time to time.  I've reached a point where I often know a topic (well, the parts I remember) but not the terminology.  


> > 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.

I've heard of Wallace trees, but never used them.  I think they are more useful with the sort of function blocks you have in TTL/ECL chips.  When designing with gates I believe the modified Booth's algorithm is faster, but I'm not sure.  It certainly fits in an FPGA better because they all have fast adder chains in the fabric logic so the Wallace tree logic would be less effective. 


> > 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.

Ok, that makes sense.  The qualified part doesn't have multiplier blocks.  


> 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.

A shift-add multiplier is one layer of a pipelined multiplier.  So have N shift-add multipliers of M bits or N/M Booth's multipliers.  The amount of logic will be about the same other than whatever optimization factor the Booth's will offer.  I'm not sure it is less logic, but faster for sure.  Anyway, you should be able to put a lot of them into 20 kLUTs.  No, wait, you said "gates".  

I think that tells me which FPGA familly you are working with.  No one uses "gates" anymore and these guys do a lot of "qualified" business.  That explains the lack of multipliers.  20 kgates isn't really much logic either.  I'm guessing around 3,000 logic elements and these can be either logic or FF but not both? 

I wish I could remember more, but these days you can put 
A <= B * C in your code and you will get a library function block.  Let the tools work it out.  

-- 

  Rick C.

  -+ Get 1,000 miles of free Supercharging
  -+ Tesla referral code - https://ts.la/richard11209

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