On 2/14/2017 7:35 PM, Steve Pope wrote:
> rickman  <gnuarm@gmail.com> wrote:
>
>> On 2/14/2017 5:48 PM, Steve Pope wrote:
>
>>> But you still wouldn't need two multpliers to compute the two
>>> values in my example; just one multiplier plus some other logic
>>> (much less than the gate count of a second multiplier) to take care of
>>> the extremal cases to make the output exactly match.
>
>> It was a *long* way around the woods to get here.  I seriously doubt any
>> logic synthesis tool is going to substitute two multipliers and an adder
>> with a single multiplier and a bunch of other logic.
>
> I very strongly disagree ... minimizing purely combinatorial logic
> is the _sine_qua_non_ of a synthesis tool.
>
> Lots of other things synthesizers try to do are more intricate and less
> predictable, but not this.

I hear you, but I don't think the tools will be able to "see" the 
simplifications as they are not strictly logic simplifications.  Most of 
it is trig.

Take a look at just how the FFT works.  The combinations of 
multiplications work out because of properties of the sine function, not 
because of Boolean logic.

-- 

Rick C

rickman  <gnuarm@gmail.com> wrote:

>On 2/14/2017 5:48 PM, Steve Pope wrote:

>> But you still wouldn't need two multpliers to compute the two
>> values in my example; just one multiplier plus some other logic
>> (much less than the gate count of a second multiplier) to take care of
>> the extremal cases to make the output exactly match.

>It was a *long* way around the woods to get here.  I seriously doubt any 
>logic synthesis tool is going to substitute two multipliers and an adder 
>with a single multiplier and a bunch of other logic.  

I very strongly disagree ... minimizing purely combinatorial logic
is the _sine_qua_non_ of a synthesis tool.  

Lots of other things synthesizers try to do are more intricate and less
predictable, but not this.

Steve

On 2/14/2017 5:48 PM, Steve Pope wrote:
> rickman  <gnuarm@gmail.com> wrote:
>
>> On 2/14/2017 4:56 PM, Steve Pope wrote:
>
>>> rickman  <gnuarm@gmail.com> wrote:
>
>>>> On 2/14/2017 11:39 AM, Steve Pope wrote:
>
>>>>> Tim Wescott  <tim@seemywebsite.com> wrote:
>
>>>>>> On Tue, 14 Feb 2017 06:52:32 +0000, Steve Pope wrote:
>
>>>>>>> If for example you compute (a * b) and also compute (a * -b),
>>>>>>> the synthesizer is smart enough to know there are not two full
>>>>>>> multipliers needed.
>
> Note: I did not say that in an HDL, -(a * b) is equal in a bit-exact
> sense to (a * -b).
>
>>>>>> I'm pretty sure that -(a * b) is not necessarily (a * -b).
>
> We agree
>
>>>> If the tool is going to use a
>>>> single multiplier for calculating (a * b) and (a * -b),
>
>>> Okay so far
>
>>>> that implies it calculates (a * b)  and then negates that to get
>>>> (a * -b) as -(a * b), no?
>
>>> Not necessarily exactly this.
>
>> If not this, then what?  Why are you being so coy?
>
> Because one would have to look at the HDL language definition,
> the declared bit widths and declared data types and possibly other stuff.
>
> But you still wouldn't need two multpliers to compute the two
> values in my example; just one multiplier plus some other logic
> (much less than the gate count of a second multiplier) to take care of
> the extremal cases to make the output exactly match.

It was a *long* way around the woods to get here.  I seriously doubt any 
logic synthesis tool is going to substitute two multipliers and an adder 
with a single multiplier and a bunch of other logic.  Have you seen a 
tool that was that smart?  If so, that is a pretty advanced tool.

BTW, what *are* the extremal[sic] cases?

-- 

Rick C

rickman  <gnuarm@gmail.com> wrote:

>On 2/14/2017 4:56 PM, Steve Pope wrote:

>> rickman  <gnuarm@gmail.com> wrote:

>>> On 2/14/2017 11:39 AM, Steve Pope wrote:

>>>> Tim Wescott  <tim@seemywebsite.com> wrote:

>>>>> On Tue, 14 Feb 2017 06:52:32 +0000, Steve Pope wrote:

>>>>>> If for example you compute (a * b) and also compute (a * -b),
>>>>>> the synthesizer is smart enough to know there are not two full
>>>>>> multipliers needed.

Note: I did not say that in an HDL, -(a * b) is equal in a bit-exact
sense to (a * -b).  

>>>>> I'm pretty sure that -(a * b) is not necessarily (a * -b).

