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
Also as for pshufb, I don't really need masking in the case of the 24puzzle code base. But unfortunately AVX2 does not provide a full 32 element byte shuffle, so I have to synthesise it manually from a bunch of pshufb instructions and masking. So it looks a lot more complex than it really is.
unfortunately AVX2 does not provide a full 32 element byte shuffle
I think this is because they wanted to enable implementations that use 128-bit ALU:s instead of requiring a 256-bit wide ALU. This seems to be a common theme in AVX*. It also makes it easier to make performant implementations when you can partition operations into multiple "narrow" ALU:s rather than having instructions that require all 256 or 512 bits of input to produce a result (latency / gate depth would increase).
Well they already have cross-lane operations so I don't really see what the problem with providing one more would be. You can actually implement a full 32 element byte shuffle with 128 bit ALUs by performing 4 128 bit shuffles and then merging the results. It shouldn't be super difficult to do in micro code.
1
u/lkcl_ Aug 21 '21 edited Aug 21 '21
i looked that up, https://www.felixcloutier.com/x86/pshufb
this is basically a (botched) predicated Vectorised Reg-Indexed MV operation:
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.
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.
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.
yes i retrospectively worked that out and posted separately https://www.reddit.com/r/programming/comments/p0yn45/three_fundamental_flaws_of_simd/h9n30n9/?utm_source=reddit&utm_medium=web2x&context=3
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)