Terje Mathisen <terje.mathisen@tmsw.no> writes:
>Tim Rentsch wrote:
>> Terje Mathisen <terje.mathisen@tmsw.no> writes:
>>
>>> If I really had to write a 64x64->128 MUL, with no widening MUL or
>>> MULH which returns the high half, then I would punt and do it using
>>> 32-bit parts (all variables are u64): [...]
>>
>> I wrote some code along the same lines. A difference is you
>> are considering unsigned multiplication, and I am considering
>> signed multiplication.
>>
>Signed mul is just a special case of unsigned mul, right?
>
>I.e. in case of a signed widening mul, you'd first extract the signs,
>convert the inputs to unsigned, then do the unsigned widening mul,
>before finally resotirng the sign as the XOR of the input signs?

In Gforth we use:

DCell mmul (Cell a, Cell b) /* signed multiply, mixed precision */
{ DCell res;

res = UD2D(ummul (a, b));
if (a < 0)
res.hi -= b;
if (b < 0)
res.hi -= a;
return res;
}

I have this technique from Andrew Haley. It relies on twos-complement
representation.

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

Anton Ertl wrote:
> Terje Mathisen <terje.mathisen@tmsw.no> writes:
>> Tim Rentsch wrote:
>>> Terje Mathisen <terje.mathisen@tmsw.no> writes:
>>>
>>>> If I really had to write a 64x64->128 MUL, with no widening MUL or
>>>> MULH which returns the high half, then I would punt and do it using
>>>> 32-bit parts (all variables are u64): [...]
>>> I wrote some code along the same lines. A difference is you
>>> are considering unsigned multiplication, and I am considering
>>> signed multiplication.
>>>
>> Signed mul is just a special case of unsigned mul, right?
>>
>> I.e. in case of a signed widening mul, you'd first extract the signs,
>> convert the inputs to unsigned, then do the unsigned widening mul,
>> before finally resotirng the sign as the XOR of the input signs?
>
> In Gforth we use:
>
> DCell mmul (Cell a, Cell b) /* signed multiply, mixed precision */
> {
> DCell res;
>
> res = UD2D(ummul (a, b));
> if (a < 0)
> res.hi -= b;
> if (b < 0)
> res.hi -= a;
> return res;
> }
>
> I have this technique from Andrew Haley. It relies on twos-complement
> representation.
>
> - anton

Yeah, that's what Alpha does with UMULH.
I'm still trying to figure out why it works.

mitchalsup@aol.com (MitchAlsup1) writes:

> Tim Rentsch wrote:
>
>> Terje Mathisen <terje.mathisen@tmsw.no> writes:
>>
>>> Tim Rentsch wrote:
>>>
>>>> Terje Mathisen <terje.mathisen@tmsw.no> writes:
>>>>
>>>>> If I really had to write a 64x64->128 MUL, with no widening MUL or
>>>>> MULH which returns the high half, then I would punt and do it using
>>>>> 32-bit parts (all variables are u64): [...]
>>>>
>>>> I wrote some code along the same lines. A difference is you
>>>> are considering unsigned multiplication, and I am considering
>>>> signed multiplication.
>>>
>>> Signed mul is just a special case of unsigned mul, right?
>>>
>>> I.e. in case of a signed widening mul, you'd first extract the signs,
>>> convert the inputs to unsigned, then do the unsigned widening mul,
>>> before finally resotirng the sign as the XOR of the input signs?
>>>
>>> There is a small gotcha if either of the inputs are of the 0x80000000
>>> form, i.e. MININT, but the naive iabs() conversion will do the right
>>> thing by leaving the input unchanged.
>>>
>>> At the other end there cannot be any issues since restoring a negative
>>> output sign cannot overflow/fail.
>>
>> It isn't quite that simple. Some of what you describe has a risk
>> of running afoul of implementation-defined behavior or undefined
>> behavior (as for example abs( INT_MIN )). I'm pretty sure it's
>> possible to avoid those pitfalls, but it requires a fair amount
>> of care and careful thinking.
>
> It would be supremely nice if we could go back in time before
> computers and reserve an integer encoding that represents the
> value of "there is no value here" and mandate if upon integer
> arithmetic.

ISO C allows such an encoding, even for two's complement.

Sadly it appears that the latest C standard will be taking
away that allowance.