We agree

>>> If the tool is going to use a
>>> single multiplier for calculating (a * b) and (a * -b),

>> Okay so far

>>> that implies it calculates (a * b)  and then negates that to get
>>> (a * -b) as -(a * b), no?

>> Not necessarily exactly this.

>If not this, then what?  Why are you being so coy?

Because one would have to look at the HDL language definition,
the declared bit widths and declared data types and possibly other stuff.

But you still wouldn't need two multpliers to compute the two
values in my example; just one multiplier plus some other logic
(much less than the gate count of a second multiplier) to take care of 
the extremal cases to make the output exactly match.

Steve

On 2/14/2017 3:22 PM, Tim Wescott wrote:
> On Tue, 14 Feb 2017 20:42:12 +0100, Christian Gollwitzer wrote:
>
>> Am 14.02.17 um 20:21 schrieb rickman:
>>> I don't know that -(a * b) wouldn't be exactly the same result as (a *
>>> -b).
>>>
>>>
>> It is bitexact the same. In IEEE float, the sign is signalled by a
>> single bit, it doesn't use two's complement or similar. Therefore, -x
>> simply inverts the sign bit, and it doesnt matter if you do this before
>> or after the multiplication. The only possible corner cases re special
>> values like NaN and Inf; I believe that even then, the result is
>> bitexact the same, but I'm too lazy to check the standard.
>
> While the use of floats in FPGAs is getting more and more common, I
> suspect that there are still loads of FFTs getting done in fixed-point.
>
> I would need to do some very tedious searching to know for sure, but I
> suspect that if there's truncation, potential rollover, or 2's compliment
> values of 'b1000...0 involved, then my condition may be violated.
>
> And I don't know how much an optimizer is going to analyze what's going
> on inside of a DSP block -- if you instantiate one in your design and
> feed it all zeros, is the optimizer smart enough to take it out?

There is such a thing as "hard" IP which means a block of logic that is 
already mapped, placed and routed.  But they are rare, but not subject 
to any optimizations.  Otherwise yes, if you feed a constant into any 
block of logic synthesis will not only replace that logic with constants 
on the output, it will replace all the registers that may be used to 
improve the throughput of the constants.  There are synthesis commands 
to avoid that, but otherwise the tool does as it sees optimal.

The significant optimizations in an FFT come from recognizing all the 
redundant computations which the optimizer will *not* be able to see as 
they are dispersed across columns and rows or time.  Logic optimizations 
are much more obvious and basic.  Otherwise you could just feed the tool 
a DFT and let it work out the details.  Heck, that might get you some 
significant savings.  In a DFT done all at once, the tool might actually 
spot that you are multiplying a given input sample by the same 
coefficient multiple times.  But that's still not an FFT which is much 
more subtle.

-- 

Rick C

On 2/14/2017 4:56 PM, Steve Pope wrote:
> rickman  <gnuarm@gmail.com> wrote:
>
>> On 2/14/2017 11:39 AM, Steve Pope wrote:
>
>>> Tim Wescott  <tim@seemywebsite.com> wrote:
>
>>>> On Tue, 14 Feb 2017 06:52:32 +0000, Steve Pope wrote:
>
>>>>> If for example you compute (a * b) and also compute (a * -b),
>>>>> the synthesizer is smart enough to know there are not two full
>>>>> multipliers needed.
>
>>>> I would be very leery of an optimizer that felt free to optimize things
>>>> so that they are no longer bit-exact --
>
>>> Of course, synthesizers need to be bit-exact and conform to the
>>> HDL language spec
>
>>>> and for some combinations of
>>>> bits, I'm pretty sure that -(a * b) is not necessarily (a * -b).
>
>>> That is not the example I gave, but in either example you still would
>>> not need two multipliers, just one multiplier and some small amount of
>>> logic; any reasonable synthesizer would not use two multipliers
>>> worth of gates.
>
>> How is that not the example you gave?  If the tool is going to use a
>> single multiplier for calculating (a * b) and (a * -b),
>
> Okay so far
>
>> that implies it calculates (a * b)  and then negates that to get
>> (a * -b) as -(a * b), no?
>
> Not necessarily exactly this.

If not this, then what?  Why are you being so coy?


>> I don't know that -(a * b) wouldn't be exactly the same result as (a *
>> -b).
>
> You just answered your own question.

