On Sunday, August 22, 2021 at 11:54:59 PM UTC-6, Thomas Koenig wrote:
> It worked well on Zen 1 despite that
> architecture only "faking" AVX2 with 128-bit registers.

You can fake AVX-256 with a 128-bit ALU, but I don't see
how you can fake it if your *registers* are too short.

Assuming this is a typo, this is the same sort of thing
they're doing in the current generation with AVX-512.

John Savard

Quadibloc <jsavard@ecn.ab.ca> writes:
>You can fake AVX-256 with a 128-bit ALU, but I don't see
>how you can fake it if your *registers* are too short.

Use two 128-bit registers to implement a YMM register. You can see it
nicely if you measure the number of physical registers:

ROB XMM YMM
size GPRs regs regs year microarchitecture
128 92 128 64 2015 Carrizo (Excavator)
192 145 144 66 2017 Zen
224 141 147 143 2019 Zen2

Note that the number of YMM registers is half (or less) that of XMM
registers on Carrizo and Zen.

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

On Tuesday, August 24, 2021 at 8:41:02 AM UTC+1, Terje Mathisen wrote:

> Modifying it to while (i+1<n && a[i] <= m) would work I think, but it is
> easier to check the index below:
> while (i<n) {
> while (i<n && a[i]<=m)
> i++;
> if (i < n) {
> m = a[i];
> nm = i;
> }
> i++;

while (i<n) {
// skip up to first max
while (i<n && a[i]<=m) i++;
// continue as long as picking new m
while (i<n && a[i]>m) {
m = a[i];
nm = i;
i++;
}
}

sorry, reviving this one as i am looking to implement it in SVP64 assembler, does the above look reasonable as a way to parallelise this?

phase 1: while (i<n && a[i]<=m) i++;

a batch can be loaded, each one tested against m, and the vector length truncated at the first fail (a[i] > m)

phase 2: while (i<n && a[i]>m) { m = a[i]; nm = i; i++; }

*another* batch loaded, tested against m, and this time the new m is always updated, looping ends when m is no longer to be updated.

of course if alternating greater less greater less appears in the data this is a sequential algorithm!

l.

luke.l...@gmail.com wrote:
> On Tuesday, August 24, 2021 at 8:41:02 AM UTC+1, Terje Mathisen wrote:
>
> while (i<n) {
> // skip up to first max
> while (i<n && a[i]<=m) i++;
> // continue as long as picking new m
> while (i<n && a[i]>m) {
> m = a[i];
> nm = i;
> i++;
> }
> }
>
> sorry, reviving this one as i am looking to implement it in SVP64
> assembler, does the above look reasonable as a way to parallelise this?
>
> phase 1: while (i<n && a[i]<=m) i++;
> a batch can be loaded, each one tested against m, and the
> vector length truncated at the first fail (a[i] > m)
>
> phase 2: while (i<n && a[i]>m) { m = a[i]; nm = i; i++; }
>
> *another* batch loaded, tested against m, and this time the new m is always updated, looping ends when m is no longer to be updated.
>
> of course if alternating greater less greater less appears in the data this is a sequential algorithm!

I think your code looks good.

If we want to min-max optimize for minimum time on maximally bad input,
then another algorithm is probably needed.

Terje

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

On Wednesday, April 26, 2023 at 6:16:14 PM UTC+1, Terje Mathisen wrote:
> luke.l...@gmail.com wrote:
> > while (i<n) {
> > // skip up to first max
> > while (i<n && a[i]<=m) i++;
> > // continue as long as picking new m
> > while (i<n && a[i]>m) {
> > m = a[i];
> > nm = i;
> > i++;
> I think your code looks good.

thanks for checking, Terje.

i was able to use a cheat of SVP64 which uses
a scalar as an "accumulator":

sv.max. *1, *1, *0

which loop-unrolls as:

for i in range(VL):
GPR(1+i) = MAX(GPR(1+i), GPR(0+i)
CR[1+i].GT = 1 if MAX was true else 0

which, with a little thought, you should spot that that
cascades through to the last element as the biggest
number.

so not only do you get the last entry in the Vector set to
the maximum, you also get an "Audit Trail" in the
Vector of Condition Register Fields of when a max
was detected.

and *that* you can then use to grab the index of the
last-successful MAX-was-actually-greater.

> If we want to min-max optimize for minimum time on maximally bad input,
> then another algorithm is probably needed.

yyeah i added a Parallel Reduction Schedule into Simple-V,
which performs a... damn there's a word for it - "work-priority"?
more efficient rather than the low-latency one which does
duplicate work in some cases.

anyway, if you *only* wanted the mix/max of a vector, then
a Parallel Reduction would be the obvious choice.

but finding the index? that's tricky. i'm still thinking about it.

l.

On Wednesday, April 26, 2023 at 10:51:28 AM UTC-5, luke.l...@gmail.com wrote:
> On Tuesday, August 24, 2021 at 8:41:02 AM UTC+1, Terje Mathisen wrote:

> while (i<n) {
> // skip up to first max
> while (i<n && a[i]<=m) i++;
> // continue as long as picking new m
> while (i<n && a[i]>m) {
> m = a[i];
> nm = i;
> i++;
> }
> }
<
The best VVM code would be:
for( i = 1, m = a[0], nm = 0; i < max; i++ )
if( a[i] >= m )
m = a[i], nm = i;
<
Compiling into:
<
MOV Ri,#1
LDD Rm,[Ra]
MOV Rnm,#0
VEC Rt,{}
LDD Rai,[Ra,Ri<<3]
FCMP Rs,Rai,Rm
PGE Rs,TT
MOV Rm,Rai
MOV Rnm,Ri
LOOP LE,Ri,#1,Rmax
<
Since this is a thread on VVM...............
<
The loop can run as wide as the cache port, starting K new LDDs
every cycle. {where K is 2 or 4 or 8 depending on the width of the
cache port(s)}
<
When a new maximum is found, there may be a 1-to-(K-1)-cycle
hiccup in the loop timing (depending on available resources and
strings of new maxima.) {So, if you run into one new maximum
there is a 1-cycle hiccup, but if you run into 7 successive new
maxima there is a 7-cycle hiccup.}
<
So, while your code looks like it will do what you want; the target
ISA is what is driving you to excess expression complexity.

On Wednesday, April 26, 2023 at 6:57:22 PM UTC+1, MitchAlsup wrote:

> The best VVM code would be:
> for( i = 1, m = a[0], nm = 0; i < max; i++ )
> if( a[i] >= m )
> m = a[i], nm = i;

relying on the scalar-autovectorisation from hazard identification, yes.

> Since this is a thread on VVM...............

yippeee :)

> <
> The loop can run as wide as the cache port, starting K new LDDs
> every cycle. {where K is 2 or 4 or 8 depending on the width of the
> cache port(s)}

multi-issue (OoO) speculative LDs, yes.

> <
> When a new maximum is found, there may be a 1-to-(K-1)-cycle
> hiccup in the loop timing (depending on available resources and
> strings of new maxima.) {So, if you run into one new maximum
> there is a 1-cycle hiccup, but if you run into 7 successive new
> maxima there is a 7-cycle hiccup.}

yes, this was the issue i ran smack into with an early version
of an algorithm, the amount of parallelism is data-dependent.

> So, while your code looks like it will do what you want; the target
> ISA is what is driving you to excess expression complexity.

SVP64 Vertical-First could achieve the same simplicity, i wanted
to see if there was a parallel-processing way, exploiting the
Horizontal-First mode.

l.