>> Note that my goal is only to avoid the possibility of undefined
>> behavior that comes from signed overflow. My approach is to safely
>> determine whether the signed multiplication would overflow, and if
>> it wouldn't then simply use signed arithmetic to get the result.
>
> Double width multiplication cannot overflow. 2n = nxn then, ignoring
> the top n bits gives you your non-overflowing multiply.

C does not guarantee that. The point of the exercise is to
write code assuming nothing more than what the C standard
mandates.

EricP <ThatWouldBeTelling@thevillage.com> writes:

> Anton Ertl wrote:
>
>> Terje Mathisen <terje.mathisen@tmsw.no> writes:
>>
>>> Tim Rentsch wrote:
>>>
>>>> Terje Mathisen <terje.mathisen@tmsw.no> writes:
>>>>
>>>>> If I really had to write a 64x64->128 MUL, with no widening MUL or
>>>>> MULH which returns the high half, then I would punt and do it using
>>>>> 32-bit parts (all variables are u64): [...]
>>>>
>>>> I wrote some code along the same lines. A difference is you
>>>> are considering unsigned multiplication, and I am considering
>>>> signed multiplication.
>>>
>>> Signed mul is just a special case of unsigned mul, right?
>>>
>>> I.e. in case of a signed widening mul, you'd first extract the
>>> signs, convert the inputs to unsigned, then do the unsigned
>>> widening mul, before finally resotirng the sign as the XOR of the
>>> input signs?
>>
>> In Gforth we use:
>>
>> DCell mmul (Cell a, Cell b) /* signed multiply, mixed precision */
>> {
>> DCell res;
>>
>> res = UD2D(ummul (a, b));
>> if (a < 0)
>> res.hi -= b;
>> if (b < 0)
>> res.hi -= a;
>> return res;
>> }
>>
>> I have this technique from Andrew Haley. It relies on twos-complement
>> representation.
>
> Yeah, that's what Alpha does with UMULH.
> I'm still trying to figure out why it works.

It works because a sign bit works like a value bit
with a weight of -2**(N-1), where N is the width of
the memory holding the signed value. So instead
of subtracting 2**(N-1) * b, assuming a is negative,
we have instead added 2**(N-1) * b, so we need to
subtract 2 * 2**(N-1) * b, or 2**N * b, which means
subtracting b from the high order word of the result.
And of course similarly for when b is negative.

(Note that the above holds for two's complement, but
not for ones' complement or signed magnitude.)

Michael S <already5chosen@yahoo.com> schrieb:

> Even for Cray/NEC-style vectors, the same throughput for different
> precision is not an universal property. Cray's and NEC's vector
> processors happen to be designed like that, but one can easily imagine
> vector processors of similar style that have 2 or even 3 times higher
> throughput for SP vs DP.
> I personally never encountered such machines, but would be surprised if
> it were never built and sold back by one or another usual suspect (may
> be, Fujitsu?) in days when designers liked Cray's style.

I worked on such a machine, and (IIRC) single precision was faster
on that machine. That may have been due to the comparatively
low memory throughput of the single load/store pipeline that it had.

But it's been a few decades, and my memory may be off (and I don't
have any handbooks from the time).

On Tue, 12 Mar 2024 19:00:46 +0000
mitchalsup@aol.com (MitchAlsup1) wrote:

> Michael S wrote:
>
> > On Tue, 12 Mar 2024 17:18:36 +0000
> > mitchalsup@aol.com (MitchAlsup1) wrote:
>
> >>
> >> While theoretically possible, they did not do this because both
> >> halves of a 2×SP would not arrive from memory necessarily
> >> simultaneously. {Consider a gather load you need a vector of
> >> addresses 2× as long for pairs of SP going into a single vector
> >> register element.}
>
> > Doctor, it hurts when I do this!
> > So, what prevents you from providing no gather with resolution
> > below 64 bits?
>
> Well, then, you have SP values in a container than could hold 2 and
> you don't get any SIMD speedup.
>

(1) - a need for full gather it hopefully rare. Majority of time things
accessed continuously or, at worst, with non-unit strides.
My personal rule of thumb is "if I need generic gather, most likely I
shouldn't have been bothered with vectorizing." Of course, as every
rule of thumb, it's imprecise.
(2) - there are several important applications that naturally have
pair-wise data layout. Complex numbers is just one.

