Fundamental flaws of SIMD ISAs (2021)

In AVX-512 we have a platform that rewards the assembly language programmer like few platforms have since the 6502. I see people doing really clever things that are specific to the system and one level it is really cool but on another level it means SIMD is the domain of the specialist, Intel puts out press releases about the really great features they have for the national labs and for Facebook whereas the rest of us are 5-10 years behind the curve for SIMD adoption because the juice isn't worth the squeeze.

Just before libraries for training neural nets on GPUs became available I worked on a product that had a SIMD based neural network trainer that was written in hand-coded assembly. We were a generation behind in our AVX instructions so we gave up half of the performance we could have got, but that was the least of the challenges we had to overcome to get the product in front of customers. [1]

My software-centric view of Intel's problems is that they've been spending their customers and shareholders money to put features in chips that are fused off or might as well be fused off because they aren't widely supported in the industry. And that they didn't see this as a problem and neither did their enablers in the computing media and software industry. Just for example, Apple used to ship the MKL libraries which like a turbocharger for matrix math back when they were using Intel chips. For whatever reason, Microsoft did not do this with Windows and neither did most Linux distributions so "the rest of us" are stuck with a fraction of the performance that we paid for.

AMD did the right thing in introducing double pumped AVX-512 because at least assembly language wizards have some place where their code runs and the industry gets closer to the place where we can count on using an instruction set defined 12 years ago.

[1] If I'd been tasked with updating the to next generation I would have written a compiler (if I take that many derivatives by hand I'll get one wrong.) My boss would have ordered me not to, I would have done it anyway and not checked it in.

I have similar thoughts,

I don't understand the push for variable width SIMD. Possibly due to ignorance but I think it's an abstraction that can be specialized for different hardware so the similar tradeoffs between low level languages and high level languages apply. Since I already have to be aware of hardware level concepts such as 256bit shuffle not working across 128bit lanes and different instructions having very different performance characteristics on different CPUs I'm already knee deep in hardware specifics. While in general I like abstractions I've largely given up waiting for a 'sufficiently advanced compiler' that would properly auto-vectorize my code. I think AGI AI is more likely to happen sooner. At a guess it seems to be that SIMD code could work on GPUs but GPU code has different memory access costs so the code there would also be completely different.

So my view is either create a much better higher level SIMD abstraction model with a sufficiently advanced compiler that knows all the tricks or let me work closely at the hardware level.

As an outsider who doesn't really know what is going on it does worry me a bit that it appears that WASM is pushing for variable width SIMDs instead of supporting ISAs generally supported by CPUs. I guess it's a portability vs performance tradeoff - I worry that it may be difficult to make variable as performant as fixed width and would prefer to deal with portability by having alternative branches at code level.

  >> Finally, any software that wants to use the new instruction set needs to be rewritten (or at least recompiled). What is worse, software developers often have to target several SIMD generations, and add mechanisms to their programs that dynamically select the optimal code paths depending on which SIMD generation is supported.

> I code with SIMD as the target, and have special containers that pad memory to SIMD width...

I think this may be domain-specific. I help maintain several open-source audio libraries, and wind up being the one to review the patches when people contribute SIMD for some specific ISA, and I think without exception they always get the tail handling wrong. Due to other interactions it cannot always be avoided by padding. It can roughly double the complexity of the code [0], and requires a disproportionate amount of thinking time vs. the time the code spends running, but if you don't spend that thinking time you can get OOB reads or writes, and thus CVEs. Masked loads/stores are an improvement, but not universally available. I don't have a lot of concrete suggestions.

I also work with a lot of image/video SIMD, and this is just not a problem, because most operations happen on fixed block sizes, and padding buffers is easy and routine.

I agree I would have picked other things for the other two in my own top-3 list.

[0] Here is a fun one, which actually performs worst when len is a multiple of 8 (which it almost always is), and has 59 lines of code for tail handling vs. 33 lines for the main loop: https://gitlab.xiph.org/xiph/opus/-/blob/main/celt/arm/celt_...

I agree; and the article seems to have also quite a few technical flaws:

