9 ms·

Fundamental flaws of SIMD ISAs (2021)

153 points by fanf2 2y ago

pkhuong 2y ago
There's more to SIMD than BLAS. https://branchfree.org/2024/06/09/a-draft-taxonomy-of-simd-usage/ https://branchfree.org/2024/06/09/a-draft-taxonomy-of-simd-u... .
- camel-cdr 2y ago
  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).
convolvatron 2y ago
i would certainly add lack of reductions ('horizontal' operations) and a more generalized model of communication to the list.
- adgjlsfhk1 2y ago
  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.
  - convolvatron 2y ago
    kinda? this is sort of a direct result of the 'vectors are just sliced registers' model. if i do a pairwise operation and divide my domain by 2 at each step, is the resulting vector sparse or dense? if its dense then I only really top out when i'm in the last log2slice steps.
    - sweetjuly 2y ago
      Yes, but this is not cheap for hardware. CPU designers love SIMD because it lets them just slap down ALUs in parallel and get 32x performance boosts. Reductions, however, are not entirely parallel and instead have a relatively huge gate depth. For example, suppose an add operation has a latency of one unit in some silicon process. To add reduce a 32 element vector, you'll have a five deep tree, which means your operation has a latency of five units. You can pipeline this, but you can't solve the fact that this operation has a 5x higher latency than the non-reduce operations.
      - adgjlsfhk1 2y ago
        for some, you can cheat a little (e.g. partial sum reduction), but then you don't get to share IP with the rest of your ALUs. I do really want to see what an optimal 32 wide reduction and circuit looks like. For integers, you pretty clearly can do much better than pairwise reduction. float sounds tricky
- dzaima 2y ago
  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.
TinkersW 2y ago
I write a lot of SIMD and I don't really agree with this.. Flaw1:fixed width I prefer fixed width as it makes the code simpler to write, size is known as compile time so we know the size of our structures. Swizzle algorithms are also customized based on the size. Flaw2:pipelining no CPU I care about is in order so mostly irrelevant, and even scalar instructions are pipelined Flaw3: tail handling I code with SIMD as the target, and have special containers that pad memory to SIMD width, no need to mask or run a scalar loop. I copy the last valid value into the remaining slots so it doesn't cause any branch divergence.
- aengelke 2y ago
  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.
freeone3000 2y ago
x86 SIMD suffers from register aliasing. xmm0 is actually the low-half of ymm0, so you need to explicitly tell the processor what your input type is to properly handle overflow and signing. Actual vectorized instructions don’t have this problem but you also can’t change it now.
pornel 2y ago
There are alternative universes where these wouldn't be a problem. For example, 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), then we could adjust SIMD width for existing binaries instead of waiting decades for a new baseline or multiversioning faff. 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.
- LegionMammal978 2y ago
  > 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.
  - winwang 2y ago
    Fun fact which I'm 50%(?) sure of: a single branch divergence for integer instructions on current nvidia GPUs won't hurt perf, because there are only 16 int32 lanes anyway.
  - pornel 2y ago
    CPUs are not good at branchy code either. Branch mispredictions cause costly pipeline stalls, so you have to make branches either predictable or use conditional moves. Trivially predictable branches are fast — but so are non-diverging warps on GPUs. Conditional moves and masked SIMD work pretty much exactly like on a GPU. Even if you have a branchy divide-and-conquer problem ideal for diverging threads, you'll get hit by a relatively high overhead of distributing work across threads, false sharing, and stalls from cache misses. My hot take is that GPUs will get more features to work better on traditionally-CPU-problems (e.g. AMD Shader Call proposal that helps processing unbalanced tree-structured data), and CPUs will be downgraded to being just a coprocessor for bootstrapping the GPU drivers.
gitroom 2y ago
Oh man, totally get the pain with compilers and SIMD tricks - the struggle's so real. Ever feel like keeping low level control is the only way stuff actually runs as smooth as you want, or am I just too stubborn to give abstractions a real shot?
sweetjuly 2y ago
Loop unrolling isn't really done because of pipelining but rather to amortize the cost of looping. Any modern out-of-order core will (on the happy path) schedule the operations identically whether you did one copy per loop or four. The only difference is the number of branches.
- Remnant44 2y ago
  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.
  - adgjlsfhk1 2y ago
    The part that's really weird is that on modern CPUs predicted branches are free iff they're sufficiently rare (<1 out of 8 instructions or so). but if you have too many, you will be bottlenecked on the branch since you aren't allowed to speculate past a 2nd (3rd on zen5 without hyperthreading?) branch.
    - dzaima 2y ago
      The limiting thing isn't necessarily speculating, but more just the number of branches per cycle, i.e. number of non-contiguous locations the processor has to query from L1 / uop cache (and which the branch predictor has to determine the location of). You get that limit with unconditional branches too.
      - gpderetta 2y ago
