7 ms·

Dynamic bit shuffle using AVX-512

90 points by ibobev 3y ago

LispSporks22 3y ago
> Suppose that you want to reorder, arbitrarily, the bits in a 64-bit word. 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.
- trillic 3y ago
  Cryptography
- dan-robertson 3y ago
  Static reorderings can be used for some data layouts, eg interleaving the bits of an x and y coordinate, but you should hope they’d be cheaper than dynamic reordering.
SomeRndName11 3y ago
Not many people know, but Alder Lake's implementation of AVX-512 supports FP16 format, and FP16 version of AVX-512 is so extremely fast, it is almost touching GPU performance.
slashdev 3y ago
I really love playing with vector instructions, especially AVX2, which is the most limited in my opinion. You get a whole bunch of oddly shaped legos, and it’s very challenging to build something beautiful from them. But also very fun and rewarding.
- trentnelson 3y ago
  You might enjoy https://trent.me/is-prefix-of-string-in-table/ https://trent.me/is-prefix-of-string-in-table/
Cold_Miserable 3y ago
I knew about the instruction that Daniel Lemire missed too. It seems useless to me.
llogiq 3y ago
I sometimes wonder what CPU designers think when building such weird instructions? They must have some programs in mind that could be run faster with them, or else the additional transistors are just lost weight. But then compilers and language runtimes might or might not use those instructions. Add to that the fact that modern CPUs are basically their own compilers (going from "machine code" to microcode) and you have weirdness atop of more weirdness. But perhaps this is just for business sake; adding more instruction sets to provide a barrier to the competition, because programs using this run faster but are no longer portable to competitors' CPUs.
- dtx1 3y ago
  I think back to the Playstation 2-3 or N64 that all took years for developers to fully utilize the capabilities of the hardware. Yet the hardware engineers must have known how to do it long before the software side totally figured it out. After years of SW Development it's still just magic sand to me
  - ReactiveJelly 3y ago
    I don't know. If the HW engineers knew something, wouldn't Sony or Nintendo have had them lend a hand on 1st-party titles?
    - corysama 3y ago
      I can tell you that for 3rd party titles back in the PS2/N64 days, the HW engineers handed you a spec manual explaining such useful things as "Bit 7 at address 0x70002048 toggle RFTAG mode on the MDEC". This was great when I went to write a VU emulator because no VU debugger was available. But, not so great when trying to figure out how to use the beast effectively. If you google "ps2 sdk docs" you can still find them after a while. If it's a doc with examples of how to do anything, it's from the software team at Sony Europe. 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 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-each-major-console-a-developers-perspective/ https://venturebeat.com/games/what-is-making-games-like-for-...
pavlov 3y ago
The vector permute was a highlight of the PowerPC vector extensions (AltiVec) in the late 1990s. It made a real difference for many media processing algorithms where the data is often packed and you need to pick apart the components for vector execution. 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.
- fsfod 3y ago
  At least AMD kept AVX-512 in there small Zen4C cores and just sacrificed some cache instead. I have to wonder if it was intel marketing that killed off working AVX-512 in consumer P-cores after they were released because the E-cores just become dead weight with AVX-512 enabled.
  - paulmd 3y ago
    nobody really knows what is going on with AVX-512 inside intel. 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.
    - 3y ago
mikewarot 3y ago
I have this weird architecture I'm emulating that I call a bit-grid.[1] The basic idea is an FPGA with NO routing fabric at all... just a 2d grid of look up tables that take a single bit input from each neighbor, and output a single bit to each, which means each look up table holds 64 bits (4*16 possible input states) of "program". Clocking is in two phases (like the colors of a chess board) to prevent all manner of grief, and make it easier to think about. Each phase is NOT Turning Complete, but the grid is. 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? [1] https://esolangs.org/wiki/Bitgrid https://esolangs.org/wiki/Bitgrid [2] https://github.com/mikewarot/Bitgrid https://github.com/mikewarot/Bitgrid
- foota 3y ago
  Does the shape of the grid matter? If not, I think you'd benefit from constraining the width such that the data for three rows fits within L1, so that iterating over one row leaves the data from the start of the next row in L1 by the time you get to it.
  - foota 3y ago
    Edit: 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.
anonymousDan 3y ago
By coincidence I just started playing with AVX-512 this week. It's a lot of fun, but I have to say there is a dearth of resources on how to use it. For example I would love a simple visualisation for each operation as to how the various vectors and/or memory are transformed. Can anyone recommend some good books/learning resources?
- anonymousDan 3y ago
  Answering my own question a little, on further exploration the Intel optimisation actually has a good chapter on avx512: https://www.intel.com/content/www/us/en/content-details/671488/intel-64-and-ia-32-architectures-optimization-reference-manual.html https://www.intel.com/content/www/us/en/content-details/6714...
- icelusxl 3y ago
  * Visualization: https://www.officedaytime.com/simd512e/ https://www.officedaytime.com/simd512e/ * Book: https://link.springer.com/book/10.1007/978-1-4842-4063-2 https://link.springer.com/book/10.1007/978-1-4842-4063-2
  - anonymousDan 3y ago
    Amazing, thanks!
- deleted 3y ago
  [deleted]
- alecco 3y ago
  Short intro with some visuals http://const.me/articles/simd/simd.pdf http://const.me/articles/simd/simd.pdf
- jeffffff 3y ago
  there are only a handful of instructions that do interesting things beyond parallel versions of basic arithmetic and bitwise operations. https://branchfree.org/2019/05/29/why-ice-lake-is-important-a-bit-bashers-perspective/ https://branchfree.org/2019/05/29/why-ice-lake-is-important-... provides a good overview of them.
