7 ms·
SIMD Matters: Graph Coloring
- a1o 2y ago> The conventional wisdom is that it is difficult to achieve real gains from SIMD. This has been my experience often times I misunderstood how much can be gained by using SIMD, and preparing the data to be "eaten" by SIMD instructions is not trivial. I have many times attempted to use just to profile and see it didn't improve things at all and made the code really hard to understand. Kudos for Erin here this is really hard work and it's great it paid off well and gave good results here!
- bob1029 2y ago> preparing the data to be "eaten" by SIMD instructions is not trivial I've always found my best experiences with SIMD to be one level removed from the actual scary bits. I.e., using primitives from libraries which are inherently optimized. My favorite SIMD abstraction right now is Vector<T> in .NET: https://learn.microsoft.com/en-us/dotnet/api/system.numerics.vector-1 https://learn.microsoft.com/en-us/dotnet/api/system.numerics... If you're worried you'd get that one wrong too, you can go up another level of abstraction and use something like Matrix4x4 and its members which are also optimized.
- neonsunset 2y agoInterestingly enough, Vector<T> itself is a bit limited and has smaller API than Vector128/256/512<T>. It is being improved to match those and then expand further, but it happens incrementally, in 8, now in 9 and more changes after - after all, compiler treats it pretty much the same as vector of respective width under the hood. The main problem with writing SIMD code for the first time is it's a learning curve to understand that the performance improvement doesn't come from just performing n element operations per single instruction but also reducing the book-keeping that usually comes per element per loop iteration like conditional branches to terminate the loop, branchy element selects over branchless shuffles in vectors, loading more data at a time, etc. Which is why many first time attempts lead to wrong impression that vectorization is hard, while the truth is they just stumble into known "don't do that, also do less" traps like needlessly spilling vectors or writing to intermediate buffers instead of directly, modifying individual vector elements or even iterating them, avoiding actual vector operations. There's a new-ish guide on vectorization if you're interested: https://github.com/dotnet/runtime/blob/main/docs/coding-guidelines/vectorization-guidelines.md https://github.com/dotnet/runtime/blob/main/docs/coding-guid...
- CreepGin 2y agoI really appreciate the write-up and showing the most important code snippets. Intuitively, this feels like a narrower version of using Z-order curve.
- vkazanov 2y agoThe other problem with simd is that in modern cpu-centric languages it often requires a rewrite for every vector width. And for 80% of the cases by the point there is enough vectorizable data for a programmer to look into simd, a gpu can provide 1000%+ of perf AND a certain level of portability. So right now simd is a niche tool for super low-level things: certain decompression algos, bits of math here and there, solvers, etc. And it also takes a lot of space on your cpu die. Like, A LOT.
- adrianN 2y agoCompilers are becoming reasonably good at autovectorization if you’re a bit careful how you write your code. I wouldn’t say that simd is niche. You often don’t get the really great improvements you can achieve by being clever manually, but the improvements are still very measurable in my experience.
- secondcoming 2y agoclang may be getting better, but gcc isn't. Being 'careful how you write your code' is putting it mildly. IME you have to hold the compiler's hand at every step. Using 'bool' instead of 'int' can make gcc give up on autovectorisation, for example. You need to use intrinsics, or a wrapper lib around them, if you want to be sure that SIMD is being used.
- cvadict 2y agoIMHO, the overhead of perpetually babysitting compiler diagnostics or performance metrics to ensure your latest update didn't confound the auto-vectorizer is never a net positive over just using something like xsimd, Google highway, etc.
- whiterknight 2y agoThe compiler can’t fix your data layout
- titzer 2y agoIt depends on how high-level the abstraction you're using is. Things like Halide do pretty significant reorganization of your code and data to achieve parallel speedup. And of course if you are using Tensor libraries you're doing exactly that. It all depends on the level of abstraction.
- mgaunard 2y agoThe main problem of SIMD remains the same: it requires working with structures of arrays rather than arrays of structures, which makes it more difficult to combine and layer objects on top of each other.
- machinekob 2y agoJust wrap array of structures in SIMD it is not that hard at least in 95% of cases
- thesz 2y agoExpress your algorithms as queries over arrays and you can change representation of arrays keeping queries the same. Who said SQL and columnar/row storage models? ;) Something like LINQ can do the job as well.
- eigenspace 2y agoSIMD works fine with arrays of structures. It's sometimes awkward for people to phrase algorithms in terms of SIMD over arrays of structs, but that's often a problem imposed by poor programming language design, not a fundamental problem with SIMD itself.
- immibis 2y agoRather, it's a fundamental problem with arrays of structs.
- CoastalCoder 2y agoCould you elaborate on this? I'd think that a fundamental problem is memory I/O bandwidth, and (depending on cache policy) poor cache hit ratios.
- jeltz 2y agoI assume they are talking about scatter/gather load and store. But even using those I assume performance typically will be worse due to cache misses.
- unwind 2y agoVery cool and informative article, and I love that Box2d is in C nowadays that really makes it clear. Great job! I saw a small typo: // wide float typedef b2FloatW __m128; The `typedef` is backwards, the alias and the underlying type name are in the wrong order and need to be swapped around.
- noelwelsh 2y ago> This is a bit ironic because on x64 all math is SIMD math, it is just inefficient SIMD math. I don't understand this statement at the end of the article? Can anyone explain? TIA.
- mcraiha 2y agoI assume it means "SSE2 is baseline / non-optional for x86-64, so compilers can always use SSE1/SSE2 instructions when targeting x86-64." https://stackoverflow.com/a/50786881 https://stackoverflow.com/a/50786881
- au8er 2y agoThere is no independent scalar floating point unit for most modern CPUs. When scalar floating point arithmetic is needed, it is send to the SIMD unit. This pretty means that scalar and vectorised floating point operations usually have the same latency. If you do any scalar floating point operations, the CPU is just doing vectorised operations except with only 1 useful value.
- kbolino 2y agoIs it really true that there's no scalar FPU at all? What about x87? The instructions are still there even in 64-bit long mode, they use their own registers, and there are enough idiosyncrasies (80-bit extended-double precision, stack-based operations, etc.) that I would expect it to be easier to just include a dedicated scalar x87 FPU than try to shoehorn x87 compatibility into the SIMD units.
- xoranth 2y agoOn x86-64, compilers use SIMD instructions and registers to implement floating point math, they just use the single lane instructions. E.g. (https://godbolt.org/z/94b3r8dMn https://godbolt.org/z/94b3r8dMn): float my_func(float lhs, float rhs) { return 2.0f * lhs - 3.0f * rhs; } Becomes: my_func(float, float): addss xmm0, xmm0 mulss xmm1, DWORD PTR .LC0[rip] subss xmm0, xmm1 ret (addss, mulss and subss are SSE2 instructions.)
- xoranth 2y agoGeneral questions for gamedevs here. How useful is SIMD given that now we have compute shaders on the GPU? If so, what workloads still require SIMD/why would you choose one over the other?
- eigenspace 2y agoI'm not a gamedev, but I do a lot of numerical work. GPUs are great, but they're no replacement for SIMD. For example, I just made a little example on my desktop where I summed up 256 random Float32 numbers, and doing it in serial takes around 152 nanoseconds, whereas doing it with SIMD took just 10 nanoseconds. Doing the exact same thing with my GPU took 20 microseconds, so 2000x slower: julia> using CUDA, SIMD, BenchmarkTools julia> function vsum(::Type{Vec{N, T}}, v::Vector{T}) where {N, T} s = Vec{N, T}(0) lane = VecRange{N}(0) for i ∈ 1:N:length(v) s += v[lane + i] end sum(s) end; julia> let L = 256 print("Serial benchmark: "); @btime vsum(Vec{1, Float32}, v) setup=(v=rand(Float32, $L)) print("SIMD benchmark: "); @btime vsum(Vec{16, Float32}, v) setup=(v=rand(Float32, $L)) print("GPU benchmark: "); @btime sum(v) setup=(v=CUDA.rand($L)) end; Serial benchmark: 152.239 ns (0 allocations: 0 bytes) SIMD benchmark: 10.359 ns (0 allocations: 0 bytes) GPU benchmark: 19.917 μs (56 allocations: 1.47 KiB) The reason for that is simply that it just takes that long to send data back and forth to the GPU and launch a kernel. Almost none of that time was actually spent doing the computation. E.g. here's what that benchmark looks like if instead I have 256^2 numbers: julia> let L = 256^2 print("Serial benchmark: "); @btime vsum(Vec{1, Float32}, v) setup=(v=rand(Float32, $L)) print("SIMD benchmark: "); @btime vsum(Vec{16, Float32}, v) setup=(v=rand(Float32, $L)) print("GPU benchmark: "); @btime sum(v) setup=(v=CUDA.rand($L)) end; Serial benchmark: 42.370 μs (0 allocations: 0 bytes) SIMD benchmark: 2.669 μs (0 allocations: 0 bytes) GPU benchmark: 27.592 μs (112 allocations: 2.97 KiB) so we're now at the point where the GPU is faster than serial, but still slower than SIMD. If we go up to 256^3 numbers, now we're able to see a convincing advantage for the GPU: julia> let L = 256^3 print("Serial benchmark: "); @btime vsum(Vec{1, Float32}, v) setup=(v=rand(Float32, $L)) print("SIMD benchmark: "); @btime vsum(Vec{16, Float32}, v) setup=(v=rand(Float32, $L)) print("GPU benchmark: "); @btime sum(v) setup=(v=CUDA.rand($L)) end; Serial benchmark: 11.024 ms (0 allocations: 0 bytes) SIMD benchmark: 2.061 ms (0 allocations: 0 bytes) GPU benchmark: 353.119 μs (113 allocations: 2.98 KiB) So the lesson here is that GPUs are only worth it if you actually have enough data to saturate the GPU, but otherwise you're way better off using SIMD. GPUs are also just generally a lot more limiting than SIMD in many other ways.
- mikewarot 2y ago>This is the magic of graph coloring and enables me to solve multiple contact constraints simultaneously without a race condition. <TANGENT> This hits me, like a ton of bricks, as one of the most elegant ways to describe why I add 2 phases of clocking ("like colors on a chessboard" is the phrase I've been using) to my BitGrid[1] hobby project. I wonder what other classes of problems this could solve. This feels oddly parallel, like a mapping of the Langlands program into computer science.[2] [1] https://esolangs.org/wiki/Bitgrid https://esolangs.org/wiki/Bitgrid [2] https://en.wikipedia.org/wiki/Langlands_program https://en.wikipedia.org/wiki/Langlands_program
- 01HNNWZ0MV43FF 2y agoThat looks cool. I want to raise some nits, though: - If they're sending and receiving along diagonals, aren't those actually bishop-neighbors, not rook-neighbors? - Think you meant Crypt of the Necro _dancer_ - The grid in the background makes it hard to discern whether they also send to rook-neighbors - Secret 4th nit - Wait, are the cells just rotated 45 in the diagram and not in the prose?
- mikewarot 2y agoI didn't write it up at Esolang, someone else did. I wouldn't have rotated it 45 degrees.
- dahart 2y ago> aren’t those actually bishop-neighbors, not rook-neighbors? There are 2 grids, so it depends on your frame of reference. The node connections are oriented 90 degrees to the shape of the node in the picture, which means rook neighbors is accurate relative to the nodes. The background is off by 45 degrees, so node connections relative to the background grid are diagonal, or bishop, moves.
- ccppurcell 2y agoThis is a total longshot but my PhD and research has been in graph algorithms including colouring, and I'm looking for a career change. If anyone has any advice at all (roles or companies that use these skills, tools to learn, etc) I'd be very interested. Caveats: my knowledge is mostly theoretical (eg proving np-hardness or algorithm existence results) but I'm very good at thinking algorithmically. I have only hobbyist programming skills but I am a fast learner. Thanks!
- JonChesterfield 2y agoCompiler dev is graph algorithms when it's being done well. Not a very friendly introduction to programming though.
- _a_a_a_ 2y agoStrange claim, can you explain a little more please.
- titzer 2y agoI generally concur. Compilers that do advanced optimizations represent both control flow and data flow of the program as a graph where the nodes can represent basic blocks or operations in the program. One of the most graph-like IRs is called the "sea of nodes" and literally represents the entire program as a directed graph of nodes and edges that represent dependencies. Most compiler programs amount to traversing, matching, and transforming one or more nodes at a time. Graph coloring itself (i.e. the graph coloring problem) is often used to solve register allocation, a key optimization needed to make efficient use of the fastest storage in modern computers, the register file. Graph coloring works on a different representation of the program called the Interference Graph, where nodes represent variables and edges represent interferences. Graph coloring for general graphs is NP-complete, so heuristics are used. So yes, I mostly concur. Compiler algorithms are usually graph algorithms.
- yvdriess 2y agoControl flow and data flow of programs are modelled as graphs so that certain analysis and transformations can be applied. That involves subgraph similarities, graph searches, graph transformation rules etc. And at the tail end, register allocation is graph coloring. Check out the LLVM and MLIR projects if you want some concrete modern examples.
- baq 2y ago> The Apple M2 smokes! I was about this surprised when I made a jupyter notebook with a few gigs of numbers shuffled around and xgboosted and after I was done prototyping on an M1 Air and ran it on my serious box (a 12700k) it was actually slower, and noticeably.
- deleted 2y ago[deleted]
- patrick451 2y ago> I also implemented all the wide math functions to work with this. It seems that I have arranged all the data perfectly for the compiler to use automatic vectorization. But it seems this doesn’t really happen to a sufficient degree to compete with my hand written SSE2. I will keep this example in mind the next time somebody trots out the line that you should just trust the compiler.
- intalentive 2y agoIs the AVX2 implementation using the full 256-bit register width? If so, I am surprised that it is only 14% faster than SSE. If not, I would like to see how the results compare with the rest of the tests.
- p0nce 2y agoDoubling the register size only affects things if CPU operations were the bottleneck. Often he bottleneck is memory accesses.
- openasocket 2y agoThey didn't really explain why graph coloring can be done quickly in this case. I'm not familiar with graph coloring theory, but I know the general graph coloring problems are NP-complete. I'm guessing the reason you can use a greedy algorithm to get a decent coloring quickly is because you know the graph is planar, and because you don't actually care about getting a minimal coloring.
- deleted 2y ago[deleted]
- jvanderbot 2y agoProbably. It's like: TSP is really really easy if you know your input is N vertices with N-1 edges forming a line.
- jtolmar 2y agoColoring a graph is trivial, just give every node its own color. The NP-complete problems are for finding the optimal number of colors, or determining if the graph can be colored using a set small number of colors. Erin's solution aims for a small number of colors, but doesn't try to be the optimal number.