Everybody should know that a signed division by 2^n cannot be
done with a single right shift :-) but having this as a single
instruction instead of four without branches, three with a branch
or two if you happen to own a POWER would make sense, especially
a conditional add of 2**n - 1 should be easier to do in hardware
than in software.

Does ISA actually implement this?

On 2021-05-11, Thomas Koenig wrote:
> Everybody should know that a signed division by 2^n cannot be
> done with a single right shift :-) but having this as a single
> instruction instead of four without branches, three with a branch
> or two if you happen to own a POWER would make sense, especially
> a conditional add of 2**n - 1 should be easier to do in hardware
> than in software.
>
> Does ISA actually implement this?
>

Good point. I think that many programmers mistakenly do x >> n
thinking that they implement x / 2^n, even when x is a signed
integer. Likewise, many programmers probably think that x / 2^n
will automatically be converted to a plain shift, which is only
true for unsigned integers.

In other words - there may be a use for such an instruction.

Different ISA:s perform differently, of course. E.g. see what
happens on godbolt.org (one of my favorite online services):

https://godbolt.org/z/KGKnqzasz

For the C code:

int div16(int x) {
return x / 16;
}

....different compilers and ISA:s seem to produce between 3 and
6 instructions (excluding the return).

/Marcus

On 5/11/2021 3:44 AM, Thomas Koenig wrote:
> Everybody should know that a signed division by 2^n cannot be
> done with a single right shift :-) but having this as a single
> instruction instead of four without branches, three with a branch
> or two if you happen to own a POWER would make sense, especially
> a conditional add of 2**n - 1 should be easier to do in hardware
> than in software.
>
> Does ISA actually implement this?

If you are talking about a "sign preserving" right shift (i.e. algebraic
versus logical shift), then yes, there are ISAs that implement that
instruction.

--
- Stephen Fuld
(e-mail address disguised to prevent spam)

On Tuesday, May 11, 2021 at 11:38:22 AM UTC-5, Marcus wrote:
> On 2021-05-11, Thomas Koenig wrote:
> > Everybody should know that a signed division by 2^n cannot be
> > done with a single right shift :-) but having this as a single
> > instruction instead of four without branches, three with a branch
> > or two if you happen to own a POWER would make sense, especially
> > a conditional add of 2**n - 1 should be easier to do in hardware
> > than in software.
> >
> > Does ISA actually implement this?
> >
> Good point. I think that many programmers mistakenly do x >> n
> thinking that they implement x / 2^n, even when x is a signed
> integer. Likewise, many programmers probably think that x / 2^n
> will automatically be converted to a plain shift, which is only
> true for unsigned integers.
<
I taught a FORTRAN compiler to do the 4 instruction version
way back in 1981.
>
> In other words - there may be a use for such an instruction.
<
Also note: this is one compelling reason for 1s-complement
arithmetics.
>
> Different ISA:s perform differently, of course. E.g. see what
> happens on godbolt.org (one of my favorite online services):
>
> https://godbolt.org/z/KGKnqzasz
>
> For the C code:
>
> int div16(int x) {
> return x / 16;
> }
>
> ...different compilers and ISA:s seem to produce between 3 and
> 6 instructions (excluding the return).
>
> /Marcus

Thomas Koenig <tkoenig@netcologne.de> writes:
>Everybody should know that a signed division by 2^n cannot be
>done with a single right shift :-)

Depends on the language and sometimes on its implementation. E.g., on
Gforth:

-9 4 / . -3 ok
-9 2 arshift . -3 ok

>but having this as a single
>instruction instead of four without branches, three with a branch
>or two if you happen to own a POWER would make sense, especially
>a conditional add of 2**n - 1 should be easier to do in hardware
>than in software.
>
>Does ISA actually implement this?

Even Aarch64, which supports pretty exotic stuff in some cases, needs
4 instructions for a signed symmetric division (or at least that's
what I get with gcc).

Is this frequent enough to merit a special instruction? Or do people
use unsigned numbers or explicit shift if they are
performance-conscious and want to divide by 2^n?

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

What percentage of integer {signed and unsigned} arithmetic
uses saturated semantics ?

MitchAlsup <MitchAlsup@aol.com> schrieb:

> What percentage of integer {signed and unsigned} arithmetic
> uses saturated semantics ?

What programming language supports or demands it? I am
only aware of the "unsigned wraps around, integer overflow
is undefined" variety.

On 5/11/2021 3:44 AM, Thomas Koenig wrote:
> Everybody should know that a signed division by 2^n cannot be
> done with a single right shift :-) but having this as a single
> instruction instead of four without branches, three with a branch
> or two if you happen to own a POWER would make sense, especially
> a conditional add of 2**n - 1 should be easier to do in hardware
> than in software.
>
> Does ISA actually implement this?
>

Yes. Mill right shift carries a rounding mode attribute, like FP, which
gives this behavior among other interesting things. The tool chain
replaces signed DIV with the corresponding single shift instruction as a
peephole. And left shift carries an overflow behavior attribute too
(modulo/saturate/throw/double width result).

