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 2 of 2 — ← Prev page 1 [2]

#29377

On Thu, 2 Apr 2020 12:39:55 -0700 (PDT), Rick C
<gnuarm.deletethisbit@gmail.com> wrote:

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

The nice feature with 1¨s complement is that you can negate a number
by simply inverting all bits in a word. Thus inserting the inverters
in one data path and both inverting and some other operation can be
used in a single instruction.

The problem with 2¨s complement is that after inverting all bits, "1"
must be added to the result, requiring an adder and the ripple carry
can propagate through all bit positions. Thus complementing a number
needs an ADD instruction and takes as long as an ordinary ADD, Of
course these days with carry look-ahead logic, the ADD is nearly as
fast as AND/OR instructions.

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

With linear ADCs the zero line can be freely selected. One could put
the zero at 1/3 FSD and hence large  numeric range on one side.

However, in floating point ADCs the range just around zero is of most
interest, thus the sign/magnitude is more appropriate than biased
unsigned or 2'c complement. The floating point sign/magnitude is used
e.g. in digital telephony, so that weak signals are reproduced better.

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

#29379

On Friday, April 3, 2020 at 2:34:42 AM UTC-4, upsid...@downunder.com wrote:
> On Thu, 2 Apr 2020 12:39:55 -0700 (PDT), Rick C
> <gnuarm.deletethisbit@gmail.com> wrote:
> 
> >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.  
> 
> The nice feature with 1究 complement is that you can negate a number
> by simply inverting all bits in a word. Thus inserting the inverters
> in one data path and both inverting and some other operation can be
> used in a single instruction.
> 
> The problem with 2究 complement is that after inverting all bits, "1"
> must be added to the result, requiring an adder and the ripple carry
> can propagate through all bit positions. Thus complementing a number
> needs an ADD instruction and takes as long as an ordinary ADD, Of
> course these days with carry look-ahead logic, the ADD is nearly as
> fast as AND/OR instructions.

Exactly, and the 2's complement doesn't have the various issues the 1's complement does.  It only has a single value for zero.  I can't recall how they deal with that.  If you subtract 2 from 1 you would get an all ones word which is zero, so you have to subtract another 1 to get -1 which is all ones with the LSB zero.  So it's not really simpler, just messy in different ways. 

Actually the invert and add 1 is pretty easy to do in an ALU.  You already have the adder, just add a conditional inverter in front and you have a subtract, oh, don't forget to add the 1 through the carry in.  Easy and no different timing than the ALU without the inverter if it's done in the same LUT in an FPGA.  In fact, I've seen macros for add/sub blocks. 

The same sort of trick can be used to turn an adder into a mux.  In the instruction fetch unit of a CPU I designed there are multiple sources for the address, plus there is a need for an incrementer.  This is combined in one LUT per bit by using an enable to disable one of the inputs which only passes the other input like a mux.  I think I use that for the return address. 


> >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. 
> 
> With linear ADCs the zero line can be freely selected. One could put
> the zero at 1/3 FSD and hence large  numeric range on one side.
> 
> However, in floating point ADCs the range just around zero is of most
> interest, thus the sign/magnitude is more appropriate than biased
> unsigned or 2'c complement. The floating point sign/magnitude is used
> e.g. in digital telephony, so that weak signals are reproduced better.

You are talking about u-Law/A-Law compression.  Yes, very familiar with that.  Not really relevant to the native data format on CPUs though.  I know in u-Law there is a bias which can muck things up if you aren't careful.  So it's not even signed magnitude either.  

-- 

  Rick C.

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

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

#29381

On 03/04/2020 10:29, Rick C wrote:
> On Friday, April 3, 2020 at 2:34:42 AM UTC-4, upsid...@downunder.com
> wrote:
>> On Thu, 2 Apr 2020 12:39:55 -0700 (PDT), Rick C 
>> <gnuarm.deletethisbit@gmail.com> wrote:
>> 
>>> 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.
>> 
>> The nice feature with 1究 complement is that you can negate a
>> number by simply inverting all bits in a word. Thus inserting the
>> inverters in one data path and both inverting and some other
>> operation can be used in a single instruction.
>> 
>> The problem with 2究 complement is that after inverting all bits,
>> "1" must be added to the result, requiring an adder and the ripple
>> carry can propagate through all bit positions. Thus complementing a
>> number needs an ADD instruction and takes as long as an ordinary
>> ADD, Of course these days with carry look-ahead logic, the ADD is
>> nearly as fast as AND/OR instructions.
> 
> Exactly, and the 2's complement doesn't have the various issues the
> 1's complement does.  It only has a single value for zero.  I can't
> recall how they deal with that.  If you subtract 2 from 1 you would
> get an all ones word which is zero, so you have to subtract another 1
> to get -1 which is all ones with the LSB zero.  So it's not really
> simpler, just messy in different ways.