bob1029 2y ago
> Since the register size is fixed there is no way to scale the ISA to new levels of hardware parallelism without adding new instructions and registers. I look at SIMD as the same idea as any other aspect of the x86 instruction set. If you are directly interacting with it, you should probably have a good reason to be. I primarily interact with these primitives via types like Vector<T> in .NET's System.Numerics namespace. With the appropriate level of abstraction, you no longer have to worry about how wide the underlying architecture is, or if it even supports SIMD at all. I'd prefer to let someone who is paid a very fat salary by a F100 spend their full time job worrying about how to emit SIMD instructions for my program source.
timewizard 2y ago
> Another problem is that each new SIMD generation requires new instruction opcodes and encodings. It requires new opcodes. It does not strictly require new encodings. Several new encodings are legacy compatible and can encode previous generations vector instructions. > so the architecture must provide enough SIMD registers to avoid register spilling. Or the architecture allows memory operands. The great joy of basic x86 encoding is that you don't actually need to put things in registers to operate on them. > Usually you also need extra control logic before the loop. For instance if the array length is less than the SIMD register width, the main SIMD loop should be skipped. What do you want? No control overhead or the speed enabled by SIMD? This isn't a flaw. This is a necessary price to achieve the efficiency you do in the main loop.
- camel-cdr 2y ago
  > 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.
  - timewizard 2y ago
    > That's just spilling with fewer steps. Another way to say this is it's "more efficient." > The executed uops should be the same. And "more densely coded."
    - camel-cdr 2y ago
      hm, I was wondering how the density compares with x86 having more complex encodings in general. vaddps zmm1,zmm0,ZMMWORD PTR [r14] takes six bytes to encode: 62 d1 7c 48 58 0e In SVE and RVV a load+add takes 8 bytes to encode.
- dzaima 2y ago
  > 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)
lauriewired 2y ago
The three “flaws” that this post lists are exactly what the industry has been moving away from for the last decade. Arm’s SVE, and RISC-V’s vector extension are all vector-length-agnostic. RISC-V’s implementation is particularly nice, you only have to compile for one code path (unlike avx with the need for fat-binary else/if trees).
dragontamer 2y ago
1. Not a problem for GPUs. NVdia and AMD are both 32-wide or 1024-bit wide hard coded. AMD can swap to 64-wide mode for backwards compatibility to GCN. 1024-bit or 2048-bit seems to be the right values. Too wide and you get branch divergence issues, so it doesn't seem to make sense to go bigger. In contrast, the systems that have flexible widths have never taken off. It's seemingly much harder to design a programming language for a flexible width SIMD. 2. Not a problem for GPUs. It should be noted that kernels allocate custom amounts of registers: one kernel may use 56 registers, while another kernel might use 200 registers. All GPUs will run these two kernels simultaneously (256+ registers per CU or SM is commonly supported, so both 200+56 registers kernels can run together). 3. Not a problem for GPUs or really any SIMD in most cases. Tail handling is O(1) problem in general and not a significant contributor to code length, size, or benchmarks. Overall utilization issues are certainly a concern. But in my experience this is caused by branching most often. (Branching in GPUs is very inefficient and forces very low utilization).
- dzaima 2y ago
  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).
  - dragontamer 2y ago
    Note that AVX512 have per-lane execution masks so I'm not fully convinced that tail handling should even be a thing anymore. If(my lane is beyond the buffer) then (exec flag off, do not store my lane). Which in practice should be a simple vcompress instruction (AVX512 register) and maybe a move afterwards??? I admit that I'm not an AVX512 expert but it doesn't seem all that difficult with vcompress instructions + execmask.
