9 ms·
Understanding SIMD: Infinite complexity of trivial problems
- Agingcoder 2y agoThis is the first time I hear ‘hyperscalar’. Is this generally accepted ? ( I’ve been using SIMD since the MMX days so am a bit surprised )
- dragontamer 2y agoI don't think so. Superscalar is a real term (multiple operations in one clock tick due to parallel pipelines within a core). But hyperscalar is cringe to me. There are tons of words describing SIMD already, it seems unclear why someone would make up a new word to describe an already existing concept. Especially when a similar word (superscalar) already is defined and likely gets confused for this new word.
- ashvardanian 2y agoThat may have been my mistake. I use super & hyper interchangeably and don't always notice :) PS: Should be an easy patch, will update!
- dragontamer 2y agoMaybe not. Superscalar is when say... Think of the following assembly code. Add r1, r2 Sub r3, r4 And the add and subtract both happen on the same clock tick. The important thing is that a modern CPU core (and even GPU core) have multiple parallel ALU pipelines inside of them. Because r1, r2, r3 and r4 are fully independent, a modern CPU can detect the potential parallelism here and act in parallel. After CPUs mastered this trick, the next out of order processors were invented (which not only allowed for super scalar operations, but allowed the subtract to execute first if for some reason the CPU core were waiting on r1 or r2). There are a ton of ways that modern CPUs and GPUs extract parallelism from seemingly nothingness. And because all the techniques are independent, we can have superscalar out-of-order SIMD (like what happens in AVX512 in practice). SIMD is... SIMD. It's one instruction applied to lots of data in parallel. It's totally different. You really need to use the correct word for the specific kind of parallelism that you are trying to highlight. I expect that the only word that makes sense in this article is SIMD.
- pyrolistical 2y agoI wish hardware exposed an api that allowed us to submit a tree of instructions so the hardware doesn’t need figure out which instructions are independent. Lots of this kind of work can be done during compilation but cannot be communicated to hardware due to code being linear
- dragontamer 2y agoThat's called VLIW and Intel Itanium is considered one of the biggest chip failures of all time. There is an argument that today's compilers are finally good enough for VLIW to go mainstream, but good luck convincing anyone in today's market to go for it. ------ A big problem with VLIW is that it's impossible to predict L1, L2, L3 or DRAM access. Meaning all loads/stores are impossible to schedule by the compiler. NVidia has interesting barriers that get compiled into its SASS (a level lower than PTX assembly). These barriers seem to allow the compiler to assist in the dependency management process but ultimately still require a decoder in the NVidia core final level before execution.
- neerajsi 2y agoVliw is kind of the dual of what pyrolistical was asking for. Vliw lets you bundle instructions that are known to be independent rather than encode instructions to mark known dependencies. The idea pyrolistical mentioned is closer to explicit data graph execution: https://en.m.wikipedia.org/wiki/Explicit_data_graph_execution https://en.m.wikipedia.org/wiki/Explicit_data_graph_executio....
- creato 2y agoVLIW is still in use in multiple DSP products on the market today, and they are good successful products in their niche. They work very well if your code can be written as a loop without branches (or very limited branches) in the body, and a lot of instruction level parallelism in the body. Unfortunately for Intel, most code doesn't look like that. But for most workloads that happen to also be a good case for SIMD, it is (can be) great.
- deleted 2y ago
- spacemanspiff01 2y agoI thought it was referring to this? https://en.m.wikipedia.org/wiki/Hyperscale_computing https://en.m.wikipedia.org/wiki/Hyperscale_computing IE our simd implementation allows you to scale across different architectures/ CPU revisions without having to rewrite assembly for each CPU processor? Edit: Rereading, that does not make much sense...
- Joker_vD 2y ago> SIMD instructions are complex, and even Arm is starting to look more “CISCy” than x86! Thank you for saying it out loud. XLAT/XLATB of x86 is positively tame compared to e.g. vrgatherei16.vv/vrgather.vv.
- deleted 2y ago[deleted]
- saagarjha 2y agoThat's RISC-V, no?
- dragontamer 2y agoIntel needs to see what has happened to their AVX instructions and why NVidia has taken over. If you just wrote your SIMD in CUDA 15 years ago, NVidia compilers would have given you maximum performance across all NVidia GPUs rather than being forced to write and rewrite in SSE vs AVX vs AVX512. GPU SIMD is still SIMD. Just... better at it. I think AMD and Intel GPUs can keep up btw. But software advantage and long term benefits of rewriting into CUDA are heavily apparent. Intel ISPC is a great project btw if you need high level code that targets SSE, AVX, AVX512 and even ARM NEON all with one codebase + auto compiling across all the architectures. ------- Intels AVX512 is pretty good at a hardware level. But software methodology to interact with SIMD using GPU-like languages should be a priority. Intrinsics are good for maximum performance but they are too hard for mainstream programmers.
- dist-epoch 2y ago> If you just wrote your SIMD in CUDA 15 years ago, NVidia compilers would have given you maximum performance across all NVidia GPUs That's not true. For maximum performance you need to tweak the code to a particular GPU model/architecture. Intel has SSE/AVX/AVX2/AVX512, but CUDA has like 10 iterations of this (increasing capabilities). Code written 15 years ago would not use modern capabilities, like more flexible memory access, atomics.
- dragontamer 2y agoMaximum performance? Okay, you'll have to upgrade to ballot instructions or whatever and rearchitect your algorithms. (Or other wavefront / voting / etc. etc. new instructions that have been invented. Especially those 4x4 matrix multiplication AI instructions). But CUDA -> PTX intermediate code has allowed for significantly more flexibility. For crying out loud, the entire machine code (aka SASS) of NVidia GPUs has been cycled out at least 4 times in the past decade (128-bit bundles, changes to instruction formats, acquire/release semantics, etc etc) It's amazing what backwards compatibility NVidia has achieved in the past 15 years thanks to this architecture. SASS changes so dramatically from generation to generation but the PTX intermediate code has stayed highly competitive.
- EVa5I7bHFq9mnYK 2y agoC# vectors do a great job of simplifying those intrinsics in a safe and portable manner.
- ashvardanian 2y agoThere are dozens of libraries, frameworks, and compiler toolchains that try to abstract away SIMD capabilities, but I don't think it's a great approach. The only 2 approaches that still make sense to me: A. Writing serial vectorization-aware code in a native compiled language, hoping your compiler will auto-vectorize. B. Implementing natively for every hardware platform, as the ISA differences are too big to efficiently abstract away anything beyond 128-register float multiplication and addition. This article, in a way, an attempt to show how big the differences even for simple data-parallel floating-point tasks.
- dzaima 2y agoThere's the middle-ground approach of having primarily target-specific operations but with intersecting ones named the same, and allowing easily building custom abstractions on top of such to paper over the differences how best it makes sense for the given application. That's the approach https://github.com/mlochbaum/Singeli https://github.com/mlochbaum/Singeli takes. There's a good amount of stuff that can clearly utilize SIMD without much platform-specificness, but doesn't easily autovectorize - early-exit checks in a loop, packed bit boolean stuff, some data rearranging, probing hashmap checks, some very-short-variable-length-loop things. And while there might often be some parts that do just need to be entirely target-specific, they'll usually be surrounded by stuff that doesn't (the loop, trip count calculation, loads/stores, probably some arithmetic).
- neonsunset 2y agoNumerics in .NET are not a high-level abstraction and do out of box what many mature vectorized libraries end up doing themselves - there is significant overlap between NEON, SSE* and, if we overlook vector width, AVX2/512 and WASMs PackedSIMD. .NET has roughly three vector APIs: - Vector<T> which is platform-defined width vector that exposes common set of operations - Vector64/128/256/512<T> which has wider API than the previous one - Platform intrinsics - basically immintrin.h Notably, platform intrinsics use respective VectorXXX<T> types which allows to write common parts of the algorithm in a portable way and apply platform intrinsics in specific areas where it makes sense. Also some method have 'Unsafe' and 'Native' variants to allow for vector to exhibit platform-specific behavior like shuffles since in many situations this is still the desired output for the common case. The .NET's compiler produces competitive with GCC and sometimes Clang codegen for these. It's gotten particularly good at lowering AVX512.
- juancn 2y agoThe main problem is that there are no good abstractions in popular programming languages to take advantage of SIMD extensions. Also, the feature set being all over the place (e.g. integer support is fairly recent) doesn't help either. ISPC is a good idea, but execution is meh... it's hard to setup and integrate. Ideally you would want to be able to easily use this from other popular languages, like Java, Python, Javascript, without having to resort to linking a library written in C/C++. Granted, language extensions may be required to approach something like that in an ergonomic way, but most somehow end up just mimicking what C++ does and expose a pseudo assembler.
- pjmlp 2y agoThe best is the GPU programming approach, with specialised languages Just like using SQL is much more sane than low level C APIs to handle BTree nodes. The language extensions help, but code still requires too much low level expertise, with algorithms and data structures having to take SIMD/MIMD capabilities into account anyway.
- Conscat 2y agoI think the EVE library for C++ is a great abstraction. It's got an unusual syntax using subscript operator overloading, but that winds up being a very ergonomic and flexible way to program with masked-SIMD.
- secondcoming 2y agoI’m not sure about EVE. I trialled it by trying to uppercase a string and even though I got it working in the end it was quite unpleasant. Their docs need to be better.
- deleted 2y ago[deleted]
- Earw0rm 2y agostd::experimental::simd is happening. It should be part of c++26.
- bob1029 2y agoI see a lot of "just use the GPU" and you'd often be right. SIMD on the CPU is most compelling to me due to the latency characteristics. You are nanoseconds away from the control flow. If the GPU needs some updated state regarding the outside world, it takes significantly longer to propagate this information. For most use cases, the GPU will win the trade off. But, there is a reason you don't hear much about systems like order matching engines using them.
- pclmulqdq 2y agoYou would be surprised. The GPU often loses even for small neural nets given the large latency. Anything that needs high throughput or is sized like an HPC problem should use a GPU, but a lot of code benefits from SIMD on small problems.
- gmueckl 2y agoIf you run many small tasks on the GPU, you can increase throughput by overlapping transfers and computation. There may also be other ways to batch problems together, but that depends on the algorithms. The one truly unfixable issue is round-trip latency.
- gopalv 2y ago> The GPU often loses even for small neural nets given the large latency Apple's neural engine shows that you can live in between those two worlds. As you said, the trouble is the latency, the programming model is still great.
- deleted 2y ago[deleted]
- moldavi 2y agoDo Apple's chips (M1 etc) change this at all, since they share memory with the GPU?
- bob1029 2y agoI think an argument could be made depending on the real world timings. How much closer in time is the Apple GPU vs one on a PCIe bus?
- a1o 2y ago[flagged]
- ashvardanian 2y agoMay be a false positive. There were multiple passes of human writers working on the post - first, preparing the meat, and later reorganizing it for more casual readers.
- deleted 2y ago[deleted]
- benchmarkist 2y agoLooks like a great use case for AI. Set up the logical specification and constraints and let the AI find the optimal sequence of SIMD operations to fulfill the requirements.
- fooblaster 2y agoNo, there are decades of compiler literature for solving this problem.
- benchmarkist 2y agoThat's even better then. Just let the AI read the literature and write the optimal compiler.
- fooblaster 2y agoIt would probably be easier to clone the existing repository than get an llm to regurgitate llvm.
- benchmarkist 2y agoThe AI would learn from llvm as well.
- saagarjha 2y agoI think your comments would be improved if you learned from LLVM first.
- benchmarkist 2y agoWhy would I learn anything if we're going to have AGI in less than 3 years according to silicon valley luminaries like Sam Altman? He's rich because he's super smart and everything he says is correct so you sir should get with the program and start thinking how to logically specify tasks so that Sam Altman's AGI can solve it for you instead of telling me to learn LLVM.
- TinkersW 2y agoYou can simplify the 2x sqrts as sqrt(a*b), overall less operations so perhaps more accurate. It would also let you get rid of the funky lane swivels. As this would only use 1 lane, perhaps if you have multiple of these to normalize, you could vectorize it.
- a_gopher 2y agomy thoughts exactly - crazy to know all these arcane SIMD opcodes but not know basic maths!!
- ashvardanian 2y agoSquare root computation can be tricky, often relying on approximations. These approximations tend to perform best for mid-range values, while accuracy can degrade for very large or very small values. With this in mind, a product of roots is generally more accurate than a root of products. From a SIMD perspective, it’s worth noting that on most platforms, the cost of computing one square root or two is the same. On modern x86 server CPUs, for instance, you can calculate up to 8 double-precision roots in parallel with identical latency. So there’s no additional cost in terms of performance. I hope this sheds some light on the design of my code. PS: In a previous life, I did research in Astro- and Plasma Physics. While I don’t claim to remember all the Math, it’s usually more productive to ask for clarification than to assume ignorance ;)
- harry8 2y ago> it’s usually more productive to ask for clarification than to assume ignorance ;) Good reminder for me and anyone else right there, nicely put.
- nine_k 2y agoMoments like that are enlightening. When you see something really improbable (knowing advanced SIMD while appearing to ignore basic algebra), it's likely the moment you see a gap in your picture of the world. So it's tine to learn something new and likely unexpected (else you could have guessed).
- rishi_devan 2y agoInteresting article. The article mentions "...the NumPy implementation illustrates a marked improvement over the naive algorithm...", but I couldn't find a NumPy implementation in the article.
- andix 2y agoYes, they are really great at abstracting the SIMD operations, but the abstraction has only very few common methods. I'm not sure how much real world benefits those abstractions have. Once you need more complex operations, you need to use the specific operations from System.Runtime.Intrinsics.(X86|ARM) based on the current architecture. And you need to adjust your implementation on the CPUs capabilities. There are still a lot of older x64 CPUs around that don't have AVX512 for example.
- big-chungus4 2y agocan the authors please share the numpy code too
- ashvardanian 2y agoThere are several ways to implement it in NumPy, often resulting in 20% variance. I've added a reference implementation to my mirror of the blogpost and the Modular team will soon update the original posting as well: https://ashvardanian.com/posts/understanding-simd-complexity/#introduction-to-cosine-similarity https://ashvardanian.com/posts/understanding-simd-complexity...
- marmaduke 2y agoMy approach to this is to write a bunch of tiny “kernels” which are obvious to SIMD and then inline them all, and it does a pretty good job on x86 and arm https://github.com/maedoc/tvbk/blob/nb-again/src/util.h https://github.com/maedoc/tvbk/blob/nb-again/src/util.h
- remram 2y agoDid they write bfloat16 and bfloat32 when they meant float16 and float32? On the image: https://www.modular.com/blog/understanding-simd-infinite-complexity-of-trivial-problems#:~:text=bfloat16%20compared%20to%20bfloat32 https://www.modular.com/blog/understanding-simd-infinite-com...
- sgerenser 2y agoYeah I was really confused at first, pretty sure they messed up the labels.
- ashvardanian 2y agoPatched ;)
- kristianp 2y ago> Let's explore these challenges and how Mojo helps address them You've not linked to or explained what Mojo is. There's also a lot going on with different products mentioned: Modular, Unum cloud, SimSIMD that are not contextualised either. While I'm at it, where do the others come in (Ovadia, Lemire, Lattner), you all worked on SimSIMD, I guess? That said, this is a great article, thanks. Edit: Mojo is a programming language with python-like syntax, and is a product by Modular: https://github.com/modularml/mojo https://github.com/modularml/mojo
- GeekyBear 2y agoMojo is a programming language that aims to target CPUs, GPUs and custom accelerators that was created by the same person, Lattner, behind LLVM and Clang. It's based on a newer compiler framework that has been added to the LLVM umbrella of projects. > MLIR is a newer compiler framework that allows Mojo to exploit higher level compiler passes unavailable in LLVM alone... It can often more effectively use certain types of CPU optimizations directly, like SIMD, with no direct intervention by a developer https://www.wikipedia.org/wiki/Mojo_(programming_language) https://www.wikipedia.org/wiki/Mojo_(programming_language)
- deleted 2y ago[deleted]