Yes - ones' complement has several complications, and not many benefits. 
  Sign-magnitude also has the "negative zero" issue, but has nice 
symmetry and is good for multiplication and division.  These formats 
also avoid the asymmetry of having a larger negative range than positive 
range, and odd things like "abs(-128) == -128" (using 8-bit to keep the 
numbers small).

> 
> Actually the invert and add 1 is pretty easy to do in an ALU.  You
> already have the adder, just add a conditional inverter in front and
> you have a subtract, oh, don't forget to add the 1 through the carry
> in.  Easy and no different timing than the ALU without the inverter
> if it's done in the same LUT in an FPGA.  In fact, I've seen macros
> for add/sub blocks.

Generally the "borrow" flag for subtraction is the inversion of the 
"carry" flag for addition.  This means that a "subtract with borrow" 
instruction is implemented as an "add with carry" where the subtracted 
value is complemented first.  That is, to do "A - B - borrow" you do "A 
+ ~B + carry".  That is (another) nice feature of two's complement that 
lets you re-use existing hardware without having extra carry propagation 
delays.

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

#29383

On 3/4/20 9:23 pm, David Brown wrote:
> Yes - ones' complement has several complications, and not many benefits. 
>   Sign-magnitude also has the "negative zero" issue, but has nice 
> symmetry and is good for multiplication and division.

Negative-zero can be a nice thing to have in floating point. Given that 
IEEE has both Infinities, I'm surprised they don't have proper 
infinitesimals too, but +ve and -ve zero is a close substitute.

Pointless in integer arithmetic, except to use up the assymetrical extra 
code.

CH

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

#29384

On Friday, April 3, 2020 at 6:23:14 AM UTC-4, David Brown wrote:
> On 03/04/2020 10:29, Rick C wrote:
> > On Friday, April 3, 2020 at 2:34:42 AM UTC-4, upsid...@downunder.com
> > wrote:
> >> On Thu, 2 Apr 2020 12:39:55 -0700 (PDT), Rick C 
> >> <gnuarm.deletethisbit@gmail.com> wrote:
> >> 
> >>> 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.
> >> 
> >> The nice feature with 1究 complement is that you can negate a
> >> number by simply inverting all bits in a word. Thus inserting the
> >> inverters in one data path and both inverting and some other
> >> operation can be used in a single instruction.
> >> 
> >> The problem with 2究 complement is that after inverting all bits,
> >> "1" must be added to the result, requiring an adder and the ripple
> >> carry can propagate through all bit positions. Thus complementing a
> >> number needs an ADD instruction and takes as long as an ordinary
> >> ADD, Of course these days with carry look-ahead logic, the ADD is
> >> nearly as fast as AND/OR instructions.
> > 
> > Exactly, and the 2's complement doesn't have the various issues the
> > 1's complement does.  It only has a single value for zero.  I can't
> > recall how they deal with that.  If you subtract 2 from 1 you would
> > get an all ones word which is zero, so you have to subtract another 1
> > to get -1 which is all ones with the LSB zero.  So it's not really
> > simpler, just messy in different ways.
> 
> Yes - ones' complement has several complications, and not many benefits. 
>   Sign-magnitude also has the "negative zero" issue, but has nice 
> symmetry and is good for multiplication and division.  

At least with sign magnitude it is easy to detect zero, just ignore the sign bit. 


> These formats 
> also avoid the asymmetry of having a larger negative range than positive 
> range, and odd things like "abs(-128) == -128" (using 8-bit to keep the 
> numbers small).

I don't have a problem with asymmetry.  I've never found a situation where it was a problem. 

-- 

  Rick C.

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

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

#29386

On 03/04/2020 18:38, Rick C wrote:
> On Friday, April 3, 2020 at 6:23:14 AM UTC-4, David Brown wrote:

