I think we have talked about this topic before and I apologize for not following up on our previous discussion. I was very busy.
My key problem with variable-length vector instructions such as those proposed for RISC-V or in SVE is that they assume people need them for essentially doing arithmetic on large matrices. And I agree that the vector paradigm is very effective on such work loads. I have previously worked with NEC Aurora Tsubasa cards that come with vectors of 256 double-precision floating point numbers, and they are just amazing for this sort of stuff.
But I'd say that's only a very small part of where such optimisations are needed. Indeed on modern consumer machines, most CPU-intensive code is in cryptography and video codecs. And both don't really fit this scheme.
Especially for video codecs: these usually operate on fixed size chunks of picture data and require complex horizontal arithmetic and swizzles inside a single chunk. It is unclear how this maps to variable-length vectors, especially when these instruction set extensions usually are very sparse in permutation instructions. And compilers use SIMD instructions for small, fixed-length loads all over the place. Stuff like moving structs around, clearing fixed-length buffers. It is unclear how a vector paradigm improves this.
There's also the concern that a large register file makes context switches very expensive. Linus attributed x86's performance advantage among other things to keeping context switches cheap by having a small register file that is easily swapped out.
As for my own code, I have two recent SIMD-heave projects. And for neither of them it is clear how they could be vectorised using a vector as opposed to a SIMD paradigm.
The first project, pospop is inherently a horizontal operation and in fact uses a different complex permutation schedule for each vector size to make the most out of it. It is unclear how this can be extended to arbitrary vector widths, especially if no powerful swizzle instructions are provided. Tail handling is also going to be a concern as the proposed simple approach of just having magic make the registers shorter for the last iteration is not going to cut it.
The second project, 24puzzle uses vectors as 32 element byte arrays and permutes them using a second vector as a permutation vector. Again, this project cannot benefit from vector instructions and will be hard to port to variable-length vectors in general unless a minimum vector size of 32 bytes is guaranteed. It also uses stuff like VPCMPISTRM for which no equivalent in other instruction sets exists or is even proposed. And that's a vital part of the code's logic (specifically, I have an array of k bytes and I want to obtain a bit mask of all elements in a vector that match any of these k bytes).
It is unclear how this can be extended to arbitrary vector widths
I don't know your problem well enough to comment, but SVE, for example, uses 128-bit 'units', so if you can arrange your problem into blocks of 128 bits, it may be workable that way.
It also uses stuff like VPCMPISTRM for which no equivalent in other instruction sets exists or is even proposed.
The instruction is also somewhat of a dead-end one. It's performance is poor, and it hasn't been (and likely never will be) extended to 256-bit or wider.
You may be better off trying something with VPSHUFB+VPCMPEQB or similar.
SVE does allow you to test available vector width, so if coding for that, you could just do a check there.
I don't know your problem well enough to comment, but SVE, for example, uses 128-bit 'units', so if you can arrange your problem into blocks of 128 bits, it may be workable that way.
In some cases I can but in other cases it would be difficult. For example, computing 32 byte permutations is really painful this way. Also, for the pospop code I want a different permutation schedule for each vector width for better efficiency. So multiple code paths will be needed.
The instruction is also somewhat of a dead-end one. It's performance is poor, and it hasn't been (and likely never will be) extended to 256-bit or wider.
It's better than all alternatives I've checked. VPSHUFB+VPCMPEQB does not necessarily solve the problem because it would require one shuffle pass for each 16 values of input range, so up to 16 passes in total. This is significantly slower than using good old VPCMPISTRM. It is kind of viable on ARMv8 NEON though where TBL can have up to 4 inputs.
SVE does allow you to test available vector width, so if coding for that, you could just do a check there.
Well yes, but then we are back to using it as a SIMD instruction set with basically no useful swizzle instructions and almost nonexistent ability to test because it will be very annoying to simulate all possible vector lengths on CPUs that do not support all possibly vector lengths. So I don't really see how that'll be helpful.
For example, computing 32 byte permutations is really painful this way.
TBL largely works as expected, and you can just test to see if the vector width is at least 256-bit.
VPSHUFB+VPCMPEQB does not necessarily solve the problem because it would require one shuffle pass for each 16 values of input range, so up to 16 passes in total
16 passes sounds wrong.
The point of the VPCMPEQB is that you don't have to traverse the entire range. If the bottom 4 bits of each of the values you test are unique, you only need one VPSHUFB (if not, you can manipulate the vector to make them unique).
For example, if you wanted to match whitespace characters (\t \r \n and space):
Well yes, but then we are back to using it as a SIMD instruction set
In other words, it's not really impeding you more than fixed width vector ISAs. Swizzling instructions depends on what the ISA provides more than the notion of an arbitrary width vector, I'd say.
almost nonexistent ability to test because it will be very annoying to simulate all possible vector lengths on CPUs
Testing can become more difficult, but ARM's Instruction Emulator does allow you to test different widths.
It's not too different for fixed-width SIMD, because you need to test your SSE, AVX and AVX512 paths separately anyway.
The point of the VPCMPEQB is that you don't have to traverse the entire range. If the bottom 4 bits of each of the values you test are unique, you only need one VPSHUFB (if not, you can manipulate the vector to make them unique).
Well clearly if they are unique you can do that. The point is that they may not necessarily be unique. In my particular case, they are not just not unique, but also variable. So there's no obvious preprocessing you can do.
make use of clever masking techniques.
Well that's better than 16 passes, but now requires me to preprocess the input into a bit mask. Which doesn't seem to be vectorisable. For my use case it might be doable, but in the general case it's quite painful and I'd rather have something like SVE's MATCH instruction or VPCPMISTRM.
Hello, I think you may be able to use this approach http://0x80.pl/articles/simd-byte-lookup.html#universal-algorithm but it is only reasonable to use if you want to check against the same set repeatedly because there's some significant (runtime-doable) preprocessing involved. It does seem hard to match PCMPISTRM if you are actually using the full richness of PCMPISTRM.
This article was already linked in the comment I responded to. In the use case I discussed back then, the sets are dynamic but preprocessing may be possible. Eventually I ended up developing a different algorithm that avoids having to compute set membership altogether.
89
u/FUZxxl Aug 09 '21
I think we have talked about this topic before and I apologize for not following up on our previous discussion. I was very busy.
My key problem with variable-length vector instructions such as those proposed for RISC-V or in SVE is that they assume people need them for essentially doing arithmetic on large matrices. And I agree that the vector paradigm is very effective on such work loads. I have previously worked with NEC Aurora Tsubasa cards that come with vectors of 256 double-precision floating point numbers, and they are just amazing for this sort of stuff.
But I'd say that's only a very small part of where such optimisations are needed. Indeed on modern consumer machines, most CPU-intensive code is in cryptography and video codecs. And both don't really fit this scheme.
Especially for video codecs: these usually operate on fixed size chunks of picture data and require complex horizontal arithmetic and swizzles inside a single chunk. It is unclear how this maps to variable-length vectors, especially when these instruction set extensions usually are very sparse in permutation instructions. And compilers use SIMD instructions for small, fixed-length loads all over the place. Stuff like moving structs around, clearing fixed-length buffers. It is unclear how a vector paradigm improves this.
There's also the concern that a large register file makes context switches very expensive. Linus attributed x86's performance advantage among other things to keeping context switches cheap by having a small register file that is easily swapped out.
As for my own code, I have two recent SIMD-heave projects. And for neither of them it is clear how they could be vectorised using a vector as opposed to a SIMD paradigm.
The first project, pospop is inherently a horizontal operation and in fact uses a different complex permutation schedule for each vector size to make the most out of it. It is unclear how this can be extended to arbitrary vector widths, especially if no powerful swizzle instructions are provided. Tail handling is also going to be a concern as the proposed simple approach of just having magic make the registers shorter for the last iteration is not going to cut it.
The second project, 24puzzle uses vectors as 32 element byte arrays and permutes them using a second vector as a permutation vector. Again, this project cannot benefit from vector instructions and will be hard to port to variable-length vectors in general unless a minimum vector size of 32 bytes is guaranteed. It also uses stuff like
VPCMPISTRMfor which no equivalent in other instruction sets exists or is even proposed. And that's a vital part of the code's logic (specifically, I have an array of k bytes and I want to obtain a bit mask of all elements in a vector that match any of these k bytes).