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

Groups > comp.arch.embedded > #29349 > unrolled thread

FFT Speeds

Back to article view | Back to comp.arch.embedded

Contents

  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

Page 1 of 2  [1] 2  Next page →

#29349 — FFT Speeds

I'm not building anything, I'm just curious.  I worked on a machine in the 80's called an attached array processor capable of 100 MFLOPS, the ST-100.  It could do a 1K complex FFT in 0.86 msec.  What sort of device would be required to do this today?  A desktop would far exceed this performance.  Low end single chip processors like an ARM CM3 would probably not reach this performance level.  But I bet the processor in an rPi would exceed it.  

Can anyone nail this down a bit more?  Are there ARM CM4 processors capable of a sub ms 1K complex FFT in 32 bit floating point?  Looking at the Cypress PSoC 61 is says "with single-cycle multiply (Floating Point and Memory Protection Unit)" but I think those are three separate things, single cycle integer multiply, floating point and MPU.  

Anyone know how fast a CPU like this can crank a 1k FFT?  

Of course the rack cabinet machine I'm talking about was fully capable of moving data around to keep up with the FFT so the computations were the bottle neck.  I expect in many applications in MCUs the FFT time is not the bottle neck, at least not at the 1K size, rather getting the data and moving it around is nearly as slow and the rest of the application is running on the same CPU.  The ST-100 was the equivalent of a floating point coprocessor so it only handled the math. 

-- 

  Rick C.

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

[toc] | [next] | [standalone]

#29350

On 30/03/2020 21:11, Rick C wrote:
> I'm not building anything, I'm just curious.  I worked on a machine
> in the 80's called an attached array processor capable of 100 MFLOPS,
> the ST-100.  It could do a 1K complex FFT in 0.86 msec.  What sort of
> device would be required to do this today?  A desktop would far
> exceed this performance.  Low end single chip processors like an ARM
> CM3 would probably not reach this performance level.  But I bet the
> processor in an rPi would exceed it.
> 
> Can anyone nail this down a bit more?  Are there ARM CM4 processors
> capable of a sub ms 1K complex FFT in 32 bit floating point?  Looking
> at the Cypress PSoC 61 is says "with single-cycle multiply (Floating
> Point and Memory Protection Unit)" but I think those are three
> separate things, single cycle integer multiply, floating point and
> MPU.

"MPU" is not an operation and does not need instruction cycles.  The 
Cortex-M4 has a single-cycle multiply-accumulate integer instruction 
(unlike the M3), and AFAIK the M4F has a single-cycle single precision 
floating point MAC.

But as you know, the MAC instruction is only part of the deal - you need 
other instructions for moving data into and out of registers.

I haven't timed FFT's myself.  But I found this reference:

<http://openaudio.blogspot.com/2016/09/benchmarking-fft-speed.html>