> >> > Which, of course, leaves the question of what property makes
> >> > vector processor Cray-style. Just having ALU/FPU several times
> >> > narrower than VR is, IMHO, not enough to be considered
> >> > Cray-style.
> >>
> >> That property is that the length of the vector register is chosen
> >> to absorb the latency to memory. SMID is too short to have this
> >> property.
>
> > I don't like this definition at all.
> > For starter, what is "memory"? Does L1D cache count, or only L2 and
> > higher?
>
> Those machines had no L1 or L2 (or LLC) caches. Consider the problems
> for which they were designed--arrays as big as the memory (sometimes
> bigger !!) and processed over and over again with numerical
> algorithms. Caches would simply miss on each memory reference
> (ignoring TLB effects) With the caches never supplying data to the
> calculations why have them at all ??
>
> > Then, what is "absorb" ?
>
> Absorb means that the first data of a vector arrives and can start
> calculation before the last address of the memory reference goes out.
> This, in turn, means that one can create a continuous stream of
> outbound addresses forever and thus cone can create a stream of
> continuous calculations forever. {{Where 'forever' means thousands
> of cycles but no where near the lifetime of the universe.}}
>
> Now, obviously, this means the memory system has to be able to make
> forward progress on all those memory accesses continuously.
>
> > Is the whole VR register file part of
> > absorbent or latency should be covered by one register?
>
> A single register covers a single memory reference latency.
>
> > Is OoO
> > machinery part of absorbent?
>
> The only OoO in the CRAYs was delivery of gather data back to the
> vector register*. Scatter stores were sent out in order, as were the
> addresses of the gather loads.
>
> (*) bank conflicts would delay conflicting accesses but not those
> of other banks, creating an OoO effect of returning data. This was
> re-ordered back to IO prior to forwarding data into calculation.
>
> > Is HW threading part of absorbent?
>
> Absolutely not--none of the CRAYs did this--later XMPs and YMPs did
> use lanes (SIMD with vector) but always did calculations in order
> and always sent out addresses (and data when appropriate) in order.
>
> > And for
> > any of your possible answers I have my "Why?".
>
> No harm in asking.
>

It seems, we are talking about different things.
You are talking about Cray vectors, as done in Cray's 1/X-MP/Y-MP
series. I.e. something fixed, known and of interest mostly for
computing historians among us.
OTH, I am trying to discuss a vague notion of "Cray-style vectors". My
intentions are to see what was applicable in more recent times and
which ideas are not totally obsolete for a future.

Michael S wrote:

> On Tue, 12 Mar 2024 19:00:46 +0000
> mitchalsup@aol.com (MitchAlsup1) wrote:

>> Michael S wrote:
>>
>> > On Tue, 12 Mar 2024 17:18:36 +0000
>> > mitchalsup@aol.com (MitchAlsup1) wrote:
>>
>> >>
>> >> While theoretically possible, they did not do this because both
>> >> halves of a 2×SP would not arrive from memory necessarily
>> >> simultaneously. {Consider a gather load you need a vector of
>> >> addresses 2× as long for pairs of SP going into a single vector
>> >> register element.}
>>
>> > Doctor, it hurts when I do this!
>> > So, what prevents you from providing no gather with resolution
>> > below 64 bits?
>>
>> Well, then, you have SP values in a container than could hold 2 and
>> you don't get any SIMD speedup.
>>

> (1) - a need for full gather it hopefully rare. Majority of time things
> accessed continuously or, at worst, with non-unit strides.
> My personal rule of thumb is "if I need generic gather, most likely I
> shouldn't have been bothered with vectorizing." Of course, as every
> rule of thumb, it's imprecise.

CRAY-1 XMP gained considerable speedup (about 20%) on its benchmarks
of the day after adding Scatter/Gather and 5 more Livermore Loops
would vectorize.

> (2) - there are several important applications that naturally have
> pair-wise data layout. Complex numbers is just one.

What about Quaterions--which alleviate the programmer from having to
remember which multiplications are subtracted instead of added.