- Register width: we somewhat maxed out at 512 bits, with Intel going back to 256 bits for non-server CPUs. I don't see larger widths on the horizon (even if SVE theoretically supports up to 2048 bits, I don't know any implementation with ~~>256~~ >512 bits). Larger bit widths are not beneficial for most applications and the few applications that are (e.g., some HPC codes) are nowadays served by GPUs.

- The post mentions available opcode space: while opcode space is limited, a reasonably well-designed ISA (e.g., AArch64) has enough holes for extensions. Adding new instructions doesn't require ABI changes, and while adding new registers requires some kernel changes, this is well understood at this point.

- "What is worse, software developers often have to target several SIMD generations" -- no way around this, though, unless auto-vectorization becomes substantially better. Adjusting the register width is not the big problem when porting code, making better use of available instructions is.

- "The packed SIMD paradigm is that there is a 1:1 mapping between the register width and the execution unit width" -- no. E.g., AMD's Zen 4 does double pumping, and AVX was IIRC originally designed to support this as well (although Intel went directly for 256-bit units).

- "At the same time many SIMD operations are pipelined and require several clock cycles to complete" -- well, they are pipelined, but many SIMD instructions have the same latency as their scalar counterpart.

- "Consequently, loops have to be unrolled in order to avoid stalls and keep the pipeline busy." -- loop unroll has several benefits, mostly to reduce the overhead of the loop and to avoid data dependencies between loop iterations. Larger basic blocks are better for hardware as every branch, even if predicted correctly, has a small penalty. "Loop unrolling also increases register pressure" -- it does, but code that really requires >32 registers is extremely rare, so a good instruction scheduler in the compiler can avoid spilling.

In my experience, dynamic vector sizes make code slower, because they inhibit optimizations. E.g., spilling a dynamically sized vector is like a dynamic stack allocation with a dynamic offset. I don't think SVE delivered any large benefits, both in terms of performance (there's not much hardware with SVE to begin with...) and compiler support. RISC-V pushes further into this direction, we'll see how this turns out.

> I prefer fixed width

Another reason to prefer fixed width, compilers may pass vectors to functions in SIMD registers. When register size is unknown at compile time, they have to pass data in memory. For complicated SIMD algorithms the performance overhead gonna be huge.

> I prefer fixed width

Do you have examples for problems that are easier to solve in fixed-width SIMD?

I maintain that most problems can be solved in a vector-length-agnostic manner. Even if it's slightly more tricky, it's certainly easier than restructuring all of your memory allocations to add padding and implementing three versions for all the differently sized SIMD extensions your target may support. And you can always fall back to using a variable-width SIMD ISA in a fixed-width way, when necessary.

AFAIK about every modern CPU uses out of order von Neumann architecture. The only people who don't are the handful of researchers and people who work with the government research into non van Neumann designed systems.

These days, I strongly believe that loop unrolling is a pessimization, especially with SIMD code.

Scalar code should be unrolled by the compiler to the SIMD word width to expose potential parallelism. But other than that, correctly predicted branches are free, and so is loop instruction overhead on modern wide-dispatch processors. For example, even running a maximally efficient AVX512 kernel on a zen5 machine that dispatches 4 EUs and some load/stores and calculates 2048 bits in the vector units every cycle, you still have a ton of dispatch capacity to handle the loop overhead in the scalar units.

The cost of unrolling is decreased code density and reduced effectiveness of the instruction / uOp cache. I wish Clang in particular would stop unrolling the dang vector loops.

The looping overhead is trivial, especially on simd code where the loop overhead will use the scalar hardware.

Unrolling is definitely needed for properly scheduling and pipelining SIMD code even on OoO cores. Remember that an OoO core cannot reorder dependent instructions, so the dependencies need to be manually broken, for example by adding additional accumulators, which in turn requires additional unrolling, this is especially important on SIMD code which typically is non-branchy with long dependency chains.

> Any modern out-of-order core will (on the happy path) schedule the operations identically whether you did one copy per loop or four.

I cannot agree because in an unrolled loop you have less counter increment instructions.

