Jeremy Linton wrote:
> On 5/11/2021 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.
>
> Its also seems to be the cases that few C/etc programmers want overflow,
> and likely would be just as happy with saturating operations by default.
> The advantage beyond it just making more sense, is that it closes a
> whole class of security holes caused by incorrect bounds checking.
>
> This like the alias/restrict mess is something that probably should be
> corrected with something similar to "use strict" in a compilation unit
> that reverses the standard behavior unless the programmer explicitly
> asks for overflow or aliasing.

I had only heard about its use for digital signal processing.
DSP's with saturate arithmetic instructions had a competitive advantage.

The noise generated by clipping a signal is much less than wrapping around.

Apparently GCC internally supports saturate arithmetic in its
Register Transfer Language (RTL) presumably for DSP chips.

https://gcc.gnu.org/onlinedocs/gccint/Arithmetic.html

However given the number of codecs now executed on general processors
saturating arithmetic shows up there too
e.g. ARM Cortex-M4 has saturating arithmetic for 8, 16 and 32 bits.

Stefan Monnier <monnier@iro.umontreal.ca> schrieb:

> I just happen to (think I) know that I use them in a way which will
> never overflow (e.g. because it's bounded by something like the number
> of heap allocated objects or the number of elements in an array).

I talked to a guy who had a massively parallel simulation going
on one of the university clusters. He burned a few million Euros
doing his simulations, too.

One of the problems he faced was that his model started failing
mysteriously on the very large problems distributed across too
many compute nodes.

The problem? He had more than 2^31 elements in his flow simulation...

So yes, this is a real problem.

> So Ideally I want the compiler to feel free to perform optimizations
> that assume things like associativity (even though those optimizations
> may cause code which previously overflowed to not overflow any more, and
> vice versa).

That, I cannot agree with. Rewriting code into something that does
not work from something that works is usually called a "compiler
bug" :-) unless it is expressively permitted by the language,
or the user was brave enough to set a flag such as -ffast-math
because of its seductive name.

On Monday, May 24, 2021 at 4:46:08 PM UTC-5, Thomas Koenig wrote:
> Stefan Monnier <mon...@iro.umontreal.ca> schrieb:
> > I just happen to (think I) know that I use them in a way which will
> > never overflow (e.g. because it's bounded by something like the number
> > of heap allocated objects or the number of elements in an array).
> I talked to a guy who had a massively parallel simulation going
> on one of the university clusters. He burned a few million Euros
> doing his simulations, too.
>
> One of the problems he faced was that his model started failing
> mysteriously on the very large problems distributed across too
> many compute nodes.
>
> The problem? He had more than 2^31 elements in his flow simulation...
<
Why was he not using 64-bit containers ?
>
> So yes, this is a real problem.
<
For idiots......
<
> > So Ideally I want the compiler to feel free to perform optimizations
> > that assume things like associativity (even though those optimizations
> > may cause code which previously overflowed to not overflow any more, and
> > vice versa).
> That, I cannot agree with. Rewriting code into something that does
> not work from something that works is usually called a "compiler
> bug" :-) unless it is expressively permitted by the language,
> or the user was brave enough to set a flag such as -ffast-math
> because of its seductive name.

Thomas Koenig [2021-05-24 21:46:06] wrote:
>> I just happen to (think I) know that I use them in a way which will
>> never overflow (e.g. because it's bounded by something like the number
>> of heap allocated objects or the number of elements in an array).
[...]
> The problem? He had more than 2^31 elements in his flow simulation...

Indeed, the use of 32bit `int`s to count heap objects is a common bug in
64bit systems. If the system had crashed with an overflow error,
I think he'd have seen the problem much more quickly.

> Stefan Monnier <monnier@iro.umontreal.ca> schrieb:
>> So Ideally I want the compiler to feel free to perform optimizations
>> that assume things like associativity (even though those optimizations
>> may cause code which previously overflowed to not overflow any more, and
>> vice versa).
>
> That, I cannot agree with. Rewriting code into something that does
> not work from something that works is usually called a "compiler
> bug" :-)

