熵和并行随机数生成器种子

Question

我有一个循环，我会给一些点添加噪音；这些点稍后将作为一些统计测试的基础。所涉及的数据集非常大，因此我想使用openMP并行化以加快速度。问题出现在当我想要拥有多个PRNG时。我有自己的PRNG类，基于NR的模数方法（我认为是rand4），但我不确定如何正确地种子化PRNG以确保适当的熵。

通常情况下，我会做这样的事情：

prng.initTimer();

但是如果我有一个PRNG数组，每个工作线程一个，那么我不能简单地在每个实例上调用initTimer -- 计时器可能不会改变，并且计时器的接近可能引入相关性。

我需要保护自然相关性，而不是恶意攻击者（这是实验数据），因此我需要一种安全的方法来种子化RNG数组。

我考虑过简单地使用

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

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

- CppUser123

---

你应该在这里添加 [parallel] 标签。 - Flash

使用NV 第三版伪随机数生成器，或者至少使用Mersenne Twister。NR2中的那些是糟糕的。有很多文献介绍了好的选择，可以使用多个种子来避免相关性问题。 - Alexandre C.

@Alexandre C. NV 3rd edition是什么？我同意Numerical recipes中的PRNGs很糟糕（这就是你所说的NR吧？）。 - pic11

@pic11：哎呀，我是说NR。第二版的生成器非常过时而且太复杂了。第三版的生成器很好。Mersenne Twister 介于两者之间，它是一个很好的伪随机数生成器但仍然复杂，并且自那以后有更好的伪随机数生成器被发明出来。 - Alexandre C.

Answer 1

种子 PRNG 并不一定会创建独立的流。您应该仅对第一个实例（称为参考）进行种子，并通过快速转发参考实例来初始化其余实例。这仅在您知道每个线程将使用多少随机数并且快速转发算法可用时才有效。

我不太了解您的 rand4（谷歌搜索，但没有找到具体信息），但您不应该假设只要种子就可以创建独立的流。您可能希望使用不同（更好的）PRNG。看看 WELL。它快速，具有良好的统计特性，并由知名专家开发。 WELL 512 和 1024 是可用的最快的 PRNG 之一，两者都具有巨大的周期。您可以使用不同的种子初始化几个 WELL 实例，以创建独立的流。由于巨大的周期，几乎没有机会使您的 PRNG 生成重叠的随机数流。

如果你的伪随机数生成器（PRNGs）经常被调用，请注意虚假共享。这篇Herb Sutter's文章解释了虚假共享如何影响多核性能。将多个PRNGs打包成连续的数组几乎是引起虚假共享的完美配方。为了避免虚假共享，可以在PRNGs之间添加填充或在堆/自由存储区上分配PRNGs。在后一种情况下，每个RNG都应该使用某种对齐的分配器单独分配。你的编译器应该提供一个对齐的malloc版本。查看文档（实际上谷歌搜索比阅读手册更快）。Visual C++有_aligned_malloc，GCC有memalign和posix_memalign。对齐值必须是CPU缓存行大小的倍数。通常的做法是沿着128字节边界对齐。为了获得可移植的解决方案，可以使用TBB的缓存对齐分配器。

- pic11

Answer 2

我认为这取决于您的伪随机数生成器（PRNG）的属性。通常 PRNG 的弱点是低位熵和前 n 个值的熵较低。因此，我认为您应该检查您的 PRNG 是否存在此类弱点，并相应地更改代码。

也许一些 diehard tests 可以提供有用的信息，但您也可以检查前 n 个值及其统计特性（如总和和方差），并将它们与预期值进行比较。

例如，对 PRNG 进行种子处理，并对 PRNG 的前 100 个值进行模 11 求和，重复 R 次。如果总和与预期值（5*100*R）非常不同，则说明您的 PRNG 存在上述一项或两项弱点。

不了解 PRNG 的情况下，我会选择使用类似以下的东西：

prng[0].initTimer();
// Throw the first 100 values away
for(int i=1; i < 100; i++)
   prng[0].getRandNum();
// Use only higher bits for seed values (assuming 32 bit size)
for(int i=1; i<numRNGs; i++)
   prng[i].init(((prng[0].getRandNum() >> 16) << 16)
               + (prng[0].getRandNum() >> 16));

当然，这些都是关于伪随机数生成器的猜测。如果使用理想的伪随机数生成器，您的方法应该可以正常工作。

- schnaader

---

通常 PRNG 的弱点是低位熵和前 n 个值的熵较低：但现在不再是这样了。 - Alexandre C.

感谢这个持久的链接。我运行了前90个测试，得到了两个WEAKs和其余的都是PASSes，没有丢弃任何数据。我会采用您的舍弃选项来运行，但为了可移植性，我可能会避免位移操作。 - CppUser123

@CppUser123 你测试了所有的伪随机数生成器吗？ - Null Set

当然，这些都是关于PRNG的猜测。确实。 - pic11

不，我后来才看到你的回复。你说得很有道理——我可能要么（1）不并行化它，要么（2）编写/dev/random和Windows加密API实现，因为我的应用程序是多平台的。老实说，这只是整个应用程序中非常小的一部分，努力/回报比可能不在那里。 - CppUser123

Answer 3

如果您使用相同类型的 PRNG 的数字序列来种子化您的 PRNGs，它们将会产生相同的数字序列，每个序列都比前一个偏移一个。如果您想要它们产生不同的数字，您需要使用来自不同 PRNG 的伪随机数序列来种子化它们。

或者，如果您在类 Unix 系统上有 /dev/random，您可以从该设备中读取一系列随机数作为您的种子。

- Null Set