Hacker News Reader

Comment by daniel-cussen | Hacker News Reader

Shuffle is the SIMD's killer app. It's apparently an interesting but expensive circuit, but it's smart to prioritize it. Absolute best instruction, hands down. So double-pumping yes isn't full speed meaning single cycle, but that increases the compatibility with AVX512 code. I guess if a program executed itself as a function of its runtime from CPUID it might not, and of course there's all kinds of...but for pedestrian purposes, meaning everything on github, it's a step. Hey 40% speedup on Cinebench, that's buen.

View on HN

> Shuffle is the SIMD's killer app

A shame that AVX512 only has pshufb (aka: permute), and is missing the GPU-instruction "bpermute", aka backwards permute.

pshufb is effectively a "gather" instruction over a AVX register. Equivalent to GPU permutes.

bpermute, in GPU land, is a "scatter" instruction over a vector register. There's no CPU / AVX equivalent of it. But I keep coming up with good uses of the bpermute instruction (much like pshufb is crazy flexible, its inverse, the backwards permute, is also crazy flexible).

--------

Almost any code that's finding itself "gathering" data across a vector register, will inevitably "scatter" the data back at some point.

Much like how "pext" is the "gather" instruction for 64-bits, you need pdep to handle the equal-and-opposite case. Its incredibly silly that AVX / AVX512 has implemented only one-half of this concept (gather / pshufb / aka Permute).

I wish for the day that Intel/AMD implements (scatter / backwards-pshufb / aka Backwards-Permute).

-------

Fortunately, I got Vega64 and NVidia Graphics Cards with both permute and bpermute instructions for high-speed shuffling of data. But CPU-space should benefit from this concept too.

OK that's cool, didn't know about bpermute. Made sense there should be a counterpart. Well when you only have pshufb, it works OK, yeah there's tons of gaps but if you're clever and...and if you compromise speed...thanks for telling me about bpermute!

Why do you say shuffle is “SIMD’s killer app”? I’ve only dabbled in vector instructions from a learning perspective, and seen others mention it’s important too, but have yet to understand why.

Because you can do things using bitmasks and single instructions instead of brute forcing using multiple instructions.

Let's say you have a whole heap of 8-bit numbers you want to multiply by 2 and you have a set of 256-bit registers and a nice SIMD multiply command. If you don't have a shuffle you need to assemble your series of 2s for the second operand for each lane before you can even start. This is going to take hundreds of instructions and hundreds of clocks. Shuffle means you load up lane 0 with the "2" and then splat the contents of lane 0 across the other 31 lanes in two instructions and a few clocks using the shuffle unit.

N.B. Shuffle isn't just about splatting. There's a whole heap of different operations it can do that are useful. I just picked a simple example with an obvious massive performance increase for illustrative purposes.

I think that example is too simple to show the benefit of shuffle. It's like explaining the benefit of an adder by showing how you can move a value with X = Y + 0. Especially since there's also a (much simpler) piece of hardware dedicated to ultra-fast splat/broadcast (under the right conditions).

You're not talking about shuffle, you're talking about broadcast. Shuffle instructions is where you take one or two vectors, and output a third with elements from any index of the input. So for example `out = [in[2], in[1]]` is a shuffle of a vector of length 2.

It's useful for example if you have say RGB color data stored contiguously in memory as say RGBRGBRGBRGB..., and you want to vectorize operations on R, B and G separately. You can load a few registers like [RGBR][GBRG][BRGB], and then shuffle them to [RRRR][BBBB][GGGG]. In fact it's not entirely trivial how to shuffle optimally, it takes a few shuffles to get there.

More generally, if you have an array of structs, you often need to go to struct of arrays to do vectorized operations on the array, before returning to an array of struct again.

Another example is fast matrix transpose (in fact you can think of the RGB example a 3 by N matrix transpose to N by 3, where N is the vector width -- AoS -> SoA is a transpose too, in a sense). Suppose you have a matrix of size N by N where N is the vector width, you need N lg N shuffles to transpose the matrix.

It's basically several moves for the price of one. Given that you operate on multiple values at once, being able to shuffle or duplicate values comes up all the time.

For example if you're filtering four image lines at a time using a 1D filter kernel, you'll want to replicate the filter coefficient to each SIMD element, so that you can multiply each of the four pixel values with the same coefficient. Shuffle lets you replicate a single coefficient value into all the elements of a register in one instruction.

Which is the point of SIMD. Several moves for the price of one.

This Rust issue [0] was the best short summary of what an SIMD Shuffle is I could find:

„A "shuffle", in SIMD terms, takes a SIMD vector (or possibly two vectors) and a pattern of source lane indexes (usually as an immediate), and then produces a new SIMD vector where the output is the source lane values in the pattern given.“

[0] https://github.com/rust-lang/portable-simd/issues/11

I use PSHUFB to convert 24-bit RGB to 32-bit RGBX or BGRX. Without a shuffle instruction it'd be quite a bit harder.

Here is an overview of the usage of the shuffle instruction to speed up decompression in ClickHouse: https://habr.com/ru/company/yandex/blog/457612/

Reply on news.ycombinator.com