AVX / SSE版xorshift128 +

我正在努力制作最快的高质量RNG。 阅读http://xorshift.di.unimi.it/,xorshift128 +似乎是一个不错的选择。 C代码是

#include  uint64_t s[ 2 ]; uint64_t next(void) { uint64_t s1 = s[ 0 ]; const uint64_t s0 = s[ 1 ]; s[ 0 ] = s0; s1 ^= s1 <> 17 ) ^ ( s0 >> 26 ) ) ) + s0; // b, c } 

我不是SSE / AVX专家,但我的CPU支持SSE4.1 / SSE4.2 / AVX / F16C / FMA3 / XOP指令。 你怎么能用这些来加速这段代码(假设你想要制作数十亿这样的随机数)以及在实践中这个加速的预期限制是多少?

XorShift确实是一个不错的选择。 它是如此的好,如此之快,需要如此少的状态,我很惊讶地看到这么少的采用。 它应该是所有平台上的标准生成器。 我已经在8年前自己实现了它,即使这样它也可以生成800MB / s的随机字节。

您不能使用向量指令来加速生成单个随机数。 这几条指令中的指令级并行性太少。

但是您可以轻松地加速生成N个数字,其中N是目标指令集的向量大小。 只需并行运行N个发电机。 保持N个生成器的状态并同时生成N个数字。

如果客户端代码一次需要一个数字,则可以保留N(或更多)数字的缓冲区。 如果缓冲区为空,则使用向量指令填充它。 如果缓冲区不为空,则只返回下一个数字。

对于其他可能会遇到这个问题的人,我认为这个C ++代码使用AVX2正确地实现了4个并行运行的xorshift128plus生成器:

 __m256i xorshift128plus_avx2(__m256i &state0, __m256i &state1) { __m256i s1 = state0; const __m256i s0 = state1; state0 = s0; s1 = _mm256_xor_si256(s1, _mm256_slli_epi64(s1, 23)); state1 = _mm256_xor_si256(_mm256_xor_si256(_mm256_xor_si256(s1, s0), _mm256_srli_epi64(s1, 18)), _mm256_srli_epi64(s0, 5)); return _mm256_add_epi64(state1, s0); } 

我使用的标量实现是:

 u64 xorshift128plus(u64 &state0, u64 &state1) { u64 s1 = state0; const u64 s0 = state1; state0 = s0; s1 ^= s1 << 23; // a state1 = s1 ^ s0 ^ (s1 >> 18) ^ (s0 >> 5); // b, c return state1 + s0; } 

这与xorshiftplus文章中的相同。 请注意,原始问题的右移常数与文中的右移常数不一致。