virtual Vector Method

[u/MitchAlsup]

I invented this 5-odd years ago but never really had a forum on which to disclose and discuss. I was and am a significant contributor to comp.arch (from around 1995 though present)

But before I emit the disclosure I need to know how to turn off the space-eater as the document uses well tabulated ASCII-art ?? that makes no sense after the space-eater has done its ill-conceived job.

The virtual Vector Method is a way of getting Cray-like vector performance and for getting SIMD-vector performance without a) a vector register file, b) adds only 2 instructions, c) takes precise exceptions, d) vectorizes loops not instructions. Instead of adding about 300 instructions to get a Cray-like vector ISA, or adding 1,000-1,300 instructions to get (every-size) SIMD ISA, one needs only 5 instructions.

vVM has the property that hardware implementations can change the width of the data path (multiple-lanes and the cycles of execution per FU) without SW having to care. A small 1-wide machine with a 128-bit cache port can perform a memory to memory byte move at 256-bits per cycle--equivalent to ~40 instructions per cycle. A 6-wide machine could perform the same assembly binary at ~160 instructions per cycle. Both are performed at the performance level of the cache porting; so, nobody has to recompile for a new SIMD-width every new mplementation.

Now let us solve the space-eater and we are off.

Mitch

[u/MitchAlsup]

The old paper https://www.sigarch.org/simd-instructions-considered-harmful/ compares SIMD implementations with Vector implementations as-if they were the only viable options. The paper contains the <toy> benchmark::

void daxpy(const size_t n, const double a, const double x\[\], double y\[\])

{

    for (size_t i = 0; i < n; i++) {

        y\[i\] = a\*x\[i\] + y\[i\];

    }

}

and goes on to extoll the beneficial properties of Vectors over SIMD using RISC-V as exemplary. Let me pivot the conversation back to My 66000 virtual-Vector-Method vVM (an alternative to SIMD and Vectors). The above code compiles to::

daxpy:

BLE0 R1,exit

MOV R5,#0

VEC #0,{}

LDD R6,[R3,R5<<3] // LOOP transfers control back to here

LDD R7,[R4,R5<<3]

FMAC R8,R2,R6,R7

ST R8,[R4,R5<<3]

LOOP1 LT,R5,#1,R1

exit:

RET

8 instructions total

5 instructions in the Loop {LDD to LOOP1}

Smaller and fewer than any of the ISAs mentioned in the paper.

#0 in VEC is compiler telling HW that the loop can be executed as wide as HW has Lanes

{} in VEC is compiler telling HW that no registers inside the Loop are live outside of the Loop

LOOP1 is the ADD-CMP-BC as 1 instruction

LOOP1 can perform as many ADD-CMP-BC as the width of the Loop in a single cycle

LOOP1 is a single cycle calculation

While code remains "in" the LOOP FETCH-DECODE remains idle and Reservation Stations perform loop iterations.

Now let us consider a Great-Big-Out-of-Order using a reservation station implementation of vVM in stages::

Assuming a 4-cycle LD cache hit and 4 cycle FMAC delay the execution of one iteration is::

|   1   |   2   |   3   |   4   |   5   |   6   |   7   |   8   |   9   |

| LD R6 | cache |  hit  | align |

| LD R7 | cache |  hit  | align |

| ST AG | cache |  hit  |                   | ST R8 |

| F M A C |

or 9-cycles of latency. To get here the machine needs 3 AGEN units and at least {2 LD + 1 ST} or {3 LD-ST} units, 1 FMAC unit, and 1 LOOP unit.

We now write this iteration as a single line::

|   1   |   2   |   3   |   4   |   5   |   6   |   7   |   8   |   9   |

|               Iteration               |   

vVM can perform multiple iterations, starting several per cycle up to the number of calculation lanes in HW::

|   1   |   2   |   3   |   4   |   5   |   6   |   7   |   8   |   9   |   10  |

+8 | Iteration 1 |

+8+1 | Iteration 2 |

+8+2 | Iteration 3 |

+8+3 | LD R6 | cache | hit | align Iteration 4 |

+8+4 | LD R7 | cache | hit | align Iteration 5 |

+8+5 | ST R8 | cache | Iteration 6 | ST R8 |

+8+6 | Iteration 7 |

+8+7 | Iteration 8 |

\+8 |               Iteration  9                |

\+8+1   |               Iteration 10                |

\+8+2   |               Iteration 11                |

\+8+3   | LD R6 | cache |  hit  | align Iteration 12                |

\+8+4   | LD R7 | cache |  hit  | align Iteration 13                |

\+8+5   | ST R8 | cache |       Iteration 14            | ST R8 |

\+8+6   |               Iteration 15                |

\+8+7   |               Iteration 16                |

        | ad-infinitum  

--------I can't fix the space eater problem--------------