FWIW, I tend to agree. Maybe we only need to allow the compiler to
remove overflow situations, and that should give the compiler a free
enough hand (e.g. to simplify `b + x - b` to `x`).

Stefan

On 5/24/2021 1:14 PM, Stefan Monnier wrote:
>> Its also seems to be the cases that few C/etc programmers want overflow,
>> and likely would be just as happy with saturating operations by default.
>
> In my case, the vast majority of uses of something like `int` is for
> numbers which should be treated as belonging to mathematical set of
> integers (aka Z).
>
> I just happen to (think I) know that I use them in a way which will
> never overflow (e.g. because it's bounded by something like the number
> of heap allocated objects or the number of elements in an array).
>
> So Ideally I want the compiler to feel free to perform optimizations
> that assume things like associativity (even though those optimizations
> may cause code which previously overflowed to not overflow any more, and
> vice versa). But I'd also like to know if my assumptions were wrong
> (aka when `int` failed to model the set Z), so I'd like the code to
> check for overflows and coredump when it happens. It doesn't have to
> coredump exactly when the operation takes place in the code, but it
> should coredump some time between the moment the offending operation
> took place and the next externally-visible effect.
>
>
> Stefan
>

That's exactly Mill semantics for excepting operations: an exception
sets the NaR bit on the result, whose payload holds debug info to locate
the op that threw. Only later, when the NaR is used in something
visible, do you get a hardware fault and core dump or whatever you have
the OS give you.

This lets you speculatively execute potentially excepting ops without
problems if the speculations was untaken.

On 24/05/2021 23:46, Thomas Koenig wrote:
> Stefan Monnier <monnier@iro.umontreal.ca> schrieb:
>
>> I just happen to (think I) know that I use them in a way which will
>> never overflow (e.g. because it's bounded by something like the number
>> of heap allocated objects or the number of elements in an array).
>
> I talked to a guy who had a massively parallel simulation going
> on one of the university clusters. He burned a few million Euros
> doing his simulations, too.
>
> One of the problems he faced was that his model started failing
> mysteriously on the very large problems distributed across too
> many compute nodes.
>
> The problem? He had more than 2^31 elements in his flow simulation...
>
> So yes, this is a real problem.

The problem isn't the overflow handling - it is that he used a type that
was too small for the values it needed to handle. Any kind of overflow
handling (UB, saturation, wrapping, etc.) would also result in the
program not doing what it was supposed to do. Some kind of trapping on
overflow would still not have let the program work - but it would have
made it faster to find the problem.

>
>> So Ideally I want the compiler to feel free to perform optimizations
>> that assume things like associativity (even though those optimizations
>> may cause code which previously overflowed to not overflow any more, and
>> vice versa).
>
> That, I cannot agree with. Rewriting code into something that does
> not work from something that works is usually called a "compiler
> bug" :-) unless it is expressively permitted by the language,
> or the user was brave enough to set a flag such as -ffast-math
> because of its seductive name.
>

