8 ms·
Flavors of SIMD
- svantana 8y agoI find that modern c++ compilers can do a pretty good job of auto-vectorization, given that the code is "vector-friendly" to begin with. But writing code in that style is a bit of black magic with lots of trial and error. I wish compiler vendors would publish "style guides" for this purpose, or at least a collection of best practices.
- gameswithgo 8y agoLeveraging auto vectorization can be nice, as you can compile for different targets with one set of code, and not have to write out intrinsics for SSE2, AVX2, AVX512 etc. But yeah it is tricky, you might get it all sorted and a compiler upgrade ruins it, or it won't work on another compiler, or someone updates your function later not realizing you carefully tuned it to get vectorized and it ruins it. Also there are some clever hacks you can do with intrinsics that compilers won't figure out sometimes. I made a library in Rust that will let you write a single function using abstracted intrinsics, that can produce SSE2/SSE41/AVX2 versions at compile time: https://github.com/jackmott/simdeez https://github.com/jackmott/simdeez
- Asooka 8y agoSeems to me like it would be a good idea to have a tool (superoptimiser?) that can take your simple code and rewrite it with intrinsics, which you then check into source control. So you have a doFooGeneric and have the tool generate doFooSSE, doFooSSE4, doFooAVX2, doFooNEON and select one at runtime (like Intel's compiler does) or at compile time. Since you'll only run the tool infrequently, it can spend a lot of time trying to find the best vectorisation.
- colejohnson66 8y agoSide note: GCC supports feature based dispatch too[0] [0]: https://lwn.net/Articles/691932/ https://lwn.net/Articles/691932/
- gnufx 8y agoYes, but target_clones, at least, isn't a panacea. If you know how to make it work in a shared library, I'm rather interested.
- gameswithgo 8y agoanother Rust library "Faster" attempts to do that. Its cool, but the downside is simple code can't always translate optimally to intrinsics. Like if you ask for a "floor" operation for instance. With SSE2 you have no floor operation. So you either can do a floor one at a time, or use some clever combinations of other SSE2 intrinsics to do a floor, or, if you can accept certain constraints, you can use a faster option using less intrinsics. So your simple code needs to specify which you want, which ends up being kind of like intrinsics. Also your simple code has to line everything up in arrays anyway so intrinsics don't add that much complexity. I do overload operators in SIMDeez so some of the time your code can look pretty simple.
- stochastic_monk 8y agoI have a similar project in C++ supporting SSE2,AVX2, and AVX512 here: https://github.com/dnbaker/vec https://github.com/dnbaker/vec. I've used it for numerical code and sketch data structures, for example. (See https://github.com/dnbaker/frp https://github.com/dnbaker/frp or https://github.com/dnbaker/sketch https://github.com/dnbaker/sketch, respectively). Most of the work I do, the compiler just isn't able to vectorize, so I just write intrinsics. I similarly wrapped FFTW and the Sleef trigonometric function library so that I can generate optimal code for a variety of types and architectures.
- microcolonel 8y ago> But writing code in that style is a bit of black magic with lots of trial and error. I wish compiler vendors would publish "style guides" for this purpose, or at least a collection of best practices. I think that would be more difficult than teaching developers to look at the generated code sometimes. At least some JavaScript developers do this, so I don't see why C++ developers can't.
- planteen 8y agoI think C++ developers do this a lot. I often see links to godbolt.org on Stack Overflow and Bjarne himself on YouTube videos. The tricky part is the are a number of different valid march flags for x86 and ARM that support SIMD.
- microcolonel 8y ago> The tricky part is the are a number of different valid march flags for x86 and ARM that support SIMD. Sure, but if you're writing software which works on AMD64, you can see prettymuch every autovectorization opportunity that exists on other platforms. Most of the autovectorizer functionality in gcc and clang is platform-agnostic, AFAIK.
- planteen 8y agoYes you can see the broad opportunity but various things can easily break vectorization between extensions of x86 and ARM. The first that comes to mind is use of doubles instead of floats. Another is too wide of an inner loop, especially on algorithms that must be tuned for cache line sizes. You can also run into accuracy & stability issues between different x86 instruction extensions - it's really a nightmare to debug those.
- Something1234 8y agoIsn't the best flag `-march=native`? It gives you all the vectorization that your processor supports, or at least I think that's the case? At least if you don't have to provide builds for other people's machines.
- wyldfire 8y agoFWIW clang has a feature called opt-viewer [1] [2] that isn't quite a style guide but instead gives explicit indication when and why it couldn't optimize particular code. [1] https://llvm.org/devmtg/2016-11/Slides/Nemet-Compiler-assistedPerformanceAnalysis.pdf https://llvm.org/devmtg/2016-11/Slides/Nemet-Compiler-assist... [2] https://github.com/androm3da/optviewer-demo https://github.com/androm3da/optviewer-demo
- IshKebab 8y agoUseful, thanks! God knows why they chose YAML though...
- jancsika 8y agoIf a failure of auto-vectorization in a hot code path decreases performance enough for the user to perceive it as a bug, then it seems like explicitly maintaining SIMD/NEON code-paths would be preferable to dealing with auto-vectorization black magic. But I've never done either.
- gnufx 8y agoVectorization failures (where vectorization would be correct) should be reported as a bug. Note that GCC has some parameters to tune vectorization about from forcing it with pragmas.
- slack3r 8y agoIt may be black magic now, but people are working on making the black magic something lesser mortals don't have to worry about (eg: https://theory.stanford.edu/~aiken/publications/papers/asplos06.pdf https://theory.stanford.edu/~aiken/publications/papers/asplo...) Unfortunately, no one is actually paying attention to all this research being done in ivory tower academics. Sad!
- jcranmer 8y agoSuperoptimization is slow, and it's generally considered feasible only for shortish bits of code. A block of about 30 instructions takes around 10 minutes to superoptimize even on state-of-the-art stochastic superoptimizers. You also need correct semantics for instructions. Go read the PCMPISTRI instruction and try to write out the SMT formulas for it so you can prove equivalence. Floating point is in an even worse state, since most interesting floating point transformations are only legal if you're willing to slacken requirements for bit-equivalence. Superoptimization is not mature enough to become part of the regular compiler flow. What is happening is you're seeing people couple superoptimizers to find missing optimizations in the compiler--John Regehr is basically doing this for LLVM's InstCombine pass with Souper.
- slack3r 8y agoLol, my comment was restricted to SIMD, which definitely does not take 10 minutes. Secondly, no mainstream compiler actually compiles code to the PCMPISTRI instruction. Presumably it was meant to be used directly as assembly. I'm not sure why you are bringing in this obscure instruction into the discussion of superoptimizers. I personally have a paranoid fantasy where NSA/GCHQ introduced this instruction to speed up password cracking. :D
- jcranmer 8y agoYou're citing the classic superoptimization paper, although it's actually quite old at this point. The goal of superoptimization has always been to try to compile to the no-real-C-equivalent instructions in an ISA, which includes the weird vector instructions such as PCMPISTRI. (I believe Strata attempted to match some of these instructions, and I think they managed to get formulas for about half of the weird immediate forms--these are the instructions that caused them to match "half" an instruction). In any practical vectorized tight inner-loop, the block you're trying to optimize is inherently going to be large. Superoptimization is exponential in the size of the block being optimized, which limits its utility. That was my entire point: it becomes unacceptably expensive way too quickly to get used in compilers. (Some of the code I'm looking at right now has 100s of instructions in a single basic block, definitely not atypical for a compiler).
- abainbridge 8y agoHmmm, I feel like I've been waiting for a compiler to get clever enough to auto-vectorize my code since MMX was new. It never seems to happen. I guess I need that style guide. For example, here's a hello-world type SIMD problem: auto-vectorize a simple alpha blending pixel painting routine. struct Pixel { unsigned char r, g, b, a; }; // Draw a horizontal row of alpha blended pixels into a scan line. // Assume clipping is already done. void hline(Pixel *scanline, int startIdx, int len, Pixel c) { len &= 0xfff0; // Let the compiler assume that the length is always a multiple of 4. int invAlpha = 255 - c.a; for (int i = 0; i < len; i+=4) { Pixel &dest = scanline[startIdx + i]; dest.r = (dest.r * invAlpha + c.r * c.a) >> 8; dest.g = (dest.g * invAlpha + c.g * c.a) >> 8; dest.b = (dest.b * invAlpha + c.b * c.a) >> 8; } } And here is GCC 8 _not_ auto-vectorizing it: https://godbolt.org/z/zPZL-J https://godbolt.org/z/zPZL-J Is this the kind of thing you think should be auto-vectorizable by the compiler? If so, any idea how to persuade the compiler to do it?
- tomsmeding 8y agoTo properly auto-vectorise this, you need to transform your ArrayOfStructures (AoS) representation to a StructureOfArrays (SoA) form, i.e. put all the r's next to each other, all the g's, etc. Then your operations are nicely in groups of four adjacent elements and the compiler will almost surely vectorise it. I'm no black magician, but I think the fact that the operations you want to do in parallel (the r's of four adjacent pixels) do not access adjacent memory cells, requiring a gather instruction or somesuch, which I hear is either slow or unsupported. Alternatively, it could vectorise the pixels themselves, but that's three elements, not four. Does it auto-vectorise it if you also do the operation on the a's?
- abainbridge 8y ago> Does it auto-vectorise it if you also do the operation on the a's? Good point. Combined with fixing my loop increment (that jcranmer made me realize was wrong), I now get some vectory goodness: https://godbolt.org/z/yTJzKH https://godbolt.org/z/yTJzKH No idea what it all means. It'll be interesting to benchmark.
- wmu 8y agoRecently I checked how different compilers vectorize various C++ standard algorithms: http://0x80.pl/notesen/2019-02-02-autovectorization-gcc-clang.html http://0x80.pl/notesen/2019-02-02-autovectorization-gcc-clan... You'll also find there a hint how to rewrite std::replace algorithm to make it vectorizable.
- leeter 8y agoA few thoughts: * This might be a good candidate for a compute shader, the swizzle abilities of shaders make quite a few of the things they are doing much easier as does the faster memory connections GPUs (usually) have. * The committee is actually looking at potential ways to handle this http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2018/p1101r0.html http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2018/p110... has been proposed. There is also a lot of discussion about support for GPUs in a standard way, but I haven't seen any proposals myself.
- gameswithgo 8y agoiirc the domain this guy is working in, is one where the GPU is going to be busy with rendering, so he may prefer to keep this on the cpu. But you are right that any time you turn to SIMD, you might be able to turn to the GPU and get a much biggger win.
- leeter 8y agoSo what I'm somewhat curious about is if this isn't an argument for heterogeneous GPU usage. Schedule this on an iGPU while the main GPU is busy. The main downside, as I alluded to above, would be memory bandwidth unless there is a good on die cache for the iGPU or it has dedicated memory. That said with a multi-gpu setup you might also have another card you could use. The other thought I have is that it's very difficult to keep the GPU 100% saturated in my experience. If the vertex count is high enough to make the PCI-e transition worth it (and it would seem to be), then you can potentially cycle steal a bit on the main GPU. This will potentially slow down the main render but speed up the overall. This would be particularly true if you can rebind the resource back for use in the main render pipe.
- gameswithgo 8y agoAll ideas that can work in certain situtions. As GPUs get more like CPUs and CPUs get more like GPUs things will just get fuzzier I imagine.
- dragontamer 8y ago
- BooneJS 8y ago> unfortunately, the use of SIMD can make the code less portable and less maintainable Unfortunately general purpose processors aren’t getting any faster, but they are getting more specialized. At some point in the future package managers for OSS May have to do LLVM compilation on the machine just to specifically target the bits and baubles of the specific architecture it’s running on.
- gameswithgo 8y agoAOT compilation on install! the best of AOT and JIT worlds! Android does this already.
- pjmlp 8y agoYour information is bit outdated regarding Android. Android did AOT on install between 5 and 7 versions. With Android 7, they introduced a mixed model, of an hand written interpreter in Assembly, JIT compiler with PGO, followed by AOT compilation with PGO data when the device is idle. As extra information, AOT on install for mobile phones, was introduced on Windows Phone 8, and has been available in mainframes and some Pascal USCD systems since the early 80's.
- pjmlp 8y agoAs neighboring comment states, a common feature in Android, and in all managed languages with JIT/AOT toolchains.
- dragontamer 8y agoGood GPU (SIMD) code is written in a very, very different manner than good CPU code. Case in point: NVidia has 32 x 32-bit shaders per L1 cache / Shared Memory (a Symmetric Multiprocessor, or SM). Each SM can run 32-warps at a time, for an effective 1024 "shader threads" per L1 cache. In contrast: CPUs have 1-core, with 2-way SMT. That's 2-threads per L1 cache. IBM has a Power9 CPU with 8-way SMT for 8-threads on one core, but that's as far as you get with traditional CPUs. Effectively: GPUs are memory-constrained. Not memory-bandwidth constrained btw (GPUs have a TON of bandwidth), but literally memory constrained. Each shader only has ~500 bytes, probably less, that it can access efficiently (more if you have "uniform" data that can be shared between shaders). And maybe 2MB total per shader before you run out of RAM entirely. --------- GPU code is innately parallel, so any memory allocation you do is multiplied by a thousand fold, or more. Vega64 needs at least 16384 work-items before it has occupancy 1 per vALU (64 compute units, 4 work queues per compute unit, 64 vALUs per queue)... and needs x10 work-items for max occupancy (a total of 163840 work-items in flight). If you have max occupancy 10 and allocate 16-bytes per work-item, and you just allocated 2.6MB of data on the GPU. I'm not kidding. You run out of space very quickly on GPUs. While GPUs struggle with this multiplicative problem per work-item, CPUs have a ton of memory. That's 32kB of L1 cache typically available per thread (64kB per core, but typically you have two threads per core thanks to Hyperthreading). That's the core of GPU vs CPU programming IMO. Dealing with the grossly constrained memory conditions of the GPU environment.
- dragontamer 8y agoSome thoughts on my experiments with SIMD Programming: 1. AVX2 is good, but tedious to use manually. The difficulty problem with AVX2 is that it is SIMD of SIMD: Its 2-way SIMD of 128-bit. Going "across" the lanes of the 128-bit bunches can only be done with rare instructions... or through L1 cache (write to memory, then read back in another register). 2. "#pragma OpenMP SIMD" seems to be the most portable way to attempt to "force" autovectorization. Its compatible across GCC, CLang, and ICC, and other compilers. Visual Studio unfortunately does NOT support this feature, but VSC++ has well documented auto-vectorization features. 3. If you are sticking to Visual C++, its auto-vectorization capabilities are pretty good. Enable compiler warnings so that you know which loops fail to auto-vectorize. Be sure to read those warnings carefully. https://docs.microsoft.com/en-us/cpp/parallel/auto-parallelization-and-auto-vectorization?view=vs-2017 https://docs.microsoft.com/en-us/cpp/parallel/auto-paralleli... 4. If you keep reaching for the SIMD button, the GPU Programming model seems superior. If you must use a CPU, try the ISPC: Intel's SPMD Program Compiler (https://ispc.github.io/ https://ispc.github.io/) so that your "programming model" is at least correct. 5. If a huge portion of your code is SIMD-style, a dedicated GPU is better. GPUs have more flops and memory bandwidth. GPUs have faster local memory (aka "shared memory" on NVidia, or "LDS" on AMD) and faster thread-group communications than a CPU. Know how amazing vpshufb is? Well, GPUs will knock your socks off with ballot(), CUDA __shfl(), AMD Cross-lane operations and more (https://gpuopen.com/amd-gcn-assembly-cross-lane-operations/ https://gpuopen.com/amd-gcn-assembly-cross-lane-operations/). 6. To elaborate on point #5: GPUs simply have better gather/scatter capabilities. The GPU's "shared" or "LDS" memory (just 64kB or so) is very small, but provides arbitrary gather/scatter capabilities across "lanes" of GPU SIMD units. They even support relatively efficient atomic operations. Yes, even vpshufb seems relatively limited compared to what is available on GPUs. 7. Raw AVX2 assembly seems "easy" if what you need is a 128-bit or 256-bit register. For example, if you are writing Complex-Doubles (real+imaginary number), then it is very straightforward to write 128-bit SIMD code to handle your arithmetic. But if you are writing "true SIMD" code, such as the style in the 1986 Seminal Paper "Data Parallel Algorithms" (https://dl.acm.org/citation.cfm?id=7903 https://dl.acm.org/citation.cfm?id=7903), then stick with ISPC or GPU-style coding instead. 8. Be sure to read that paper: "Data Parallel Algorithms" to get insight into true SIMD Programming. GPU programmers already know what is in there, but its still cool to read one of the first papers on the subject (in 1986 nonetheless!)
- Const-me 8y ago> It’s not immediately clear how to make this use SIMD… unless you use gathers. Gathers are slow. With SSE2, you only need 2 instructions to check for duplicate indices. First _mm_shuffle_epi32 to “rotate” the triangle [a,b,c] into e.g. [b,c,a], second _mm_cmpeq_epi32 to do per-lane comparison between the original and rotated. Similarly, with AVX2, same approach can be used to check 2 triangles at once. For best result, unroll the loop into batches of 4 triangles (8 for AVX), and use 128/256 bit loads.
- microtherion 8y agoOne option which I have not seen mentioned here yet is to use a platform independent API with a platform optimized implementation. i.e. if your operations can be expressed in terms of BLAS primitives, then ATLAS can give you a good part of the benefit of hand optimized code, without much of the hassle: http://math-atlas.sourceforge.net http://math-atlas.sourceforge.net
- gnufx 8y agoYes, that's important for portable performance, but not with ATLAS. Unless it's improved since I last tried, it's generally slower than OpenBLAS (or BLIS, by extension) and doesn't do dynamic dispatch on the micro-architecture like OpenBLAS and BLIS -- currently on x86_64 and also aarch64 with OpenBLAS. (To deal with small matrices (on x86_64 only) you want libxsmm backed by OpenBLAS or BLIS.) From previous experience I'd guess BLIS' new generic C micro-kernel for GEMM will beat ATLAS with recent GCC vectorizing it. Note in the case of GEMM, the most important part of BLAS, vectorizing is only really relevant after you've restructured it.