It appears that Thomas Koenig <tkoenig@netcologne.de> said:
>MitchAlsup <MitchAlsup@aol.com> schrieb:
>
>> What percentage of integer {signed and unsigned} arithmetic
>> uses saturated semantics ?
>
>What programming language supports or demands it? I am
>only aware of the "unsigned wraps around, integer overflow
>is undefined" variety.

Given that many popular chips have dedicated hardware that does saturated
arithmetic, there must be something that uses it.

R's,
John
--
Regards,
John Levine, johnl@taugh.com, Primary Perpetrator of "The Internet for Dummies",
Please consider the environment before reading this e-mail. https://jl.ly

On Tuesday, May 11, 2021 at 3:58:58 PM UTC-5, John Levine wrote:
> It appears that Thomas Koenig <tko...@netcologne.de> said:
> >MitchAlsup <Mitch...@aol.com> schrieb:
> >
> >> What percentage of integer {signed and unsigned} arithmetic
> >> uses saturated semantics ?
> >
> >What programming language supports or demands it? I am
> >only aware of the "unsigned wraps around, integer overflow
> >is undefined" variety.
<
> Given that many popular chips have dedicated hardware that does saturated
> arithmetic, there must be something that uses it.
<
Graphics languages use it so that RGB blending does not wrap.
>
> R's,
> John
> --
> Regards,
> John Levine, jo...@taugh.com, Primary Perpetrator of "The Internet for Dummies",
> Please consider the environment before reading this e-mail. https://jl.ly

On 5/11/21 3:58 PM, John Levine wrote:
> It appears that Thomas Koenig <tkoenig@netcologne.de> said:
>> MitchAlsup <MitchAlsup@aol.com> schrieb:
>>
>>> What percentage of integer {signed and unsigned} arithmetic
>>> uses saturated semantics ?
>>
>> What programming language supports or demands it? I am
>> only aware of the "unsigned wraps around, integer overflow
>> is undefined" variety.
>
> Given that many popular chips have dedicated hardware that does saturated
> arithmetic, there must be something that uses it.
>
Signal processing code is full of saturating arithmetic. But I don't know of
any programming language that supports it directly. LLVM supports saturated
add/sub in the intermediate language. Not sure if anything uses it yet.

brian

> R's,
> John
>

On 5/11/2021 12:32 PM, Anton Ertl wrote:
> Thomas Koenig <tkoenig@netcologne.de> writes:
>> Everybody should know that a signed division by 2^n cannot be
>> done with a single right shift :-)
>
> Depends on the language and sometimes on its implementation. E.g., on
> Gforth:
>
> -9 4 / . -3 ok
> -9 2 arshift . -3 ok
>
>> but having this as a single
>> instruction instead of four without branches, three with a branch
>> or two if you happen to own a POWER would make sense, especially
>> a conditional add of 2**n - 1 should be easier to do in hardware
>> than in software.
>>
>> Does ISA actually implement this?
>
> Even Aarch64, which supports pretty exotic stuff in some cases, needs
> 4 instructions for a signed symmetric division (or at least that's
> what I get with gcc).
>
> Is this frequent enough to merit a special instruction? Or do people
> use unsigned numbers or explicit shift if they are
> performance-conscious and want to divide by 2^n?
>

It seems like it could be supported...

However the ways I can think of it would likely add enough cost and
latency to the shift unit to make it "not likely worthwhile".

Option 1, if input is negative:
Negate Input;
Do Shift;
Negate Output.

Option 2, if input is negative:
Detect if ((Input&((1<<n)-1))!=0);
If So, Add 1 to output.

If one had an absolute-value instruction which set a status flag based
on whether or not the input was negative, this could be combined with a
conditional negate to reduce it to 3 instructions.

....

On 5/13/2021 11:59 PM, BGB wrote:
> On 5/11/2021 12:32 PM, Anton Ertl wrote:
>> Thomas Koenig <tkoenig@netcologne.de> writes:
>>> Everybody should know that a signed division by 2^n cannot be
>>> done with a single right shift :-)
>>
>> Depends on the language and sometimes on its implementation.  E.g., on
>> Gforth:
>>
>> -9 4 / . -3  ok
>> -9 2 arshift . -3  ok
>>
>>> but having this as a single
>>> instruction instead of four without branches, three with a branch
>>> or two if you happen to own a POWER would make sense, especially
>>> a conditional add of 2**n - 1 should be easier to do in hardware
>>> than in software.
>>>
>>> Does ISA actually implement this?
>>
>> Even Aarch64, which supports pretty exotic stuff in some cases, needs
>> 4 instructions for a signed symmetric division (or at least that's
>> what I get with gcc).
>>
>> Is this frequent enough to merit a special instruction?  Or do people
>> use unsigned numbers or explicit shift if they are
>> performance-conscious and want to divide by 2^n?
>>
>
> It seems like it could be supported...
>
> However the ways I can think of it would likely add enough cost and
> latency to the shift unit to make it "not likely worthwhile".
>
> Option 1, if input is negative:
>  Negate Input;
>  Do Shift;
>  Negate Output.
>
> Option 2, if input is negative:
>  Detect if ((Input&((1<<n)-1))!=0);
>  If So, Add 1 to output.
>
>
> If one had an absolute-value instruction which set a status flag based
> on whether or not the input was negative, this could be combined with a
> conditional negate to reduce it to 3 instructions.
>
> ...