>> >> > Which, of course, leaves the question of what property makes
>> >> > vector processor Cray-style. Just having ALU/FPU several times
>> >> > narrower than VR is, IMHO, not enough to be considered
>> >> > Cray-style.
>> >>
>> >> That property is that the length of the vector register is chosen
>> >> to absorb the latency to memory. SMID is too short to have this
>> >> property.
>>
>> > I don't like this definition at all.
>> > For starter, what is "memory"? Does L1D cache count, or only L2 and
>> > higher?
>>
>> Those machines had no L1 or L2 (or LLC) caches. Consider the problems
>> for which they were designed--arrays as big as the memory (sometimes
>> bigger !!) and processed over and over again with numerical
>> algorithms. Caches would simply miss on each memory reference
>> (ignoring TLB effects) With the caches never supplying data to the
>> calculations why have them at all ??
>>
>> > Then, what is "absorb" ?
>>
>> Absorb means that the first data of a vector arrives and can start
>> calculation before the last address of the memory reference goes out.
>> This, in turn, means that one can create a continuous stream of
>> outbound addresses forever and thus cone can create a stream of
>> continuous calculations forever. {{Where 'forever' means thousands
>> of cycles but no where near the lifetime of the universe.}}
>>
>> Now, obviously, this means the memory system has to be able to make
>> forward progress on all those memory accesses continuously.
>>
>> > Is the whole VR register file part of
>> > absorbent or latency should be covered by one register?
>>
>> A single register covers a single memory reference latency.
>>
>> > Is OoO
>> > machinery part of absorbent?
>>
>> The only OoO in the CRAYs was delivery of gather data back to the
>> vector register*. Scatter stores were sent out in order, as were the
>> addresses of the gather loads.
>>
>> (*) bank conflicts would delay conflicting accesses but not those
>> of other banks, creating an OoO effect of returning data. This was
>> re-ordered back to IO prior to forwarding data into calculation.
>>
>> > Is HW threading part of absorbent?
>>
>> Absolutely not--none of the CRAYs did this--later XMPs and YMPs did
>> use lanes (SIMD with vector) but always did calculations in order
>> and always sent out addresses (and data when appropriate) in order.
>>
>> > And for
>> > any of your possible answers I have my "Why?".
>>
>> No harm in asking.
>>

> It seems, we are talking about different things.
> You are talking about Cray vectors, as done in Cray's 1/X-MP/Y-MP
> series. I.e. something fixed, known and of interest mostly for
> computing historians among us.

Fair enough, but it remains my model for how to discuss vector calculations.

> OTH, I am trying to discuss a vague notion of "Cray-style vectors". My
> intentions are to see what was applicable in more recent times and
> which ideas are not totally obsolete for a future.

Only after you figure out a way to feed 2-LDs and consume 1 ST per-cycle
continuously (cache miss or cache hit; TLB miss or TLB hit) are you in a
position to utilize CRAY-like vector-register architecture effectively.

EricP <ThatWouldBeTelling@thevillage.com> writes:
>Anton Ertl wrote:
>> DCell mmul (Cell a, Cell b) /* signed multiply, mixed precision */
>> {
>> DCell res;
>>
>> res = UD2D(ummul (a, b));
>> if (a < 0)
>> res.hi -= b;
>> if (b < 0)
>> res.hi -= a;
>> return res;
>> }
>>
>> I have this technique from Andrew Haley. It relies on twos-complement
>> representation.
>>
>> - anton
>
>Yeah, that's what Alpha does with UMULH.
>I'm still trying to figure out why it works.

Let's consider the case where a>=0 and b<0, and cells are 64 bits. ua
is a interpreted as unsigned cell, and ub is b interpreted as unsigned
cell. The following computations are in Z (the unlimited
integers). For the case under consideration:

ua=a
ub=b+2^64

res = ua*ub = a*(b+2^64)= a*b + a*2^64

So,

a*b = res - a*2^64

The other cases are similar.

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

Thomas Koenig wrote:

> MitchAlsup1 <mitchalsup@aol.com> schrieb:
>> Thomas Koenig wrote:

>>> However, what I did put in the paper (and what the subsequent
>>> revision by a J3 subcommittee left in) is a prohibition against
>>> using unsigneds in a DO loop. The reason is semantics of
>>> negative strides.
>>
>>> Currently, in Fortran, the number of iterations of the loop
>>
>>> do i=m1,m2,m3
>>> ....
>>> end do
>>
>>> is (m2-m1+m3)/m3 unless that value is negative, in which case it
>>> is zero (m3 defaults to 1 if it is not present).
>>
>>> So,
>>
>>> do i=1,3,-1
>>
>>> will be executed zero times, as will
>>
>>> do i=3,1
>>
>>> Translating that into arithmetic with unsigned integers makes
>>> little sense, how many times should
>>
>>> do i=1,3,4294967295
>>
>>> be executed?
>>
>> 3-1+4294967295 = 4294967297 // (m2-m1+m3)
>>
>> 4294967297 / 4294967295 = 1.0000000004656612874161594750863
>>
>> So the loop should be executed one time. {{And yes I know 4294967295 ==
>> 0x1,0000,0001}} What would you expect on a 36-bit machine (2s-complement)
>> where 4294967295 is representable naturally ??

