使用 AVX2 在给定范围内生成随机数，比 SVML _mm256_rem_epu32 余数更快？

Question

我目前正在尝试使用 AVX2 实现 XOR_SHIFT 随机数生成器，它实际上非常简单且非常快速。但是我需要能够指定一个范围。这通常需要取模。

这对我来说是一个主要问题，原因有两个：

将 _mm256_rem_epu32() / _mm256_rem_epi32() SVML 函数添加到我的代码中需要运行我的循环时间从大约 270 毫秒减少到 1.8 秒。哎哟！
SVML 仅适用于 MSVC 和英特尔编译器

使用 AVX2 进行取模是否有明显更快的方法？

非矢量代码：

 std::srand(std::time(nullptr));
 std::mt19937_64 e(std::rand());

 uint32_t seed = static_cast<uint32_t>(e());

 for (; i != end; ++i)
 {
      seed ^= (seed << 13u);
      seed ^= (seed >> 7u);
      seed ^= (seed << 17u);

      arr[i] = static_cast<T>(low + (seed % ((up + 1u) - low)));
 }//End for

向量化：

  constexpr uint32_t thirteen = 13u;
  constexpr uint32_t seven = 7u;
  constexpr uint32_t seventeen = 17u;

  const __m256i _one = _mm256_set1_epi32(1);
  const __m256i _lower = _mm256_set1_epi32(static_cast<uint32_t>(low));
  const __m256i _upper = _mm256_set1_epi32(static_cast<uint32_t>(up));
                           
  __m256i _temp = _mm256_setzero_si256();
  __m256i _res = _mm256_setzero_si256();
                                                            
  __m256i _seed = _mm256_set_epi32(
       static_cast<uint32_t>(e()),
       static_cast<uint32_t>(e()),
       static_cast<uint32_t>(e()),
       static_cast<uint32_t>(e()),
       static_cast<uint32_t>(e()),
       static_cast<uint32_t>(e()),
       static_cast<uint32_t>(e()),
       static_cast<uint32_t>(e())
  );

  for (; (i + 8uz) < end; ++i)
  {
       //Generate Random Numbers
       _temp = _mm256_slli_epi32(_seed, thirteen);
       _seed = _mm256_xor_si256(_seed, _temp);

       _temp = _mm256_srai_epi32(_seed, seven);
       _seed = _mm256_xor_si256(_seed, _temp);

       _temp = _mm256_slli_epi32(_seed, seventeen);
       _seed = _mm256_xor_si256(_seed, _temp);

       //Narrow
       _temp = _mm256_add_epi32(_upper, _one);
       _temp = _mm256_sub_epi32(_temp, _lower);
       _temp = _mm256_rem_epu32(_seed, _temp); //Comment this line out for a massive speed up but incorrect results
       _res = _mm256_add_epi32(_lower, _temp);                                        

       _mm256_store_si256((__m256i*) &arr[i], _res);
  }//End for

Answer 1

如果您的范围小于 1670 万，并且不需要加密级别的分布质量，则缩小这些随机数的一种简单且相对快速的方法是 FP32 数学。

这是一个未经测试的示例。下面的函数采用带有随机位的整数向量，并将这些位转换为 [ 0 .. range - 1 ] 区间内的整数。

// Ideally, make sure this function is inlined,
// by applying __forceinline for vc++ or __attribute__((always_inline)) for gcc/clang
inline __m256i narrowRandom( __m256i bits, int range )
{
    assert( range > 1 );

    // Convert random bits into FP32 number in [ 1 .. 2 ) interval
    const __m256i mantissaMask = _mm256_set1_epi32( 0x7FFFFF );
    const __m256i mantissa = _mm256_and_si256( bits, mantissaMask );
    const __m256 one = _mm256_set1_ps( 1 );
    __m256 val = _mm256_or_ps( _mm256_castsi256_ps( mantissa ), one );

    // Scale the number from [ 1 .. 2 ) into [ 0 .. range ),
    // the formula is ( val * range ) - range
    const __m256 rf = _mm256_set1_ps( (float)range );
    val = _mm256_fmsub_ps( val, rf, rf );

    // Convert to integers
    // The instruction below always truncates towards 0 regardless on MXCSR register.
    // If you want ranges like [ -10 .. +10 ], use _mm256_add_epi32 afterwards
    return _mm256_cvttps_epi32( val );
}

内联时，应该编译成4条指令，vpand、vorps、vfmsub132ps、vcvttps2dq可能比_mm256_rem_epu32快一个数量级在你的例子中。

使用 AVX2 在给定范围内生成随机数，比 SVML _mm256_rem_epu32 余数更快？

Generate random numbers in a given range with AVX2, faster than SVML _mm256_rem_epu32 remainder?

c++

random

simd

modulo

avx