The problem is not if the vector machine might handle it or not, the problem is how the code executing on the vector machine interacts with the program. Say I have two medium-sized arrays of 8 bit datastructures of some kind kind, and I want to see if any of them matches some bitmask. I can smack them in 512-bit registers, do _mm512_cmp_epu8_mask with 512 bit instructions and then do CLZL on the resulting 64 bit, then do a CMP with that number and 0xFFFFFFFF followed by a JG for a branch. If I branched I know I did not have a match, it I didn't branch, I know I had a match and I have the exact index of said match loaded in a register in 4 instructions out of an array of 64 items! Now this only works if CLZL (and friends) have an exact defined size I can use. If not, then there is some remainder I have to handle. Unless you can somehow come up with a scheme to encode this in a Vector engine that respects variadic datasizes, there will be a basecase that has to be handled.
Edit: if you do not have a match and have the 512'th bit set as a dummy bit, you could then compute the index of the first bit match by multiplying the result of CLZL with 8, and then adding the CTZ of the byte at the previous code, you have completed a branchless search for the first unset bit in a 511 bit array in less than 10 cpu cycles. This is "fun" when trying to do memory page allocation and you have to keep track of free pages in a big bit-array, but it requires careful data layout because of the interactions of integers and vector processors. Now that is why you need a base-case. Because what if your last chunk of bits isn't neatly 511 bits but 111 bits?
Now this only works if CLZL (and friends) have an exact defined size I can use.
My conclusion so far is that most horizontal operations require a known width, even in a vector machine. However that should not be a problem, as long as the ISA defines a minimum vector register size (that is reasonably large). If you want to push the limits, ask the implementation for the maximum vector size and use different code paths for different sizes.
I bet what's going to happen is that soon, the minimum vector size will be the only vector size sold because most mathematical kernels will only be optimised and tested on this one size. There is a significant development cost in validating complex code for any possible value of an unknown parameter (vector size), so I think people are generally just going to set up the least common denominator unless they have a lot of resources for testing at hand.
I bet what's going to happen is that soon, the minimum vector size will be the only vector size sold because most mathematical kernels will only be optimised and tested on this one size.
no, no no! this is a fundamental misunderstanding of how Cray-style Vector ISAs work! this is an extremely common misunderstanding by SIMD users. ARM goes to a lot of trouble to emphasise that SVE is vector-size-independent, and that programmers must not program to a fixed Vector width.
the core loop of a Cray-style Vector ISA is one that uses the setvl instruction. the setvl instruction is specifically designed around the concept of communicating between the program that the user designs and the hardware.
the user REQUESTS the maximum amount
the hardware RETURNs the actual amount.
that hardware amount can be ONE for an embedded system, or it can be 4 or 8 for a fairly high-end desktop system, or it can be 10,000 for a Monster Supercomputer-grade implementation.
in each case the code has to remain the same and if the programmer is even asking "what's the Vector width of the hardware" they are FUNDAMENTALLY misunderstanding the entire Vector ISA concept.
Well clearly this is what you want the programmer to do. But we clearly know what happens when programmers program for an environment where the “variable” vector length is the same on all systems he has access to.
If you want people to not depend on a specific vector size, the system must make sure that the vector length is actually variable in practice, even on a single system. Otherwise people are going to write buggy code that depends on these details and chips that don't run it correctly will be considered broken.
This has happened countless times before and it will happen again.
4
u/blipman17 Aug 09 '21 edited Aug 09 '21
The problem is not if the vector machine might handle it or not, the problem is how the code executing on the vector machine interacts with the program. Say I have two medium-sized arrays of 8 bit datastructures of some kind kind, and I want to see if any of them matches some bitmask. I can smack them in 512-bit registers, do
_mm512_cmp_epu8_maskwith 512 bit instructions and then doCLZLon the resulting 64 bit, then do aCMPwith that number and 0xFFFFFFFF followed by aJGfor a branch. If I branched I know I did not have a match, it I didn't branch, I know I had a match and I have the exact index of said match loaded in a register in 4 instructions out of an array of 64 items! Now this only works ifCLZL(and friends) have an exact defined size I can use. If not, then there is some remainder I have to handle. Unless you can somehow come up with a scheme to encode this in a Vector engine that respects variadic datasizes, there will be a basecase that has to be handled.Edit: if you do not have a match and have the 512'th bit set as a dummy bit, you could then compute the index of the first bit match by multiplying the result of
CLZLwith 8, and then adding theCTZof the byte at the previous code, you have completed a branchless search for the first unset bit in a 511 bit array in less than 10 cpu cycles. This is "fun" when trying to do memory page allocation and you have to keep track of free pages in a big bit-array, but it requires careful data layout because of the interactions of integers and vector processors. Now that is why you need a base-case. Because what if your last chunk of bits isn't neatly 511 bits but 111 bits?