24

问题

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

备择方案

以下是我到目前为止想到的替代方案：

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

    我有点担心系统熵池耗尽的情况，因为我不知道系统内部 PRNG 是如何运行的。/dev/urandom由于使用 Mersenne Twister 本身的事实，我是否会意外地获得准确识别 Mersenne Twister 连续状态的连续种子？可能与我对下一点的担忧密切相关。

  2. 从第一个中播种一个 PRNG，/dev/urandom另一个从第一个中播种。

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

  3. 从一开始就用非梅森信息播种其他人。

    由于使用相同的算法来生成随机数和生成初始种子感觉好像是个坏主意，所以我考虑引入一些不依赖于 Mersenne Twister 算法的元素。例如，我可以将线程 id 异或到初始种子向量的每个元素中。这会让事情变得更好吗？

  4. 在线程之间共享一个 PRNG。

    这将确保只有一个序列具有 Mersenne Twister 的所有已知和理想特性。但是控制对该生成器的访问所需的锁定开销确实让我有些担心。由于我没有发现相反的证据，我假设我作为图书馆用户将负责防止对 PRNG 的并发访问。

  5. 预先生成所有随机数。

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

问题

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

你知道我的哪些担忧是有道理的，哪些仅仅是因为我对事情的实际运作缺乏洞察力吗？

4

8 回答 8

7

我会选择＃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_devicepull实现。/dev/urandom如果它默认使用 /dev/urandom ，那么通常你可以说std::random_device("/dev/random")是否要使用 /dev/random 。

于 2013-02-17T18:14:35.937 回答
5

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

但是我会选择#5。如果它有效，那很好。如果没有，您仍然可以优化它。

关键是创建一个好的PRNG 比人们想象的要困难得多。对于线程应用程序来说，一个好的 PRNG 很可能还有待研究。

如果 CPU 的数量足够低，您可以跳过蛙跳。例如，如果您有 4 个核心，则使用相同的值初始化所有核心，但将核心 1 PRNG 提前 1、#2 和 #3 提前 3。然后在需要新数字时总是提前 4 步。

于 2013-02-17T17:47:42.083 回答
3

我会使用一个实例来播种其他实例。我很确定你可以很容易地安全地做到这一点。

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

种子线 1 与 1，种子线 2 与 2，依此类推。

如果您需要 monte carlo，这将为您提供可重复的结果，易于跟踪和实施。

于 2013-02-17T21:05:53.543 回答
2

请看以下论文：伪随机数生成器的动态创建及其实现：Dynamic Creator。它解决了这个确切的问题。

于 2013-02-17T17:44:28.853 回答
2

如果您真的想在数学上正确，请使用 SFMT 算法作者提供的跳转函数。跳转功能保证两个不同 PRNG 流之间的最小序列数。

然而，实际上，一个 /dev/urandom 初始化就足够了。

于 2018-02-23T03:26:51.320 回答
1

我会说＃3是赢家。使用 processID 或 threadID 之类的东西为每个线程播种；虽然从技术上讲，您可能会重叠，但这种可能性极小。一旦你离开个位数，即使是连续的数字也不应该与种子相关（我不知道 Twister 算法，但我见过的最差的 PRNG 高于 7）。与大多数 PRNG 方程的范围相比，一百万个 PRNG 并不算多。

最后，您可以相当轻松地进行检查。检查每个线程生成的最后一个种子与每个其他线程中的所有数字。如果种子出现在线程中，则检查之前在每个线程中生成的数字；如果它们也匹配，那么您就会发生冲突，需要重新播种您的流并重试。

于 2013-02-17T17:41:03.227 回答
1

有一个实现（和已发表的论文）专门涉及使用 Mersenne Twister 进行并行计算。它是由 MT 的原始作者编写的。他们将其称为“Dynamic Creator”，可以在这里找到：

http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/DC/dc.html

那将是研究您对 MT19937 的具体用法的好地方，尤其是那里的论文。

于 2013-03-13T11:36:00.943 回答