I think it is fine for the compiler to perform optimisations that assume
associativity and which cause code which would overflow in a different
integer model to work without overflow. That's the integer model I like
for normal use. But the "vice versa" part needs more care - it's okay
if the compiler introduces new overflows as long as the results are
correct in the end. (So "z = x - y" can be implemented as "u = 2^n - y;
z = x + u;" as long as the overflow of 2^n does not affect the end result.)

I use "-ffast-math" in my floating point code, but I have checked the
flags it sets and effects it has, and know it is safe for the kind of
floating point I handle. I don't think that counts as "brave". Simply
enabling it because it sounds like it makes your maths go faster is
fool-hardy, rather than brave.

Thomas Koenig <tkoenig@netcologne.de> writes:
>One of the problems he faced was that his model started failing
>mysteriously on the very large problems distributed across too
>many compute nodes.
>
>The problem? He had more than 2^31 elements in his flow simulation...

Sounds like what I predicted in 2001 <9jruht$2nb$1@news.tuwien.ac.at>
about I32LP64:

|And many of these bugs will
|surface in the next years, as arrays grow beyond 2G elements.

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

Jeremy Linton <reply-to-list@nospam.org> writes:
>Its also seems to be the cases that few C/etc programmers want overflow,
>and likely would be just as happy with saturating operations by default.

Language like "want overflow" is a sign of muddled thinking. What is
it that you think few programmers want?

* Defined behaviour on overflow? If so, which one?
* Modulo (wraparound) arithmetic
* Trap-on-overflow
* saturating arithmetic
* something else?

* Undefined behaviour on overflow?

* Or do you mean that few c programmers intend overflow to happen?

* Or maybe you think that few C programmers want to think about overflow?

And once you have defined what you mean, on what basis do you make
your claim?

>The advantage beyond it just making more sense, is that it closes a
>whole class of security holes caused by incorrect bounds checking.

Saturation is useful for signal processing, but elsewhere?

If programmers don't want to think about overflow, trapping is usually
more useful for waking them up.

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

On Tuesday, May 25, 2021 at 11:40:59 AM UTC-5, Anton Ertl wrote:
> Jeremy Linton <reply-...@nospam.org> writes:
> >Its also seems to be the cases that few C/etc programmers want overflow,
> >and likely would be just as happy with saturating operations by default.
> Language like "want overflow" is a sign of muddled thinking. What is
> it that you think few programmers want?
>
> * Defined behaviour on overflow? If so, which one?
> * Modulo (wraparound) arithmetic
> * Trap-on-overflow
> * saturating arithmetic
> * something else?
>
> * Undefined behaviour on overflow?
>
> * Or do you mean that few c programmers intend overflow to happen?
>
> * Or maybe you think that few C programmers want to think about overflow?
>
> And once you have defined what you mean, on what basis do you make
> your claim?
> >The advantage beyond it just making more sense, is that it closes a
> >whole class of security holes caused by incorrect bounds checking.
> Saturation is useful for signal processing, but elsewhere?
<
Texture access can saturate at the edge of the texture (or wrap around to
the other side, depending...) and I would not call texture access signal
processing.
>
> If programmers don't want to think about overflow, trapping is usually
> more useful for waking them up.
> - anton
> --
> 'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
> Mitch Alsup, <c17fcd89-f024-40e7...@googlegroups.com>

On Tue, 25 May 2021 15:59:43 GMT, anton@mips.complang.tuwien.ac.at
(Anton Ertl) wrote:

>Saturation is useful for signal processing, but elsewhere?

Also for image processing.

>If programmers don't want to think about overflow, trapping is usually
>more useful for waking them up.

Absolutely.

The real problem is that when programmers really DO want wrap-around
semantics, most often it is for containers whose size is not a
multiple of 8-bit bytes: e.g., 3-bit numbers, 12-bit numbers, etc.

YMMV,
George

On 2021-05-25 21:09, George Neuner wrote:
> On Tue, 25 May 2021 15:59:43 GMT, anton@mips.complang.tuwien.ac.at
> (Anton Ertl) wrote:
>
>> Saturation is useful for signal processing, but elsewhere?
>
> Also for image processing.
>
>
>> If programmers don't want to think about overflow, trapping is usually
>> more useful for waking them up.
>
> Absolutely.
>
> The real problem is that when programmers really DO want wrap-around
> semantics, most often it is for containers whose size is not a
> multiple of 8-bit bytes: e.g., 3-bit numbers, 12-bit numbers, etc.

Ada:

type mod_3_bits is mod 8;
-- Wrap-around arithmetic in the range 0 .. 7.

type mod_12_bits is mod 2**12:
-- Wrap-around arithmetic in the range 0 .. 4095.

etc.

On 25 May 2021, George Neuner wrote
(in article<k3eqaghgtdpepj5b2t9irjto5f4puroanl@4ax.com>):

> On Tue, 25 May 2021 15:59:43 GMT, anton@mips.complang.tuwien.ac.at
> (Anton Ertl) wrote:
>
> > Saturation is useful for signal processing, but elsewhere?
>
> Also for image processing.
>
> > If programmers don't want to think about overflow, trapping is usually
> > more useful for waking them up.
>
> Absolutely.
>
> The real problem is that when programmers really DO want wrap-around
> semantics, most often it is for containers whose size is not a
> multiple of 8-bit bytes: e.g., 3-bit numbers, 12-bit numbers, etc.

Needless to say (?) this is available in Ada.

--
Bill Findlay

George Neuner wrote:
> On Tue, 25 May 2021 15:59:43 GMT, anton@mips.complang.tuwien.ac.at
> (Anton Ertl) wrote:
>
>> Saturation is useful for signal processing, but elsewhere?
>
> Also for image processing.
>
>
>> If programmers don't want to think about overflow, trapping is usually
>> more useful for waking them up.
>
> Absolutely.
>
> The real problem is that when programmers really DO want wrap-around
> semantics, most often it is for containers whose size is not a
> multiple of 8-bit bytes: e.g., 3-bit numbers, 12-bit numbers, etc.

Most old-school programmers learned a long time ago that you should
extend the size of all such arrays/containers/buffers to be a power of
two. :-)

