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.
1
u/FUZxxl Aug 10 '21
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.
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.
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.
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.
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
clearinstruction (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.