The 180 MHz M4F chip does 2.1.K 512 length single-precision FFT's per 
second, which means it would take a bit over 1 ms for a 1K FFT.  (I 
couldn't see if that was for complex FFT.)  The chip will do 
single-cycle floating point operations, but feeding the data in and out 
will be the bottleneck.

If you want faster, there are some Cortex-M7 devices at up to 528 MHz 
from NXP (the i.mx RT "crossover" family).  The M7 does up to two 
instructions per cycle, and the chips have plenty of single-cycle 
tightly-coupled ram.  You might peak at 6 to 8 times the performance of 
the K66F here, which would be well within your target.


If you really want top-speed FFT, you need a DSP chip.  These have 
several advantages - they have instructions that combine the loads, MAC 
and stores in one instruction, multiple ram blocks with separate buses 
for parallel access, and special counters and addressing modes designed 
specifically for circular buffers and FFT algorithms.  Some of TI's top 
models get ridiculous speeds from their super-scaler multi-core devices. 
  On the other hand, they are a real pain for anything /but/ DSP algorithms!


> 
> Anyone know how fast a CPU like this can crank a 1k FFT?

The Cortex-M devices are not fast CPUs - they are nice, solid 
microcontrollers.  The Cortex-A devices are fast CPUs with vector 
processing, super-scaling, etc., and will do FFT's a lot faster than any 
Cortex-M.

> 
> Of course the rack cabinet machine I'm talking about was fully
> capable of moving data around to keep up with the FFT so the
> computations were the bottle neck.  I expect in many applications in
> MCUs the FFT time is not the bottle neck, at least not at the 1K
> size, rather getting the data and moving it around is nearly as slow
> and the rest of the application is running on the same CPU.  The
> ST-100 was the equivalent of a floating point coprocessor so it only
> handled the math.
> 

[toc] | [prev] | [next] | [standalone]

#29352

On 2020-03-30 David Brown wrote in comp.arch.embedded:
>
> I haven't timed FFT's myself.  But I found this reference:
>
><http://openaudio.blogspot.com/2016/09/benchmarking-fft-speed.html>
>
> The 180 MHz M4F chip does 2.1.K 512 length single-precision FFT's per 
> second, which means it would take a bit over 1 ms for a 1K FFT.  (I 
> couldn't see if that was for complex FFT.)  The chip will do 
> single-cycle floating point operations, but feeding the data in and out 
> will be the bottleneck.
>
> If you want faster, there are some Cortex-M7 devices at up to 528 MHz 
> from NXP (the i.mx RT "crossover" family).  The M7 does up to two 
> instructions per cycle, and the chips have plenty of single-cycle 
> tightly-coupled ram.  You might peak at 6 to 8 times the performance of 
> the K66F here, which would be well within your target.

A while back I timed a 250k single precision complex FFT on a 400 MHz
ST M7, using the fftw lib with pre-planned fft. This took 330ms. May
have been limited by memory speed as the data did not fit in internal
or tightly coupled RAM and was in external SDRAM. While the FFT was
running, new data for two channels was coming in at 250 kSPS (IRQ/DMA),
which probably also had in impact on the (memory) performance.

-- 
Stef    (remove caps, dashes and .invalid from e-mail address to reply by mail)

Maryann's Law:
	You can always find what you're not looking for.

[toc] | [prev] | [next] | [standalone]

#29354

Un bel giorno Rick C digitò:

> I'm not building anything, I'm just curious.  I worked on a machine in
> the 80's called an attached array processor capable of 100 MFLOPS, the
> ST-100.  It could do a 1K complex FFT in 0.86 msec.  What sort of device
> would be required to do this today?

A beefed-up microcontroller should be enough:

http://www.ti.com/lit/an/spry288a/spry288a.pdf

C28x family runs up to 200 MHz and does 1k complex FFT in 53219 cycles,
i.e. 0.27 ms. Of course there are caveats, you must run everything in RAM
and very tight.

Some models are also dual core.

-- 
Fletto i muscoli e sono nel vuoto.

[toc] | [prev] | [next] | [standalone]

#29357

On 1/4/20 1:14 am, dalai lamah wrote:
> Un bel giorno Rick C digitò:
> 
>> I'm not building anything, I'm just curious.  I worked on a machine in
>> the 80's called an attached array processor capable of 100 MFLOPS, the
>> ST-100.  It could do a 1K complex FFT in 0.86 msec.  What sort of device
>> would be required to do this today?
> 
> A beefed-up microcontroller should be enough:
> 
> http://www.ti.com/lit/an/spry288a/spry288a.pdf
> 
> C28x family runs up to 200 MHz and does 1k complex FFT in 53219 cycles,
> i.e. 0.27 ms. Of course there are caveats, you must run everything in RAM
> and very tight.
> 
> Some models are also dual core.
> 

All other things being equal, doubling the length of an FFT adds one 
complex multiply per sample. So performance is O(log2(N))

Clifford Heath

[toc] | [prev] | [next] | [standalone]

#29358

Clifford Heath <no.spam@please.net> writes:
> All other things being equal, doubling the length of an FFT adds one
> complex multiply per sample. So performance is O(log2(N))

I think you mean N log N.  Usually we think of complex multiplication as
4 real multiplications plus 2 additions.  I wonder if (on machines with
1 cycle MAC) that makes complex FFT 4x slower than real FFT, or if they
have some interesting optimizations, parallelism, etc.

[toc] | [prev] | [next] | [standalone]

#29359

On 1/4/20 12:41 pm, Paul Rubin wrote:
> Clifford Heath <no.spam@please.net> writes:
>> All other things being equal, doubling the length of an FFT adds one
>> complex multiply per sample. So performance is O(log2(N))
> 
> I think you mean N log N.

Ahh yes, sorry. Mis-translated by omitting "per sample" :)

>  Usually we think of complex multiplication as
> 4 real multiplications plus 2 additions.  I wonder if (on machines with
> 1 cycle MAC) that makes complex FFT 4x slower than real FFT, or if they
> have some interesting optimizations, parallelism, etc.

Memory/cache behaviour is often the limiting factor. Bailey's approach 
to ordering the computation can radically assist though:

<https://www.davidhbailey.com/dhbpapers/fftq.pdf>

Ultimately I want an RPi-like module with a GPU  that supports CUDA... 
for a lower price than the Jetson Nano :). It's a shame to have to jump 
to an FPGA or funky DSP chip when a GPU is perfect for the job.