Alternatively you need a way to wrap from a different point, i.e. like
doing BCD math inside a 32 or 64-bit register value you need carries
that jumps from 9 to 16.

The classic method is to add the missing amount and then detect any
carries out from this stage, which you can do with branch-free code but
it is far slower than a simple "n &= 7".

Terje

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

Bill Findlay wrote:
> On 25 May 2021, George Neuner wrote
> (in article<k3eqaghgtdpepj5b2t9irjto5f4puroanl@4ax.com>):
>
>> On Tue, 25 May 2021 15:59:43 GMT, anton@mips.complang.tuwien.ac.at
>> (Anton Ertl) wrote:
>>
>>> Saturation is useful for signal processing, but elsewhere?
>>
>> Also for image processing.

Images are just 2D signals...
>>
>>> If programmers don't want to think about overflow, trapping is usually
>>> more useful for waking them up.

:-)

Terje

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

On Tuesday, May 25, 2021 at 1:09:17 PM UTC-5, George Neuner wrote:
> On Tue, 25 May 2021 15:59:43 GMT, an...@mips.complang.tuwien.ac.at
> (Anton Ertl) wrote:
>
> >Saturation is useful for signal processing, but elsewhere?
> Also for image processing.
> >If programmers don't want to think about overflow, trapping is usually
> >more useful for waking them up.
> Absolutely.
>
> The real problem is that when programmers really DO want wrap-around
> semantics, most often it is for containers whose size is not a
> multiple of 8-bit bytes: e.g., 3-bit numbers, 12-bit numbers, etc.
<
Which is why the Shift instructions in My 66000 can have an optional length
specifier and one can "smash" any container into the proper signed or unsigned
value. SL Rd,Rc,<length:0>.
This <l:0> is a degenerate subset of the extract instruction (which is an extension
of the SL instruction.)
>
> YMMV,
> George

Terje Mathisen <terje.mathisen@tmsw.no> schrieb:
> George Neuner wrote:
>> On Tue, 25 May 2021 15:59:43 GMT, anton@mips.complang.tuwien.ac.at
>> (Anton Ertl) wrote:
>>
>>> Saturation is useful for signal processing, but elsewhere?
>>
>> Also for image processing.
>>
>>
>>> If programmers don't want to think about overflow, trapping is usually
>>> more useful for waking them up.
>>
>> Absolutely.
>>
>> The real problem is that when programmers really DO want wrap-around
>> semantics, most often it is for containers whose size is not a
>> multiple of 8-bit bytes: e.g., 3-bit numbers, 12-bit numbers, etc.
>
> Most old-school programmers learned a long time ago that you should
> extend the size of all such arrays/containers/buffers to be a power of
> two. :-)

Something to unlearn... I worked on Siemens/Fujitsu
VP vector computers for a while. These machines got their memory
speed by having many memory banks, arranged to they could feed
their vector registers at one word per cycle, the memory banks
taking turns.

If you had the lowest dimension of your array as a power of two,
that meant waiting for a single memory bank each time you accessed
an array element along the second-lowest dimension.

The loss in efficiency for having an array like

REAL A(1024,...)

vs

REAL A(1025,...)

was astonishing, a factor of 30 or so IIRC.

