CPU-Abstracted SIMD Is Bad

Many modern languages have a some way to do SIMD in such a way that is agnostic of the host ISA or CPU. This seems like a natural abstraction, given that compilers already abstract over CPUs features broadly. For example, Zig has:

fn simdAddAndReduce(x: @Vector(16, u8), y: @Vector(16, u8)) u32 {
    // Does a vectorized addition and reduction.
    // No ISA-specific intrinsics or instructions here!
    return @reduce(.Max, x + y);
}

While this looks nice in theory, in this post, I will make the case that, in the current day, such abstractions are not good enough to be justified over using ISA-specific compiler intrinsics, at least not in the context of a high performance library implementing vectorized algorithms.¹

SIMD Today

Modern applications SIMD look much different than in decades past. In the 90s, SIMD on commercial computers was concerned primarily with speeding up audio and visual software on inexpensive hardware. Image processing, for example, is a classic and straightfoward application of SIMD: something like a grayscale operation can be performed by doing simple vectorized math on chunks of pixels instead of single pixels.

However, the innovative SIMD algorithms of today are much more complicated than just performing math on chunks of numbers. One algorithm I consider a hallmark of modern SIMD is the Keiser-Lemire UTF-8 validation algorithm, which shows the application of SIMD in string processing.

How does the algorithm work? The core component is evident in what the authors call it: the lookup algorithm. A vectorized lookup is simply a function that does the following:

where $x$ is a vector of width $N$ and $\text{table}$ is a table of some (small) size that provides scalar values. On today's hardware, $\text{lookup}(x)$ can be achieved using tbl/vqtbl4q_u8 for ARM, or VPSHUFB/_mm256_shuffle_epi8 for x86_64.²

So how do we do $\text{lookup}(x)$ in a modern programming language with a hardware-agnostic SIMD abstraction? Many langauges cannot.³ At least, not unless $x$ is a compile-time constant. The reason why is because LLVM doesn't have an IR instruction for doing a dynamic vectorized lookup;⁴ it only has one for when $x$ is constant. In fact, much of the LLVM vector IR is outdated, and in my opinion, doesn't reflect well the modern capabilities of hardware.

The consequence of this is that LLVM languages also do not have dynamic vectorized lookup instructions. Furthermore, LLVM's autovectorizers are not good at recognizing when a dynamic lookup can be used, even in the most obvious cases. Thus, you will have a lot of trouble trying to implement the Keiser-Lemire lookup algorithm without using intrinsics in your favorite compiled language.

The point is that modern SIMD patterns have evolved past what LLVM is built to support.

Different SIMD Capabilities

The next big issue is that not all instruction set architectures have even remotely similar SIMD capabilities. For example, a common operation in SIMD algorithms is the movemask. On Intel's SSE instruction set, this is called PMOVMSKB. This instruction takes the high bit from each byte of the input vector and concatenates them into an integer.

movemask({ 0xFF, 0x00, 0xFF, 0xFF, 0xFF, 0x00, 0x00, 0xFF }) = 0b10011101

ARM Neon does not have a PMOVMSKB equivalent. Thus, any ISA-abstracted SIMD implementation is going to have to burn a lot of cycles to emulate it on ARM chips. You can read Langdale's blog post for details on this problem.

You might wonder, though: if we need PMOVMSKB on ARM, why not let a ISA-abstracted SIMD abstraction generate optimal code for us instead of writing it ourselves using intrinsics? The answer is that there are faster but semantically different alternatives to PMOVMSKB on ARM.

In this ARM community blog post, an approach to the movemask problem is presented. I won't go over the details, but essentially, ARM Neon has a very fast way to do this:

arm_movemask({ 0xFF, 0x00, 0xFF, 0xFF, 0xFF, 0x00, 0x00, 0xFF }) = 0xF00FFF0F

Instead of having one bit per lane as with PMOVMSKB, there are 4 bits per lane. Despite the fundamental layout difference, the way one might use this "movemask with multiplicity" is almost the exact same as the PMOVMSKB movemask.

This is just one example that highlights big a problem with abstracted SIMD: fast SIMD routines often take advantage of hardware- or ISA-specific facts, beyond what an optimizer can do a simple pass for.

Non-Uniform Behavior

The next quirk is that, even when two ISAs have similar instructions, they often have subtly different behavior that force an ISA-abstracted SIMD implementations to generate sub-optimal code to handle.

To illustrate this, let's go back to a previous section, with $\text{lookup}$ instructions. On ARM, this can be achieved with tbl, and on x86_64, this can be achieved with VPSHUFB. One good question to ask is: what happens when the lookup index $x_i$ goes out of bounds of the table? The maximum addressable slot in a table for tbl is 63, and for VPSHUFB it is 15. On Neon, out of bounds indices result in a zero being placed in the result vector. But for x86_64, it wraps around into the 4 bit range!

Thus, in order to achieve uniform behavior for an abstract "lookup" instruction, one must lower into machine instructions that attempt to correct the differences in behavior across ISAs, either choosing OOB to result in 0, modular behavior, or undefined behavior.

Conclusion

I hope these points helped illustrate my point that the current state of ISA-abstracted SIMD is not quite good enough for use in high performance libraries. I'm not saying that it is impossible for LLVM to get on par with using ISA-specific intrinsics, just that a lot of work would have to be done in order for that to be the case.

One thing I would at least like to see in LLVM is a way to perform lookups, and then perhaps a way to do movemasks. Then, a handful of modern SIMD algorithms could be ported over to LLVM IR and performance can be measured using those algorithms as references.

As always, if you have any questions, comments, or pushbacks about anything on this post, please send me an email at mail@dzfrias.dev!