c++ - 熵和并行随机数生成器播种

Question

我有一个循环，我在其中向某些点添加噪声；这些后来被用作一些统计测试的基础。

涉及的数据集非常大，所以我想使用 openMP 将其并行化以加快处理速度。当我想要多个 PRNG 时，问题就出现了。我有自己的基于 NR 模方法(我认为是 rand4)的 PRNG 类，但我不确定如何正确播种 PRNG 以确保适当的熵

通常我会做这样的事情

prng.initTimer();

但是如果我有一组 prng，每个工作线程一个，那么我不能简单地在每个实例上调用 initTimer —— 计时器可能不会改变，计时器关闭可能会引入相关性。

我需要防止自然相关性，而不是恶意攻击者(这是实验数据)，所以我需要有一种安全的方法来为 rng 数组做种。

我想到了简单地使用

prng[0].initTimer()
for(int i=1; i<numRNGs; i++)
     prng[i].init(prng[0].getRandNum());

然后调用我的循环，但我不确定这是否会在模方​​法中引入相关性。

Answer 1

播种 PRNG 不一定会创建独立的流。您应该只播种第一个实例(称为引用)并通过快速转发引用实例来初始化其余实例。这仅在您知道每个线程将消耗多少个随机数并且快速转发算法可用时才有效。

我对你的 rand4 了解不多(用谷歌搜索，但没有找到任何具体信息)，但你不应该假设仅通过播种就可以创建独立的流。您可能想使用不同的(更好的)PRNG。看看WELL .它速度快，具有良好的统计特性，由知名专家开发。 WELL 512 和 1024 是可用的最快的 PRNG 之一，并且都有很长的周期。您可以使用不同的种子初始化多个 WELL 实例，以创建独立的流。由于周期较长，您的 PRNG 生成随机数重叠流的可能性几乎为零。

如果您的 PRNG 被频繁调用，请提防虚假共享。这Herb Sutter's文章解释了错误共享如何破坏多核性能。将多个 PRNG 打包到一个连续的数组中几乎是错误共享的完美秘诀。为了避免虚假共享，要么在 PRNG 之间添加填充，要么在堆/空闲存储上分配 PRNG。在后一种情况下，应使用某种对齐分配器单独分配每个 RNG。您的编译器应该提供对齐 malloc 的版本。检查文档(好吧，谷歌搜索实际上比阅读手册更快)。 Visual C++ 有 _aligned_malloc，GCC 有 memalign 和 posix_memalign。 aliment 值必须是 CPU 缓存行大小的倍数。通常的做法是沿 128 字节边界对齐。对于可移植解决方案，您可以使用 TBB 的缓存对齐分配器。