I haven't run benchmarks, but I would still avoid using powers
of two for the lowest array dimension on a modern system.

On 25 May 2021, Niklas Holsti wrote
(in article <ih4vkmFlrniU1@mid.individual.net>):

> On 2021-05-25 21:09, George Neuner wrote:
> > On Tue, 25 May 2021 15:59:43 GMT, anton@mips.complang.tuwien.ac.at
> > (Anton Ertl) wrote:
> >
> > > Saturation is useful for signal processing, but elsewhere?
> >
> > Also for image processing.
> >
> >
> > > If programmers don't want to think about overflow, trapping is usually
> > > more useful for waking them up.
> >
> > Absolutely.
> >
> > The real problem is that when programmers really DO want wrap-around
> > semantics, most often it is for containers whose size is not a
> > multiple of 8-bit bytes: e.g., 3-bit numbers, 12-bit numbers, etc.
>
> Ada:
>
> type mod_3_bits is mod 8;
> -- Wrap-around arithmetic in the range 0 .. 7.
>
> type mod_12_bits is mod 2**12:
> -- Wrap-around arithmetic in the range 0 .. 4095.
>
> etc.

Where "etc" means, e.g.:

type NEST_depth is mod 19; -- wraps from 18 to 0

type NEST is array (KDF9.NEST_depth) of KDF9.word;

type SJNS_depth is mod 17; -- wraps from 16 to 0

type SJNS is array (KDF9.SJNS_depth) of KDF9.SJNS_link;

These are real examples from my KDF9 emulator.

--
Bill Findlay

Thomas Koenig wrote:
> Terje Mathisen <terje.mathisen@tmsw.no> schrieb:
>> George Neuner wrote:
>>> On Tue, 25 May 2021 15:59:43 GMT, anton@mips.complang.tuwien.ac.at
>>> (Anton Ertl) wrote:
>>>
>>>> Saturation is useful for signal processing, but elsewhere?
>>>
>>> Also for image processing.
>>>
>>>
>>>> If programmers don't want to think about overflow, trapping is usually
>>>> more useful for waking them up.
>>>
>>> Absolutely.
>>>
>>> The real problem is that when programmers really DO want wrap-around
>>> semantics, most often it is for containers whose size is not a
>>> multiple of 8-bit bytes: e.g., 3-bit numbers, 12-bit numbers, etc.
>>
>> Most old-school programmers learned a long time ago that you should
>> extend the size of all such arrays/containers/buffers to be a power of
>> two. :-)
>
> Something to unlearn... I worked on Siemens/Fujitsu
> VP vector computers for a while. These machines got their memory
> speed by having many memory banks, arranged to they could feed
> their vector registers at one word per cycle, the memory banks
> taking turns.
>
> If you had the lowest dimension of your array as a power of two,
> that meant waiting for a single memory bank each time you accessed
> an array element along the second-lowest dimension.
>
> The loss in efficiency for having an array like
>
> REAL A(1024,...)
>
> vs
>
> REAL A(1025,...)
>
> was astonishing, a factor of 30 or so IIRC.
>
> I haven't run benchmarks, but I would still avoid using powers
> of two for the lowest array dimension on a modern system.
>
I have of course hit that exact problem a number of times, as you write
the standard workaround is to extend array dimensions to a close
(relative) prime, with the 17-way memory layout of an early computer the
canonical example of doing the opposite, i.e. creating a memory
subsystem which wasn't susceptible to these kinds of problems.

I'm assuming they got the idea from the 17-year cicadas which I believe
are swarming this year in the US?

Anyway, the only places where I tend to use these powers of two buffer
sizes are one-dimensional and small enough that the entire buffer will
just use a fraction of $L1.

I personally discovered this problem when writing a sliding window comms
protocol around 1983 (Super Kermit), where my solution was to split my
file buffer size (typically 16-32 KB) in such a way that I could easily
determine the relative starting point of any given packet, even when
each of those could have any given size in the 105 to 9000 range.

As a final note, using a relative prime which is of the form 2^n +/- 1
makes it possible to do the DIV/MOD calculations very fast with cheap
hardware, but today you would probably just use a reciprocal MUL.