Clifford Heath

[toc] | [prev] | [next] | [standalone]

#29360

On Tuesday, March 31, 2020 at 10:40:48 PM UTC-4, Clifford Heath wrote:
> On 1/4/20 12:41 pm, Paul Rubin wrote:
> > Clifford Heath <no.spam@please.net> writes:
> >> All other things being equal, doubling the length of an FFT adds one
> >> complex multiply per sample. So performance is O(log2(N))
> > 
> > I think you mean N log N.
> 
> Ahh yes, sorry. Mis-translated by omitting "per sample" :)
> 
> >  Usually we think of complex multiplication as
> > 4 real multiplications plus 2 additions.  I wonder if (on machines with
> > 1 cycle MAC) that makes complex FFT 4x slower than real FFT, or if they
> > have some interesting optimizations, parallelism, etc.
> 
> Memory/cache behaviour is often the limiting factor. Bailey's approach 
> to ordering the computation can radically assist though:
> 
> <https://www.davidhbailey.com/dhbpapers/fftq.pdf>
> 
> Ultimately I want an RPi-like module with a GPU  that supports CUDA... 
> for a lower price than the Jetson Nano :). It's a shame to have to jump 
> to an FPGA or funky DSP chip when a GPU is perfect for the job.

I assume CUDA is a development language for GPUs?  The rPi GPU has a not fully documented GPU so it may or may not support CUDA.  But an FPGA is easy enough to find on a daughtercard for the rPi.  Or are you saying you just don't want to mess with an FPGA at all and would rather use software on a GPU? 

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.  A GPU might be a bit fun though.  I've worked with Transputers and programmed an attached array processor (4 ALUs in parallel).  I expect a GPU would be a step up from either of those.  

Too bad the rPi GPU is not accessible.  That could make for an interesting target. 

BTW, thanks to those who pointed out FFT benchmarks.  Looks like a single chip CPU does come pretty close to two rack cabinets from 30+ years ago.  It doesn't warm the room as well though. 

-- 

  Rick C.

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

[toc] | [prev] | [next] | [standalone]

#29361

On 1/4/20 2:53 pm, Rick C wrote:
> On Tuesday, March 31, 2020 at 10:40:48 PM UTC-4, Clifford Heath wrote:
>> Ultimately I want an RPi-like module with a GPU  that supports CUDA...
>> for a lower price than the Jetson Nano :). It's a shame to have to jump
>> to an FPGA or funky DSP chip when a GPU is perfect for the job.
> 
> I assume CUDA is a development language for GPUs?

Yes.

> The rPi GPU has a not fully documented GPU so it may or may not support CUDA. 

Correct. Same for ODroid.

> But an FPGA is easy enough to find on a daughtercard for the rPi.  Or are you saying you just don't want to mess with an FPGA at all and would rather use software on a GPU?