dang 2y ago
Related: Three Fundamental Flaws of SIMD - https://news.ycombinator.com/item?id=28114934 https://news.ycombinator.com/item?id=28114934 - Aug 2021 (20 comments)
xphos 2y ago
Personally, I think load and increment address register in a single instruction is extremely valuable here. It's not quite the risc model but I think that it is actually pretty significant in avoiding a von nurmon bottleneck with simd (the irony in this statement) I found that a lot of the custom simd cores I've written for simply cannot issue instructions fast enough risvc. Or when they it's in quick bursts and than increments and loop controls that leave the engine idling for more than you'd like. Better dual issue helps but when you have seperate vector queue you are sending things to it's not that much to add increments into vloads and vstores
- codedokode 2y ago
  > 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) These operations can be executed in parallel, while with auto-incrementing you cannot do that.
codedokode 2y ago
I think that packed SIMD is better in almost every aspect and Vector SIMD is worse. With vector SIMD you don't know the register size beforehand and therefore have to maintain and increment counters, adding extra unnecessary instructions, reducing total performance. With packed SIMD you can issue several loads immediately without dependencies, and if you look at code examples, you can see that the x86 code is more dense and uses a sequence of unrolled SIMD instructions without any extra instructions which is more efficient. While RISC-V has 4 SIMD instructions and 4 instructions dealing with counters per loop iteration, i.e. it wastes 50% of command issue bandwidth and you cannot load next block until you increment the counter. The article mentions that you have to recompile packed SIMD code when a new architecture comes out. Is that really a problem? Open source software is recompiled every week anyway. You should just describe your operations in a high level language that gets compiled to assembly for all supported architectures. So as a conclusion, it seems that Vector SIMD is optimized for manually-written assembly and closed-source software while Packed SIMD is made for open-source software and compilers and is more efficient. Why RISC-V community prefers Vector architecture, I don't understand.
- LoganDark 2y ago
  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.
  - codedokode 2y ago
    Makes sense - writing or updating software is easier that designing or updating hardware. To illustrate: anyone can write software but not everyone has access to chip manufacturing fabs.
    - LoganDark 2y ago
      Atomic Semi may be looking to change that (...eventually)
- IshKebab 2y ago
stephencanon 2y ago
The basic problem with almost every "SIMD is flawed, we should have vector ISAs" article or post (including the granddaddy, "SIMD Instructions Considered Harmful"), is that they invariably use SAXPY or something else trivial where everything stays neatly in lane as their demonstration case. Of course vector ISAs look good when you show them off using a pure vector task. This is fundamentally unserious. There is an enormous quantity of SIMD code in the world that isn't SAXPY, and doesn't stay neatly in lane. Instead it's things like "base64 encode this data" or "unpack and deinterleave this 4:2:2 pixel data, apply a colorspace conversion as a 3x3 sparse matrix and gamma adjustment in 16Q12 fixed-point format, resize and rotate by 15˚ with three shear operations represented as a linear convolution with a sinc kernel per row," or "extract these fields from this JSON data". All of which _can totally be done_ with a well-designed vector ISA, but the comparison doesn't paint nearly as rosy of a picture. The reality is that you really want a mixture of ideas that come from fixed-width SIMD and ideas that come from the vector world (which is roughly what people actually shipping hardware have been steadily building over the last two decades, implementing more support for unaligned access, predication, etc, while the vector ISA crowd writes purist think pieces)
Someone 2y ago
> Since the register size is fixed there is no way to scale the ISA to new levels of hardware parallelism without adding new instructions and registers. I think there is a way: vary register size per CPU, but also add an instruction to retrieve register size. Then, code using the vector unit will sometimes have to dynamically allocate a buffer for intermediate values, but it would allow for software to run across CPUs with different vector lengths. Does anybody know whether any architecture does this?
thierry_src 2y ago
One of my worry about the presented ideas, and this is present in RISC-V vector ISA if I'm not mistaken, is that register-size-independent vector instructions have random execution times depending on hardware register width. I remember seeing presentations of extensions to AVX (during probably a supercomputing related event in Spain years ago ?) that some complex, matrix to matrix instructions could have data dependent execution time, in addition to possible hardware register size dependencies. In some contexts, and for overall security, this could be very problematic. Has this been discussed?
- dzaima 2y ago
  RISC-V does have a Zvkt extension that requires that the set of instructions useful for crypto have data-independent timing. (it includes requiring that shuffle timings are independent of table data, but allows timings to vary across different index inputs)