> Correct (of course).

It seems to me that the problem is not using unsigned integers as
DO LOOP indexes, the problem is there is no compiler error message
from "4294967295 does not fit in integer container". Bringing the
problem to the programmer. THEN everybody is free (under the above)
to implement unsigned DO LOOPs.

> The same result would be expected for

> do i=1u,3u,-1u

> (asusming an u suffix for unsigned numbers).

> The problem is that this violates a Fortran basic assumption since
> FORTRAN 77, which is that DO loops can be zero-trip.

(m2-m1+m3)/m3

(3-1+(-1))/-1 = -1 and the loop should not be taken at all.
BUT
-1u = 4294967293
Therefore:
(3u-1u+(-1u))/-1u =
(3-1+4294967293)/4294967293 = 1.0000000004656612874161594750863 again.

Once again this is a problem only when a constant integer value
cannot be precisely represented--and deserves a warning/error
message instead of a complete ban.

> This is a can of worms that I would like to leave unopened.

I understand why, I just think the fickle finger of fate should
point at the constant rather than the type.

> Same goes for array slices. Even assuming that no negative
> indices are used, the slice a(1:3:-1) is zero-sized in Fortran,
> as is a(3:1) .

> For a(1u:3u:-1u) the same logic that you outlined above would apply,
> making it a slice with one element.

> Not going there :-)

> OTH, I am trying to discuss a vague notion of "Cray-style vectors". My
> intentions are to see what was applicable in more recent times and
> which ideas are not totally obsolete for a future.