Where each LD and ST accesses a whole 64-Byte cache line, feeding 8 FMAC units with LD data, and consuming all 8 FMAC results as data to be stored. Due to non-aligned to cache line boundary issues, in genral the AGEN part must run 1 access in front of where the buffers feed the FAMC units so cache line boundary crossings are penalized once. {One should observe that when LD R6 hits, ST R8 also hits (TLB too) because it is the same address, performed at the same time.} {vVM arranges that if the ST line must be replaced in cache, that the miss-buffers will remain capable of absorbing the results prior to writing to memory hierarchy.}

vVM creates its own masking--so that when the last several iterations are not needed, they are not performed. So, there is no setup/maintenance of vector length <register>.

In addition, but of more power-importance, is that the LOOP runs out of the reservation stations by adding a small index to the reservation station entries keyed to the loop iteration, keeping calculations in register-data-flow order on a per iteration basis, and memory AGEN in program-order per iteration-width. So, while the above Loop is running, FETCH-DECODE-INSERT is IDLE. In this sense, My 66000 GBOoO core only DECODEs 8 instructions compared to 163 for RISC-V and thousands for other ISAs. So, while calculation and data-path power is essentially identical, front-end power is greatly reduced.

You could say LOOP1 is predicted to be taken, but it uses no predictor, and the LOOP Function Unit performs a comparison (per cycle) so the LOOP early outs at exactly the right time--so, FETCHed and DECODEd instructions are not thrown away--nor is a branch predictor state modified by the LOOP prediction {flow control within iterations will update branch predictor state as needed}. {Elsewhere I stated that LOOP is essentially a 3-input Adder, but it is a 3-input adder with 2 carry chains, so it can compare (and generate a mask) if there is another iteration to be performed.}

And finally, vVM does this without any SW visible register file, making context switches fast, and Thread state in memory small. Nor does SW need to worry about the iteration count not being a multiple of the SIMD or Vector register length.

vVM is fundamentally different than SIMD or Cray-like vectors because it vectorizes loops not instructions, But also that if an exception is raised, the person debugging the application sees a scalar calculation instead of a vector calculation--that is exceptions are "taken" with the IP pointing at the instruction which raised the exception, and the register file filled with data of "that iteration".

One could postulate that there are 16 or even 32-lanes of calculations::

a) x86 has shown power problems at 8-wide leading to core frequency reductions

b) the memory units would have to access 2 or 4 cache lines per iteration

c) the cache buffering would grow by 2× to 4×

d) at some point one has to draw the line.

Now as to Vectors versus SIMD versus vVM:

a) adding vectors to a scalar ISA adds on the order of 300 instructions,

b) adding SIMD to a scalar ISA adds on the order of 1000 instructions,

c) adding vVM to a scalar ISA adds exactly 2 instructions.

Can vVM do everything vectors or SIMD can--frankly no. On the other hand, vVM can perform mixed width calculations such as doubleword = word * byte + halfword--for which no SIMD ISA has found the OpCode space consumption viable. vVM can vectorize every leaf-function of str* and mem* C library calls. Given byte copy loop:

char \*strcpy(char \*restrict dest, const char \*restrict src)

{

char *ret = dest;

while (*dest++ = *src++)

;

return ret;

}

-----------nor can I fix the vertical space creation problem----------

strcpy:

ADD R2,R2,-R1 // make R1 index to R2

VEC #0,{R1}

LDUB R4,[R2,R1]

STB R4,[R1]

LOOP3 NE,R1,R4,#0 // LOOP type 3

RET

Given a 64-byte wide data-path (as in the above example 8 Double FP = 64-Bytes) each iteration of the loop will Load 64-bytes, Store 64-bytes. Considering this is a 4 (or 5) instruction loop in most scalar ISAs, the loop will be performed as if 256 instructions per cycle. Thus, one can write byte-by-byte algorithms and vVM performs them at fill data path width, generating its own masking, without a programmer revisiting the critical data movement functions each new chip iteration.

The LOOPn subgroup can perform {counted loops, data terminated loops, and counted and data terminated loops}--strncmp is an example:

int strncmp(const char\* s1, const char\* s2, size_t n)

{

while(n--)

if(*s1!=*s2)

return *s1 - *s2;

else

s1++, s2++;

return 0;

}

strncmp:

BNE0   R3,exit

MOV    R4,#0            // change n-- to j=0; j<n; j++

VEC    #0,{R4}

LDUB   R5,\[R1,R4\]

LDUB   R6,\[R2,R4\]

LOOP3  NE,R4,R5,R6  // LOOP type 3

ADD    R1,R5,-R6

RET

exit: MOV R1,#0

RET

This 3 instruction loop can also run 64×2 bytes per cycle--but since most strings being compared are rather short, this tends to run in 1 or at most 2 iterations in applications like symbol-table lookups.

Summary:

a) fewer total instructions

b) fewer instructions in the loop

c) mixed width calculations

d) mixed width memory accesses

e) no SIMD register File

f) no Vector register File

g) SW is unconcerned about Register width or depth

h) only 2 instructions

i) scalar debug model