3 ms·

There are 4 parts. Spoiler: I went to AVX and beat the state of the art by 1.8x Also, doing it on the GPU is worth it, if you do large batches.

dragontamer 1y ago
As far as fast RNGs available, Imma just plug an old, incomplete, weekend project for ya.... https://github.com/dragontamer/AESRand https://github.com/dragontamer/AESRand Especially because you are already in the AVX domain, a fast AVX RNG that uses like 3 registers should be useful to ya. .... Yeah I'm pretty sure aesenc these days has more throughout than multiply. (Edit: aesenc, at least a singular round, is largely a 32-bit operation and this has less complexity than a 64-bit multiply. Yeah I know it's over 128-bits but seriously, it's surprising how 'little' AES actually shuffles bits around per round). If you are fine with an inferior RNG, you probably can skip one or two instructions I did there. But the 'two rounds of AES' seems to be the minimum to pass PractRand or BigCrush. ------- Today, AES on AVX512 can perform 4x AES in parallel over all 512 bits. But the overall technique I did back then should allow for arbitrary skipping ahead as well. (Ex: thread#0 starts with iteration #0. Thread#1 starts with iteration #1000000. Etc. etc. with consistency because my increment function is simple 64-bit adds, a 64-bit multiply will skip forward easily) Alas, I don't think AESENC was ever ported to ymm registers and this your choices are 128-bit AESRAND vs 512-bit AESRAND.
- jesse__ 1y ago
  Hey, thanks for the comment! I did actually take a look at the aes instructions and came to the conclusion that they are in fact faster than the hash I used, but I think I'd decided I would have to swizzle the data in a way that was a pain because of how the aes mixdown works (ie it mixes across lanes, so I would have to change the output pattern, if that makeshifts sense) Maybe I'll dust it off one day and try again. That seems like it could be an easy win.
  - dragontamer 1y ago
    > but I think I'd decided I would have to swizzle the data in a way that was a pain because of how the aes mixdown works (ie it mixes across lanes, so I would have to change the output pattern, if that makeshifts sense) 100% agree. I solved this with a 64-bit x2 SIMD add instruction. State += 0x0305071113171923, which ensures a 1-bit 'carry bit' dependency as well so we have (barely) enough data mixing for lots of cool entropy effects. Because this is an odd number (bottom bit is 1), it cycles every 2^64, which should be a sufficient cycle length for most simulations. That 1-bit difference was enough to then pass PractRand and BigCrush. Don't swizzle the bits. Just add a number across all 128-bits (as 2x 64-bit adds) and bam. We get a lot of lovely RNG properties thanks to AES mixing. It's not 'purely' aesenc. I did a few little tidbits that fixed all the problems of AES data mixing. ------ The real fun part is that the latency/dependency limitation on my code is this Add instruction. The AES stuff is done in parallel later and thus easily parallelizes to modern 4x512-bit AES as is available on Zen5. (Maybe the compilers won't see it yet, but it's bloody obvious for humans to see it IMO). IE: the critical path of my code is: simd-add state, 0x030507..... State gets SSA'd by the out of order system on the processors and thus future iterations of the RNG loop can execute in parallel.
    - jesse__ 1y ago
      That sounds really great. I'm away from the office for the week but when I'm back I'll take a closer look and maybe squeeze some more juice out of it :)

dragontamer 1y ago

As far as fast RNGs available, Imma just plug an old, incomplete, weekend project for ya.... https://github.com/dragontamer/AESRand https://github.com/dragontamer/AESRand Especially because you are already in the AVX domain, a fast AVX RNG that uses like 3 registers should be useful to ya. .... Yeah I'm pretty sure aesenc these days has more throughout than multiply. (Edit: aesenc, at least a singular round, is largely a 32-bit operation and this has less complexity than a 64-bit multiply. Yeah I know it's over 128-bits but seriously, it's surprising how 'little' AES actually shuffles bits around per round). If you are fine with an inferior RNG, you probably can skip one or two instructions I did there. But the 'two rounds of AES' seems to be the minimum to pass PractRand or BigCrush. ------- Today, AES on AVX512 can perform 4x AES in parallel over all 512 bits. But the overall technique I did back then should allow for arbitrary skipping ahead as well. (Ex: thread#0 starts with iteration #0. Thread#1 starts with iteration #1000000. Etc. etc. with consistency because my increment function is simple 64-bit adds, a 64-bit multiply will skip forward easily) Alas, I don't think AESENC was ever ported to ymm registers and this your choices are 128-bit AESRAND vs 512-bit AESRAND.

jesse__ 1y ago
Hey, thanks for the comment! I did actually take a look at the aes instructions and came to the conclusion that they are in fact faster than the hash I used, but I think I'd decided I would have to swizzle the data in a way that was a pain because of how the aes mixdown works (ie it mixes across lanes, so I would have to change the output pattern, if that makeshifts sense) Maybe I'll dust it off one day and try again. That seems like it could be an easy win.
- dragontamer 1y ago
  > but I think I'd decided I would have to swizzle the data in a way that was a pain because of how the aes mixdown works (ie it mixes across lanes, so I would have to change the output pattern, if that makeshifts sense) 100% agree. I solved this with a 64-bit x2 SIMD add instruction. State += 0x0305071113171923, which ensures a 1-bit 'carry bit' dependency as well so we have (barely) enough data mixing for lots of cool entropy effects. Because this is an odd number (bottom bit is 1), it cycles every 2^64, which should be a sufficient cycle length for most simulations. That 1-bit difference was enough to then pass PractRand and BigCrush. Don't swizzle the bits. Just add a number across all 128-bits (as 2x 64-bit adds) and bam. We get a lot of lovely RNG properties thanks to AES mixing. It's not 'purely' aesenc. I did a few little tidbits that fixed all the problems of AES data mixing. ------ The real fun part is that the latency/dependency limitation on my code is this Add instruction. The AES stuff is done in parallel later and thus easily parallelizes to modern 4x512-bit AES as is available on Zen5. (Maybe the compilers won't see it yet, but it's bloody obvious for humans to see it IMO). IE: the critical path of my code is: simd-add state, 0x030507..... State gets SSA'd by the out of order system on the processors and thus future iterations of the RNG loop can execute in parallel.
  - jesse__ 1y ago
    That sounds really great. I'm away from the office for the week but when I'm back I'll take a closer look and maybe squeeze some more juice out of it :)