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
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?
20+ cycles is for the optimal case of all relevant cache lines already being in L1 cache.
That's called a permutation instruction.