多线程的随机数生成

Question

问题

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

备选方案

到目前为止，我想过以下替代方案：

1. 从 /dev/urandom 独立为每个线程提供 PRNG 的种子。

   我有点担心系统熵池耗尽的情况，因为我不知道系统内部PRNG的操作方式。是否有可能由于 /dev/urandom 使用的是 Mersenne Twister 本身而意外获得连续的种子，这些种子恰好标识 Mersenne Twister 的连续状态？这与我对下一个点的关注很相关。

2. 从 /dev/urandom 中提取一个 PRNG 的种子，然后使用该种子生成其他 PRNG 的种子。

   基本上是相同的担忧：使用一个PRNG来为另一个使用相同算法的PRNG提供种子是好事还是坏事？或换句话说，在此过程中从mt19937读取625个32位整数是否直接对应于mt19937生成器在任何时刻的内部状态？

3. 使用来自第一个 PRNG 的非Mersenne信息为其他 PRNG 提供种子。

   采用同一算法生成随机数和初始种子可能不是一个好主意，因此我考虑引入一些不依赖于Mersenne Twister算法的元素。例如，可以将线程ID与每个初始种子向量元素进行异或运算。这样做是否会改善情况？

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

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

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

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

问题

你推荐哪种方法，为什么？或者你有其他建议吗？

你知道我的哪些担忧是合理的，哪些只是由于我对事情实际运作的了解不足而产生的吗？

- MvG

---

我以前也有同样的问题。https://dev59.com/oG7Xa4cB1Zd3GeqPoU4v 幸运的是，我在Java上。 - YankeeWhiskey

@YankeeWhiskey，那里被接受的答案看起来像这里的选项3：您可以从使用平台相关熵源的SecureRandom生成的UUID中获取种子，而不仅仅是Mersenne Twister。 - MvG

所有建议的方法都会导致生成重复的随机数。一般来说，您要求从可能的2 ** 32个数字中获得2 * 20个“随机”数字。这是很多的要求，因此您需要重新考虑您想要从1百万个随机32位整数中获得的属性。如果唯一性是其中之一，那么这些方法都不会起作用。 - President James K. Polk

@GregS，个别重复的数字不会让我担心。我可能应该指定一个子序列长度的下限。我认为，由两个线程完全复制的10个数字的序列可能会开始给我带来麻烦。但是，2 ** 320位的偶然巧合似乎是如此不太可能，以至于我认为一旦两个线程有了这么多共同点，它们很可能也有更多的共同点。 - MvG

好的，听起来你已经考虑清楚了，这很好。我担心的实际上是生日悖论的结果。只要一些重复不会对你的算法造成致命影响，那么你应该没问题。 - President James K. Polk

Answer 1

我会选择第一种方式，从urandom中为每个伪随机数生成器提供种子。这样可以确保状态是完全独立的（只要种子数据是独立的）。通常情况下，除非您有很多线程，否则将有足够的熵可用。此外，根据用于/dev/urandom的算法，您几乎肯定不需要担心它。

因此，您可以使用以下类似的代码来创建每个伪随机数生成器：

#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。

- bames53

---

感谢您不仅给出了选择的建议，还指出了我从boost（mt19937）导入或自己实现的random_device在C++11中已有标准化，尽管API有些不同。这可能有助于避免依赖于boost。 - MvG

提醒我，当我第一次检查（好几年前，我想）各种编译器没有使用相同的mt19937实现（相同的种子产生不同的结果），因此使用boost更容易复制。我想知道现在情况如何。 - Eamon Nerbonne

引擎需要产生相同的结果，但是分发版本不需要。 - bames53

你是完全正确的：我刚刚检查了，确实针对未经加工的mt19937生成器，例如MSC和GCC返回相同的序列，但是使用该生成器进行均匀分布（以及其他分布）会产生不同的结果。 但是，这仍然可能存在问题：如果您想在某个分布下重现RNG序列，则无法使用内置的c++11库。 - Eamon Nerbonne

顺便提一下，MSC还不支持return std::mt19937{q};构造语法。 - Eamon Nerbonne

Answer 2

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

但是，我会选择方案#5。如果它能正常工作，那就很好。如果不能，您仍然可以对其进行优化。

关键是创建一个良好的PRNG比人们想象的要困难得多。面向线程应用程序的优秀PRNG很可能仍是研究对象。

如果CPU数量足够少，您可以使用跳跃式的方法。例如，如果您有4个核心，则将所有核心初始化为相同的值，但是将第1个PRNG向前推进1步，第2个PRNG向前推进2步，第3个PRNG向前推进3步。然后，在需要新数字时始终推进4步。

- Udo Klein

Answer 3