Yes, that. I want the array processor already defined for me, I just 
want to tell it what to do.
> Personally I much prefer coding FPGAs in HDL

I would too, if I had already learnt to do it.

>  trying to get a sequentially executing CPU to appear to be processing in parallel.  A GPU might be a bit fun though.

Yes, exactly.

> BTW, thanks to those who pointed out FFT benchmarks.  Looks like a single chip CPU does come pretty close to two rack cabinets from 30+ years ago.  It doesn't warm the room as well though.

In 1986 I was at HP, and we took delivery of one of their 3D Turbo SRX 
graphics rendering boxes... with hardware radiosity for rendering 
surfaces, etc... minimally configured, as we only needed it for 
configuration testing. But it was my desktop computer... That thing 
would still dim the lights when you turned it on!

The performance was dwarfed by single-chip PC graphics cards in less 
than ten years.

Clifford Heath

[toc] | [prev] | [next] | [standalone]

#29363

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.

-- 
Cheers
Clive

[toc] | [prev] | [next] | [standalone]

#29365

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.  By shift and add multiplier I assume you mean a single adder that is used sequentially to generate a multiply in N clocks?  

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.  

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. 

-- 

  Rick C.

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

[toc] | [prev] | [next] | [standalone]

#29368

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

[toc] | [prev] | [next] | [standalone]

#29369

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

[toc] | [prev] | [next] | [standalone]

#29370

On Thu, 2 Apr 2020 09:40:34 +0100, Clive Arthur
<cliveta@nowaytoday.co.uk> 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.
>
>> 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.

Implementing e.g. a 32 x 32 Wallace tree multiplier with MSI chips is
nasty, due to the huge number of interconnections. The product
consisting of two input AND gates produces 1024 lines. Then full
adders (preferably with carry look ahead) are required to count the
number of "1" bits. This requires multiple stages with the adder
propagation delays in each stage.

This is not a problem in e.g. in FFT calculations, since the
multiplies can be pipelined, producing one product every adder
propagation delay time but the total time taken by a single multiply
can be 10 or more adder propagation times,

[toc] | [prev] | [next] | [standalone]

#29371

On 4/1/20 12:32 PM, 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.
> 

Going back to this basic question, If I presume you are asking not about
the fairly limited number hard core multipliers that many FPGAs have
included, but about implementation in the FPGA fabric, and are comparing
one design which has a full tree implemented in parrallel, and can run
at a throughput of 1 multiply per cycle (it may take several cycle to
get a new result, but a new multiply can be done every cycle) verse an
implementation that uses reduced hardware but serially iterates the
answer in N cycles, my first impression is that the additional control
mechanisms to iterate probably take more logic than the fully parallel
solution and thus costs space, and thus has a lower throughput for a
given number of logic cells dedicated to multipliers. Someone would
really need to design this to be sure. Maybe the fact that the sequencer
could drive many serial multipliers might make a difference.

[toc] | [prev] | [next] | [standalone]

#29372

On Thursday, April 2, 2020 at 8:02:57 AM UTC-4, Richard Damon wrote:
> On 4/1/20 12:32 PM, Clive Arthur wrote:
> > 
<snipped>
> > 
> > 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.
> > 
> 
> Going back to this basic question, If I presume you are asking not about
> the fairly limited number hard core multipliers that many FPGAs have
> included, but about implementation in the FPGA fabric, and are comparing
> one design which has a full tree implemented in parrallel, and can run
> at a throughput of 1 multiply per cycle (it may take several cycle to
> get a new result, but a new multiply can be done every cycle) verse an
> implementation that uses reduced hardware but serially iterates the
> answer in N cycles, my first impression is that the additional control
> mechanisms to iterate probably take more logic than the fully parallel
> solution and thus costs space, and thus has a lower throughput for a
> given number of logic cells dedicated to multipliers. Someone would
> really need to design this to be sure. Maybe the fact that the sequencer
> could drive many serial multipliers might make a difference.