Another way to look at the difference between SSE-style vectors (which
I'd call "short vectors") at the ISA level is the fact that SSE-style
vector instructions are designed under the assumption that the latency
of a vector instruction will be more or less the same as that of
a non-vector instruction (i.e. you have enough ALUs to do all the
operations at the same time), whereas Cray-style vector instructions
(which we could call "long vectors") are designed under the assumption
that the latency will be somewhat proportional to the length of the
vector because the core of the CPU will only access a chunk of the
vector at a time.

So, short vectors have a fairly free hand at shuffling data across their
vector (e.g. bitmatrix transpose), and they can be
implemented/scheduled/dispatched just like any other instruction, but
the vector length tends to be severely limited and exposed all over
the place.

In contrast long vectors usually depend on specialized implementations
(e.g. chaining) to get good performance, but their length is
easier/cheaper to change.

AFAICT long vectors made sense when we could build machines with
a memory bandwidth that was higher and ALUs were more expensive.
Nowadays we tend to have the opposite.

Also, the massive number of transistors we spend nowadays on OoO means
that a good OoO CPU can dispatch individual non-vector instructions to
ALUs just as well as the Cray did with its vectors with chaining.

Stefan

Stefan Monnier wrote:

>> OTH, I am trying to discuss a vague notion of "Cray-style vectors". My
>> intentions are to see what was applicable in more recent times and
>> which ideas are not totally obsolete for a future.

> Another way to look at the difference between SSE-style vectors (which
> I'd call "short vectors") at the ISA level is the fact that SSE-style
> vector instructions are designed under the assumption that the latency
> of a vector instruction will be more or less the same as that of
> a non-vector instruction (i.e. you have enough ALUs to do all the
> operations at the same time),

In the early-mid 1980s there was a class of processor assist engines
using the tern Array-Processor that performed a Cray-like vector in
the same latency as a scalar operation. CRAY streamed single-operands
through FUs, Array processors took entire <but shorter> vectors through
lanes of calculations.

I would call these "medium vector" to distinguish from (short vector)
SIMD and (long vector) CRAY {or just vector without qualifier}. So we
have::
SIMD <short> vector
ARRAY <medium> vector
CRAY <long> vector
CDC <memory> vector

> whereas Cray-style vector instructions
> (which we could call "long vectors") are designed under the assumption
> that the latency will be somewhat proportional to the length of the
> vector because the core of the CPU will only access a chunk of the
> vector at a time.

> So, short vectors have a fairly free hand at shuffling data across their
> vector (e.g. bitmatrix transpose), and they can be
> implemented/scheduled/dispatched just like any other instruction, but
> the vector length tends to be severely limited and exposed all over
> the place.

Consuming OpCode space like nobody's business.

> In contrast long vectors usually depend on specialized implementations
> (e.g. chaining) to get good performance, but their length is
> easier/cheaper to change.

The only limitation is when one masks out beats of the vector from
calculation of memory referencing. This is what kept CRAY at 64-element
vectors. It was also the Achilles heal of CRAY--once memory gets more
than 64 beats away, the length of the vector can no longer absorb the
latency to memory. NEC did not have this problem.

> AFAICT long vectors made sense when we could build machines with
> a memory bandwidth that was higher and ALUs were more expensive.
> Nowadays we tend to have the opposite.

While BW is important (very) it is latency that is crucial. Latency
to memory must be smaller than vector length.

> Also, the massive number of transistors we spend nowadays on OoO means
> that a good OoO CPU can dispatch individual non-vector instructions to
> ALUs just as well as the Cray did with its vectors with chaining.

Not "just as well" but "within spitting distance of"

> Stefan

On Wed, 13 Mar 2024 15:02:12 -0400
Stefan Monnier <monnier@iro.umontreal.ca> wrote:

> > OTH, I am trying to discuss a vague notion of "Cray-style vectors".
> > My intentions are to see what was applicable in more recent times
> > and which ideas are not totally obsolete for a future.
>
> Another way to look at the difference between SSE-style vectors (which
> I'd call "short vectors") at the ISA level is the fact that SSE-style
> vector instructions are designed under the assumption that the latency
> of a vector instruction will be more or less the same as that of
> a non-vector instruction (i.e. you have enough ALUs to do all the
> operations at the same time), whereas Cray-style vector instructions
> (which we could call "long vectors") are designed under the assumption
> that the latency will be somewhat proportional to the length of the
> vector because the core of the CPU will only access a chunk of the
> vector at a time.
>

I sympathize with your direction, but want to point out that
historically in x86 world implementations of those or another SIMD
instruction sets that had twice higher throughput for scalar FP ops vs
full-width FP ops were and are very common. As to latency, many of
these implementations had (and may be still have?) one cycle longer
latency for scalar vs full-width.

Similar throughput differences can be seen on few aarch64 processors.
E.g. on Cortex-A75, where Q-form of common FP arithmetic instructions
has half of throughput of scalar and D-form, but latency is not
affected.
I'd guess that the same applies to LITTLE Arm cores, but can't be sure,
because Cortex-A53 Software Optimization Guide does not exist and
Cortex-A55 Software Optimization Guide is not very comprehensible.

> So, short vectors have a fairly free hand at shuffling data across
> their vector (e.g. bitmatrix transpose), and they can be
> implemented/scheduled/dispatched just like any other instruction, but
> the vector length tends to be severely limited and exposed all over
> the place.
>
> In contrast long vectors usually depend on specialized implementations
> (e.g. chaining) to get good performance, but their length is
> easier/cheaper to change.
>
> AFAICT long vectors made sense when we could build machines with
> a memory bandwidth that was higher and ALUs were more expensive.
> Nowadays we tend to have the opposite.
>

16x DP FMA (dual-issue 512-bit), as in server-class Intel cores, is
still expensive, less so in area, more so in effect on max. power
consumption.
As to memory, I find this argument false, at least in its original form
often stated here by Mitch.
There are many important algorithms, both in dense linear algebra and
in digital signal processing, where it is easily possible to reduce
memory read to DP FMA ratio to 5-6 bytes/DP-FMA. With 32 software
visible vector registers and with more programmer's effort the ratio
could be pushed further down, sometimes below 4 bytes.
I know little about other computationally intensive fields (apart
from dense linear algebra and DSP, that is), but would expect that if
not 5-6 then at least 8-9 bytes/DP-FMA (or equivalents for lower
precisions) are not out of reach in other field as well.

> Also, the massive number of transistors we spend nowadays on OoO means
> that a good OoO CPU can dispatch individual non-vector instructions to
> ALUs just as well as the Cray did with its vectors with chaining.
>
>
> Stefan

On 3/13/24 3:24 PM, MitchAlsup1 wrote:
> Stefan Monnier wrote:
[snip]
>> So, short vectors have a fairly free hand at shuffling data across their
>> vector (e.g. bitmatrix transpose), and they can be
>> implemented/scheduled/dispatched just like any other instruction, but
>> the vector length tends to be severely limited and exposed all over
>> the place.
>
> Consuming OpCode space like nobody's business.

Is that necessarily the case? Excluding the shuffle operations, I
think only loads and stores would need to have length specifiers.
Shuffle operations become much more expensive with larger
'vectors', so providing the same granularity of shuffle for larger
vectors seems questionable. (With scatter/gather, permute/shuffle
may be less useful anyway.)

The metadata would not even _have_ to be saved, though such would
be better than unnecessarily saving/restoring huge contexts and if
one can support variable-sized contexts one can support additional
metatdata.

If loads and stores were masked, the number of instruction
"encodings" would not need to be increased, but using zero-
extended masks to indicate smaller vector size seems less than
ideal.

Lane-based operations with different length operands would
presumably narrow the result (the later elements of the longer
operand would not be used) and allow the possible error to be
detected.

Unlike My 66000's VVM, different-sized elements would require
unpack/pack operations (where VVM needs to implicitly pack an
operand if it wanted to take advantage of reduced storage). This
would not increase instruction encodings as vector length is
increased. (VVM also provides sequential exceptions while SIMD is
conceptually all at once.)

Am I missing something when I assume that lane-based (SIMD)
operations do not need size information in the instruction? The
extra metadata is not free (perhaps especially as that controls
execution at least for efficiency), but if opcode explosion is so
undesirable using metadata might be preferred.

MitchAlsup1 wrote:
> Michael S wrote:
>> Doctor, it hurts when I do this!
>> So, what prevents you from providing no gather with resolution
>> below 64 bits?
>
> Well, then, you have SP values in a container than could hold 2 and you
> don't get any SIMD speedup.

I've looked at this issue since Larrabee (which was the first cpu I had
access to which supported gather):

For a 32-bit gather in a 64-bit environment, the only good solution I've
been able to come up with is to use a 64-bit base register and then
require all the sources to be within 4GB from that base, so that you can
use the 32-bit wide gather addresses as indices/offsets from that base.

<dest_vector_reg> = gather(base_reg, src_vector_reg)

It would be up to the implementer to decide if the src_vector_reg is
used as signed or unsigned offsets from the base. It is also possible to
extend adressability by having the offsets be scaled by the element
size, so effectively

dest[i] = [base+src[i]*4]

for single precision values.

Terje

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

Anton Ertl wrote:
> Terje Mathisen <terje.mathisen@tmsw.no> writes:
>> Tim Rentsch wrote:
>>> Terje Mathisen <terje.mathisen@tmsw.no> writes:
>>>
>>>> If I really had to write a 64x64->128 MUL, with no widening MUL or
>>>> MULH which returns the high half, then I would punt and do it using
>>>> 32-bit parts (all variables are u64): [...]
>>>
>>> I wrote some code along the same lines. A difference is you
>>> are considering unsigned multiplication, and I am considering
>>> signed multiplication.
>>>
>> Signed mul is just a special case of unsigned mul, right?
>>
>> I.e. in case of a signed widening mul, you'd first extract the signs,
>> convert the inputs to unsigned, then do the unsigned widening mul,
>> before finally resotirng the sign as the XOR of the input signs?
>
> In Gforth we use:
>
> DCell mmul (Cell a, Cell b) /* signed multiply, mixed precision */
> {
> DCell res;
>
> res = UD2D(ummul (a, b));
> if (a < 0)
> res.hi -= b;
> if (b < 0)
> res.hi -= a;
> return res;
> }
>
> I have this technique from Andrew Haley. It relies on twos-complement
> representation.

Nice!

Subtracting the results of having used the sign bit as part of the
multiplication.

Here you can probably schedule the fixup to happen in parallel with the
actual multiplication:

;; inputs in r9 & r10, result in rdx:rax, rbx & rcx as scratch

mov rax,r9 ;; All these can start in the first cycle
mul r10
mov rbx,r9 ;; The MOV can be handled by the renamer
sar r9,63
mov rcx,r10 ;; Ditto
sar r10,63

and rbx,r9 ;; Second set of ops
and rcx,r10

add rbx,rcx ;; Third cycle

sub rdx,rbx ;; Do a single adjustment as soon as the MUL finishes

Terje

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

On Thu, 14 Mar 2024 23:56:04 -0400
"Paul A. Clayton" <paaronclayton@gmail.com> wrote:

> On 3/13/24 3:24 PM, MitchAlsup1 wrote:
> > Stefan Monnier wrote:
> [snip]
> >> So, short vectors have a fairly free hand at shuffling data across
> >> their vector (e.g. bitmatrix transpose), and they can be
> >> implemented/scheduled/dispatched just like any other instruction,
> >> but the vector length tends to be severely limited and exposed all
> >> over the place.
> >
> > Consuming OpCode space like nobody's business.
>
> Is that necessarily the case? Excluding the shuffle operations, I
> think only loads and stores would need to have length specifiers.
> Shuffle operations become much more expensive with larger
> 'vectors', so providing the same granularity of shuffle for larger
> vectors seems questionable. (With scatter/gather, permute/shuffle
> may be less useful anyway.)
>
<snip>
>
> Am I missing something when I assume that lane-based (SIMD)
> operations do not need size information in the instruction? The
> extra metadata is not free (perhaps especially as that controls
> execution at least for efficiency), but if opcode explosion is so
> undesirable using metadata might be preferred.

I would guess that Mitch operates under assumption that we are still
talking about ISA that is very similar to CRAY Y-MP.
I.e. non-load-store, but more like AVX512, where one of the source
operands could be in memory.
That is, I had never seen CRAY Y-MP ISA docs, but would imagine that it
was like that.

Terje Mathisen <terje.mathisen@tmsw.no> writes:
>Here you can probably schedule the fixup to happen in parallel with the
>actual multiplication:
>
>;; inputs in r9 & r10, result in rdx:rax, rbx & rcx as scratch
>
> mov rax,r9 ;; All these can start in the first cycle
> mul r10
> mov rbx,r9 ;; The MOV can be handled by the renamer
> sar r9,63
> mov rcx,r10 ;; Ditto
> sar r10,63
>
> and rbx,r9 ;; Second set of ops
> and rcx,r10
>
> add rbx,rcx ;; Third cycle
>
> sub rdx,rbx ;; Do a single adjustment as soon as the MUL finishes

Of course on AMD64 you could just use imul instead.

RISC-V also supports signed as well as unsigned (and also
signed*unsigned) multiplication, and I think that's also the case for
ARM A64. But on Alpha this technique would be useful.

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

Paul A. Clayton wrote:

> On 3/13/24 3:24 PM, MitchAlsup1 wrote:
>> Stefan Monnier wrote:
> [snip]
>>> So, short vectors have a fairly free hand at shuffling data across their
>>> vector (e.g. bitmatrix transpose), and they can be
>>> implemented/scheduled/dispatched just like any other instruction, but
>>> the vector length tends to be severely limited and exposed all over
>>> the place.
>>
>> Consuming OpCode space like nobody's business.

> Is that necessarily the case? Excluding the shuffle operations, I
> think only loads and stores would need to have length specifiers.

Add signed byte add unsigned byte, add signed half, add unsigned half
add signed int, add unsigned int, add long, add 2 floats, add double

compared to ADD integer, add float and add double.

And then there is the addsub group, too.

I may be possible to avoid OpCode explosion, but neither x86, nor ARM
got anywhere close to avoiding the deluge of OpCodes.

MitchAlsup1 wrote:

> Paul A. Clayton wrote:

>> On 3/13/24 3:24 PM, MitchAlsup1 wrote:
>>> Stefan Monnier wrote:
>> [snip]
>>>> So, short vectors have a fairly free hand at shuffling data across their
>>>> vector (e.g. bitmatrix transpose), and they can be
>>>> implemented/scheduled/dispatched just like any other instruction, but
>>>> the vector length tends to be severely limited and exposed all over
>>>> the place.
>>>
>>> Consuming OpCode space like nobody's business.

>> Is that necessarily the case? Excluding the shuffle operations, I
>> think only loads and stores would need to have length specifiers.

> Add signed byte add unsigned byte, add signed half, add unsigned half
> add signed int, add unsigned int, add long, add 2 floats, add double

All of the above come in 64-bit, 128-bit, 256-bit, and 512-bit variants.

> compared to ADD integer, add float and add double.

> And then there is the addsub group, too.

> I may be possible to avoid OpCode explosion, but neither x86, nor ARM
> got anywhere close to avoiding the deluge of OpCodes.