SIMD Matters: Graph Coloring

&gt;This is the magic of graph coloring and enables me to solve multiple contact constraints simultaneously without a race condition.<p>&lt;TANGENT&gt; This hits me, like a ton of bricks, as one of the most elegant ways to describe why I add 2 phases of clocking (&quot;like colors on a chessboard&quot; is the phrase I&#x27;ve been using) to my BitGrid[1] hobby project.<p>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]<p>[1] <a href="https:&#x2F;&#x2F;esolangs.org&#x2F;wiki&#x2F;Bitgrid" rel="nofollow">https:&#x2F;&#x2F;esolangs.org&#x2F;wiki&#x2F;Bitgrid</a><p>[2] <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Langlands_program" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Langlands_program</a>

&gt; The conventional wisdom is that it is difficult to achieve real gains from SIMD.<p>This has been my experience often times I misunderstood how much can be gained by using SIMD, and preparing the data to be &quot;eaten&quot; by SIMD instructions is not trivial. I have many times attempted to use just to profile and see it didn&#x27;t improve things at all and made the code really hard to understand.<p>Kudos for Erin here this is really hard work and it&#x27;s great it paid off well and gave good results here!

The 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.

&gt; 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.<p>I will keep this example in mind the next time somebody trots out the line that you should just trust the compiler.

Very cool and informative article, and I love that Box2d is in C nowadays that really makes it clear. Great job!<p>I saw a small typo:<p><pre><code> &#x2F;&#x2F; wide float typedef b2FloatW __m128; </code></pre> The `typedef` is backwards, the alias and the underlying type name are in the wrong order and need to be swapped around.

They didn&#x27;t really explain why graph coloring can be done quickly in this case. I&#x27;m not familiar with graph coloring theory, but I know the general graph coloring problems are NP-complete. I&#x27;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&#x27;t actually care about getting a minimal coloring.

Is 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.

General 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&#x2F;why would you choose one over the other?

&gt; This is a bit ironic because on x64 all math is SIMD math, it is just inefficient SIMD math.<p>I don&#x27;t understand this statement at the end of the article? Can anyone explain? TIA.

I really appreciate the write-up and showing the most important code snippets.<p>Intuitively, this feels like a narrower version of using Z-order curve.

This is a total longshot but my PhD and research has been in graph algorithms including colouring, and I&#x27;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&#x27;d be very interested.<p>Caveats: my knowledge is mostly theoretical (eg proving np-hardness or algorithm existence results) but I&#x27;m very good at thinking algorithmically. I have only hobbyist programming skills but I am a fast learner. Thanks!

&gt; The Apple M2 smokes!<p>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.

The other problem with simd is that in modern cpu-centric languages it often requires a rewrite for every vector width.<p>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.<p>So right now simd is a niche tool for super low-level things: certain decompression algos, bits of math here and there, solvers, etc.<p>And it also takes a lot of space on your cpu die. Like, A LOT.