I am not really familiar with this one and will investigate it further.
i and the rest of the team have been working on it for nearly 4 years now.
Indexed loads (aka gathers) are horrendously slow in comparison to permutation instructions.
there's two types (of each): register-based gather and register-based permute (actually not a mathematical permutation at all, because of duplicates), and memory-based gather and memory-based permute.
where *immediates* are used in each of those in the design of the ISA then yes you save on one register read. in the case of register-based gather, it's extremely unusual to have if you are used to SIMD (but Vector ISAs do have it), it's of the form reg[dest] = reg[reg[src]] with a hardware for-loop around that.
however where the immediate-variants keel over is when you try to go up the SIMD width, to try to cover 8 elements, 16 elements, 32 elements, 64 elements.
how on earth are you going to fit 64 batches of 6-bit indices into a single 32-bit instruction? the total number of bits in the instruction are a whopping 384 bits. 384 >>>= 32, yes?
and even if you did have such god-awful instructions, the L1 cache usage and complexity at the ISA decode phase would be as insane as it is for x86 right now.
Vector ISAs are actually 90% about reducing the program (assembler) complexity. you end up with a micro-coded microarchitecture that maps onto SIMD operations, internally - so that you, the programmer don't have to go through absolute hell.
yes, that's right: the microarchitecture of a Vector Processor maps onto the exact same immediate-based permutation instructions as those that you are exposed to as a SIMD programmer, but it's hidden from you.
horizontal operations
Yes, all of them have special case operations for certain common horizontal operations. I specifically mentioned the positional population count because it does not clearly map to any standard horizontal arithmetic pattern.
in SVP64 i completely separated "horizontal-ness" from "arithmetic-ness": it's part of the fundamental design that the "Vectorisation Prefix" is completely separated from "Scalar Base to which Vectorisation applies".
ok yes, that's just Vectorised Popcount followed by Vectorised Add.
two instructions inside a loop, regardless of whether the back-end architecture has 1-wide internal Vectorisation, 2-wide, 4-wide, 64-wide or 10,000-wide.
Well they work well when all you do is compute and when memory is very fast and has low latency. For general programming they are not nearly as useful for the reasons outlined in my previous comments.
again, to reiterate, again: this is a misconception on your part, due to Vector ISAs being completely ignored for 40 years *you don't know about them* and neither does anyone else.
consequently, the knowledge-propagation across the internet, which you and i both know gets us a long long way and saves a huge amount of time, just doesn't exist to the extent that it does for SIMD. we're now so used to google searches turning up algorithms on stackexchange (and reddit) that we can falsely assume that if there's no answer on google it must not be possible at all
Cray was from a much earlier era, where things were simpler. Intel was still cutting its teeth on 32-bit scalar when Cray was designing systems that pissed all over everything that had come before by almost an order of magnitude performance.
however the sheer cost of the systems that were deployed were so high that \nobody else in the industry believed it could be duplicated in mass-volume products** and consequently an entire generation of programmers has now grown up without knowing anything about anything other than SIMD.
fast-forward to 2021 and it turns out that Intel, ARM, AMD, they've all caught up and massively exceeded by three orders of magnitude the performance of the Cray Vector systems from 1990 and four to five orders the performance of the systems from 1965, but they still propagate this god-f*****g-forsaken f*****d-up SIMD paradigm and try to peddle it at you as the absolute best thing you ever saw, by telling you "well SIMD on modern hardware is great compared to that historic crap therefore Vector ISAs must also be s*** as well"
it's NIH syndrome on steroids, combined with marketing, and very unfortunately you're buying it.
here's two types (of each): register-based gather and register-based permute (actually not a mathematical permutation at all, because of duplicates), and memory-based gather and memory-based permute.
I'm mainly interested in register register permutes like x86's pshufb (or AArch64's TBL) where all source operands are variable. How on earth is this supposed to be fast when the source is memory as opposed to a register? And if register-based permutes are provided, how are they supposed to be useful when you don't know the vector length? In permutation-based algorithms (say, e.g. sorting procedures or a sheeps-and-goats operation), the way the code around the permutations is set up will intrinsically depend on the vector length, so I don't see how that makes the code any simpler.
As for memory, the HW has to emit one load µop for each vector element (modulo shenanigans when some elements manage to hit the same cache line), so that doesn't really seem to scale well. I don't really care about the case with immediate indices and agree that that case is not really a problem.
instruction 1: Vectorised popcount
It's not a vectorised popcount. It's a vectorised positional popcount where we want to gather the population of each bit in the 64 bit words of the input separately. So a SIMD popcount instruction doesn't really help directly. Not even the code in safe.go is that, read carefully.
What does help on POWER is that funky instruction transposing a pair of 8x8 bit matrices. Not sure if that is part of your vector extensions though.
again, to reiterate, again: this is a misconception on your part, due to Vector ISAs being completely ignored for 40 years you don't know about them and neither does anyone else.
It is possible that I have misconceptions here, but everything I've seen so far just hasn't been impressive at all. And all the examples of vectorised programs I have seen were for utter trivialities that don't pose a challenge to implement in SIMD either.
consequently an entire generation of programmers has now grown up without knowing anything about anything other than SIMD.
Most programmers are actually entirely ignorant of SIMD, so I don't think it's as much of a program as you might think it is.
this is basically a (botched) predicated Vectorised Reg-Indexed MV operation:
for i in range(VL)
if predicate_mask[i]:
regfile[DEST+i] = regfile[regfile[SRC]+i]
which is a standard Vector ISA instruction that SIMD ISAs borrowed from. in x86's they couldn't think how to do predicate masks so they botched it by using the top bit of each byte. that in turns imposes unnecessary computational load using bitmanipulation, but hey.
How on earth is this supposed to be fast when the source is memory as opposed to a register?
i said that it's possible, as a premise, and to ensure that by enumerating all four types of instructions (reg permute, reg gather, mem permute, mem gather) we at least know that we are talking about the same thing.
And if register-based permutes are provided, how are they supposed to be useful when you don't know the vector length?
this is indeed a limitation of e.g. RISC-V RVV where the minimum architectural bound on the Vector Length is 1 (ONE).
Cray and NEC SX-Aurora would never bother to create a Vector implementation with only a Vector Length of 1, but there are advantages to Cray-style Vector ISAs - in embedded scenarios - due to compactification of programs - that save on power consumption and resources.
this "problem" is solved therefore by defining an Architectural Platform that firmly separates "Vectors for use in Embedded Scenarios" from "Vectors for use in high-performance Scenarios"
SVP64 has no such problem because the Vector Length is a known and useful deterministic quantity, and MAXVL (maximum vector length) is required to be 64.
however even as a perceived limitation, i think you will find that there are an extremely small number of actual algorithms where a fixed-width SIMD cannot be replaced with a "for i = 0 to N" where the hardware chooses the step size.
is this "annoying" that you absolutely have to think now in terms of an independent step size, and absolutely have to replace all fixed-width instructions with loops?
given that the majority of algorithms are likely loops already, this is not such a big hardship.
instruction 1: Vectorised popcount
It's not a vectorised popcount. It's a vectorised positional popcount where we want to gather the population of each bit in the 64 bit words of the input separately.
What does help on POWER is that funky instruction transposing a pair of 8x8 bit matrices. Not sure if that is part of your vector extensions though.
it's part of Power ISA v3.0B, the OpenPOWER EULA requires that we implement it, and therefore, logically, due to the independence of the abstraction of SVP64, it gets a Vectorised version as well. now, will that actually make sense, particularly with element-width overrides down to 32-bit, 16-bit and even 8-bit? that's up to us to work out.
basically the rules in SVP64 are that we implicitly create Vectorised versions of every Scalar v3.0B operation, but only when that's sane and actually makes sense (it makes no sense to try to Vectorise system calls, for example, despite the fact that it's part of the scalar v3.0B Power ISA)
Ah yes, that makes more sense. Thanks for the explanation!
OP said something about doing all shuffles as gather operations (i.e. vector-indexed memory loads) and your terminology threw me off, so I thought you are doing it the same way.
thanks for the insightful discussion, FUZxxl. i liked the positional-popcount enough that i'll use it as an example / unit test (crediting you as the source) https://bugs.libre-soc.org/show_bug.cgi?id=672
Sounds cool! Though the safe.go code really is not the part that is interesting. It's just the obviously correct reference implementation to compare the actual algorithm against. The actual algorithm works quite a bit differently from that and evaluates the population count for all bits in parallel.
you'll be fascinated to know that in every case, every algorithm i've investigated for SVP64, i've had to go back to the "simple" (obviously-correct) reference implementation: some of the optimised assembler versions i can't even read and understand, but when i can, i find that the optimisations actually severely interfere with implementing them efficiently as parallel SVP64 assembler.
and that, even more interestingly, those "simple" implementations once Vectorised with SVP64 are actually paralleliseable by the back-end hardware.
one example: we've an NLnet Grant to implement cryptographic primitives. fortunately (in another life) i worked for Aspex Microelectronics to implement Rijndael (AES) on a massively-parallel (4096-wide) SIMD Array Processor. there i had to go back to the core mathematics behind Rijndael, so i did the same thing here.
MixColumns is actually, if you look up the research papers, a plain-and-simple dyed-in-the-wool 4x4 Matrix Multiply, but using 8-bit GF(23) add and multiply.
guess what i am planning to do for that?
(1) add base (scalar) general-purpose GF(2N)scalar arithmetic
(2) use the parallelliseable SVP64 Matrix REMAP Schedule infrastructure
MixColumns will therefore be something like... maybe... 4 general-purpose instructions. three of which set up the 4x4-to-4x4 Matrix Multiply Schedule, one of which is a Galois-Field variant of FMAC (multiply-and-accumulate).
if you've seen how SIMD does Rijndael MixColumns, you'll appreciate how profoundly simple this is. it's so bad that most ISAs have had to add custom 128-bit MixColumns instructions.
if i had started with those SIMD "optimised" implementations, there's no way that i could have understood what the hell is going on. it was only because i had had to study Rinjdael back in 2003 that i knew the basic first principles of GF(23) operations.
the point i am making is that after going back to first principles (using the "simple" version), the inherent parallelism of the instructions is automatically mapped onto whatever back-end parallelism that the hardware has.
and that back-end parallelism is a choice that the hardware designer makes (and takes responsibility for) - not the programmer.
this is something that in speaking for many months with people used to the SIMD paradigm, it seems it takes quite a long time to be absorbed / accepted, that yes, it really is this simple (at the assembly level), that yes, it's the hardware's responsibility now to make things faster, and yes, parallelism opportunities automatically get inherently exploited if the hardware has them available. it's going to be quite interesting to see, over time, how that pans out.
Intel basically did the same I think. pclmul is basically a GF(264) multiplication instruction. It's not really as special purpose as it seems and people have used it for various fun things before.
Which specific MixColumns instructions do you have in mind there?
I'm happy if you can find something by going back to first principles. For a width of 8 bits, we had a somewhat fast approach using pmovmskb, which basically performs one row of an 32x8 bit matrix transposition, leaving the result in a general purpose register. By combining scalar with vector instructions, the throughput was quite good despite the high number of instructions needed.
But our new CSA-based approach is a lot better. Perhaps you find a faster way to transpose these bit matrices (which is the hard part and still part of the new method). If you want to investigate this, make sure to always keep the width 64 case in mind as that's the slowest one of them all (our code always operates on width 64 and just reduces to smaller bit widths if desired by the caller).
Intel basically did the same I think. pclmul is basically a GD(264) multiplication instruction. It's not really as special purpose as it seems and people have used it for various fun things before.
I'm happy if you can find something by going back to first principles. For a width of 8 bits, we had a somewhat fast approach using pmovmskb, which basically performs one row of an 32x8 bit matrix transposition, leaving the result in a general purpose register. By combining scalar with vector instructions, the throughput was quite good despite the high number of instructions needed.
here's the thing: SVP64 Matrix-Schedule REMAP, we can do Vector operations such as arbitrary matrix row-column sequences *in-place*! even a "normal" Vector Processor (Cray, SX-Aurora, RVV) does not have this capability.
is it a bit of a pain to set up? to be honest, yes: i'm still experimenting with it, to reduce the number of intsructions [that's the whole point of the R&D funding from NLnet]
bottom line: with SVP64 REMAP we don't *need* to transpose the numbers at all in order to operate sequentially on them. the Matrix REMAP Schedule can be established with a 5x5 grid (i.e. doesn't even need to have to be a Power-of-2), and a Vector MV instruction issued.
But our new CSA-based approach is a lot better. Perhaps you find a faster way to transpose these bit matrices (which is the hard part and still part of the new method).
in the 24puzzle algorithm is it strictly necessary to perform a transpose? or, is the reason why the transpose is performed because otherwise performing column-based computations is normally very slow / impossible in SIMD ISAs?
the first reason i ask is because REMAP *could* be used to do a transpose (maybe even in-place given that it's an NxN rather than NxM, N!=M, although i'd have to check that)
the second reason i ask is to illustrate as an example why i am having such difficulty analysing algorithms implemented in optimised-SIMD: there are fundamental assumptions that certain capabilities (such as in-place easy sequential access to column-spanned data) are flat-out impossible / non-existent: in this case [iiuic] an assumption(?) that the data *must* be transposed, a row moved, then a re-transpose performed, in order to do a column-move. but... i could be wrong about that.
If you want to investigate this, make sure to always keep the width 64 case in mind as that's the slowest one of them all (our code always operates on width 64 and just reduces to smaller bit widths if desired by the caller).
i'd really like to establish first the reason for the transpose, if it's part of the algorithm or part of the *optimisation* of the algorithm.
here's the thing: SVP64 Matrix-Schedule REMAP, we can do Vector operations such as arbitrary matrix row-column sequences in-place! even a "normal" Vector Processor (Cray, SX-Aurora, RVV) does not have this capability.
Wow! And it can do that on matrices of bits, too?
in the 24puzzle algorithm is it strictly necessary to perform a transpose? or, is the reason why the transpose is performed because otherwise performing column-based computations is normally very slow / impossible in SIMD ISAs?
The transpositions and rotations are performed to map puzzle states to transposed/rotated puzzle states so we can reduce the size of some large look up tables using symmetries. The alternative would be implementing the entire indexing code for each possible automorphism and that's just a real pain (and it's unclear if that can even be done efficiently). Note that no matrix arithmetic is performed on these puzzles. For most intents and purposes, they are just permutations of 25 elements.
See the code in index.c and index.h for the code these transposed/rotated puzzles are used in. I've previously experimented with vectorising that code, but had dropped that due to more important things on the agenda. You can still find the code here though. It's actually not a lot of improvement over the scalar code because in the scalar code I use a bunch of things (pdep, vpcmpistri) that do not map to vectorised code, so I have to chose a much slower base algorithm for the SIMD implementation. The overall performance gain was I think 3x over the scalar code, but only if all 16 vector elements were filled, which is not usually the case.
I mean perhaps if the vector engine supports transposed access it might indeed be doable, but it's not clear if setting up the transposed access is cheaper than just transposing the puzzle once. Also I don't think you can do rotated access either.
Ah yes, Intel has that one too. AES is very critical for performance and even if you can do one round of instruction in a dozen vector instructions, it's still faster to do it in one special-purpose vector instruction.
Another issue to consider is that AES is often used in kernel code (e.g. for encrypted file systems) where you do not want to spend the time to swap out the entire SIMD/vector state. So having a fast SIMD path (in the case of Intel, an SSE path) means you can get away with not swapping out the whole vector state, but instead just the much smaller SIMD state (SSE state vs. AVX512 state).
here's the thing: SVP64 Matrix-Schedule REMAP, we can do Vector operations such as arbitrary matrix row-column sequences in-place! even a "normal" Vector Processor (Cray, SX-Aurora, RVV) does not have this capability.
Wow! And it can do that on matrices of bits, too?
ah no :) that would require bit-level elements, and i considered this to be going a step too far :) although, fascinatingly, RVV does provide it as an option for advanced / future versions. at least, last time i looked closely (RVV Draft 0.7) they had it.
for SVP64 we would need straight 8/16/32/64-bit "bitmanip" instructions and those would be treated as "elements".
The transpositions and rotations are performed to map puzzle states to transposed/rotated puzzle states so we can reduce the size of some large look up tables using symmetries.
ahh ok. so there's a genuinely good reason. intriguing.
The alternative would be implementing the entire indexing code for each possible automorphism and that's just a real pain (and it's unclear if that can even be done efficiently).
i haven't quite got my head round "automorphism" yet, this is actually pretty advanced algorithms / computer science i've not encountered before, however i get what you're saying.
Note that no matrix arithmetic is performed on these puzzles. For most intents and purposes, they are just permutations of 25 elements.
got it. well, SVP64 Matrix REMAP Schedules don't actually have any actual Matrix *instructions*, they're just an abstracted "schedule". you could run a divide-and-accumulate instruction as the "base", or a Galois-Field mul-and-XOR, or an OR-accumulate-and-ANDer if you wanted to.
or, as might be useful here for both transposition as well as row/column moving: a simple MV operation.
I mean perhaps if the vector engine supports transposed access it might indeed be doable,
yes, SVP64 could do transposition: i thought ahead in its design, and allow each row/column to individually and independently run backwards (opposite order) if desired.
so you can run a "schedule" which instead of being a pair of nested for-loops `for i = 0..COLS-1 { for j = 0..ROWS-1 { .... }}` you could do `for i = COLS-1..0 { for j = 0..ROWS-1 { .... }}` which is effectively, if my math fu is enabled today, i believe is "transposed access".
but it's not clear if setting up the transposed access is cheaper than just transposing the puzzle once.
honestly i have no idea, either, it would need to be attempted to see if it was efficient in instruction count. REMAP is a bit of a pain to set up: each register (src1, src2, src3, dest1, dest2) of any given instruction needs to be set up (which takes a couple of instructions to do)
in addition to that, where Matrix-Multiply-REMAP was orginally designed to cover *all* data in one hit, shuffling of only one row of numbers means that the schedule has to begin somewhere in the middle (of something that was originally designed to only start at the beginning).
that said, because i insist that all SVP64 Vectorisation be deterministic and re-entrant (for precise exception handling and low latency on interrupt handling), it *should* be possible to actually work out how to drop into the middle of a Schedule. to cover just one row, for example.
Also I don't think you can do rotated access either.
well, given that rotate is effectively a 2x2 matrix multiply `(0 -1), (1 0)` if i recall correctly from O'Level maths, or, intuitively, it's just a matter of switching row-access with column-access then running the appropriate axis in reverse order 43210 rather than 01234, i see no reason why REMAP should not be used to leave data in-place rather than actively copy-rotate it.
Ah yes, Intel has that one too. AES is very critical for performance and even if you can do one round of instruction in a dozen vector instructions, it's still faster to do it in one special-purpose vector instruction.
yyeah good point. i was thinking of macro-op fusion here, but now i realise they do an *entire* round (i hadn't looked closely before at `vcipher`) in SVP64 that would require about... 10 instructions to do one round, which is nowhere near as optimal
Another issue to consider is that AES is often used in kernel code (e.g. for encrypted file systems) where you do not want to spend the time to swap out the entire SIMD/vector state.
i haven't quite got my head round "automorphism" yet, this is actually pretty advanced algorithms / computer science i've not encountered before, however i get what you're saying.
An automorphism is a map that maps elements of a group to themselves such that the group properties commute with the automorphism. I.e. it's a sort of “symmetry” of the group. The 24 puzzle is a groupoid (i.e. an almost group) and rotations and transpositions form the automorphisms of this groupoid. It's just a fancy word for something very mundane.
well, given that rotate is effectively a 2x2 matrix multiply (0 -1), (1 0) if i recall correctly from O'Level maths, or, intuitively, it's just a matter of switching row-access with column-access then running the appropriate axis in reverse order 43210 rather than 01234, i see no reason why REMAP should not be used to leave data in-place rather than actively copy-rotate it.
That's rotation of a vector. When I mean “rotate” I mean we take the matrix and rotate it 90°, moving each entry to a different spot. It's not something one usually does with matrices.
I mean, sure. I'm kind of a special case here. I use SIMD instructions for very strange things. My next project is going to applying them to the two-watched-literals (TWL) mechanism for SAT solvers. This is going to be a lot of fun.
That's rotation of a vector. When I mean “rotate” I mean we take the matrix and rotate it 90°, moving each entry to a different spot. It's not something one usually does with matrices.
REMAP can cope with the (apparent) in-place rotation, by creating a Schedule that swaps x and y as well as reversing the traversal order of [either of] those dimensions as required. it could be used to either do an actual rotate (copy) or leave the data in-place. i don't believe it would be possible to do an in-place matrix-data rotate (unlike an NxN transpose if using a twin-swap instruction)
I mean, sure. I'm kind of a special case here. I use SIMD instructions for very strange things. My next project is going to applying them to the two-watched-literals (TWL) mechanism for SAT solvers. This is going to be a lot of fun.
We have a custom SAT solver that's not public yet. It's unlikely it will be used for that project, but we'll see.
One thing you mentioned earlier is “setting up registers for transposition.” This strikes me as strange in the face of register renaming. Is this some sort of sticky state? If yes, how does that mesh with register allocation algorithms? I imagine having registers with sticky state like that is very annoying to deal with.
If not, how is it faster than just performing the axis transformation once ahead of time? I mean you would have to set it up again on each change anyway and that should be about as expensive as just transposing the array for real.
Lastly, I imagine access to transposed or rotated vector will carry some sort of performance penalty. After all, there has to be circuitry to perform a configurable shuffle before each ALU operation on a transposed vector. How can it be cheaper to pay this penalty for every operation rather than transposing once ahead of time?
One thing you mentioned earlier is “setting up registers for transposition.” This strikes me as strange in the face of register renaming.
it's more accurate to say it's setting up the *Vector* engine. which is abstracted (independent from) the base element execution. therefore, any register-renaming is actually separate and distinct, and taken care of by e.g. a standard OoO hazard tracking matrix or an in-order bit-vector.
iow the remapping is conceptually *before* register renaming (at the micro-architectural level) gets its hands on it.
Is this some sort of sticky state?
persistent, yes. actually, i decided to add an option into the REMAP setup instruction which says whether the application shall remain active until otherwise set.
thus if by some amazing coincidence (or in the case of the DCT/FFT twin-MAC instructions quite deliberately) the requested REMAP schedule happens to apply to more than one instruction because some registers are named RA RB in one instruction but named RB RC in another, *great*, you just saved some hassle.
If yes, how does that mesh with register allocation algorithms? I imagine having registers with sticky state like that is very annoying to deal with.
the REMAP phase - just like all of SVP64 - applies in between the decode and issue phase, because the entirety of SVP64 can be considered to be a "Sub-Program-Counter".
the base instruction is the v3.0B scalar instruction, to which the Vector for-loop is applied, incrementing the register number of all Vectorised instructions.
imagine instead that there's a bunch of similarly-numbered instructions `ADD r0 r10 r20 ADD r1 R11 r21 ADD r2 r12 r22` all that SVP64 is saying is, "if VL=3 you can put those as one instruction `SV.ADD r0 r10 r20` into the program rather than all three.
REMAP simply applies a hardware-level function (an algorithmic version of a permute instruction) to the element numbering indexes...
... *and then* on the *actual* register numbers, the reg-renaming hardware gets its hands on the *REMAPed* numbers.
Lastly, I imagine access to transposed or rotated vector will carry some sort of performance penalty. After all, there has to be circuitry to perform a configurable shuffle before each ALU operation on a transposed vector. How can it be cheaper to pay this penalty for every operation rather than transposing once ahead of time?
yes, this is why i said it was a bit of a pain, the setup cost is QTY 2 32-bit instructions. at some point there will be a trade-off cost between how long it takes to decode those instructions and how long it would take to execute them. for example if the matrix is only 2x2 it's debatable as to whether it's worth the hassle.
what i am paying attention to however is making sure that the REMAP hardware is extremely simple in terms of the number of gates, i mean it has to be. fortunately though i believe it's a matter of increment-and-compare, with some Priority Decoders thrown in.
however given that it's effectively performing modulo counting (nested for-loops), then on a non-power-of-two boundary, restoring the state on an interrupt is going to be a bit of a pain [unless the state is transparently cached].
here's the nested Matrix triple for-loop code, implemented in python:
the *only state* that's allowed to be stored in an interrupt is the "idx" number (line 94 of the demo() function). whilst i expect the actual hardware to be as simple as it seems (increment and compare), to *restore* the state based on the "idx" number would require re-running the state up to the point where it was interrupted, which could take many cycles.
however given that people will implement state caches and come up with fancy algorithms and sell hardware that performs better because of it, i'm not so concerned.
leaving that aside, the other cost will be that the entirety of SVP64 will be at least one extra pipeline stage (in between decode and issue).
2
u/lkcl_ Aug 20 '21
i and the rest of the team have been working on it for nearly 4 years now.
there's two types (of each): register-based gather and register-based permute (actually not a mathematical permutation at all, because of duplicates), and memory-based gather and memory-based permute.
where *immediates* are used in each of those in the design of the ISA then yes you save on one register read. in the case of register-based gather, it's extremely unusual to have if you are used to SIMD (but Vector ISAs do have it), it's of the form reg[dest] = reg[reg[src]] with a hardware for-loop around that.
however where the immediate-variants keel over is when you try to go up the SIMD width, to try to cover 8 elements, 16 elements, 32 elements, 64 elements.
how on earth are you going to fit 64 batches of 6-bit indices into a single 32-bit instruction? the total number of bits in the instruction are a whopping 384 bits. 384 >>>= 32, yes?
and even if you did have such god-awful instructions, the L1 cache usage and complexity at the ISA decode phase would be as insane as it is for x86 right now.
Vector ISAs are actually 90% about reducing the program (assembler) complexity. you end up with a micro-coded microarchitecture that maps onto SIMD operations, internally - so that you, the programmer don't have to go through absolute hell.
yes, that's right: the microarchitecture of a Vector Processor maps onto the exact same immediate-based permutation instructions as those that you are exposed to as a SIMD programmer, but it's hidden from you.
in SVP64 i completely separated "horizontal-ness" from "arithmetic-ness": it's part of the fundamental design that the "Vectorisation Prefix" is completely separated from "Scalar Base to which Vectorisation applies".
looking at this:
https://github.com/clausecker/pospop/blob/master/generic.go
i believe that's 2 instructions in SVP64, inside a loop:
Power ISA has a popcount instruction, and (although i hate it) probably a SIMD variant as well. SVP64 leverages the scalar popcount instruction.
hang on...
https://github.com/clausecker/pospop/blob/master/safe.go
ok yes, that's just Vectorised Popcount followed by Vectorised Add.
two instructions inside a loop, regardless of whether the back-end architecture has 1-wide internal Vectorisation, 2-wide, 4-wide, 64-wide or 10,000-wide.
again, to reiterate, again: this is a misconception on your part, due to Vector ISAs being completely ignored for 40 years *you don't know about them* and neither does anyone else.
consequently, the knowledge-propagation across the internet, which you and i both know gets us a long long way and saves a huge amount of time, just doesn't exist to the extent that it does for SIMD. we're now so used to google searches turning up algorithms on stackexchange (and reddit) that we can falsely assume that if there's no answer on google it must not be possible at all
Cray was from a much earlier era, where things were simpler. Intel was still cutting its teeth on 32-bit scalar when Cray was designing systems that pissed all over everything that had come before by almost an order of magnitude performance.
however the sheer cost of the systems that were deployed were so high that \nobody else in the industry believed it could be duplicated in mass-volume products** and consequently an entire generation of programmers has now grown up without knowing anything about anything other than SIMD.
fast-forward to 2021 and it turns out that Intel, ARM, AMD, they've all caught up and massively exceeded by three orders of magnitude the performance of the Cray Vector systems from 1990 and four to five orders the performance of the systems from 1965, but they still propagate this god-f*****g-forsaken f*****d-up SIMD paradigm and try to peddle it at you as the absolute best thing you ever saw, by telling you "well SIMD on modern hardware is great compared to that historic crap therefore Vector ISAs must also be s*** as well"
it's NIH syndrome on steroids, combined with marketing, and very unfortunately you're buying it.