Dynamic bit shuffle using AVX-512
lemire.me
lemire.me
So, I can emulate this thing on my desktop PC at about 28 nSec/cell using some Pascal code[2]. I'm thinking that if I upgrade to a machine with AVX512 instructions, it might get radically faster. What I can't figure out is how this instruction actually works, and what gains I would actually get.
The Intel documentation on this instruction is as clear as mud. There's no example with all the bits shown and worked through, leading the reader to have no ledge on which to make some intellectual purchase towards understanding.
Questions:
If I were to fork over the cash for a machine with AVX512 instructions, how many of these instructions can actually execute/second?
Wouldn't moving a bunch of values to/from memory basically empty out all the caches and make this thing really slow anyway?
Does anyone have a worked out example with bits shown for all the sources and destinations before/after the instruction, so I can see what it does?
The interesting idea about the bitgrid is that you can spread the emulation across cores, as none of the cells are Turing complete. Do all of phase A, then all of phase B, repeat.
I'm guessing there some out there, but it's not the people I have accounts with.
For your first question, the instructions are documented on the Intel website[0]. Many instructions have Latency and Throughput figures, which indicate how many cycles they take to execute. These are not straightforward to interpret due to instruction pipelining.
As for cache exhaustion, that depends on how quickly you consume more data from memory. It's worth noting that the registers are an entire cache line in width, and that Latency figures are given for the instructions that load from memory into the AVX registers.
[0] https://www.intel.com/content/www/us/en/docs/intrinsics-guid...
Here’s another idea how to optimize. Instead of a single 2D array, I would rework the memory layout. Specifically, make 6 2D arrays. Two with uint64_t values, for even/odd cells in the lookup tables. Two with bits for even/odd cells in the old grid state. Two with bits for even/odd cells in the new grid state. This improves RAM access patterns because any half of the cycle loads / stores half as many cache lines. After the complete cycle, swap old state with new state.
Gathering inputs from neighbors, and scattering output to them could be a bit tricky this way, but you can simplify if you can limit grid size to even number in both X and Y direction. At least the even/odd halves will be of the equal size this way.
Actually... what if you broke the grid up in to N by N blocks, and simulated 2N half time steps (each decreasing the side length by 2) of that block? You'd need to do a similar sort of chess grid over the blocks, and emit like "partial outputs" from each block, then run a pass going the reverse direction, consuming the partial outputs and initial inputs. This way, you can fit a block entirely within a cores L1 for N time steps, and naturally get parallelism by simulating multiple blocks at once.
You should be able to simulate N time steps like this with just 2 loads of the data (program and state) instead of 2 * N.
It's probably the same issues as with neural networks: they have to work on a whole batch of inputs to be efficient. They load only a few weights at a time into registers, then use those on the whole batch before loading the next weights.
So my guess would be: If you only run a single grid, and the grid is large, you may end up memory-bound and you can afford running inefficient instructions.
(Btw. sounds like bitgrid would map 1:1 into the LUTs of an FPGA. Might be a fun project to generate VHDL for it and then let it actually run in parallel. The less straight-forward part being the logic to get the data out of the FPGA again.)
Sony Japan's documentation for how to use a mouse & keyboard on the PS2 was literally just the URL "https://www.usb.org/document-library/usb-20-specification". Eventually, they provided a binary-only keyboard library that everyone complained was buggy, but actually just had documentation that was so brief it was easily misunderstood. After black-box testing it for an hour it was clear it worked fine, just not how anyone would expect it to.
Many years ago I made a tiny stir online by writing a stream-of-consciousness report of the experience of dealing with stuff like this for a decade. https://venturebeat.com/games/what-is-making-games-like-for-...
Different constraints and challenges on both sides of the aisle give rise to compromises which end up with lowered performance or lowered ease of use. This is one area where great authority over the entire stack lends you lots of leeways, e.g. Apple designing Metal API and the HW for it.
[1] https://en.wikipedia.org/wiki/Michael_Abrash [2] https://www.anandtech.com/show/2580/9
Most Intel ISA extensions come from either customers asking for specific instructions, or from Intel engineers (from the hardware side) proposing reasonable extensions to what already exists.
LRBni, which eventually morphed into AVX-512, was developed by a team mostly consisting of programmers without long ties to Intel hw side, as a greenfield project to make an entirely new vector ISA that should be good from the standpoint of a programmer. I strongly feel that they have succeeded, and AVX-512 is transformative when compared to all previous Intel vector extensions.
The downside is that as they had much less input and restraint from the hw side, it's kind of expensive to implement, especially in small cores. Which directly led to its current market position.
And so it is in life
Realistically though, how likely would a GCC/clang be to emit these instructions when I'm working on some lookup tables, assuming I permit it to use them (e.g. via `-march=native` on a machine that supports the extension)? My gut feeling would be that unless I specifically make sure to structure my code to be as close to the semantics of the instructions as possible, these instructions would never ever be emitted. Or has the world of compiler optimizers advanced enough that rewriting that is commonplace now?
I have a data structure library (in Rust) where I would love to have these. The problem is that AVX-512 just isn't common enough to rely on it yet, and I don't even have it on my workstation CPU (Radeon 6850, from just last year).
But in particular whether they had something in mind, I suspect Intel was thinking about video codecs and containers for a lot of these. If you read through the specs for them, you will find all sorts of places which call for things like this.
But yes, whether compiler developers can make good use of these. Questionable. They are really for specialized optimization workflows.
The "strange" instructions are actually not that niche, it's just that usage tends to be "indirect" and therefore people don't notice.
[^0] E.g. https://xoranth.net/memcmp-avx2
Also super great for emulation, and anyone else who does a lot of bulk bit-twiddling.
The whole discourse has become super weird (up to and including Linux himself ;) because of Intel 10nm delays. With the only AVX-512 products being 14nm-based intel server chips for 5 years, and then only coming to laptop for another couple years, and then only a single terrible generation of desktop parts that nobody bought, and with AMD launching super competitive (usually leading) products in those segments, obviously there wasn't a whole lot of real consistent adoption in software. And what adoption there was, was complicated by the fact that the largest adopter (server market) had to drop clocks massively and even pause processing to allow voltage to swing up enough, because they were 14nm products on a feature that was really aimed at 10nm and beyond. And then Intel yanked it out of all the desktop and laptop chips and seems poised to just ignore it for another 5 years.
Everyone just decided that because it wasn't getting adopted that it was inherently useless, up to and including Linus himself. But it wasn't getting adopted because it was a complete mess on the Intel side and AMD didn't even support it, so why bother?
The AVX-512 story is inextricably bound up in the 10nm delays and the organizational problems that have plagued Intel ever since. It's such a great thing that AMD didn't buy into the naysaying.
> They must have some programs in mind that could be run faster with them
Yeah, all new instructions are built with some workload in mind. This may or may not be specified in the architecture manual or you have to reverse-engineer it from the press releases.
I’ve got the impression that AVX-512 is finally a good and comprehensive vector ISA from Intel, not just a tolerable one. Sadly it seems to be so comprehensive that the x86-64 vendors can’t afford the die area to ship it widely, or they treat it as an enterprise feature.
Linus has commented that it's trivial to trap the first time an AVX instruction is used and pin it to a P-core (they used to do this as an optimization to avoid saving/restoring AVX registers in non-AVX code) and he doesn't know why that patch isn't on his desk.
The other problem is presumably that CPUID depends on what core it's executed on but... it seems straightforward for code to just run a CPUID on every single core (using affinity) and analyze the results. OK, 16 AVX-512 threads and 8 AVX2 threads, that's fine! It is obviously not the way code is currently written but code isn't written for AVX-512 right now anyway, and it should be literally an hour of work for a C dev.
I guess maybe they just didn't want the long tail of support but with their future architectures being heterogeneous too, they don't seem to have any plan either, and they're still shipping the AVX-512 units in silicon, meaning they are paying millions of dollars for a feature that isn't enabled. Very, very weird.
Fun fact, Alder can actually be run with AVX-512 enabled even with E-cores active. There is an undocumented MSR flag that seems to allow this. Has to be the stepping/BIOS revision before it was locked out though.
Because then anytime a program links to a vector-supporting library such as glibc, there’s a high chance they’ll be pinned to a P-core when an E-core and AVX2 would’ve sufficed.
* Book: https://link.springer.com/book/10.1007/978-1-4842-4063-2
What's the application of this? Theres's a Twitter article in the next sentence, but looks like I need to sign up to see it.