Or just integrate the integer shifter with the FP normalization shifter
and apply the right rounding mode.

Ivan Godard <ivan@millcomputing.com> writes:
>Or just integrate the integer shifter with the FP normalization shifter
>and apply the right rounding mode.

It's funny: signed integers are 2s-complement, and shift right
naturally floors (rounds towards negaitve infinity). FP numbers are
sign/magnitude, and shift right naturally rounds towards 0. But FP
also has rounding modes that have to take the sign bit into account,
and you can use that rounding correction to implement round-towards-0
for integers. I think the right rounding mode is flooring (it
increases the negative magnitude of an FP number), which is
particularly ironic.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

BGB <cr88192@gmail.com> schrieb:

> Option 1, if input is negative:
> Negate Input;
> Do Shift;
> Negate Output.
>
> Option 2, if input is negative:
> Detect if ((Input&((1<<n)-1))!=0);
> If So, Add 1 to output.
>
>
> If one had an absolute-value instruction which set a status flag based
> on whether or not the input was negative, this could be combined with a
> conditional negate to reduce it to 3 instructions.

Hacker's Delight gives a two instruction sequence for POWER using
its shrsi instruction. This shifts right and sets the carry bit
if the number being shifted is negative and one or more 1-bits
are being shifted out. Combine this with an instruction to add
the carry bit to a register, and you're at two instructions.

One example of such an instruction is sradi.

Ivan Godard wrote:
> On 5/13/2021 11:59 PM, BGB wrote:
>> On 5/11/2021 12:32 PM, Anton Ertl wrote:
>>> Thomas Koenig <tkoenig@netcologne.de> writes:
>>>> Everybody should know that a signed division by 2^n cannot be
>>>> done with a single right shift :-)
>>>
>>> Depends on the language and sometimes on its implementation.  E.g., on
>>> Gforth:
>>>
>>> -9 4 / . -3  ok
>>> -9 2 arshift . -3  ok
>>>
>>>> but having this as a single
>>>> instruction instead of four without branches, three with a branch
>>>> or two if you happen to own a POWER would make sense, especially
>>>> a conditional add of 2**n - 1 should be easier to do in hardware
>>>> than in software.
>>>>
>>>> Does ISA actually implement this?
>>>
>>> Even Aarch64, which supports pretty exotic stuff in some cases, needs
>>> 4 instructions for a signed symmetric division (or at least that's
>>> what I get with gcc).
>>>
>>> Is this frequent enough to merit a special instruction?  Or do people
>>> use unsigned numbers or explicit shift if they are
>>> performance-conscious and want to divide by 2^n?
>>>
>>
>> It seems like it could be supported...
>>
>> However the ways I can think of it would likely add enough cost and
>> latency to the shift unit to make it "not likely worthwhile".
>>
>> Option 1, if input is negative:
>>  Â Negate Input;
>>  Â Do Shift;
>>  Â Negate Output.
>>
>> Option 2, if input is negative:
>>  Â Detect if ((Input&((1<<n)-1))!=0);
>>  Â If So, Add 1 to output.
>>
>>
>> If one had an absolute-value instruction which set a status flag based
>> on whether or not the input was negative, this could be combined with
>> a conditional negate to reduce it to 3 instructions.
>>
>> ...
>
> Or just integrate the integer shifter with the FP normalization shifter
> and apply the right rounding mode.

Exactly!

If you can do trunc/floor/ceil/nearest_or_even then it is easy to handle
negative values in whatever way the language requires.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

On Friday, May 14, 2021 at 2:10:23 AM UTC-5, Ivan Godard wrote:
> On 5/13/2021 11:59 PM, BGB wrote:
> > On 5/11/2021 12:32 PM, Anton Ertl wrote:
> >> Thomas Koenig <tko...@netcologne.de> writes:
> >>> Everybody should know that a signed division by 2^n cannot be
> >>> done with a single right shift :-)
> >>
> >> Depends on the language and sometimes on its implementation. E.g., on
> >> Gforth:
> >>
> >> -9 4 / . -3 ok
> >> -9 2 arshift . -3 ok
> >>
> >>> but having this as a single
> >>> instruction instead of four without branches, three with a branch
> >>> or two if you happen to own a POWER would make sense, especially
> >>> a conditional add of 2**n - 1 should be easier to do in hardware
> >>> than in software.
> >>>
> >>> Does ISA actually implement this?
> >>
> >> Even Aarch64, which supports pretty exotic stuff in some cases, needs
> >> 4 instructions for a signed symmetric division (or at least that's
> >> what I get with gcc).
> >>
> >> Is this frequent enough to merit a special instruction? Or do people
> >> use unsigned numbers or explicit shift if they are
> >> performance-conscious and want to divide by 2^n?
> >>
> >
> > It seems like it could be supported...
> >
> > However the ways I can think of it would likely add enough cost and
> > latency to the shift unit to make it "not likely worthwhile".
> >
> > Option 1, if input is negative:
> > Negate Input;
> > Do Shift;
> > Negate Output.
> >
> > Option 2, if input is negative:
> > Detect if ((Input&((1<<n)-1))!=0);
> > If So, Add 1 to output.
> >
> >
> > If one had an absolute-value instruction which set a status flag based
> > on whether or not the input was negative, this could be combined with a
> > conditional negate to reduce it to 3 instructions.
> >
> > ...
> Or just integrate the integer shifter with the FP normalization shifter
> and apply the right rounding mode.
<
Here you go again, putting Integer Instructions through the FP units......
<
In before the separate Register file crowd.