Terje

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

On Wednesday, May 26, 2021 at 1:04:41 AM UTC-5, Terje Mathisen wrote:
> Thomas Koenig wrote:
> > Terje Mathisen <terje.m...@tmsw.no> schrieb:
> >> George Neuner wrote:
> >>> On Tue, 25 May 2021 15:59:43 GMT, an...@mips.complang.tuwien.ac.at
> >>> (Anton Ertl) wrote:
> >>>
> >>>> Saturation is useful for signal processing, but elsewhere?
> >>>
> >>> Also for image processing.
> >>>
> >>>
> >>>> If programmers don't want to think about overflow, trapping is usually
> >>>> more useful for waking them up.
> >>>
> >>> Absolutely.
> >>>
> >>> The real problem is that when programmers really DO want wrap-around
> >>> semantics, most often it is for containers whose size is not a
> >>> multiple of 8-bit bytes: e.g., 3-bit numbers, 12-bit numbers, etc.
> >>
> >> Most old-school programmers learned a long time ago that you should
> >> extend the size of all such arrays/containers/buffers to be a power of
> >> two. :-)
> >
> > Something to unlearn... I worked on Siemens/Fujitsu
> > VP vector computers for a while. These machines got their memory
> > speed by having many memory banks, arranged to they could feed
> > their vector registers at one word per cycle, the memory banks
> > taking turns.
> >
> > If you had the lowest dimension of your array as a power of two,
> > that meant waiting for a single memory bank each time you accessed
> > an array element along the second-lowest dimension.
> >
> > The loss in efficiency for having an array like
> >
> > REAL A(1024,...)
> >
> > vs
> >
> > REAL A(1025,...)
> >
> > was astonishing, a factor of 30 or so IIRC.
> >
> > I haven't run benchmarks, but I would still avoid using powers
> > of two for the lowest array dimension on a modern system.
> >
> I have of course hit that exact problem a number of times, as you write
> the standard workaround is to extend array dimensions to a close
> (relative) prime, with the 17-way memory layout of an early computer the
> canonical example of doing the opposite, i.e. creating a memory
> subsystem which wasn't susceptible to these kinds of problems.
<
Boroughs Scientific Processor BSP.
>
> I'm assuming they got the idea from the 17-year cicadas which I believe
> are swarming this year in the US?
>
> Anyway, the only places where I tend to use these powers of two buffer
> sizes are one-dimensional and small enough that the entire buffer will
> just use a fraction of $L1.
>
> I personally discovered this problem when writing a sliding window comms
> protocol around 1983 (Super Kermit), where my solution was to split my
> file buffer size (typically 16-32 KB) in such a way that I could easily
> determine the relative starting point of any given packet, even when
> each of those could have any given size in the 105 to 9000 range.
>
> As a final note, using a relative prime which is of the form 2^n +/- 1
> makes it possible to do the DIV/MOD calculations very fast with cheap
> hardware, but today you would probably just use a reciprocal MUL.
> Terje
>
> --
> - <Terje.Mathisen at tmsw.no>
> "almost all programming can be viewed as an exercise in caching"

On Mi 26 Mai 2021 at 08:04, Terje Mathisen <terje.mathisen@tmsw.no> wrote:

> I have of course hit that exact problem a number of times, as you write
> the standard workaround is to extend array dimensions to a close
> (relative) prime, with the 17-way memory layout of an early computer the
> canonical example of doing the opposite, i.e. creating a memory
> subsystem which wasn't susceptible to these kinds of problems.
>
> I'm assuming they got the idea from the 17-year cicadas which I believe
> are swarming this year in the US?

Well, the only thing that really matters is, that the number is prime.

'Andreas

Andreas Eder wrote:
> On Mi 26 Mai 2021 at 08:04, Terje Mathisen <terje.mathisen@tmsw.no> wrote:
>
>> I have of course hit that exact problem a number of times, as you write
>> the standard workaround is to extend array dimensions to a close
>> (relative) prime, with the 17-way memory layout of an early computer the
>> canonical example of doing the opposite, i.e. creating a memory
>> subsystem which wasn't susceptible to these kinds of problems.
>>
>> I'm assuming they got the idea from the 17-year cicadas which I believe
>> are swarming this year in the US?
>
> Well, the only thing that really matters is, that the number is prime.

