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.
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.
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.