On 5/14/2021 2:10 AM, Ivan Godard wrote:
> On 5/13/2021 11:59 PM, BGB wrote:
>> On 5/11/2021 12:32 PM, Anton Ertl wrote:
>>> Thomas Koenig <tkoenig@netcologne.de> writes:
>>>> Everybody should know that a signed division by 2^n cannot be
>>>> done with a single right shift :-)
>>>
>>> Depends on the language and sometimes on its implementation.  E.g., on
>>> Gforth:
>>>
>>> -9 4 / . -3  ok
>>> -9 2 arshift . -3  ok
>>>
>>>> but having this as a single
>>>> instruction instead of four without branches, three with a branch
>>>> or two if you happen to own a POWER would make sense, especially
>>>> a conditional add of 2**n - 1 should be easier to do in hardware
>>>> than in software.
>>>>
>>>> Does ISA actually implement this?
>>>
>>> Even Aarch64, which supports pretty exotic stuff in some cases, needs
>>> 4 instructions for a signed symmetric division (or at least that's
>>> what I get with gcc).
>>>
>>> Is this frequent enough to merit a special instruction?  Or do people
>>> use unsigned numbers or explicit shift if they are
>>> performance-conscious and want to divide by 2^n?
>>>
>>
>> It seems like it could be supported...
>>
>> However the ways I can think of it would likely add enough cost and
>> latency to the shift unit to make it "not likely worthwhile".
>>
>> Option 1, if input is negative:
>>   Negate Input;
>>   Do Shift;
>>   Negate Output.
>>
>> Option 2, if input is negative:
>>   Detect if ((Input&((1<<n)-1))!=0);
>>   If So, Add 1 to output.
>>
>>
>> If one had an absolute-value instruction which set a status flag based
>> on whether or not the input was negative, this could be combined with
>> a conditional negate to reduce it to 3 instructions.
>>
>> ...
>
> Or just integrate the integer shifter with the FP normalization shifter
> and apply the right rounding mode.

It is possible.

I was going to assert originally that these is a problem if the
renormalization shifter:
Only does a left-shift;
Isn't quite wide enough to be used for integer shifts;
...

But, then realized, this probably meant to use the input-side right
shifter, followed by the main adder (say, internally it uses a 64-bit
adder with a carry-in flag), and already implements some similar logic
for other reasons, ...

It actually seems possible, as the logic is basically analogous to doing
the Int->Float and Float->Int conversion logic at the same time, and
fudging one of the exponents to cause it to implement a right shift.

So, it should be technically possible to pull off something like this
via slight tweaks to an FADD unit...

....

On Friday, May 14, 2021 at 11:00:53 AM UTC-5, BGB wrote:
> On 5/14/2021 2:10 AM, Ivan Godard wrote:
> > On 5/13/2021 11:59 PM, BGB wrote:
> >> On 5/11/2021 12:32 PM, Anton Ertl wrote:
> >>> Thomas Koenig <tko...@netcologne.de> writes:
> >>>> Everybody should know that a signed division by 2^n cannot be
> >>>> done with a single right shift :-)
> >>>
> >>> Depends on the language and sometimes on its implementation. E.g., on
> >>> Gforth:
> >>>
> >>> -9 4 / . -3 ok
> >>> -9 2 arshift . -3 ok
> >>>
> >>>> but having this as a single
> >>>> instruction instead of four without branches, three with a branch
> >>>> or two if you happen to own a POWER would make sense, especially
> >>>> a conditional add of 2**n - 1 should be easier to do in hardware
> >>>> than in software.
> >>>>
> >>>> Does ISA actually implement this?
> >>>
> >>> Even Aarch64, which supports pretty exotic stuff in some cases, needs
> >>> 4 instructions for a signed symmetric division (or at least that's
> >>> what I get with gcc).
> >>>
> >>> Is this frequent enough to merit a special instruction? Or do people
> >>> use unsigned numbers or explicit shift if they are
> >>> performance-conscious and want to divide by 2^n?
> >>>
> >>
> >> It seems like it could be supported...
> >>
> >> However the ways I can think of it would likely add enough cost and
> >> latency to the shift unit to make it "not likely worthwhile".
> >>
> >> Option 1, if input is negative:
> >> Negate Input;
> >> Do Shift;
> >> Negate Output.
> >>
> >> Option 2, if input is negative:
> >> Detect if ((Input&((1<<n)-1))!=0);
> >> If So, Add 1 to output.
> >>
> >>
> >> If one had an absolute-value instruction which set a status flag based
> >> on whether or not the input was negative, this could be combined with
> >> a conditional negate to reduce it to 3 instructions.
> >>
> >> ...
> >
> > Or just integrate the integer shifter with the FP normalization shifter
> > and apply the right rounding mode.
> It is possible.
>
> I was going to assert originally that these is a problem if the
> renormalization shifter:
> Only does a left-shift;
> Isn't quite wide enough to be used for integer shifts;
<
The normalizer in and DP FMAC unit is at least 213-bits wide.
> ...
>
> But, then realized, this probably meant to use the input-side right
> shifter, followed by the main adder (say, internally it uses a 64-bit
> adder with a carry-in flag), and already implements some similar logic
> for other reasons, ...
>
> It actually seems possible, as the logic is basically analogous to doing
> the Int->Float and Float->Int conversion logic at the same time, and
> fudging one of the exponents to cause it to implement a right shift.
>
> So, it should be technically possible to pull off something like this
> via slight tweaks to an FADD unit...
<
Possibly, but the multiplier is dealing with 53+53 bit things minimum,
if said multiplier also FDIV and SQRT then it is 57+57
if said multiplier also Transcendentals then it is 58+58.....
>
> ...

