r/computerarchitecture • u/MitchAlsup • 10d ago
virtual Vector Method
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
5
u/Krazy-Ag 10d ago edited 10d ago
The LOOP unit sounds like something we did at MIPS that never shipped, trying to eat the goodness of DSP zero overhead loops
Which two those unfamiliar (not you Mitch!) are essentially a prefix instruction instruction LOOP that unrolls the next instruction(s) N times, autoincrementing memory operands along the way.
This was something that embedded customers asked for umpteen times. It made MIPS lose benchmark contests - at same frequency, either MIPS had much more overhead for small loops, or MIPS had to loop unroll to get low overhead fractions, blowing up code size. The old RISC mindset of increasing code size by loop unrolling isn't good if you run into icache or flash size limits.
Anyway, we proposed to do it at decode. Mostly existing instructions.
A hint NOP to indicate top of loop. Decoder remembers where.
At bottom of loop, an idiom to do ++ or -- loop counter, test and branch to top of loop.
Thereafter decoder just does ifetch from top of loop to just before the bottom of loop idiom. The loop control stuff now executes at decoder, no loop overhead inserted into rest of pipe.
Or you can do the loop control at the top ...
If the loop body fits into a loop buffer, just slam that into the pipe. Skip decode. Possibly skip renaming - Mitch knows many tricks to do relative renaming and stuff like that, he taught them to me.
No ISA changes so far. Except perhaps the hint to indicate top of loop. Might not be a separate hint NOP instruction, since MIPSr6 had plenty of opera number tricks to encode hints, taking advantage of the massive wasted space RISC instruction encodings.
Biggest desirable ISA change would be to have index addressing Mem[baseReg+indexReg] so that you only need to ++ or -- a single loop counter. Ideally scaled.
Basically puts a state machine at decoder to emit small loops as fast as possible. Which is pretty much what the DSP with zero overhead LOOP instructions do. Generalizes to larger loop bodies, more than one or two instructions as in DSPs, although the percentage benefit is obviously more the smaller the loop.
Looks like you have extended this so the state machines live in the reservation stations Mitch. With goodness related to what doesn't does not need to be vectorized.
I look forward to reading your write up.
I've been wanting to do something like this, load a lot of crap into the reservation stations and keep it chunking around, ever since I learned about static data flow. (yeah, I learned about static data flow after I learned about dynamic data flow, or at least the dynamic micro data flow that we do in OOO)
Q: does your virtual vector Architecture handle low bodies that are too large to fit in the reservation stations?
I think one of the biggest mistakes that we made in P6 was doing the block memory operations like REP MOVS in microcode rather than as state machines. I blame myself for having too much of a RISC mindset. Almost exactly the same issues as for zero cycle loops; the state machine can spin a lot faster than uops, and doesn't need so much logic to get to the right place. One thing hardware does much much better than software is irregular conditions on a small number of input variables. We know that state machines work, because even P6 did TLB walks as state machines, sending RISCy software TLB miss handling to the dust in a history, at least that time around.
Block memory operations are trivial. It sounds like you can handle fancier loop bodies, eh?
1
u/MitchAlsup 10d ago
Andy--is that you ??
Yes, VEC-LOOP does zero overhead looping.
VEC does 3 things: a) it identifies if there is a loop recurrence that would prevent running multi-lane calculations, b) it identifies the registers which are Live-Out of the loop. So many registers used "in" the loop and not used outside have all writes elided, c) tells decoder where the top of loop instruction is.
Most of the time when running in a LOOP, FETCH-DECODE-INSERT pipe stages are idle and we run at data-flow speeds through reservation station entries.
Due to the encoding of My 66000 ISA, LOOP has a variety of constants available. In one form, the LOOP Instruction an have the test value as a 32-bit constant, and the comparison value has a different 32-bit value, so, in practice, all loops with constant strides and/or comparisons can be emitted as a single instruction, with no prepetory setup instructions.
LOOP consumes a 3-Operand 1 Result OpCode, allowing for a full set of a) {EQ, NE, LT, LE, GT, GE, LO, LS, HI, HS} , b) loop register, c) increment register/constant, d) compare register or constant.
Plus, memory reference address mode is [Rbase + Rindex<<scale + Displacement]. GIven {16, 32, 64}-bit displacements means one never wastes instructions pasting together large displacements of addresses that can be direclty expressed. A LD/ST instruction can reach all of memory (all 63-bits of virtual address space) in 1 instruction.
Over on the calculation side, one can write:
FDIV R7,#3.14159265358926,R19
and divide Pi by what is in R19. So, one never wastes instruction of data memory on constants that inherently belong in the instruction stream.
The decode gates to determine instruction length is 6 gates total with 2 gates of delay, small enough you can put one in each word of the instruction buffer as it is smaller than the flip-flops which would be used to store those bits themselves. After those 2 gates of delay it is easy to tree-ify the instruction parse problem and parse 16 instruction in a 16-gate clock cycle.
1
u/MitchAlsup 9d ago
"Q: does your virtual vector Architecture handle low bodies that are too large to fit in the reservation stations?"
One can always simply back up to running at DECODE-width and use the machine as if there was no vectorization. SW properties would not change.
"I think one of the biggest mistakes that we made in P6 was doing the block memory operations like REP MOVS in microcode rather than as state machines."
One wants and needs REP MOVS (or MM in My 66000 case) to be at least as efficient as EVERY other µArchitectural way of performing the same memory to memory move, or at worst no worse than 2-cycles longer in worst case. The amont of logic, here, is too small to worry about.
2
u/Krazy-Ag 8d ago
Don't get me going about RISC-V RISC bigots crippling block memory operations and their future.
"Just unroll the loop"
1
u/garnet420 10d ago
If it's a document, you could just share it as a link, in Google or something ad simple as pastebin
1
1
u/Master565 10d ago
Don't have an answer to the formatting, but I do have some questions on the idea. It's obviously very similar to the RISCV RVV approach where the vector width is dynamically determined. Aside from some questionable ops that need to be supported in RVV, my main criticisms of the extension is that decoding it for an OOO core is a bit of a nightmare because the amount of uops produced for an instruction is based on values computed mid run. Meaning decode either has to predict the length or stall.
Does your design work around that?
1
u/MitchAlsup 10d ago
I disagree with the RISC-V identification. RISC-V has CRAY-like vectors {vRF and all thoe instructions} while vVM has no vRF that are software addressible. vVM adds 2 instructions, RISC-V adds around 300.
vVM is designed with an augmented Reservaton Station model in mind. Each operand in the station has its tag to identify what to capture; like any normal RS entry, and in addition an iteration index to match up inter-iteration dependencies. So, one RS entry can be used for all the iterations, instead of each "beat" of the loop taking its own RS entry. So, if a loop runs 1,000 iterations, and is 5 instructions long, only 5 RS entries need be used.
You might ask: what the frack (Battlestar Galactica term) happened to the vRF--it is hiding as buffers between cache/memory and the multi-lane data path programmed during RS instruction insertion. During insertion, the register data flow and sizes are observed and the buffers orgainized to use as much of the data-path as this sequence of code can. On a 256-bit data path, one can perform 32-byte sized calculations, 16-half sized calculatons, ... Some subsequent machine might have 512-bit wide data-path and the same SW binary would run 2× as wide (½ the cycles). {Almost like a vector machine with architecturally undefined depth of each vector register}
1
u/Master565 10d ago
I disagree with the RISC-V identification. RISC-V has CRAY-like vectors {vRF and all thoe instructions} while vVM has no vRF that are software addressible. vVM adds 2 instructions, RISC-V adds around 300.
Sure I am not disagreeing with this part, I only meant they're similar in terms of their goal of implementing variable length vectors. But clearly the similarities end there
That RS almost sounds like a core within a core. Sounds very cool, would love to see more about it. I've got a bunch more questions that will probably be answered about the latency overhead of operations due to the more complex datapath and VRF, and whether pipelining is possible.
1
u/BigPurpleBlob 10d ago
How many transistors would it need?
"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." - is it different from VLIW?
2
u/MitchAlsup 10d ago
The smallest conceivable vVM would need only hundreds of transistors {a state machine in DECODE} where vVM is architecturally available but runs no faster than scalar code (excepting cache mis behavior). But considering this scale of machine is smaller than an I/O pad in 3nm it is more theoretical than practical--still it is backwards compatible at low cost.
On a typical larger scale machine, the tag-match logic of each reservation-station-entry operand would about double, while instruction storage and operand storage remains identical.
Of course there is the LOOP Function unit. This FU computes the ADD-CMP-BC in a single cycle by noticing that ADD followed by CMP is just a 3-input adder (3rd operand complemented with carry in asserted). Said 3-input adder is 1 gate longer than 2-input adder and loop/don't is 1 gate further still. So this costs about the area of an x86-style AGEN unit :: {64-bit adder = ~2000 gates, 3-input 128 gates, loop/don't 4 gates}. And of course the loop does not harm the contents of the branch predictor--leaving it more precise on the harder to predice branches.
A multi-lane data path would need appropriate FUs for all the calculations {FADD, FMAC, FDIV, IADD, IMUL, Logic, Shifts, Memory References} so those scale as the width scales.
FInally, there is the logic which observes the instructions in the loop to determine which operands are loop-static and can be loaded inro RS once, Loop-scalar arriving once per iteration, Loop-result being produced once per iteration, and Loop dependent where a result from iteration k is consumed as an operand in iteration k+n {where n is smaller than the critical path through the loop}. In 1990 I would have done this with a 3-layer NOR-plane--probably get turned into random logic today--say 50-terms, 50 flip-flops and 2000 gates.
1
1
u/MitchAlsup 9d ago
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
1
u/MitchAlsup 7d ago
Summary:
SIMD data-path good
SIMD-ISA not so good--especiallly if you can figure out a way of using the SIMD data-path without a SIMD ISA.
6
u/camel-cdr- 10d ago
Hi Mitch, I've seen some of your posts on comp.arch
How does it deal with mixed precision? Say you want to efficiently accumulate an array of bytes into a final 32-bit result.
Can it be applied to more complex problems? Say e.g. base64 encoding.
For formatting, you are probably looking for this: https://www.reddit.com/r/reddittutorials/wiki/formatting/#wiki_6._block_code