pklausler 3y ago
This goes way back at least to the late 80's when the Cray C-90 introduced its "bit matrix multiplication" instructions.

90 points by ibobev 3y ago

> Suppose that you want to reorder, arbitrarily, the bits in a 64-bit word. 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.

trillic 3y ago
Cryptography
dan-robertson 3y ago
Static reorderings can be used for some data layouts, eg interleaving the bits of an x and y coordinate, but you should hope they’d be cheaper than dynamic reordering.

SomeRndName11 3y ago

Not many people know, but Alder Lake's implementation of AVX-512 supports FP16 format, and FP16 version of AVX-512 is so extremely fast, it is almost touching GPU performance.

slashdev 3y ago

I really love playing with vector instructions, especially AVX2, which is the most limited in my opinion. You get a whole bunch of oddly shaped legos, and it’s very challenging to build something beautiful from them. But also very fun and rewarding.

trentnelson 3y ago
You might enjoy https://trent.me/is-prefix-of-string-in-table/ https://trent.me/is-prefix-of-string-in-table/

Cold_Miserable 3y ago

I knew about the instruction that Daniel Lemire missed too. It seems useless to me.

llogiq 3y ago

I sometimes wonder what CPU designers think when building such weird instructions? They must have some programs in mind that could be run faster with them, or else the additional transistors are just lost weight. But then compilers and language runtimes might or might not use those instructions. Add to that the fact that modern CPUs are basically their own compilers (going from "machine code" to microcode) and you have weirdness atop of more weirdness. But perhaps this is just for business sake; adding more instruction sets to provide a barrier to the competition, because programs using this run faster but are no longer portable to competitors' CPUs.

dtx1 3y ago
I think back to the Playstation 2-3 or N64 that all took years for developers to fully utilize the capabilities of the hardware. Yet the hardware engineers must have known how to do it long before the software side totally figured it out. After years of SW Development it's still just magic sand to me
- ReactiveJelly 3y ago
  I don't know. If the HW engineers knew something, wouldn't Sony or Nintendo have had them lend a hand on 1st-party titles?
  - corysama 3y ago
    I can tell you that for 3rd party titles back in the PS2/N64 days, the HW engineers handed you a spec manual explaining such useful things as "Bit 7 at address 0x70002048 toggle RFTAG mode on the MDEC". This was great when I went to write a VU emulator because no VU debugger was available. But, not so great when trying to figure out how to use the beast effectively. If you google "ps2 sdk docs" you can still find them after a while. If it's a doc with examples of how to do anything, it's from the software team at Sony Europe. 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 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-each-major-console-a-developers-perspective/ https://venturebeat.com/games/what-is-making-games-like-for-...

pavlov 3y ago

The vector permute was a highlight of the PowerPC vector extensions (AltiVec) in the late 1990s. It made a real difference for many media processing algorithms where the data is often packed and you need to pick apart the components for vector execution. 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.

fsfod 3y ago
At least AMD kept AVX-512 in there small Zen4C cores and just sacrificed some cache instead. I have to wonder if it was intel marketing that killed off working AVX-512 in consumer P-cores after they were released because the E-cores just become dead weight with AVX-512 enabled.
- paulmd 3y ago
  nobody really knows what is going on with AVX-512 inside intel. 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.
  - 3y ago

mikewarot 3y ago

I have this weird architecture I'm emulating that I call a bit-grid.[1] The basic idea is an FPGA with NO routing fabric at all... just a 2d grid of look up tables that take a single bit input from each neighbor, and output a single bit to each, which means each look up table holds 64 bits (4*16 possible input states) of "program". Clocking is in two phases (like the colors of a chess board) to prevent all manner of grief, and make it easier to think about. Each phase is NOT Turning Complete, but the grid is. 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? [1] https://esolangs.org/wiki/Bitgrid https://esolangs.org/wiki/Bitgrid [2] https://github.com/mikewarot/Bitgrid https://github.com/mikewarot/Bitgrid

foota 3y ago
Does the shape of the grid matter? If not, I think you'd benefit from constraining the width such that the data for three rows fits within L1, so that iterating over one row leaves the data from the start of the next row in L1 by the time you get to it.
- foota 3y ago
  Edit: 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.

anonymousDan 3y ago

By coincidence I just started playing with AVX-512 this week. It's a lot of fun, but I have to say there is a dearth of resources on how to use it. For example I would love a simple visualisation for each operation as to how the various vectors and/or memory are transformed. Can anyone recommend some good books/learning resources?

anonymousDan 3y ago
Answering my own question a little, on further exploration the Intel optimisation actually has a good chapter on avx512: https://www.intel.com/content/www/us/en/content-details/671488/intel-64-and-ia-32-architectures-optimization-reference-manual.html https://www.intel.com/content/www/us/en/content-details/6714...
icelusxl 3y ago
* Visualization: https://www.officedaytime.com/simd512e/ https://www.officedaytime.com/simd512e/ * Book: https://link.springer.com/book/10.1007/978-1-4842-4063-2 https://link.springer.com/book/10.1007/978-1-4842-4063-2
- anonymousDan 3y ago
  Amazing, thanks!
deleted 3y ago
[deleted]
alecco 3y ago
Short intro with some visuals http://const.me/articles/simd/simd.pdf http://const.me/articles/simd/simd.pdf
jeffffff 3y ago
there are only a handful of instructions that do interesting things beyond parallel versions of basic arithmetic and bitwise operations. https://branchfree.org/2019/05/29/why-ice-lake-is-important-a-bit-bashers-perspective/ https://branchfree.org/2019/05/29/why-ice-lake-is-important-... provides a good overview of them.

pklausler 3y ago

This goes way back at least to the late 80's when the Cray C-90 introduced its "bit matrix multiplication" instructions.