I have designed shift/add multipliers and the control logic is not much.  There is a log2(N) bit counter and minimal other logic.  The shift/add multiplier only works with unsigned multipliers (or is it the multiplicand?) so there needs to be a 2's complement before and after the multiplier.  I'm pretty sure the Booth's algorithm handles sign automagically, but I won't swear to it.  I did this over a decade ago.  I'm pretty sure if you are doing a bunch of multipliers the shift/add uses more real estate for the same throughput, but I don't recall the details of modified Booth's so I can't say for sure.  

-- 

  Rick C.

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

[toc] | [prev] | [next] | [standalone]

#29373

On 2.4.20 21:16, Rick C wrote:
> On Thursday, April 2, 2020 at 8:02:57 AM UTC-4, Richard Damon wrote:
>> On 4/1/20 12:32 PM, Clive Arthur wrote:
>>>
> <snipped>
>>>
>>> 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.
>>>
>>
>> Going back to this basic question, If I presume you are asking not about
>> the fairly limited number hard core multipliers that many FPGAs have
>> included, but about implementation in the FPGA fabric, and are comparing
>> one design which has a full tree implemented in parrallel, and can run
>> at a throughput of 1 multiply per cycle (it may take several cycle to
>> get a new result, but a new multiply can be done every cycle) verse an
>> implementation that uses reduced hardware but serially iterates the
>> answer in N cycles, my first impression is that the additional control
>> mechanisms to iterate probably take more logic than the fully parallel
>> solution and thus costs space, and thus has a lower throughput for a
>> given number of logic cells dedicated to multipliers. Someone would
>> really need to design this to be sure. Maybe the fact that the sequencer
>> could drive many serial multipliers might make a difference.
> 
> I have designed shift/add multipliers and the control logic is not much.  There is a log2(N) bit counter and minimal other logic.  The shift/add multiplier only works with unsigned multipliers (or is it the multiplicand?) so there needs to be a 2's complement before and after the multiplier.  I'm pretty sure the Booth's algorithm handles sign automagically, but I won't swear to it.  I did this over a decade ago.  I'm pretty sure if you are doing a bunch of multipliers the shift/add uses more real estate for the same throughput, but I don't recall the details of modified Booth's so I can't say for sure.


Booth's algorithm does handle signed operands in two's complement notation.

-- 

-TV

[toc] | [prev] | [next] | [standalone]

#29374

On Thursday, April 2, 2020 at 2:33:20 PM UTC-4, Tauno Voipio wrote:
> 
> Booth's algorithm does handle signed operands in two's complement notation.

Your mention of two's complement as if there were other choices these days made me recall that in the Forth language group there is a discussion of standardizing on 2's complement... finally.  

Seems someone looked and there are literally no remaining hardware computers running anything other than 2's complement.  There is an architecture running 1's complement, but it is no longer a hardware implementation but only simulated on other machines, lol.  There must be some commercial niche for software written for that machine.  

So no real need to specify 2's complement these days although I suppose in an FPGA there could be anything.  Some ADCs are still signed magnitude, so that conceivably could be carried through the chip. 

-- 

  Rick C.

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

[toc] | [prev] | [next] | [standalone]

#29375

Rick C <gnuarm.deletethisbit@gmail.com> writes:
> Your mention of two's complement as if there were other choices

IEEE 754 floating point, relevant to this discussion, is sign-magnitude.

[toc] | [prev] | [next] | [standalone]

#29376

On Thursday, April 2, 2020 at 11:33:24 PM UTC-4, Paul Rubin wrote:
> Rick C <gnuarm.deletethisbit@gmail.com> writes:
> > Your mention of two's complement as if there were other choices
> 
> IEEE 754 floating point, relevant to this discussion, is sign-magnitude.

That's not the main data format on any machines I know of.  No one uses floating point for logic or flags.  It was an issue in Forth because of the way people perform logic using non-flags or math using flags.  A one's complement or a signed magnitude data format breaks any assumptions you make about mixing the two.  

Some people complain that the practice happens making programs potentially non-portable so it looks like they are going to standardize on two's complement so these programs will be compliant and the griping will stop.  No one is complaining the change will break anything. 

-- 

  Rick C.

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

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.arch.embedded

csiph-web