153 points by fanf2 2y ago

There's more to SIMD than BLAS. https://branchfree.org/2024/06/09/a-draft-taxonomy-of-simd-usage/ https://branchfree.org/2024/06/09/a-draft-taxonomy-of-simd-u... .

camel-cdr 2y ago
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).

convolvatron 2y ago

i would certainly add lack of reductions ('horizontal' operations) and a more generalized model of communication to the list.

adgjlsfhk1 2y ago
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.
- convolvatron 2y ago
  kinda? this is sort of a direct result of the 'vectors are just sliced registers' model. if i do a pairwise operation and divide my domain by 2 at each step, is the resulting vector sparse or dense? if its dense then I only really top out when i'm in the last log2slice steps.
  - sweetjuly 2y ago
    Yes, but this is not cheap for hardware. CPU designers love SIMD because it lets them just slap down ALUs in parallel and get 32x performance boosts. Reductions, however, are not entirely parallel and instead have a relatively huge gate depth. For example, suppose an add operation has a latency of one unit in some silicon process. To add reduce a 32 element vector, you'll have a five deep tree, which means your operation has a latency of five units. You can pipeline this, but you can't solve the fact that this operation has a 5x higher latency than the non-reduce operations.
    - adgjlsfhk1 2y ago
      for some, you can cheat a little (e.g. partial sum reduction), but then you don't get to share IP with the rest of your ALUs. I do really want to see what an optimal 32 wide reduction and circuit looks like. For integers, you pretty clearly can do much better than pairwise reduction. float sounds tricky
dzaima 2y ago
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.

TinkersW 2y ago

I write a lot of SIMD and I don't really agree with this.. Flaw1:fixed width I prefer fixed width as it makes the code simpler to write, size is known as compile time so we know the size of our structures. Swizzle algorithms are also customized based on the size. Flaw2:pipelining no CPU I care about is in order so mostly irrelevant, and even scalar instructions are pipelined Flaw3: tail handling I code with SIMD as the target, and have special containers that pad memory to SIMD width, no need to mask or run a scalar loop. I copy the last valid value into the remaining slots so it doesn't cause any branch divergence.

aengelke 2y ago
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.

freeone3000 2y ago

x86 SIMD suffers from register aliasing. xmm0 is actually the low-half of ymm0, so you need to explicitly tell the processor what your input type is to properly handle overflow and signing. Actual vectorized instructions don’t have this problem but you also can’t change it now.

pornel 2y ago

There are alternative universes where these wouldn't be a problem. For example, 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), then we could adjust SIMD width for existing binaries instead of waiting decades for a new baseline or multiversioning faff. 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.

LegionMammal978 2y ago
> 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.
- winwang 2y ago
  Fun fact which I'm 50%(?) sure of: a single branch divergence for integer instructions on current nvidia GPUs won't hurt perf, because there are only 16 int32 lanes anyway.
- pornel 2y ago
  CPUs are not good at branchy code either. Branch mispredictions cause costly pipeline stalls, so you have to make branches either predictable or use conditional moves. Trivially predictable branches are fast — but so are non-diverging warps on GPUs. Conditional moves and masked SIMD work pretty much exactly like on a GPU. Even if you have a branchy divide-and-conquer problem ideal for diverging threads, you'll get hit by a relatively high overhead of distributing work across threads, false sharing, and stalls from cache misses. My hot take is that GPUs will get more features to work better on traditionally-CPU-problems (e.g. AMD Shader Call proposal that helps processing unbalanced tree-structured data), and CPUs will be downgraded to being just a coprocessor for bootstrapping the GPU drivers.

gitroom 2y ago

Oh man, totally get the pain with compilers and SIMD tricks - the struggle's so real. Ever feel like keeping low level control is the only way stuff actually runs as smooth as you want, or am I just too stubborn to give abstractions a real shot?

sweetjuly 2y ago

Loop unrolling isn't really done because of pipelining but rather to amortize the cost of looping. Any modern out-of-order core will (on the happy path) schedule the operations identically whether you did one copy per loop or four. The only difference is the number of branches.