On 5/14/2021 1:04 PM, MitchAlsup wrote:
> On Friday, May 14, 2021 at 11:00:53 AM UTC-5, BGB wrote:
>> On 5/14/2021 2:10 AM, Ivan Godard wrote:
>>> On 5/13/2021 11:59 PM, BGB wrote:
>>>> On 5/11/2021 12:32 PM, Anton Ertl wrote:
>>>>> Thomas Koenig <tko...@netcologne.de> writes:
>>>>>> Everybody should know that a signed division by 2^n cannot be
>>>>>> done with a single right shift :-)
>>>>>
>>>>> Depends on the language and sometimes on its implementation. E.g., on
>>>>> Gforth:
>>>>>
>>>>> -9 4 / . -3 ok
>>>>> -9 2 arshift . -3 ok
>>>>>
>>>>>> but having this as a single
>>>>>> instruction instead of four without branches, three with a branch
>>>>>> or two if you happen to own a POWER would make sense, especially
>>>>>> a conditional add of 2**n - 1 should be easier to do in hardware
>>>>>> than in software.
>>>>>>
>>>>>> Does ISA actually implement this?
>>>>>
>>>>> Even Aarch64, which supports pretty exotic stuff in some cases, needs
>>>>> 4 instructions for a signed symmetric division (or at least that's
>>>>> what I get with gcc).
>>>>>
>>>>> Is this frequent enough to merit a special instruction? Or do people
>>>>> use unsigned numbers or explicit shift if they are
>>>>> performance-conscious and want to divide by 2^n?
>>>>>
>>>>
>>>> It seems like it could be supported...
>>>>
>>>> However the ways I can think of it would likely add enough cost and
>>>> latency to the shift unit to make it "not likely worthwhile".
>>>>
>>>> Option 1, if input is negative:
>>>> Negate Input;
>>>> Do Shift;
>>>> Negate Output.
>>>>
>>>> Option 2, if input is negative:
>>>> Detect if ((Input&((1<<n)-1))!=0);
>>>> If So, Add 1 to output.
>>>>
>>>>
>>>> If one had an absolute-value instruction which set a status flag based
>>>> on whether or not the input was negative, this could be combined with
>>>> a conditional negate to reduce it to 3 instructions.
>>>>
>>>> ...
>>>
>>> Or just integrate the integer shifter with the FP normalization shifter
>>> and apply the right rounding mode.
>> It is possible.
>>
>> I was going to assert originally that these is a problem if the
>> renormalization shifter:
>> Only does a left-shift;
>> Isn't quite wide enough to be used for integer shifts;
> <
> The normalizer in and DP FMAC unit is at least 213-bits wide.

Yeah ... 64 -> 54 bits (narrowing shift) ...

With rounding carry propagation limited to 12-bits in this case.

There is a possibility for long strings of 1s, but the cases that lead
to them mostly disappear if one does a carry-in during the main adder.

One of the things that helped "kill" my Long-Double FPU effort was
trying to widen these parts to 90 bits.

The Long-Double FPU would have still been too narrow to ensure
correctly-rounded Double values though, but would have reduced their
probability somewhat.

LUT cost was an issue, and timing was pretty tight at 50MHz.
I had to invoke a lot of fiddly to "make it work" here.

More recently I have applied some of the tweaks to the DP FPU to get it
to pass timing at 75MHz (and make a change that ended up leading to FADD
and FMUL being 7-cycle operations).

I can only guess what sorts of damage a 213 bit mantissa would do...

Occasional rounding errors seem like a better trade-off IMO.