将线程1种子设置为1，将线程2种子设置为2，以此类推。

如果需要使用蒙特卡罗方法，这样可以得到可重复的结果，易于跟踪和实现。

- Eterm

---

这是一个相当不错且非常简单的解决方案。 - Eamon Nerbonne

Answer 4

我建议您使用一个实例来为其他实例提供种子。我相信您可以很容易地安全地执行此操作。

即使状态空间发生微小变化，也会对下游产生相当大的影响——如果您可以确保它们的起始空间不完全相同（并且没有相同的状态前缀），那么我不会担心生成相同的数字。例如，只使用值1,2,3来为三个线程提供种子就可以正常工作——你甚至不需要为整个空间提供种子。另一个好处是通过使用明显可预测的种子，您可以轻松驳斥您在选择任何运行时选择性开选项的想法。（假设您试图证明某些东西）。

以广度优先的方式迭代非常容易实现高度无关性的“子级”。例如，如果要为N x 623 int值提供种子，则不要连续为623个值提供种子，而是选择前N个并分配，然后选择下一个N个等等。即使在seeder和children之间存在一些相关性，各个children之间的相关性几乎不存在-这就是您所关心的。

我更喜欢尽可能使用允许确定性执行的算法，因此依赖于urandom不太好。这样可以更容易地进行调试。

最后，显然-测试。这些PRNG非常强大，但请务必查看结果，并根据您正在模拟的内容进行一些相关性测试。大多数问题应该很明显-要么您已经糟糕地提供了种子并且有明显的重复子序列，您已经种植得很好，然后质量由PRNG限制所决定。

对于最终执行，在测试完成后，您可以使用urandom或线程ID来为623个状态值中的第一个提供种子，以安心。

- Eamon Nerbonne

---

在行为方面，以并行化方式进行种子初始化听起来非常有趣。但实现起来可能有些麻烦，因为我不能简单地将一个伪随机数生成器作为种子传递给其他所有生成器。但是我想我可以事先生成8 * 623字节的矩阵，转置该矩阵并将结果数组传递给构造函数或种子函数。或者像你建议的那样，只使用一个整数作为种子。关于调试的观点也很有价值。 - MvG

是的，转置会起作用。或者只需使用2个嵌套循环-实际上你不需要并行执行此操作，因为完成后你始终可以随后交出 PRNG。 - Eamon Nerbonne

我不考虑并行初始化。但是使用boost进行种子化步骤似乎是一个原子操作；我无法直接为每个值提供种子。因此，我必须找到一种方法，在单个调用中提供整个状态向量。 - MvG

当然，由于API限制，您需要在传递它们之前收集这些值 - 但这不是一个严重的障碍，对吧？ - Eamon Nerbonne

不，完全不是这样，但这意味着嵌套循环不能用于种子生成。它们可以用于生成（已转置的）矩阵。无论如何，这只是使实现变得有点比我想要的更长，但应该否则工作得非常好。 - MvG

Answer 5

请看下面的论文：动态生成伪随机数生成器和相应的实现：动态创建者。它解决了这个问题。

- NPE

---

听起来不错，不过在我真正阅读完这篇文章之前，我会保留我的投票。 - MvG

这些人绝对知道他们在谈论什么，因为Mersenne Twister也是基于他们的工作。感谢指引！使用他们的代码原样是一种可能性，而使用他们的代码来静态计算一堆（即预期核心数）mersenne_twister_engine的参数是另一种选择。 - MvG

Answer 6

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

但实际上，使用/dev/urandom初始化就足够了。

- jj1bdx

---

找到了http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/JUMP/index.html作为最有可能的指针。听起来不错。谢谢！ - MvG

Answer 7

我认为#3是胜利者。用类似进程ID或线程ID的东西种子每个线程;虽然在技术上可能会有重叠，但这是非常不可能的。即使连续的数字在超过单个数字时也不应该与种子相关(我不知道Twister算法，但我见过的最差的PRNG在7以上都很好)。一百万个PRNG对于大多数PRNG方程的范围来说并不算太多。

最后，你可以很容易地检查。检查每个线程生成的最后一个种子是否出现在其他线程的所有数字中。如果种子出现在线程中，则检查每个线程中先前生成的数字;如果它们也匹配，则表示发生了冲突，需要重新种子流并重试。

- Joe

Answer 8

有一种实现（并发表了论文），专门针对使用Mersenne Twister进行并行计算。它是由MT的原始作者开发的。他们将其称为“动态创建器”，可以在此处找到：

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

那将是一个非常好的地方，可以学习有关MT19937的具体用法，特别是那篇论文。

- Randy Howard

---

NPE的回答提供了几乎相同的信息，尽管它没有指出这些是原始的MT作者。 - MvG