Not really: Many of the smaller primes occur far too often in
real/normal code, i.e. 2,3,5 are all unsuitable, 7, 11 or 13 could have
been selected, but 17 have (like 7) fast ways to do the required div/mod
operation, with 17 slightly faster since the base has one more bit.

Terje

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

Terje Mathisen <terje.mathisen@tmsw.no> schrieb:
> Andreas Eder wrote:
>> On Mi 26 Mai 2021 at 08:04, Terje Mathisen <terje.mathisen@tmsw.no> wrote:
>>
>>> I have of course hit that exact problem a number of times, as you write
>>> the standard workaround is to extend array dimensions to a close
>>> (relative) prime, with the 17-way memory layout of an early computer the
>>> canonical example of doing the opposite, i.e. creating a memory
>>> subsystem which wasn't susceptible to these kinds of problems.
>>>
>>> I'm assuming they got the idea from the 17-year cicadas which I believe
>>> are swarming this year in the US?
>>
>> Well, the only thing that really matters is, that the number is prime.
>
> Not really: Many of the smaller primes occur far too often in
> real/normal code, i.e. 2,3,5 are all unsuitable, 7, 11 or 13 could have
> been selected, but 17 have (like 7) fast ways to do the required div/mod
> operation, with 17 slightly faster since the base has one more bit.

In software, dividing and calculating the remainder of 17 would
be done by multiplying with its inverse.

However, having a multiplier on a memory access path seems
excessive. Do you know how they did it? Special case with
shift of signed digits and add?

Thomas Koenig wrote:
> Terje Mathisen <terje.mathisen@tmsw.no> schrieb:
>> Andreas Eder wrote:
>>> On Mi 26 Mai 2021 at 08:04, Terje Mathisen <terje.mathisen@tmsw.no> wrote:
>>>
>>>> I have of course hit that exact problem a number of times, as you write
>>>> the standard workaround is to extend array dimensions to a close
>>>> (relative) prime, with the 17-way memory layout of an early computer the
>>>> canonical example of doing the opposite, i.e. creating a memory
>>>> subsystem which wasn't susceptible to these kinds of problems.
>>>>
>>>> I'm assuming they got the idea from the 17-year cicadas which I believe
>>>> are swarming this year in the US?
>>>
>>> Well, the only thing that really matters is, that the number is prime.
>>
>> Not really: Many of the smaller primes occur far too often in
>> real/normal code, i.e. 2,3,5 are all unsuitable, 7, 11 or 13 could have
>> been selected, but 17 have (like 7) fast ways to do the required div/mod
>> operation, with 17 slightly faster since the base has one more bit.
>
> In software, dividing and calculating the remainder of 17 would
> be done by multiplying with its inverse.
>
> However, having a multiplier on a memory access path seems
> excessive. Do you know how they did it? Special case with
> shift of signed digits and add?
>

Take a look at the hex reciprocal for 17, it seems pretty obvious that
this was a fixed shift & add circuit, i.e. a multi-tap access to the
output of the address generator: 255 is 15*17, with something like 16
MWord address space you only need 24 bits, so 4 copies of that 8-bit
pattern should do the trick.