>> ...
>>
>> But, then realized, this probably meant to use the input-side right
>> shifter, followed by the main adder (say, internally it uses a 64-bit
>> adder with a carry-in flag), and already implements some similar logic
>> for other reasons, ...
>>
>> It actually seems possible, as the logic is basically analogous to doing
>> the Int->Float and Float->Int conversion logic at the same time, and
>> fudging one of the exponents to cause it to implement a right shift.
>>
>> So, it should be technically possible to pull off something like this
>> via slight tweaks to an FADD unit...
> <
> Possibly, but the multiplier is dealing with 53+53 bit things minimum,
> if said multiplier also FDIV and SQRT then it is 57+57
> if said multiplier also Transcendentals then it is 58+58.....

This is assuming one uses a "square" multiplier, rather than a
"triangular" multiplier.

As-is:
Square Multiplier: 54*54 -> 108
Triangular Multiplier: 54*54 -> 72

The LongDouble used a wider multiplier:
72*72->90 (initial)
85*85->90 (likely needed to avoid some issues, *)

*: Algorithms based on iterative convergence get stuck in an infinite
loop if FADDX and FMULX use different mantissa lengths.

This means that I would need to make them agree on a fixed 80-bit mantissa.

Or: S.E15.F80.P32 (where P=Zero Padding)

I did at one point start trying to implement a combined FMAC unit, but
then realized it was likely to have a fairly high latency.

An FPU with a separate FADD and FMUL unit could give lower latency for
FADD and FMUL, and could fake FMAC with only slightly higher latency
than the combined unit.

There are some operations though which could exist with an FMAC unit
which would not work correctly with an FMUL+FADD glued together, but I
am already pushing the limits of what seems viable on the XC7A100T.

On Friday, May 14, 2021 at 2:23:49 PM UTC-5, BGB wrote:
> On 5/14/2021 1:04 PM, MitchAlsup wrote:
> > On Friday, May 14, 2021 at 11:00:53 AM UTC-5, BGB wrote:
> >> On 5/14/2021 2:10 AM, Ivan Godard wrote:
> >>> On 5/13/2021 11:59 PM, BGB wrote:
> >>>> On 5/11/2021 12:32 PM, Anton Ertl wrote:
> >>>>> Thomas Koenig <tko...@netcologne.de> writes:
> >>>>>> Everybody should know that a signed division by 2^n cannot be
> >>>>>> done with a single right shift :-)
> >>>>>
> >>>>> Depends on the language and sometimes on its implementation. E.g., on
> >>>>> Gforth:
> >>>>>
> >>>>> -9 4 / . -3 ok
> >>>>> -9 2 arshift . -3 ok
> >>>>>
> >>>>>> but having this as a single
> >>>>>> instruction instead of four without branches, three with a branch
> >>>>>> or two if you happen to own a POWER would make sense, especially
> >>>>>> a conditional add of 2**n - 1 should be easier to do in hardware
> >>>>>> than in software.
> >>>>>>
> >>>>>> Does ISA actually implement this?
> >>>>>
> >>>>> Even Aarch64, which supports pretty exotic stuff in some cases, needs
> >>>>> 4 instructions for a signed symmetric division (or at least that's
> >>>>> what I get with gcc).
> >>>>>
> >>>>> Is this frequent enough to merit a special instruction? Or do people
> >>>>> use unsigned numbers or explicit shift if they are
> >>>>> performance-conscious and want to divide by 2^n?
> >>>>>
> >>>>
> >>>> It seems like it could be supported...
> >>>>
> >>>> However the ways I can think of it would likely add enough cost and
> >>>> latency to the shift unit to make it "not likely worthwhile".
> >>>>
> >>>> Option 1, if input is negative:
> >>>> Negate Input;
> >>>> Do Shift;
> >>>> Negate Output.
> >>>>
> >>>> Option 2, if input is negative:
> >>>> Detect if ((Input&((1<<n)-1))!=0);
> >>>> If So, Add 1 to output.
> >>>>
> >>>>
> >>>> If one had an absolute-value instruction which set a status flag based
> >>>> on whether or not the input was negative, this could be combined with
> >>>> a conditional negate to reduce it to 3 instructions.
> >>>>
> >>>> ...
> >>>
> >>> Or just integrate the integer shifter with the FP normalization shifter
> >>> and apply the right rounding mode.
> >> It is possible.
> >>
> >> I was going to assert originally that these is a problem if the
> >> renormalization shifter:
> >> Only does a left-shift;
> >> Isn't quite wide enough to be used for integer shifts;
> > <
> > The normalizer in and DP FMAC unit is at least 213-bits wide.
<
> Yeah ... 64 -> 54 bits (narrowing shift) ...
>
> With rounding carry propagation limited to 12-bits in this case.
>
> There is a possibility for long strings of 1s, but the cases that lead
> to them mostly disappear if one does a carry-in during the main adder.
>
> One of the things that helped "kill" my Long-Double FPU effort was
> trying to widen these parts to 90 bits.
>
>
> The Long-Double FPU would have still been too narrow to ensure
> correctly-rounded Double values though, but would have reduced their
> probability somewhat.
>
> LUT cost was an issue, and timing was pretty tight at 50MHz.
> I had to invoke a lot of fiddly to "make it work" here.
>
> More recently I have applied some of the tweaks to the DP FPU to get it
> to pass timing at 75MHz (and make a change that ended up leading to FADD
> and FMUL being 7-cycle operations).
>
>
> I can only guess what sorts of damage a 213 bit mantissa would do...
>
> Occasional rounding errors seem like a better trade-off IMO.
<
Try having that argument with Kahan !!
> >> ...
> >>
> >> But, then realized, this probably meant to use the input-side right
> >> shifter, followed by the main adder (say, internally it uses a 64-bit
> >> adder with a carry-in flag), and already implements some similar logic
> >> for other reasons, ...
> >>
> >> It actually seems possible, as the logic is basically analogous to doing
> >> the Int->Float and Float->Int conversion logic at the same time, and
> >> fudging one of the exponents to cause it to implement a right shift.
> >>
> >> So, it should be technically possible to pull off something like this
> >> via slight tweaks to an FADD unit...
> > <
> > Possibly, but the multiplier is dealing with 53+53 bit things minimum,
> > if said multiplier also FDIV and SQRT then it is 57+57
> > if said multiplier also Transcendentals then it is 58+58.....
<
> This is assuming one uses a "square" multiplier, rather than a
> "triangular" multiplier.
<
The proper word is parallelogram not square
>
> As-is:
> Square Multiplier: 54*54 -> 108
> Triangular Multiplier: 54*54 -> 72
<
I question your definition of triangular::
> Triangular Multiplier: 54×54 -> 54 !?!
>
> The LongDouble used a wider multiplier:
> 72*72->90 (initial)
> 85*85->90 (likely needed to avoid some issues, *)
>
> *: Algorithms based on iterative convergence get stuck in an infinite
> loop if FADDX and FMULX use different mantissa lengths.
>
> This means that I would need to make them agree on a fixed 80-bit mantissa.
>
> Or: S.E15.F80.P32 (where P=Zero Padding)
>
>
> I did at one point start trying to implement a combined FMAC unit, but
> then realized it was likely to have a fairly high latency.
<
Your implementation medium is harming your ability to pull off your design.
>
> An FPU with a separate FADD and FMUL unit could give lower latency for
> FADD and FMUL, and could fake FMAC with only slightly higher latency
> than the combined unit.
<
Maybe,
FADD: 2-cycles is darned hard, 3-cycles is pretty easy.
FMUL: 4-cycles is rather standard for 16-gates/cycle machines.
FMAC: 4-cycles is pretty hard, 5-cycles is a bit better
<
AMD Athlon and Opteron used FADD=4 and FMUL=4 to simplify the
pipelineing and to prevent having both units deliver result in the same
cycle.
<
On the other hand, a single FMAC unit can do it all::
FADD: FMAC 1*Rs1+Rs2
FMUL: FMAC Rs1*Rs2+0
<
So if you find yourself in a position where you need FMAC (say to meet
IEEE 754-2008+) you can have the design team build the FMAC unit.
Later on, when building the next and wider machine, you can add an
FADD or FMUL or both based on statistics you have gathered from
generation 1. Given and FMAC, FADD is a degenerate subset which
a GOOD Verilog compiler can autogenerate if you feed it the above
fixed values {FMAC 1*Rs1+Rs2 and FMAC Rs1*Rs2+0}. THis REALLY
reduces the designer workloads.
>
>
> There are some operations though which could exist with an FMAC unit
> which would not work correctly with an FMUL+FADD glued together, but I
> am already pushing the limits of what seems viable on the XC7A100T.
<
Yep, your implementation medium is getting in your way. So are some of
your tools.

