Re: Short Vectors Versus Long Vectors

Lawrence D'Oliveiro <ldo@nz.invalid> writes:

On Tue, 23 Apr 2024 06:22:38 GMT, Anton Ertl wrote:

If your OoO capabilities are limited (and I think
they are on the Cray machines), you cannot start the second iteration of
the doall loop before the processing step of the first iteration has
finished with the register.

>
How would out-of-order execution help, anyway, given all the operations on
the vector elements are supposed to be identical?

OoO does in hardware what software pipelining does in software: If I
have a loop

for (i=0; i<n; i++)
  b[i] = a[i]+c[i];

the straightforward way to code this is:

L0:
load tmp1 = a[i]
load tmp2 = b[i]
add tmp3 = tmp1,tmp2
store c[i] = tmp3
add i = i+1
branch L0 if i<n

On an in-order CPU you then do things like loop unrolling, modulo
scheduling and modulo variable renaming to get a steady state like:

L0:
store c[i], tmp1
add tmp3 = tmp3,tmp4
load tmp9 = a[i+4]
load tmp10 = b[i+4]
store c[i+1], tmp3
add tmp5 = tmp5,tmp6
load tmp1 = a[i+5]
load tmp2 = b[i+5]
store c[i+2], tmp5
add tmp7 = tmp7,tmp8
load tmp3 = a[i+6]
load tmp4 = b[i+6]
store c[i+3], tmp7
add tmp9 = tmp9,tmp10
load tmp1 = a[i+7]
load tmp2 = b[i+7]
store c[i+4], tmp9
add tmp1 = tmp1,tmp2
load tmp3 = a[i+8]
load tmp4 = b[i+8]
add i=i+5
branch L0 if i<n-4

And that's just to cover a load latency of 4 cycles, assuming that the
machine can perform 2 loads and one store per cycle.  And you have to
generate the ramp-up and ramp-down code, and for more complicated
loops it becomes more complicated.

By contrast, on an OoO machine the straightforward code just works
efficiently, and the hardware does the reordering and register
renaming (and the Golden Cove with its 0-cycle constant additions
eliminates even a part of the reason for loop unrolling).  It creates
the ramp-up automatically, and, if the loop exit is predicted
correctly, even the ramp-down, and it overlaps the ramp-up (and
possibly the ramp-down) with adjacent code.

Back to the Crays: While the SIMD/vector semantics means that a
straightforward loop will process 64 elements rather than one before
the first load of the second iteration has to wait for the add of
the first iteration to finish, you still have to do some software
pipelining to get an overlap between that add and that load; the
longer the latency, the more software pipelining and (for register
renaming) the more registers you need.

In OoO the corresponding condition is when the OoO engine has consumed
all instances of one resource and has to wait for instructions to
finish to free these resources; ideally the hardware prefetcher avoids
that scenario, but in memory-bandwidth-limited situations it will
occur.

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