Ok, but the compiler can't do that without unrolling.

> if we didn't settle on executing compiled machine code exactly as-is, and had a instruction-updating pass (less involved than a full VM byte code compilation)

Apple tried something like this: they collected the LLVM bitcode of apps so that they could recompile and even port to a different architecture. To my knowledge, this was done exactly once (watchOS armv7->AArch64) and deprecated afterwards. Retargeting at this level is inherently difficult (different ABIs, target-specific instructions, intrinsics, etc.). For the same target with a larger feature set, the problems are smaller, but so are the gains -- better SIMD usage would only come from the auto-vectorizer and a better instruction selector that uses different instructions. The expectable gains, however, are low for typical applications and for math-heavy programs, using optimized libraries or simply recompiling is easier.

WebAssembly is a higher-level, more portable bytecode, but performance levels are quite a bit behind natively compiled code.

> Another interesting alternative is SIMT. Instead of having a handful of special-case instructions combined with heavyweight software-switched threads, we could have had every instruction SIMDified. It requires structuring programs differently, but getting max performance out of current CPUs already requires SIMD + multicore + predictable branching, so we're doing it anyway, just in a roundabout way.

Is that not where we're already going with the GPGPU trend? The big catch with GPU programming is that many useful routines are irreducibly very branchy (or at least, to an extent that removing branches slows them down unacceptably), and every divergent branch throws out a huge chunk of the GPU's performance. So you retain a traditional CPU to run all your branchy code, but you run into memory-bandwidth woes between the CPU and GPU.

It's generally the exception instead of the rule when you have a big block of data elements upfront that can all be handled uniformly with no branching. These usually have to do with graphics, physical simulation, etc., which is why the SIMT model was popularized by GPUs.

hm. Doesn't the existence of Vulkan subgroups and CUDA shuffle/ballot poke huge holes in their 'SIMT' model? From where I sit, that looks a lot like SIMD. The only difference seems to be that SIMT professes to hide (or use HW support for) divergence. Apart from that, reductions and shuffles are basically SIMD.

> There are alternative universes where these wouldn't be a problem

Do people that say these things have literally any experience of merit?

> For example, if we didn't settle on executing compiled machine code exactly as-is, and had a instruction-updating pass

You do understand that at the end of the day, hardware is hard (fixed) and software is soft (malleable) right? There will be always be friction at some boundary - it doesn't matter where you hide the rigidity of a literal rock, you eventually reach a point where you cannot reconfigure something that you would like to. And also the parts of that rock that are useful are extremely expensive (so no one is adding instruction-updating pass silicon just because it would be convenient). That's just physics - the rock is very small but fully baked.

> we could have had every instruction SIMDified

Tell me you don't program GPUs without telling me. Not only is SIMT a literal lie today (cf warp level primitives), there is absolutely no reason to SIMDify all instructions (and you better be a wise user of your scalar registers and scalar instructions if you want fast GPU code).

I wish people would just realize there's no grand paradigm shift that's coming that will save them from the difficult work of actually learning how the device works in order to be able to use it efficiently.

> load and increment address register in a single instruction is extremely valuable here

I think this is not important anymore because modern architectures allow to add offset to register value so you can write something like, using weird RISC-V syntax for addition:

    ld r2, 0(r1)
    ld r3, 4(r1)
    ld r4, 8(r1)

BLAS, specifically gemm, is one of the rare things where you naturally need to specialize on vector register width.

Most problems don't require this: E.g. your basic penalizable math stuff, unicode conversion, base64 de/encode, json parsing, set intersection, quicksort*, bigint, run length encoding, chacha20, ...

And if you run into a problem that benefits from knowing the SIMD width, then just specialize on it. You can totally use variable-length SIMD ISA's in a fixed-length way when required. But most of the time it isn't required, and you have code that easily scales between vector lengths.

*quicksort: most time is spent partitioning, which is vector length agnostic, you can handle the leafs in a vector length agnostic way, but you'll get more efficient code if you specialize (idk how big the impact is, in vreg bitonic sort is quite efficient).

> Open source software is recompiled every week anyway.