IIUC cycle time (for the EX stage) can be split into:
A- time to perform single-cycle operation
B- time to propagate the result through the forwarding network
C- time for the actual latch/flipflop

Arguably, B and C are overheads.
Has there been ISAs that aim to maximize the proportion of time spent in
A rather than B and C by having instructions that perform several
sequential operations.

I guess the "negate inputs" options in MY66000 (and the shifts in ARM3)
could be counted as such an example, tho a limited one.

I'm thinking more of an ISA where an instruction is expected to do
something like `(A op1 B) op2 C` in a single cycle (for various
combinations of `op1` and `op2` like additions, shifts, and whatnot).

I'm far from convinced it would work out well (there's a risk you'd end
up having to use a NOP for `op1` or `op2` in too many cases), but I'm
curious if someone has tried out something like that,

Stefan

On 5/14/2021 2:55 PM, Stefan Monnier wrote:
>
> IIUC cycle time (for the EX stage) can be split into:
> A- time to perform single-cycle operation
> B- time to propagate the result through the forwarding network
> C- time for the actual latch/flipflop
>
> Arguably, B and C are overheads.
> Has there been ISAs that aim to maximize the proportion of time spent in
> A rather than B and C by having instructions that perform several
> sequential operations.
>
> I guess the "negate inputs" options in MY66000 (and the shifts in ARM3)
> could be counted as such an example, tho a limited one.
>
> I'm thinking more of an ISA where an instruction is expected to do
> something like `(A op1 B) op2 C` in a single cycle (for various
> combinations of `op1` and `op2` like additions, shifts, and whatnot).
>
> I'm far from convinced it would work out well (there's a risk you'd end
> up having to use a NOP for `op1` or `op2` in too many cases), but I'm
> curious if someone has tried out something like that,
>
>
> Stefan
>