No, that's a separate question.  In fact, as Chris pointed out the IEEE 
floating point format is sign magnitude.  So it doesn't matter when you 
flip the sign bit, the rest of the number will be the same.  For two's 
complement the only issue would be using the values of max negative int 
where there is no positive number with the same magnitude.  But I can't 
construct a case were that would be a problem for this example.  Still, 
if that is a problem for one combination, then there will be cases that 
fail for the other combination.  Typically this is avoided by not using 
the max negative value regardless of the optimizations.

-- 

Rick C

rickman  <gnuarm@gmail.com> wrote:

>On 2/14/2017 11:39 AM, Steve Pope wrote:

>> Tim Wescott  <tim@seemywebsite.com> wrote:

>>> On Tue, 14 Feb 2017 06:52:32 +0000, Steve Pope wrote:

>>>> If for example you compute (a * b) and also compute (a * -b),
>>>> the synthesizer is smart enough to know there are not two full
>>>> multipliers needed.

>>> I would be very leery of an optimizer that felt free to optimize things
>>> so that they are no longer bit-exact --

>> Of course, synthesizers need to be bit-exact and conform to the
>> HDL language spec

>>> and for some combinations of
>>> bits, I'm pretty sure that -(a * b) is not necessarily (a * -b).

>> That is not the example I gave, but in either example you still would
>> not need two multipliers, just one multiplier and some small amount of
>> logic; any reasonable synthesizer would not use two multipliers
>> worth of gates.

>How is that not the example you gave?  If the tool is going to use a 
>single multiplier for calculating (a * b) and (a * -b), 

Okay so far

> that implies it calculates (a * b)  and then negates that to get 
> (a * -b) as -(a * b), no?

Not necessarily exactly this.

>I don't know that -(a * b) wouldn't be exactly the same result as (a * 
>-b).

You just answered your own question.

Steve

On Tue, 14 Feb 2017 20:42:12 +0100, Christian Gollwitzer wrote:

> Am 14.02.17 um 20:21 schrieb rickman:
>> I don't know that -(a * b) wouldn't be exactly the same result as (a *
>> -b).
>>
>>
> It is bitexact the same. In IEEE float, the sign is signalled by a
> single bit, it doesn't use two's complement or similar. Therefore, -x
> simply inverts the sign bit, and it doesnt matter if you do this before
> or after the multiplication. The only possible corner cases re special
> values like NaN and Inf; I believe that even then, the result is
> bitexact the same, but I'm too lazy to check the standard.

While the use of floats in FPGAs is getting more and more common, I 
suspect that there are still loads of FFTs getting done in fixed-point.

I would need to do some very tedious searching to know for sure, but I 
suspect that if there's truncation, potential rollover, or 2's compliment 
values of 'b1000...0 involved, then my condition may be violated.

And I don't know how much an optimizer is going to analyze what's going 
on inside of a DSP block -- if you instantiate one in your design and 
feed it all zeros, is the optimizer smart enough to take it out?
 
-- 
Tim Wescott
Control systems, embedded software and circuit design
I'm looking for work!  See my website if you're interested
http://www.wescottdesign.com

Am 14.02.17 um 20:21 schrieb rickman:
> I don't know that -(a * b) wouldn't be exactly the same result as (a * -b).
>

It is bitexact the same. In IEEE float, the sign is signalled by a 
single bit, it doesn't use two's complement or similar. Therefore, -x 
simply inverts the sign bit, and it doesnt matter if you do this before 
or after the multiplication. The only possible corner cases re special 
values like NaN and Inf; I believe that even then, the result is 
bitexact the same, but I'm too lazy to check the standard.

	Christian

On 2/14/2017 11:39 AM, Steve Pope wrote:
> Tim Wescott  <tim@seemywebsite.com> wrote:
>
>> On Tue, 14 Feb 2017 06:52:32 +0000, Steve Pope wrote:
>
>>> If for example you compute (a * b) and also compute (a * -b),
>>> the synthesizer is smart enough to know there are not two full
>>> multipliers needed.
>
>> I would be very leery of an optimizer that felt free to optimize things
>> so that they are no longer bit-exact --
>
> Of course, synthesizers need to be bit-exact and conform to the
> HDL language spec
>
>> and for some combinations of
>> bits, I'm pretty sure that -(a * b) is not necessarily (a * -b).
>
> That is not the example I gave, but in either example you still would
> not need two multipliers, just one multiplier and some small amount of
> logic; any reasonable synthesizer would not use two multipliers
> worth of gates.

How is that not the example you gave?  If the tool is going to use a 
single multiplier for calculating (a * b) and (a * -b), that implies it 
calculates (a * b)  and then negates that to get (a * -b) as -(a * b), no?

I don't know that -(a * b) wouldn't be exactly the same result as (a * 
-b).

-- 

Rick C