0x1000000 / 0x11 = 0xf0f0f, which is the same as 0x10101010 - 0x1010101
so you start by taking 4 shifted copies, duplicating the result and
shifting one copy 4 more bits up before you subtract. (You probably need
to force the final bit to zero so that the reciprocal mul (which is what
we're doing) ends up with the correct result.

Terje

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

Terje Mathisen <terje.mathisen@tmsw.no> schrieb:
> Thomas Koenig wrote:

>> However, having a multiplier on a memory access path seems
>> excessive. Do you know how they did it? Special case with
>> shift of signed digits and add?
>>
>
> Take a look at the hex reciprocal for 17, it seems pretty obvious that
> this was a fixed shift & add circuit, i.e. a multi-tap access to the
> output of the address generator: 255 is 15*17, with something like 16
> MWord address space you only need 24 bits, so 4 copies of that 8-bit
> pattern should do the trick.
>
> 0x1000000 / 0x11 = 0xf0f0f, which is the same as 0x10101010 - 0x1010101
> so you start by taking 4 shifted copies, duplicating the result and
> shifting one copy 4 more bits up before you subtract. (You probably need
> to force the final bit to zero so that the reciprocal mul (which is what
> we're doing) ends up with the correct result.

I looked at this a little bit more.

There are two ways this could have been sped up: Using the multiply
high method for division by 17, or determining the remainder of
the division first and then doing the multiplication by the inverse.

Looking at the first method: The "magic number" for division by
17 for 24 bits is 0xf0f0f1, with a rightward shift of 28 bits (in
other words, only the fist 20 bits are significant). Converting to
canoncial signed digits, as you did, gets

0xf0f0f1 = 0x1010101 - 0x0101010

which would mean adding four and subtracting three terms. Then,
multiply by 17 again (single shift and add) and subtract from
the original addess to calculate the remainder.

Another possibility would be to calculate the remainder by
summation of digits, for example by splitting a 24-bit-word into
six nibbles. The lower nibbles of each byte would be their own
remainder, and the upper ones could be calculated with a relatively
simple circuit (four to five bits). Then, there would be three
four- and three five-bit quantities to add, with a final calculation
of the remainder. Subtract that from the original address, then
you know that the address is divisible by 17, and you can use the
multiplication by the inverse modulo 2^24, so lower bits only.

Hm... not sure which method would be faster.

Anyway, this still seems to be a _lot_ of logic to put into your
memory subsystem, both in terms of cost and in terms of delay,
just to account for the fact that some people like array sizes
along the lowest dimension which are divisible by 16. I would
assume that this would cost at least a cycle on each memory access.

Thomas Koenig <tkoenig@netcologne.de> schrieb:
> Terje Mathisen <terje.mathisen@tmsw.no> schrieb:
>> Thomas Koenig wrote:
>
>>> However, having a multiplier on a memory access path seems
>>> excessive. Do you know how they did it? Special case with
>>> shift of signed digits and add?
>>>
>>
>> Take a look at the hex reciprocal for 17, it seems pretty obvious that
>> this was a fixed shift & add circuit, i.e. a multi-tap access to the
>> output of the address generator: 255 is 15*17, with something like 16
>> MWord address space you only need 24 bits, so 4 copies of that 8-bit
>> pattern should do the trick.
>>
>> 0x1000000 / 0x11 = 0xf0f0f, which is the same as 0x10101010 - 0x1010101
>> so you start by taking 4 shifted copies, duplicating the result and
>> shifting one copy 4 more bits up before you subtract. (You probably need
>> to force the final bit to zero so that the reciprocal mul (which is what
>> we're doing) ends up with the correct result.
>
> I looked at this a little bit more.

.... and a bit more.

I missed one important point: If you don't mind wasting 1/17th of
your memory, you don't need an expensive multiplication.

> Another possibility would be to calculate the remainder by
> summation of digits, for example by splitting a 24-bit-word into
> six nibbles. The lower nibbles of each byte would be their own
> remainder, and the upper ones could be calculated with a relatively
> simple circuit (four to five bits). Then, there would be three
> four- and three five-bit quantities to add, with a final calculation
> of the remainder.

or alternatively by summing up the residual by 17 in chunks of
six bits each (three different functions for each of the bits)
which gives you four five-bit numbers. Reduce to two six-bit
numbers by two layers of half and full adders, put it through the
same circuit six to five bit circuit as before, then you have two
five-bit numbers, which you add and put through the final six to
five bit circuit.

The five-bit adder can be simplified a little bit because you
are only adding values from 0 to 16, so it can be made into a
four-bit adder and a full adder with the carry out and the other
two high bits.

What you do next is to select the memory bank from the 17 values,
and then simply use the high 20 bits for addressing within the
memory bank.

So... does not sound too horrible, but it's still a lot of
effort.