Remnant44 2y ago
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.
- adgjlsfhk1 2y ago
  The part that's really weird is that on modern CPUs predicted branches are free iff they're sufficiently rare (<1 out of 8 instructions or so). but if you have too many, you will be bottlenecked on the branch since you aren't allowed to speculate past a 2nd (3rd on zen5 without hyperthreading?) branch.
  - dzaima 2y ago
    The limiting thing isn't necessarily speculating, but more just the number of branches per cycle, i.e. number of non-contiguous locations the processor has to query from L1 / uop cache (and which the branch predictor has to determine the location of). You get that limit with unconditional branches too.
    - gpderetta 2y ago

bob1029 2y ago

> Since the register size is fixed there is no way to scale the ISA to new levels of hardware parallelism without adding new instructions and registers. I look at SIMD as the same idea as any other aspect of the x86 instruction set. If you are directly interacting with it, you should probably have a good reason to be. I primarily interact with these primitives via types like Vector<T> in .NET's System.Numerics namespace. With the appropriate level of abstraction, you no longer have to worry about how wide the underlying architecture is, or if it even supports SIMD at all. I'd prefer to let someone who is paid a very fat salary by a F100 spend their full time job worrying about how to emit SIMD instructions for my program source.

timewizard 2y ago

> Another problem is that each new SIMD generation requires new instruction opcodes and encodings. It requires new opcodes. It does not strictly require new encodings. Several new encodings are legacy compatible and can encode previous generations vector instructions. > so the architecture must provide enough SIMD registers to avoid register spilling. Or the architecture allows memory operands. The great joy of basic x86 encoding is that you don't actually need to put things in registers to operate on them. > Usually you also need extra control logic before the loop. For instance if the array length is less than the SIMD register width, the main SIMD loop should be skipped. What do you want? No control overhead or the speed enabled by SIMD? This isn't a flaw. This is a necessary price to achieve the efficiency you do in the main loop.

camel-cdr 2y ago
> 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.
- timewizard 2y ago
  > That's just spilling with fewer steps. Another way to say this is it's "more efficient." > The executed uops should be the same. And "more densely coded."
  - camel-cdr 2y ago
    hm, I was wondering how the density compares with x86 having more complex encodings in general. vaddps zmm1,zmm0,ZMMWORD PTR [r14] takes six bytes to encode: 62 d1 7c 48 58 0e In SVE and RVV a load+add takes 8 bytes to encode.
dzaima 2y ago
> 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)

lauriewired 2y ago

The three “flaws” that this post lists are exactly what the industry has been moving away from for the last decade. Arm’s SVE, and RISC-V’s vector extension are all vector-length-agnostic. RISC-V’s implementation is particularly nice, you only have to compile for one code path (unlike avx with the need for fat-binary else/if trees).

dragontamer 2y ago

1. Not a problem for GPUs. NVdia and AMD are both 32-wide or 1024-bit wide hard coded. AMD can swap to 64-wide mode for backwards compatibility to GCN. 1024-bit or 2048-bit seems to be the right values. Too wide and you get branch divergence issues, so it doesn't seem to make sense to go bigger. In contrast, the systems that have flexible widths have never taken off. It's seemingly much harder to design a programming language for a flexible width SIMD. 2. Not a problem for GPUs. It should be noted that kernels allocate custom amounts of registers: one kernel may use 56 registers, while another kernel might use 200 registers. All GPUs will run these two kernels simultaneously (256+ registers per CU or SM is commonly supported, so both 200+56 registers kernels can run together). 3. Not a problem for GPUs or really any SIMD in most cases. Tail handling is O(1) problem in general and not a significant contributor to code length, size, or benchmarks. Overall utilization issues are certainly a concern. But in my experience this is caused by branching most often. (Branching in GPUs is very inefficient and forces very low utilization).

dzaima 2y ago
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).
- dragontamer 2y ago
  Note that AVX512 have per-lane execution masks so I'm not fully convinced that tail handling should even be a thing anymore. If(my lane is beyond the buffer) then (exec flag off, do not store my lane). Which in practice should be a simple vcompress instruction (AVX512 register) and maybe a move afterwards??? I admit that I'm not an AVX512 expert but it doesn't seem all that difficult with vcompress instructions + execmask.

dang 2y ago

Related: Three Fundamental Flaws of SIMD - https://news.ycombinator.com/item?id=28114934 https://news.ycombinator.com/item?id=28114934 - Aug 2021 (20 comments)

