4 ms·

So is this instruction basically a carry-less vectorized FMAD?

dragontamer 3y ago
Seems like it. I only learned of this operation from reading this blogpost. "Permuting Bits" seems like a bloody obvious use of this instruction, but honestly, anyone who is familiar with carry-less multiplication will immediately see the widespread capabilities of this instruction. It really demonstrates to me that once again, Intel and their design of AVX512 has some very smart people in there. Its a good, flexible, operation. Albeit arcane and few people probably see how to use this instruction well, but its really exciting to see "such a good idea" from them. GF(2^8) fields (aka: 8-bit GF operations) are used in all sorts of CRC, Error-correction Reed Solomon, Elliptical Curve, etc. etc. operations. But beyond just that, bitshifts and xors innately have a huge number of applications outside of cryptography or GF-stuffs. It makes sense to make a dedicated instruction like this. ------ EDIT: Upon rereading the end of the blogpost: > I will probably keep using a SAT solver to solve the masks Yeah, that's actually what's needed to generalize this. Note: common operations like "if(a) b else c", or "min(a, b)", or such can likely be specified in terms of AVX512 operations now. Powerful, efficient, operations like GF2P8AFFINEQB, pext, pdep, and pshufb are getting damn close to an FPGA-like parallel processor. I mean, pshufb is already an arbitrary 4-bit truth table / 4-LUT if you think about it.
dzaima 3y ago
Not quite - in "A * x + b", "A" is an 8×8 matrix, while "x" and "b" are 8-bit vectors. (it's vectorized over "A" and "x", but not "b", which is the immediate value)
- dragontamer 3y ago
  I appreciate the correction. So this is perhaps more accurately denoted as: * (A[0] * x + A[1] * x + ... A[7] * x + B). If we normalize everything to 8-bit values. This is a far more powerful operation than I initially described. Where * is this pseudo-multiply (bitshift and xor) operation and + is XOR.
- deleted 3y ago
  [deleted]
- dragontamer 3y ago
  https://www.felixcloutier.com/x86/gf2p8affineqb https://www.felixcloutier.com/x86/gf2p8affineqb VGF2P8AFFINEQB zmm1{k1}{z}, zmm2, zmm3/m512/m64bcst, imm8 So there are 3x AVX512 registers + 1x 8-bit immediate. zmm1 seems to be the output register, the 64x 8-bit results. zmm2 seems to be the "64x parallel x" in Ax + b. zmm3 seems to be a 8x parallel A-matrix. I'm not sure how these 8x A-matrices line up to the final result, but perhaps 8-at-a-time is the logical conclusion. (outputs values#0-7 use A[0] matrix. Output#8-15 uses A[1] matrix?) imm8 seems to be "b" in the Ax + b formula, and is shared with all operations. -------- EDIT: I think I get it now. Edited this post with my latest understanding.
  - dzaima 3y ago
    Yeah the edited version is correct; it matches up each group of eight "x" values with one "A" matrix (such that, in the bitwise representation of the arguments, there's no data transfer happening across 64-bit blocks; this ends up quite limiting if you want different matrices, so most of the uses are ones where the matrix is the same for all elements).
    - dragontamer 3y ago
      This is nuts. https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html#text=AFFINE%2520&ig_expand=3657 https://www.intel.com/content/www/us/en/docs/intrinsics-guid... Intel's documentation is claiming 0.5 CPI, or a bandwidth of 2x of these operations per clock tick. I mean, forget about bit-shuffling or permuting. I feel like with the right configuration, you can operate 512-bits of CRC32 calculations in parallel, maybe in like 3 or 4 instructions (or ~2 clock ticks) or something incredibly fast. > this ends up quite limiting if you want different matrices, so most of the uses are ones where the matrix is the same for all elements Elliptical Curves is the obvious use case. CRC is one immediate use where all the matricies are the same (and linear in the GF-field), albeit the reduction needs to be done "somehow" but that can be figured out in a later operation... probably... AES encryption is operated over 4x sets of GF(2^8). I know that AES is already got its own instruction but a full software implementation of the GF-operations behind AES might be possible with this. -------------- I dunno, there's a lot of things I see already as immediately applicable where the "A" matrix is nearly constant across all elements. And for those where A isn't constant, pipelined operation is obvious. 8x different "A" matrixies means that we can build a "pipeline" where we can AVX512-shift the bytes down by 8 as well each clock tick, and build an 8x-deep pipeline and apply those 8x A matricies in parallel while consuming 64-bytes per clock-tick, while performing 512-bit worth of operation per clock tick (no, 1024-bits because Intel chips support 2x such operations per clock tick). Pipelining, full parallelization, etc. etc. So many architectures are possible with this spec. IMO, it shows that Intel knows what they're doing with these intrinsic, and I think this is something now GPU can accomplish yet. Truly an advantage to Intel chips only. Very nice instruction. The practical benefits though (Intel-only, exceptionally arcane with very few programmers who can work with, etc. etc.) may make it a dead instruction though. But I'm sure some wizard out there is going to do something cool with this instruction over the next 5 years. (It'd probably take weeks of practice on some practice problem just to learn how to use this instruction correctly, lol)
- gpderetta 3y ago
  Thank. Seems a very powerful operation and googling around it seems to be usable for all kind of bit tricks.

Seems like it. I only learned of this operation from reading this blogpost. "Permuting Bits" seems like a bloody obvious use of this instruction, but honestly, anyone who is familiar with carry-less multiplication will immediately see the widespread capabilities of this instruction. It really demonstrates to me that once again, Intel and their design of AVX512 has some very smart people in there. Its a good, flexible, operation. Albeit arcane and few people probably see how to use this instruction well, but its really exciting to see "such a good idea" from them. GF(2^8) fields (aka: 8-bit GF operations) are used in all sorts of CRC, Error-correction Reed Solomon, Elliptical Curve, etc. etc. operations. But beyond just that, bitshifts and xors innately have a huge number of applications outside of cryptography or GF-stuffs. It makes sense to make a dedicated instruction like this. ------ EDIT: Upon rereading the end of the blogpost: > I will probably keep using a SAT solver to solve the masks Yeah, that's actually what's needed to generalize this. Note: common operations like "if(a) b else c", or "min(a, b)", or such can likely be specified in terms of AVX512 operations now. Powerful, efficient, operations like GF2P8AFFINEQB, pext, pdep, and pshufb are getting damn close to an FPGA-like parallel processor. I mean, pshufb is already an arbitrary 4-bit truth table / 4-LUT if you think about it.

dzaima 3y ago

Not quite - in "A * x + b", "A" is an 8×8 matrix, while "x" and "b" are 8-bit vectors. (it's vectorized over "A" and "x", but not "b", which is the immediate value)

dragontamer 3y ago
I appreciate the correction. So this is perhaps more accurately denoted as: * (A[0] * x + A[1] * x + ... A[7] * x + B). If we normalize everything to 8-bit values. This is a far more powerful operation than I initially described. Where * is this pseudo-multiply (bitshift and xor) operation and + is XOR.
deleted 3y ago
[deleted]
dragontamer 3y ago
https://www.felixcloutier.com/x86/gf2p8affineqb https://www.felixcloutier.com/x86/gf2p8affineqb VGF2P8AFFINEQB zmm1{k1}{z}, zmm2, zmm3/m512/m64bcst, imm8 So there are 3x AVX512 registers + 1x 8-bit immediate. zmm1 seems to be the output register, the 64x 8-bit results. zmm2 seems to be the "64x parallel x" in Ax + b. zmm3 seems to be a 8x parallel A-matrix. I'm not sure how these 8x A-matrices line up to the final result, but perhaps 8-at-a-time is the logical conclusion. (outputs values#0-7 use A[0] matrix. Output#8-15 uses A[1] matrix?) imm8 seems to be "b" in the Ax + b formula, and is shared with all operations. -------- EDIT: I think I get it now. Edited this post with my latest understanding.
- dzaima 3y ago
  Yeah the edited version is correct; it matches up each group of eight "x" values with one "A" matrix (such that, in the bitwise representation of the arguments, there's no data transfer happening across 64-bit blocks; this ends up quite limiting if you want different matrices, so most of the uses are ones where the matrix is the same for all elements).
  - dragontamer 3y ago
    This is nuts. https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html#text=AFFINE%2520&ig_expand=3657 https://www.intel.com/content/www/us/en/docs/intrinsics-guid... Intel's documentation is claiming 0.5 CPI, or a bandwidth of 2x of these operations per clock tick. I mean, forget about bit-shuffling or permuting. I feel like with the right configuration, you can operate 512-bits of CRC32 calculations in parallel, maybe in like 3 or 4 instructions (or ~2 clock ticks) or something incredibly fast. > this ends up quite limiting if you want different matrices, so most of the uses are ones where the matrix is the same for all elements Elliptical Curves is the obvious use case. CRC is one immediate use where all the matricies are the same (and linear in the GF-field), albeit the reduction needs to be done "somehow" but that can be figured out in a later operation... probably... AES encryption is operated over 4x sets of GF(2^8). I know that AES is already got its own instruction but a full software implementation of the GF-operations behind AES might be possible with this. -------------- I dunno, there's a lot of things I see already as immediately applicable where the "A" matrix is nearly constant across all elements. And for those where A isn't constant, pipelined operation is obvious. 8x different "A" matrixies means that we can build a "pipeline" where we can AVX512-shift the bytes down by 8 as well each clock tick, and build an 8x-deep pipeline and apply those 8x A matricies in parallel while consuming 64-bytes per clock-tick, while performing 512-bit worth of operation per clock tick (no, 1024-bits because Intel chips support 2x such operations per clock tick). Pipelining, full parallelization, etc. etc. So many architectures are possible with this spec. IMO, it shows that Intel knows what they're doing with these intrinsic, and I think this is something now GPU can accomplish yet. Truly an advantage to Intel chips only. Very nice instruction. The practical benefits though (Intel-only, exceptionally arcane with very few programmers who can work with, etc. etc.) may make it a dead instruction though. But I'm sure some wizard out there is going to do something cool with this instruction over the next 5 years. (It'd probably take weeks of practice on some practice problem just to learn how to use this instruction correctly, lol)
gpderetta 3y ago
Thank. Seems a very powerful operation and googling around it seems to be usable for all kind of bit tricks.