<snipped?
> 
>> These formats
>> also avoid the asymmetry of having a larger negative range than positive
>> range, and odd things like "abs(-128) == -128" (using 8-bit to keep the
>> numbers small).
> 
> I don't have a problem with asymmetry.  I've never found a situation where it was a problem.

I've previously disallowed 0x8000 as a digitised 16 bit analog value so 
I could use it as an escape word in the data stream.

-- 
Cheers
Clive

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

#29378

On 02/04/2020 21:39, Rick C wrote:
> 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.
> 

Two's complement dominates entirely for simple signed integers.  But 
other formats are used in a variety of different situations.  IEEE 
floating point, for instance, uses sign-magnitude for the mantissa, and 
offset for the exponent.

And internally in processors, various redundant forms are used in 
hardware to reduce latencies for carry chains.

In software, different representations are often used for extended 
arithmetic, as they can be much more efficient for some types of operations.


At the basic level - for types like "int" in C and the base types in 
Forth - two's complement has emerged as the undisputed winner.

(I think it was Knuth who said the biggest reason to stop using ones' 
complement is that so few people get the apostrophe in the right place!)

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

#29380

On Friday, April 3, 2020 at 3:12:52 AM UTC-4, David Brown wrote:
> 
> (I think it was Knuth who said the biggest reason to stop using ones' 
> complement is that so few people get the apostrophe in the right place!)

Sounds like an xkcd joke. 

-- 

  Rick C.

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

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

#29382

On 03/04/2020 10:30, Rick C wrote:
> On Friday, April 3, 2020 at 3:12:52 AM UTC-4, David Brown wrote:
>>
>> (I think it was Knuth who said the biggest reason to stop using ones'
>> complement is that so few people get the apostrophe in the right place!)
> 
> Sounds like an xkcd joke.
> 

I don't have a reference to it, but it is certainly believable as the 
kind of thing Knuth would say.  He had both the sense of humour ("I 
can’t go to a restaurant and order food because I keep looking at the 
fonts on the menu") and the obsession about typographic details to have 
said something on those lines.  And people regularly spell it incorrectly.

It is, of course, equally believable that the quotation is a myth, or a 
misattribution.


He certainly /did/ write about the apostrophe:


Donald Knuth, that doyen of computer science, says in Art of Computer 
Programming, Vol 2.:

     Detail-oriented readers and copy-editors should notice the position 
of the apostrophe in terms like "two's complement" and "ones' 
complement": a two's complement number is complemented with respect to a 
single power of 2, whereas a ones' complement number is complemented 
with respect to a long sequence of 1s. Indeed, there is also a twos' 
complement notation, which has radix 3 and complementation with respect 
to (2...22) (base 3).

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

#29364

Clifford Heath <no.spam@please.net> writes:
> Ultimately I want an RPi-like module with a GPU  that supports
> CUDA...

CUDA is basically Nvidia-specific.  You're more likely to find OpenCL on
those sorts of boards.  E.g. web search on "opencl odroid" gets some
hits, though it's not clear it uses the odroid's gpu.

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

#29367

On 2/4/20 4:43 am, Paul Rubin wrote:
> Clifford Heath <no.spam@please.net> writes:
>> Ultimately I want an RPi-like module with a GPU  that supports
>> CUDA...
> 
> CUDA is basically Nvidia-specific.  You're more likely to find OpenCL on
> those sorts of boards.  E.g. web search on "opencl odroid" gets some
> hits, though it's not clear it uses the odroid's gpu.

Many thanks for the pointer. It looks like the ODroid-XU3 and -XU4 
(which have the Mali T628MP6 GPU) already have OpenCL support.

I might need to reassign my ODroid-C2 to a different task and get an XU4.

Clifford Heath.

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

#29366

On 2020-03-31 21:07, Clifford Heath wrote:
> 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

But doubles the number of samples, so it's N log2(N).

Cheers

Phil Hobbs

-- 
Dr Philip C D Hobbs
Principal Consultant
ElectroOptical Innovations LLC / Hobbs ElectroOptics
Optics, Electro-optics, Photonics, Analog Electronics
Briarcliff Manor NY 10510

http://electrooptical.net
http://hobbs-eo.com

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

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

csiph-web