Bill Wulf (CMU) did this, but I forget what they called it. Mitch was at
CMU, maybe he remembers. It did address arithmetic real well, MAC, and A
<comp> B <rel> C, others not so mutch. A bit tough fitting two opcodes
and four regs into an instruction IIRC. A Thumb-like subset gets rid of
the noops. Mill's ganging is this in effect.

On Friday, May 14, 2021 at 4:55:16 PM UTC-5, Stefan Monnier wrote:
> IIUC cycle time (for the EX stage) can be split into:
> A- time to perform single-cycle operation
> B- time to propagate the result through the forwarding network
> C- time for the actual latch/flipflop
>
> Arguably, B and C are overheads.
> Has there been ISAs that aim to maximize the proportion of time spent in
> A rather than B and C by having instructions that perform several
> sequential operations.
<
For single cycle back-to-back, this is accurate. C, however, is not a delay
one can get rid of, unless one is not building a fully pipelined machine
(new operation starting every cycle in the same FU.)
>
> I guess the "negate inputs" options in MY66000 (and the shifts in ARM3)
> could be counted as such an example, tho a limited one.
<
For the My 66000 case: negate is an XOR gate where the select input to
the data-path of gates is seen 1.5 cycles before data passes through the
gate. Data gets XORed, and for integer operations, a carry bit is passed
through the network (65-bits) the carry bits are inserted into the 64-bit
adder and adds no delay. For logical instructions the XOR is all that
happens, for FP only the sign bit gets XORed.
>
> I'm thinking more of an ISA where an instruction is expected to do
> something like `(A op1 B) op2 C` in a single cycle (for various
> combinations of `op1` and `op2` like additions, shifts, and whatnot).
>
> I'm far from convinced it would work out well (there's a risk you'd end
> up having to use a NOP for `op1` or `op2` in too many cases), but I'm
> curious if someone has tried out something like that,
<
64-bit integer add is 11-gates with a carry select adder. Take a 16-gate
machine, and this gives you 5-gates for result buffering to drive the
heavily loaded result bus, pass through the forwarding logic, wire delay,
and meet setup time for the flip-flop. Yes, this path is tight. The wider
machine the tighter the path.
<
In K9, we did not have the forwarding path in the "cycle time" and could
not do back-to-back instructions. One of the things that gets dropped
as the gates-per-cycle drop or the machine gets wider or both. This also
changes the time between tag and data in reservation station design.
<
Also notice that the 12-gate-per-cycle design of *Dozer family had a lot
of strange forwarding cases--the wide ones were forwarded, any change
in data size was delayed a cycle because it was asking too much for the
data path (and the integer adder was circuit designed down to 8-gates of
delay while remaining 11-actual gates in the path.
<
Finally note that the characteristic delay of the flip-flop is 5-gates when
you include clock Jitter and clock Skew. so a 16-gate machine actually
cycles at 21-gates of delay. These 5-gates of delay really hurt at an 8-gate
delay pipeline.
<
And there is Mitch's second law:: When you take the logic in a pipelined
machine and divide each stage by 2, you end up with 2.5× as many pipeline
stages !!
>
>
> Stefan

On Friday, May 14, 2021 at 6:11:47 PM UTC-5, Ivan Godard wrote:
> On 5/14/2021 2:55 PM, Stefan Monnier wrote:
> >
> > IIUC cycle time (for the EX stage) can be split into:
> > A- time to perform single-cycle operation
> > B- time to propagate the result through the forwarding network
> > C- time for the actual latch/flipflop
> >
> > Arguably, B and C are overheads.
> > Has there been ISAs that aim to maximize the proportion of time spent in
> > A rather than B and C by having instructions that perform several
> > sequential operations.
> >
> > I guess the "negate inputs" options in MY66000 (and the shifts in ARM3)
> > could be counted as such an example, tho a limited one.
> >
> > I'm thinking more of an ISA where an instruction is expected to do
> > something like `(A op1 B) op2 C` in a single cycle (for various
> > combinations of `op1` and `op2` like additions, shifts, and whatnot).
> >
> > I'm far from convinced it would work out well (there's a risk you'd end
> > up having to use a NOP for `op1` or `op2` in too many cases), but I'm
> > curious if someone has tried out something like that,
> >
> >
> > Stefan
> >
> Bill Wulf (CMU) did this, but I forget what they called it.
<
I don't remember--when I knew Bill, he was involved with PDP-11 stuff
and the BLISS compiler stuff.
<
> Mitch was at
> CMU, maybe he remembers. It did address arithmetic real well, MAC, and A
> <comp> B <rel> C, others not so mutch. A bit tough fitting two opcodes
> and four regs into an instruction IIRC.
<
You don't need 4 registers as the calculations are serially dependent.
More like 3 operands 1 result 2 calculations.
<
> A Thumb-like subset gets rid of
> the noops. Mill's ganging is this in effect.
<
In a packetized instruction fetch model, one can perform instruction fusing
to get the same effect. { CMP-BC, LD-OP, OP-ST, ADD-CMP-BB }