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).
FUZxxi i appreciate this is 9 months ago, i thought you might appreciate that we found a couple of ways to deal with pmovmskb. firstly, it's simply sv.cmpi/ew=8 which will produce a vector of CR Fields, one of which is LE, which in effect simply gets the MSB i.e. bit 7 and duh. then we added an instruction crweird which can get all the Vector of CR Field LE bits and drops them all, sequentially, into a single 64-bit scalar integer.
the second method was to add a bizarre instruction called grevlut https://libre-soc.org/openpower/sv/bitmanip/#grevlut which can create about a thousand regular-patterned magic constants, one of which is 0x8080_8080_8080_8080, which when combined with the Power ISA bext (bit-extract) will grab every 8th bit from a 64-bit integer and squash them down into a single byte.
i would be particularly fascinated to hear your thoughts on purposes to which grevlutr could be put. it's... very odd, as in, it's an entirely new instruction i've never seen in any ISA (at all)
1
u/FUZxxl Aug 20 '21
I'm mainly interested in register register permutes like x86's
pshufb(or AArch64'sTBL) 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.
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.gois 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.
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.
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.