多个线程的随机数

Question

问题

我打算为Linux编写一个C++ 11应用程序,它根据大约一百万个伪随机32位数进行一些数值模拟(不是加密).为了加快速度,我想使用桌面CPU的所有内核在并行线程中执行模拟.我想使用mt19937由boost提供的Mersenne Twister 作为PRNG,我想由于性能原因,每个线程我应该有一个这样的PRNG.现在我不确定如何播种它们以避免在多个线程中生成相同的随机数子序列.

备择方案

以下是我到目前为止所考虑的替代方案:

1. 独立于每个线程为PRNG播种/dev/urandom.

   当系统熵池耗尽时,我有点担心,因为我不知道系统内部PRNG是如何运行的.我是否意外地获得连续的种子,这些种子准确地识别了Mersenne Twister的连续状态,因为/dev/urandom使用了Mersenne Twister本身？可能与我对下一点的担忧密切相关.

2. 种第一个PRNG /dev/urandom和第一个PRNG .

   基本上也是同样的问题:使用一个PRNG来播种另一个使用相同算法的PRNG是好还是坏？或者换句话说,在这一代中的任何时刻读取625个32位整数是否mt19937直接对应于mt19937发生器的内部状态？

3. 首先从非梅森信息中获取其他人的种子.

   由于使用相同的算法生成随机数并生成初始种子感觉某种方式可能是一个坏主意,我考虑引入一些不依赖于Mersenne Twister算法的元素.例如,我可以将线程id与初始种子向量的每个元素进行异或.这会让事情变得更好吗？

4. 在线程中共享一个PRNG.

   这将确保只有一个序列,具有Mersenne Twister的所有已知和期望的属性.但是控制对该生成器的访问所需的锁定开销确实让我有点担心.由于我没有发现任何相反的证据,我认为我作为图书馆用户将负责阻止对PRNG的并发访问.

5. 预生成所有随机数.

   这将有一个线程预先生成所有必需的1M随机数,稍后将由不同的线程使用.与整个应用程序相比,4M的内存要求会很小.在这种方法中最让我担心的是随机数本身的产生并不是并发的.整个方法也不能很好地扩展.

问题

你会建议哪种方法,为什么？或者你有不同的建议吗？

你知道我的哪些问题是合理的,而这仅仅是因为我对事情的实际运作缺乏洞察力？

Answer 1

我会选择#1,从urandom种下每个prng.这确保状态完全独立(就种子数据而言是独立的).除非你有很多线程,否则通常会有足够的熵可用.此外,根据用于/ dev/urandom的算法,您几乎肯定不必担心它.

因此,您可以使用以下内容创建每个prng:

#include <random>

std::mt19937 get_prng() {
    std::random_device r;
    std::seed_seq seed{r(), r(), r(), r(), r(), r(), r(), r()};
    return std::mt19937(seed);
}

您应该验证您的配置下的std::random_device拉动实现/dev/urandom.如果它默认使用/ dev/urandom,那么通常你可以说std::random_device("/dev/random")你是否想要使用/ dev/random.

Answer 2

您可以使用具有不同代数结构的PRNG来为不同的PRNG播种.例如MD5哈希的一些序列.

但是我会选择#5.如果它工作,那就没关系.如果没有,您仍然可以优化它.

关键在于创造一个好的 PRNG比人们预期的要难得多.线程应用程序的良好PRNG很可能仍然需要进行研究.

如果CPU的数量足够低,你就可以侥幸逃脱.例如,如果您有4个核心,则使用相同的值初始化所有核心,但是将核心1 PRNG提前1,将#2提前和#3提高3.然后在需要新数字时始终提前4步.

Answer 3

我会使用一个实例来为其他实例播种。我很确定您可以相当轻松地安全地完成此操作。

• 即使状态空间中的微小变化也会导致下游相当大的变化 - 如果您可以确保它们没有完全相同的起始空间（并且没有相同的状态前缀），我就不会担心产生相同的数字。例如，仅使用值 1、2、3 来播种三个线程就可以正常工作 - 您甚至不需要播种整个空间。另一个优点：通过使用明确可预测的种子，您可以轻松地否定您正在挑选任何运行的想法（假设您正在尝试演示某些内容）。
• 以某种方式播种是微不足道的，这意味着所得的“孩子”是高度不相关的。只需以广度优先的方式进行迭代即可；即，如果您想播种 N x 623 个 int 值，请不要按顺序播种 623 个值，而是选择第一个 N 并分配，然后分配下一个 N 等。即使播种者和子级之间存在某种相关性，各种孩子实际上应该不存在——而这就是你所关心的。
• 我更喜欢一种尽可能允许确定性执行的算法，因此依赖于 urandom 并不具有吸引力。这使得调试更加容易。
• 最后，很明显 - 测试。这些 PRNG 相当稳健，但无论如何都要关注结果并根据您所模拟的内容进行一些相关测试。大多数问题应该是显而易见的 - 要么你播种得不好并且有明显的重复子序列，要么你播种得很好，然后质量由 PRNG 限制决定。
• 对于最终执行，完成测试后，您可以使用 urandom 播种 623 个状态值中的第一个，以便安心和/或线程 ID。