Despite being potentially compiled recently, anything from most Linux package managers, and whatever precompiled downloadable executables, even if from open-source code, still targets the 20-year-old SSE2 baseline, wasting the majority of SIMD resources available on modern (..or just not-extremely-ancient) CPUs (unless you're looking at the 0.001% of software that bothers with dynamic dispatch; but for that approach just recompiling isn't enough, you also need to extend the dispatched target set).

RISC-V RVV's LMUL means that you get unrolling for free, as each instruction can operate over up to 8 registers per operand, i.e. essentially "hardware 8x unrolling", thereby making scalar overhead insignificant. (probably a minor nightmare from the silicon POV, but perhaps not in a particularly limiting way - double-pumping has been done by x86 many times so LMUL=2 is simple enough, and at LMUL=4 and LMUL=8 you can afford to decode/split into ups at 1 instr/cycle)

ARM SVE can encode adding a multiple of VL in load/store instructions, allowing manual unrolling without having to actually compute the intermediate sizes. (hardware-wise that's an extremely tiny amount of overhead, as it's trivially mappable to an immediate offset at decode time). And there's an instruction to bump a variable by a multiple of VL.

And you need to bump pointers in any SIMD regardless; the only difference is whether the bump size is an immediate, or a dynamic value, and if you control the ISA you can balance between the two as necessary. The packed SIMD approach isn't "free" either - you need hardware support for immediate offsets in SIMD load/store instrs.

Even in a hypothetical non-existent bad vector SIMD ISA without any applicable free offsetting in loads/stores and a need for unrolling, you can avoid having a dependency between unrolled iterations by precomputing "vlen*2", "vlen*3", "vlen*4", ... outside of the loop and adding those as necessary, instead of having a strict dependency chain.

Those 4 counter instructions have no dependencies though so they'll likely all be issued and executed in parallel in 1 cycle, surely? Probably the branch as well in fact.

This comment sort of reminds me of how Transmeta CPUs relied on the compiler to precompute everything like pipelining. It wasn't done by the hardware.

Tail handling is not significant for loops with tons of iterations, but there are a ton of real-world situations where you might have a loop take only like 5 iterations or something (even at like 100 iterations, with a loop processing 8 elements at a time (i.e. 256-bit vectors, 32-bit elements), that's 12 vectorized iterations plus up to 7 scalar ones, which is still quite significant. At 1000 iterations you could still have the scalar tail be a couple percent; and still doubling the L1/uop-cache space the loop takes).

It's absolutely a significant contributor to code size (..in scenarios where vectorized code in general is a significant contributor to code size, which admittedly is only very-specialized software).

> The great joy of basic x86 encoding is that you don't actually need to put things in registers to operate on them.

That's... 1 register saved, out of 16 (or 32 on AVX-512). Perhaps useful sometimes, but far from a particularly significant aspect spill-wise.

And doing that means you lose the ability to move the load earlier (perhaps not too significant on OoO hardware, but still a consideration; while reorder windows are multiple hundreds of instructions, the actual OoO limit is scheduling queues, which are frequently under a hundred entries, i.e. a couple dozen cycles worth of instructions, at which point the ≥4 cycle latency of a load is not actually insignificant. And putting the load directly in the arith op is the worst-case scenario for this)

> The great joy of basic x86 encoding is that you don't actually need to put things in registers to operate on them.

That's just spilling with fewer steps. The executed uops should be the same.

ARM NEON does have sum, min, and max reductions (and/or reductions can just be min/max if all bits in elements are the same), along with pairwise ops. RVV has sum,min,max,and,or,xor reductions. x86 has psadbw which sums windows of eight 8-bit ints, and various instructions for some pairwise horizontal stuff.

But in general building code around reductions isn't really a thing you'd ideally do; they're necessarily gonna have higher latency / lower throughput / take more silicon compared to avoiding them where possible, best to leave reducing to a single element to the loop tail.

The tricky part with reductions is that they are somewhat inherently slow since they often need to be done pairwise and a pairwise reduction over 16 elements will naturally have pretty limited parallelism.