[HN Gopher] SIMD Matters: Graph Coloring
___________________________________________________________________
SIMD Matters: Graph Coloring
Author : matt_d
Score : 151 points
Date : 2024-08-21 23:55 UTC (17 hours ago)
(HTM) web link (box2d.org)
(TXT) w3m dump (box2d.org)
| a1o wrote:
| > 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 wrote:
| > 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...
|
| 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 wrote:
| Interestingly 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-
| guid...
| CreepGin wrote:
| I 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 wrote:
| The 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 wrote:
| Compilers 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 wrote:
| clang 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 wrote:
| IMHO, 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 wrote:
| The compiler can't fix your data layout
| janwas wrote:
| I do not understand this take :) The vast majority of our code
| is vector length agnostic, as is required for SVE and RVV.
|
| GPU perf/TCO is not always better than CPU, if you can even get
| enough GPUs, and the latency is also a concern and inducement
| to do everything on the GPU, which can be limiting.
| mgaunard wrote:
| You can just use templates or macros to make it length-
| agnostic.
| secondcoming wrote:
| It's unlikely everyones cloud machines have GPUs
| neonsunset wrote:
| > The other problem with simd is that in modern cpu-centric
| languages it often requires a rewrite for every vector width.
|
| It does not:
| https://github.com/bepu/bepuphysics2/blob/master/BepuUtiliti...
| (in this case, even if you use width-specific Vector128/256/512
| - compiler will unroll operations on them into respective
| 256x2/128x4/128x2 if the desired width is not supported.
| Unfortunately .NET does not deal as well with fallbacks for
| horizontal reductions/shuffles/etc. on such vectors but it's
| easily fixable with a few helpers)
|
| Naturally, there are other languages that offer similar
| experience like Zig or Swift.
|
| Moreover, sometimes just targeting one specific width is
| already good enough (like 128b).
|
| Also you can't (easily) go to GPU for most tasks SIMD is used
| in CPUs today. Good luck parsing HTTP headers with that.
| shakow wrote:
| > a gpu can provide 1000%+ of perf AND a certain level of
| portability.
|
| Relying GPU only makes sense in a handful of context, e.g.
| "computing stuff fast is my core task" or "this will be
| deployed on beefy workstations". SIMD addresses all the
| remaining cases and will give benefits to virtually everyone
| using your software; I'm sure one could implement a GPU-based
| JSON parsing library that would blow json-simd out of the
| water, but I'm not going to deploy GTX1060 on my cloud machines
| to enjoy it.
| aseipp wrote:
| The vector width stuff is overblown. There are in practice 3
| widths for all desktop architectures (128-bit, 256-bit,
| 512-bit) and the 95th percentile of all desktops are squarely
| in the first two buckets, or alternatively you're targeting a
| specific SKU which you can optimize for. You'll have to write
| uarch specific code for absolute peak performance anyway. It's
| annoying but hardly a deal breaker for this specific task.
|
| The bigger problem is most modern ISAs just aren't very nice to
| program in. Modern takes like SVE/RVV/AVX-512 are all way
| better here and much easier to write and think about because
| their instructions are much more general and have fewer edge
| cases.
|
| > And it also takes a lot of space on your cpu die. Like, A
| LOT.
|
| No, it doesn't (what would even be the "right" amount of die
| space?) But even if it did that would not make it a waste of
| space. Using up some amount of die space may result in huge
| performance gains for some subset of floating-point tasks that
| can't be achieved in any other way. For example software
| cryptography massively relies on these units, because the
| benefit is like multiple orders of magnitude; even if that's
| taking up 10% of die space for only 0.1% of software, that
| software has disproportionate impact -- if you took away that
| functional unit, then you may have a huge net _decrease_ in
| efficiency overall, meaning you need _more_ overall processors
| to handle the same workload from before.
| TinkersW wrote:
| Basically everything you said was wrong.. The
| other problem with simd is that in modern cpu-centric languages
| it often requires a rewrite for every vector width.
|
| Nope, you can use many existing libraries that present the same
| interface for all sizes, or write your own(which is what I
| did). 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.
|
| Transfer latency & bandwidth to GPU is horrible, just utterly
| horrible. And GPU to CPU perf dif is more like 5x, and in games
| etc the GPU is already nearly maxed out And it
| also takes a lot of space on your cpu die. Like, A LOT.
|
| Relative to the performance it can offer it is a very small
| area. The gains in the article are small compared to what I
| see, probably the author is new to SIMD.*
| mgaunard wrote:
| 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.
| machinekob wrote:
| Just wrap array of structures in SIMD it is not that hard at
| least in 95% of cases
| thesz wrote:
| Express 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 wrote:
| SIMD 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 wrote:
| Rather, it's a fundamental problem with arrays of structs.
| CoastalCoder wrote:
| Could 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 wrote:
| I 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.
| CoastalCoder wrote:
| I thought (maybe wrongly) that even with s/g load and
| store, the memory transactions will still be in units of
| _contiguous_ addresses, sized according to the width of
| the memory bus.
|
| Is that not the case?
| alexhutcheson wrote:
| If you are accessing elements in memory with a constant
| stride[1], then hardware prefetchers[2] do a surprisingly
| good job at "reading ahead" and avoiding cache misses.
|
| A typical example would be: you have an array of objects of
| constant size, and you're reading a double field from a
| constant offset within each object. The hardware prefetcher
| will "recognize" this access pattern and prefetch that
| offset every sizeof(obj) bytes.
|
| The major downsides (vs. a struct-of-arrays design with
| full spatial locality) are:
|
| 1. Every prefetch pulls a full cache line, but the cache
| line will include data you don't need. In this example,
| every cache line might have 64 bytes of data, but you only
| needed the one double field (8 bytes) - the rest is not
| useful. If you were iterating over an array of doubles you
| could have pulled 8 double fields in a single cache line.
|
| 2. Specific performance is hardware-dependent, so it's hard
| to guarantee performance on e.g. low-end cores, short
| loops, or unusually long strides.
|
| [1] https://en.wikipedia.org/wiki/Stride_of_an_array
|
| [2] https://en.wikipedia.org/wiki/Cache_prefetching
| eigenspace wrote:
| > I'd think that a fundamental problem is memory I/O
| bandwidth, and (depending on cache policy) poor cache hit
| ratios.
|
| You seem to be assuming that a vectorized loop over an
| array of structs only ever uses one element from the struct
| and ignores the rest. In that case, then yes, you will get
| some bandwidth problems, but modern hardware prefetchers
| are so good that a vectorized loop that only looks at each
| Nth byte or whatever is actually much faster than one might
| think. I'll also note that the serial (non-SIMD) case also
| suffers here, but often not quite so badly as the SIMD case
| suffers.
|
| However, there's lots of cases where you want the whole
| struct. E.g. complex numbers are typically a struct of two
| real numbers, and SIMD arithmetic on vectors of structs of
| complex numbers is able to work just fine with the full
| theoretical SIMD performance improvement.
| CoastalCoder wrote:
| > You seem to be assuming that a vectorized loop over an
| array of structs only ever uses one element from the
| struct and ignores the rest.
|
| That is the worst case scenario of my concern with memory
| bandwidth.
|
| More generally, I'd imagine that any good roofline
| analysis would need to consider this data-layout issue.
|
| > but modern hardware prefetchers are so good that a
| vectorized loop that only looks at each Nth byte or
| whatever is actually much faster than one might think.
|
| I believe you. I wasn't really thinking about how
| efficiently the processor can pull the correct bytes into
| the register lanes. I was just focusing on the
| fundamental memory <--> CPU xfer part of the process.
|
| TL;DR: I'm trying to get better at using roofline
| analysis in my optimization efforts.
| neonsunset wrote:
| This. Modern SIMD extensions have gathers and scatters to
| specifically work with these kinds of memory layout. For
| example, ARM64 NEON has interleaving loads and stores in the
| form of LD2/3/4 and respective ST* counterparts.
|
| https://documentation-
| service.arm.com/static/6530e5163f12c06... (PDF)
| xoranth wrote:
| Sure, but how well do they perform compared to vector
| loads? Do they get converted to vector load + shuffle uops,
| and therefore require a specific layout anyway?
|
| Last time I tried using gathers on AVX2, performance was
| comparable to doing scalar loads.
| neonsunset wrote:
| They are pretty good: https://dougallj.github.io/applecpu
| /measurements/firestorm/L...
|
| Gathers on AVX2 _used_ to be problematic, but assume it
| shouldn 't be the case today especially if the lane-
| crossing is minimal? (if you do know, please share!)
| TinkersW wrote:
| Gather is still terrible, the only core that handles it
| well is the Intel's P core. AMD issues 40+ micro ops in
| AVX2(80 in AVX512), and the Intel E core is much worse.
|
| When using SIMD you must either use SoA or AoSoA for
| optimal performance. You can sometimes use AoS if you
| have a special hand coded swizzle loader for the format.
| whiterknight wrote:
| The friction you are feeling is that arrays of structs require
| the computer to do more work to access individual members.
| claytonwramsey wrote:
| I would argue the opposite: the problem is that our languages
| give us only rudimentary tools to represent data in SoA styles,
| which makes them difficult to apply for efficient processing.
| In other words, it's not SIMD's fault but rather the C-like
| approach to data structures. In fact, SoA is also great for
| non-SIMD parallel implementations because it yields
| improvements to memory density and cache performance.
| mgaunard wrote:
| It's not just C, but also any object-oriented language.
|
| Basically the most popular imperative paradigms are just ill-
| suited to making the most of SIMD hardware. They're designed
| with other goals in mind.
| unwind wrote:
| Very 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 wrote:
| > 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 wrote:
| I 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
| au8er wrote:
| There 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.
| xoranth wrote:
| On 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):
| 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 wrote:
| 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/why would you choose one over the
| other?
| eigenspace wrote:
| I'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 ms (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 ms (0 allocations: 0 bytes) SIMD
| benchmark: 2.669 ms (0 allocations: 0 bytes) GPU
| benchmark: 27.592 ms (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 ms (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.
| xoranth wrote:
| Thank you for your reply!
|
| > GPUs are also just generally a lot more limiting than SIMD
| in many other ways.
|
| What do you mean? (besides things like CUDA being available
| only on Nvidia/fragmentation issues.)
| eigenspace wrote:
| Here's a few random limitations I can think of other than
| those already mentioned:
|
| * Float64 math is typically around 30x slower than Float32
| math on "consumer-grade" GPUs due to an arbitrary
| limitation to stop people from using consumer grade chips
| for "workstation" purposes. This turns out to not be a big
| deal for things like machine learning, but lots of
| computational processes actually are rather sensitive to
| rounding errors and benefit a lot from using 64 bit
| numbers, which is very slow on GPUs.
|
| * Writing GPU specific functions can be quite labour
| intensive compared to writing CPU code. Julia's CUDA.jl and
| KernelAbstractions.jl packages does make a lot of things
| quite a bit nicer than in most languages, but it's still a
| lot of work to write good GPU code.
|
| * Profiling and understanding the performance of GPU
| programs is typically a lot more complicated than CPU
| programs (even if there are some great tools for it!)
| because the performance model is just fundamentally more
| complex with more stuff going on and more random pitfalls
| and gotchas.
| h0l0cube wrote:
| Specifically physics benefits from CPU processing. Efficient
| rendering pipelines are typically one-way (CPU -> GPU), whereas
| the results of physics calculations are depended on both by the
| game logic and rendering, and it's much simpler (and probably
| more efficient) to keep that computation on the CPU. The
| exception to this is could be on UMA architectures like the
| Apple M-series and the PS4, where memory transport isn't a
| limiting factor - though memory/cache invalidation might be an
| issue?
| eigenspace wrote:
| Even with UMA architectures where you eliminate the memory
| transport costs, it still costs a ton of time to actually
| launch a GPU kernel from the CPU.
| h0l0cube wrote:
| Yeah, that's why I qualified with 'could'. Really depends
| on what facilities the hardware and driver provide. If the
| GPU is on the same die, perhaps the latency isn't great,
| but I really don't have the data on that. But I'd really
| like to see something like voxel deformable/destructible
| environments leveraging UMA on the Apple M. Seems like that
| something that would be groundbreaking, if only Apple
| really cared about gaming at all.
| dxuh wrote:
| With graphics you mostly prepare everything you want to render
| and then transfer all of it to the GPU. Physics still lends
| itself fairly well to GPU acceleration as well (compared to
| other things), but simply preparing something, transferring it
| to the GPU and being done is not enough. You need to at least
| get it back, even just to render it, but likely also to have
| gameplay depend on it. And with graphics programming the
| expensive part is often the communication between the CPU and
| the GPU and trying to avoid synchronization (especially with
| the old graphics APIs), so transferring there and back is
| expensive. Also physics code is full of branches, while
| graphics usually is not. GPUs (or rather really wide
| vectorization generally) don't like branches much and if you do
| only certain parts of the physics simulation on the GPU, then
| you need to transfer there and back (and synchronize) even
| more. I'm just a hobby gamedev and I know that people have done
| physics on the GPU (PhysX), but to me the things I mentioned
| sound like big hurdles.
|
| EDIT: one more big thing is also that at least for AAA games
| you want to keep the GPU doing _graphics_ so it looks good. You
| usually never have GPU cycles to spare.
| mikewarot wrote:
| >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
|
| [2] https://en.wikipedia.org/wiki/Langlands_program
| 01HNNWZ0MV43FF wrote:
| That 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?
| ccppurcell wrote:
| This 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 wrote:
| Compiler dev is graph algorithms when it's being done well. Not
| a very friendly introduction to programming though.
| _a_a_a_ wrote:
| Strange claim, can you explain a little more please.
| baq wrote:
| > 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.
| patrick451 wrote:
| > 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.
___________________________________________________________________
(page generated 2024-08-22 17:00 UTC)