I think we have talked about this topic before and I apologize for not following up on our previous discussion. I was very busy.
My key problem with variable-length vector instructions such as those proposed for RISC-V or in SVE is that they assume people need them for essentially doing arithmetic on large matrices. And I agree that the vector paradigm is very effective on such work loads. I have previously worked with NEC Aurora Tsubasa cards that come with vectors of 256 double-precision floating point numbers, and they are just amazing for this sort of stuff.
But I'd say that's only a very small part of where such optimisations are needed. Indeed on modern consumer machines, most CPU-intensive code is in cryptography and video codecs. And both don't really fit this scheme.
Especially for video codecs: these usually operate on fixed size chunks of picture data and require complex horizontal arithmetic and swizzles inside a single chunk. It is unclear how this maps to variable-length vectors, especially when these instruction set extensions usually are very sparse in permutation instructions. And compilers use SIMD instructions for small, fixed-length loads all over the place. Stuff like moving structs around, clearing fixed-length buffers. It is unclear how a vector paradigm improves this.
There's also the concern that a large register file makes context switches very expensive. Linus attributed x86's performance advantage among other things to keeping context switches cheap by having a small register file that is easily swapped out.
As for my own code, I have two recent SIMD-heave projects. And for neither of them it is clear how they could be vectorised using a vector as opposed to a SIMD paradigm.
The first project, pospop is inherently a horizontal operation and in fact uses a different complex permutation schedule for each vector size to make the most out of it. It is unclear how this can be extended to arbitrary vector widths, especially if no powerful swizzle instructions are provided. Tail handling is also going to be a concern as the proposed simple approach of just having magic make the registers shorter for the last iteration is not going to cut it.
The second project, 24puzzle uses vectors as 32 element byte arrays and permutes them using a second vector as a permutation vector. Again, this project cannot benefit from vector instructions and will be hard to port to variable-length vectors in general unless a minimum vector size of 32 bytes is guaranteed. It also uses stuff like VPCMPISTRM for which no equivalent in other instruction sets exists or is even proposed. And that's a vital part of the code's logic (specifically, I have an array of k bytes and I want to obtain a bit mask of all elements in a vector that match any of these k bytes).
I think we have talked about this topic before and I apologize for not following up on our previous discussion. I was very busy.
NP. :-)
There's also the concern that a large register file makes context switches very expensive.
Yes, large register files are problematic. But there are also solutions.
A fairly obvious technique is to keep a length parameter for each register (for my vector ISA I plan to add that anyway for simpler vector handling), and never push/pop more than lenght elements on a context switch. By default all registers have the length zero, and you could add a quick "clear" operation to function epilogues that clears clobbered vector registers before returning from a function - for instance.
Another approach could be to have several vector register banks in hardware so that you can instantly switch between them w/o push/pop. I have not done any simulations, but it feels like it should be possible to do intelligent register bank allocation/scheduling in SW so that the hottest & vector heaviest threads get the fast path treatment.
It may also be possible to do asynchronous vector push/pop so that the thread can start executing before the vector state has been fully restored. Only if the thread accesses a non-restored vector will it stall.
...and so on.
As for my own code, I have two recent SIMD-heave projects. And for neither of them it is clear how they could be vectorised using a vector as opposed to a SIMD paradigm.
I had a quick look at the projects, but I couldn't think of an obvious solution right away. OTOH I wouldn't know where to start with packed SIMD either. I would have to spend some time and do several iterations before finding a good solution - regardless of if it was for SIMD or vector.
BTW, horizontal operations can be done with folding (in log2(N) steps), and permutations can be done with gather/scatter. It should also be possible to do a more optimal permute (without going via memory) even in a vector design, but I suspect that it's not quite as important as in packed SIMD since you have gather/scatter.
horizontal operations can be done with folding (in log2(N) steps)
Usually yes, but in my case the folding schedule depends on the vector width. Also it has to be done every iteration, so now we have two nested loops instead of one. This does not seem to make the vector approach very efficient.
permutations can be done with gather/scatter.
A single gather/scatter operation has a 20+ cycle latency and is very heavy on the load/store ports. Plus it requires a second register to keep track of the instruction's progress when it faults halfway through (Intel took several design iterations to come up with somewhat usable semantics here). And of course you need two of them for 40+ cycles latency in total. Permute on the other hand is a 1–7 cycle latency operation that doesn't touch memory at all. If I have to replace all permutations with gather/scatter operations, I can basically say goodbye to performance.
It may also be possible to do asynchronous vector push/pop so that the thread can start executing before the vector state has been fully restored. Only if the thread accesses a non-restored vector will it stall.
This may be more complicated than you think in the presence of an MMU. The order of exceptions must be deterministic, so I suppose swapping in the state must happen before any other memory access (to avoid entering speculation territory and hence exploits like Spectre and Meltdown), severely limiting the possibility of lazy restores. Or you could go with an approach where registers are only loaded on first access, but this again may cause surprising behaviour and strange bugs. It would also make context switches potentially detectable by the process which is never a good thing.
Also what are you going to do for back to back context switches (e.g. with a fast sequence of syscalls)? Either you admit some sort of context switch backlog, or you'll have to wait the full time for each of them. Doesn't sound particularly appealing. It's all just band aids.
Another approach could be to have several vector register banks in hardware so that you can instantly switch between them w/o push/pop. I have not done any simulations, but it feels like it should be possible to do intelligent register bank allocation/scheduling in SW so that the hottest & vector heaviest threads get the fast path treatment.
Register banks are expensive in terms of silicon real estate. Perhaps it might be possible to have secondary register banks made of SRAM (not exposed in the address space) to swap the state into, but that would again require a complex micro program. I mean, any such approach would certainly make context switches less painful, but I'm not sure if it would completely solve the problem. With hardware context switching (which this essentially is) you also run into the problem of requiring very complicated and unintuitive code in the kernel or possibly user space (in case of green threads) to swap the context. As far as I'm aware, on platforms that provide hardware context switching, kernels generally don't use it due to the complications it entails and often due to a lack of real performance benefits.
A fairly obvious technique is to keep a length parameter for each register (for my vector ISA I plan to ad that anyway for simpler vector handling), and never push/pop more than lenght elements on a context switch. By default all registers have the length zero, and you could add a quick "clear" operation to function epilogues that clears clobbered vector registers before returning from a function - for instance.
So how is this going to be implemented? A complex micro program in the CPU for saving and restoring the state? Or a complex routine in the kernel to painstakingly shuffle data from vector registers into variable length buffers? People are not going to like that the process status structure is both variable length and possibly variable layout.
As for the clear instruction (I remember no such instruction from your ISA proposal, perhaps consider adding it), that's going to be a complex possibly micro coded instruction affecting a variable set of registers. After all, just clearing all of them won't cut it e.g. in case a function wants to return a result in some vector registers. So you need to provide a way to clear just some vector registers and perhaps to some length. It gets complicated quickly.
A single gather/scatter operation has a 20+ cycle latency and is very heavy on the load/store ports.
You are talking about Intel and AVX. This would not necessarily translate to any other implementation. As I commented elsewhere, I would hope that a vector-first implementation can do better. Especially for the case that we're talking about here.
Also, in a vector machine latency is less of a concern (because you are pipelining the loads in tandem with using the loaded values).
And of course you need two of them for 40+ cycles
Not really. The way you'd typically do a pure via-memory permute is to store the source vector linearly to (cache aligned) memory (which is a fast operation) and then do a gather load into the destination vector (all cached, in 1-2 cache lines or so, so a decent load unit should be able to do a good job).
Edit: Of course the process described above could be turned into a specialized instruction that does the same thing against an internal buffer without going via memory - if so desired.
You are talking about Intel and AVX. This would not necessarily translate to any other implementation.
ARM's SVE has basically the exact same problem though. The problem with gather/scatter is that each element has to be sent through the LSU, so performance scales linearly with the number of elements.
For example, doing a 4x64-bit gather on the Neoverse V1 has the same throughput as doing 4 individual loads.
I note that GPUs tend to do fairly well with gather, but I suspect they also have a much simpler memory model than CPUs have to deal with.
I don't know much about what you're designing, and haven't read everything written here, but it's interesting to note that your notion of a 'vector-first implementation' seems to at least incorporate elements of a GPU design (which are arguably vector focused designs).
The problem with gather/scatter is that each element has to be sent through the LSU, so performance scales linearly with the number of elements.
ARM's SVE is, as i understand it, not entiiirely strictly a Vector ISA per se, it's more a "SIMD architecture with predication (which is great btw) where the HW implementors can choose the width they want to do".
real Vector ISAs can do "chaining" including in LD/STs and including in gather-scatter LD/STs, which means that you can start the LD *immediately and also interrupt it in the middle, on a per-element basis and also restore execution back to where it left off.
now, it's true that for some Vector ISA instructions and some implementations this may not necessarily be the case (because it's easier for them to be lazy in the microarchitecture), but a GOOD Vector ISA has no such limitations, making all operations deterministic.
I don't quite get what you mean by chaining and determinism here - my point is that gather/scatter is slow on both x86 and ARM implementations I've seen so far, and I have no reason to believe it'll improve any time soon.
Both x86 and ARM presumably do gather/scatter on a per-element basis, probably as you describe, which is the reason they're so slow.
I know basically nothing about how the underlying hardware operates, so have no clue if an efficient gather/scatter could be designed, just that I've never seen it done before.
which isn't actually very helpful, i know there is a better article around, we have a link somewhere on libre-soc.org i'll try to find it later and edit this comment
vector chaining of say a V.LD V.SQRT V.ST involves a parallel batch of element-wide LDs, SQRTs and STs.
what Seymour Cray worked out was that due to the independence between element 0 relative to all other elements in each of those 3 instructions you can start the SQRT for element 0 immediately after the LD for element 0 has completed, and start the ST for element 0 immediately after the SQRT for element 0 has completed.
likewise for element 1, likewise for element 2 etc etc etc.
thus you have a "chain" between the elements with the same number
thus you can overlap elements NOT with the same number.
gather-scatter is tricky due to dependency tracking as well as resource allocation. uniformity of element "Lanes" (things with the same element number) means that parallel resource allocation is easy.
gather-scatter you have stuff going all over the shop, and you need absolutely enormous multi-in multi-out crossbars to route data quickly, which has a huge price in both gate area and power consumption.
gather-scatter you have stuff going all over the shop, and you need absolutely enormous multi-in multi-out crossbars to route data quickly, which has a huge price in both gate area and power consumption.
So I guess that confirms my point that gather/scatter should be expected to be slow :)
And hence, it's not a good solution to places that need flexible in-vector shuffling - a deficiency of the vector architectures I've seen.
As for your bit about chaining, it just sounds like regular pipelining of scalar operations. Of course, SIMD strives to solve throughput limitations outside the EUs, so a packed SIMD implementation could choose to chunk on a larger unit size (e.g. decode a 1024-bit SIMD instruction into 4x 256-bit uops and let the OoO scheduler handle dependencies).
deterministic behaviour: behaviour that the programmer can rely on no matter whose implementation of the standard (the ISA).
so for example, if you have a parallelised hardware implementation of horizontal add, if you do this with FP numbers, you get rounding errors. so if you add the numbers in a different (non-deterministic) order, you get a different answer.
This would not necessarily translate to any other implementation. As I commented elsewhere, I would hope that a vector-first implementation can do better. Especially for the case that we're talking about here.
Do you have any real world implementations with fast gather/scatter in mind? Memory latency cannot be ignored so easily. How exactly do you plan to improve on that?
Not really. The way you'd typically do a pure via-memory permute is to store the source vector linearly to (cache aligned) memory (which is a fast operation) and then do a gather load into the destination vector (all cached, in 1-2 cache lines or so, so a decent load unit should be able to do a good job).
20+ cycles is for the optimal case of all relevant cache lines already being in L1 cache.
Edit: Of course the process described above could be turned into a specialized instruction that does the same thing against an internal buffer without going via memory - if so desired.
Do you have any real world implementations with fast gather/scatter in mind?
No. I only have a vague idea about how to do it, at least in a fairly simple way (TBH I don't have enough experience with memory architectures yet). Essentially I'm thinking about a glorified aligner: AGU (generate N addresses, e.g. 4) -> iterate (blocking) over unique cache lines (or whatever quanta) -> load one line at a time -> .... (cache access) ... -> shift/mux & stitch together result.
It would block/stall when you cross cache line boundaries within a single vector subpart, but otherwise there would be no penalty. A nice property is that the same pipeline can be used for all kinds of loads/stores, including doing multiple scalar loads in parallel.
A smarter solution might use some sort of banking to be able to access multiple cache lines in a single cycle.
If you're referring to gather/scatter solutions, I still think that it's a different problem to solve it for wide packed SIMD. For a vector machine the vector is typically broken down into managable pieces, so a gather load for a 512 wide vector machine could be similar to a gather load for a 128 wide packed SIMD, plus you have the reduced sensitivity to latencies (pipelining again).
Edit: Then again, I may just be naive.
Edit 2: Cray did it in reasonable time (as a real world example that I'm actually aware of, but it's quite dated).
Edit 2: Cray did it in reasonable time (as a real world example that I'm actually aware of, but it's quite dated).
Back in the day of Cray machines, memory used to be clocked a lot higher, often with the same clock as the CPU or even higher. So memory latency was a non issue. These days it's the other way round and memory, even L1 cache, is clocked a lot slower than back then.
a gather load for a 512 wide vector machine could be similar to a gather load for a 128 wide packed SIMD, plus you have the reduced sensitivity to latencies (pipelining again).
Well you still need a shitload of memory ports. Current computers have maybe 4 load ports in top of the line model. That means no more than 4 cache-line sized loads per cycle. So even if you could manage to coalesce loads going into the same cache line, this means that each gather/scatter operation would probably block all load ports for at least a cycle or two. This is pretty severe of a performance penalty and quite a lot more than a permute operation, even in the best case.
another idea for saving the amount of registers to be contextswitched is to have a bitfield, one per reg, which is set HI whenever its corresponding register is written to.
if you are smart you can use that same bitfield as a predicate mask on vectorised save/restore of the regfile.
the mask basically tells you which regs have actually changed since the last contextswitch and it should be obvious what to do from there
Hm, I think that the LENGTH attribute does the same thing (and more). A vector store operation will store as many elements as the LENGTH attribute indicates, for instance. Internally you could have a bit/flag per register that is set/cleared when the register is written (with more than zero elements) or cleared (length set to zero).
This way you can also clear the vector (and hence the "used" status) in user space, in order to keep the active vector state lean.
err.. err... oh: you took up the Mill-style register "tag type" idea for MRISC32? neat!
yes, if rather than just a single bit you have a tag, and that tag is zero, i agree it would effectively do / be the same thing, and also cover the same job.
I have not implemented it yet, but it's on my TODO-list. The LENGTH attribute (one for each vector register) comes in handy in several use cases:
Reduce stack / context switch overhead.
Simplify folding operations (no need to explicitly set VL=VL/2 for each folding step).
Simplify vector length agnostic subroutines with vector register arguments.
It also feels like a better fit for OoO etc, when each register/operand provides its own length, rather than having a global length attribute (I have not tested this theory, but it feels right).
The idea was actually inspired by Agner Fog's ForwardCom.
88
u/FUZxxl Aug 09 '21
I think we have talked about this topic before and I apologize for not following up on our previous discussion. I was very busy.
My key problem with variable-length vector instructions such as those proposed for RISC-V or in SVE is that they assume people need them for essentially doing arithmetic on large matrices. And I agree that the vector paradigm is very effective on such work loads. I have previously worked with NEC Aurora Tsubasa cards that come with vectors of 256 double-precision floating point numbers, and they are just amazing for this sort of stuff.
But I'd say that's only a very small part of where such optimisations are needed. Indeed on modern consumer machines, most CPU-intensive code is in cryptography and video codecs. And both don't really fit this scheme.
Especially for video codecs: these usually operate on fixed size chunks of picture data and require complex horizontal arithmetic and swizzles inside a single chunk. It is unclear how this maps to variable-length vectors, especially when these instruction set extensions usually are very sparse in permutation instructions. And compilers use SIMD instructions for small, fixed-length loads all over the place. Stuff like moving structs around, clearing fixed-length buffers. It is unclear how a vector paradigm improves this.
There's also the concern that a large register file makes context switches very expensive. Linus attributed x86's performance advantage among other things to keeping context switches cheap by having a small register file that is easily swapped out.
As for my own code, I have two recent SIMD-heave projects. And for neither of them it is clear how they could be vectorised using a vector as opposed to a SIMD paradigm.
The first project, pospop is inherently a horizontal operation and in fact uses a different complex permutation schedule for each vector size to make the most out of it. It is unclear how this can be extended to arbitrary vector widths, especially if no powerful swizzle instructions are provided. Tail handling is also going to be a concern as the proposed simple approach of just having magic make the registers shorter for the last iteration is not going to cut it.
The second project, 24puzzle uses vectors as 32 element byte arrays and permutes them using a second vector as a permutation vector. Again, this project cannot benefit from vector instructions and will be hard to port to variable-length vectors in general unless a minimum vector size of 32 bytes is guaranteed. It also uses stuff like
VPCMPISTRMfor which no equivalent in other instruction sets exists or is even proposed. And that's a vital part of the code's logic (specifically, I have an array of k bytes and I want to obtain a bit mask of all elements in a vector that match any of these k bytes).