xphos 2y ago

Personally, I think load and increment address register in a single instruction is extremely valuable here. It's not quite the risc model but I think that it is actually pretty significant in avoiding a von nurmon bottleneck with simd (the irony in this statement) I found that a lot of the custom simd cores I've written for simply cannot issue instructions fast enough risvc. Or when they it's in quick bursts and than increments and loop controls that leave the engine idling for more than you'd like. Better dual issue helps but when you have seperate vector queue you are sending things to it's not that much to add increments into vloads and vstores

codedokode 2y ago
> 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) These operations can be executed in parallel, while with auto-incrementing you cannot do that.

codedokode 2y ago

I think that packed SIMD is better in almost every aspect and Vector SIMD is worse. With vector SIMD you don't know the register size beforehand and therefore have to maintain and increment counters, adding extra unnecessary instructions, reducing total performance. With packed SIMD you can issue several loads immediately without dependencies, and if you look at code examples, you can see that the x86 code is more dense and uses a sequence of unrolled SIMD instructions without any extra instructions which is more efficient. While RISC-V has 4 SIMD instructions and 4 instructions dealing with counters per loop iteration, i.e. it wastes 50% of command issue bandwidth and you cannot load next block until you increment the counter. The article mentions that you have to recompile packed SIMD code when a new architecture comes out. Is that really a problem? Open source software is recompiled every week anyway. You should just describe your operations in a high level language that gets compiled to assembly for all supported architectures. So as a conclusion, it seems that Vector SIMD is optimized for manually-written assembly and closed-source software while Packed SIMD is made for open-source software and compilers and is more efficient. Why RISC-V community prefers Vector architecture, I don't understand.

LoganDark 2y ago
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.
- codedokode 2y ago
  Makes sense - writing or updating software is easier that designing or updating hardware. To illustrate: anyone can write software but not everyone has access to chip manufacturing fabs.
  - LoganDark 2y ago
    Atomic Semi may be looking to change that (...eventually)
IshKebab 2y ago

stephencanon 2y ago

The basic problem with almost every "SIMD is flawed, we should have vector ISAs" article or post (including the granddaddy, "SIMD Instructions Considered Harmful"), is that they invariably use SAXPY or something else trivial where everything stays neatly in lane as their demonstration case. Of course vector ISAs look good when you show them off using a pure vector task. This is fundamentally unserious. There is an enormous quantity of SIMD code in the world that isn't SAXPY, and doesn't stay neatly in lane. Instead it's things like "base64 encode this data" or "unpack and deinterleave this 4:2:2 pixel data, apply a colorspace conversion as a 3x3 sparse matrix and gamma adjustment in 16Q12 fixed-point format, resize and rotate by 15˚ with three shear operations represented as a linear convolution with a sinc kernel per row," or "extract these fields from this JSON data". All of which _can totally be done_ with a well-designed vector ISA, but the comparison doesn't paint nearly as rosy of a picture. The reality is that you really want a mixture of ideas that come from fixed-width SIMD and ideas that come from the vector world (which is roughly what people actually shipping hardware have been steadily building over the last two decades, implementing more support for unaligned access, predication, etc, while the vector ISA crowd writes purist think pieces)

Someone 2y ago

> Since the register size is fixed there is no way to scale the ISA to new levels of hardware parallelism without adding new instructions and registers. I think there is a way: vary register size per CPU, but also add an instruction to retrieve register size. Then, code using the vector unit will sometimes have to dynamically allocate a buffer for intermediate values, but it would allow for software to run across CPUs with different vector lengths. Does anybody know whether any architecture does this?

thierry_src 2y ago

One of my worry about the presented ideas, and this is present in RISC-V vector ISA if I'm not mistaken, is that register-size-independent vector instructions have random execution times depending on hardware register width. I remember seeing presentations of extensions to AVX (during probably a supercomputing related event in Spain years ago ?) that some complex, matrix to matrix instructions could have data dependent execution time, in addition to possible hardware register size dependencies. In some contexts, and for overall security, this could be very problematic. Has this been discussed?

dzaima 2y ago
RISC-V does have a Zvkt extension that requires that the set of instructions useful for crypto have data-independent timing. (it includes requiring that shuffle timings are independent of table data, but allows timings to vary across different index inputs)