多线程的随机数
问题
我打算为Linux编写一个C++11应用程序，它基于大约100万个伪随机32位数字进行一些数值模拟(而不是加密)。为了加快速度，我想使用桌面CPU的所有内核在并行线程中执行模拟。我想使用boost提供的Mersenne mt19937作为PRNG，而且出于性能考虑，我想每个线程应该有一个这样的PRNG。现在，我不确定如何为它们添加种子，以避免在多个线程中产生相同的随机数子序列。
备选方案
以下是我到目前为止所想到的其他选择：
- 为独立于
/dev/urandom的每个线程设置PRNG种子。 当系统熵池耗尽时，我有点担心，因为我不知道系统内部PRNG是如何工作的。由于/dev/urandom使用的是Mersenne本身，我是否会意外地得到准确识别Mersenne的连续状态的连续种子？可能与我对下一点的担忧密切相关。 - 从
/dev/urandom中培育一种PRNG，从第一种种开始另一种。 基本上也是同样的问题:使用一个PRNG来种子另一个使用相同的算法是好的还是坏的？换句话说，从mt19937读取625 32位整数是否直接对应于mt19937生成器在此生成过程中的任何时刻的内部状态？ - 用非Mersenne信息从一开始就给其他人播种。 由于使用相同的算法来生成随机数和生成初始种子，我觉得这可能是个坏主意，所以我考虑引入一些不依赖Mersenne算法的元素。例如，我可以将线程id异或到初始种子向量的每个元素中。这能让事情变得更好吗？
- 在线程间共享一个PRNG。 这将确保只有一个序列，所有已知的和可取的性质的默森扭曲。但控制对该生成器的访问所需的锁定开销确实让我有些担心。由于我没有发现相反的证据，我假设作为图书馆用户，我将负责防止并发访问PRNG。
- 预生成所有随机数。 这将使一个线程预先生成所有所需的1M随机数字，稍后将由不同的线程使用。与整个应用程序相比，4M的内存需求较小。在这种方法中，我最担心的是产生随机数本身并不是并发的。这种方法的规模也不太大。
问题
你会建议这些方法中的哪一种，为什么？还是你有不同的建议？
你知道我的哪些担忧是合理的，哪些仅仅是因为我缺乏对事物实际运作方式的洞察力？
回答 8
Stack Overflow用户
发布于 2013-02-17 17:44:50
我会用一个例子来播种其他的。我很肯定你可以很安全地做到这一点。
- 即使状态空间中的小变化也会导致下游相当大的变化--如果您能够确保它们没有完全相同的起始空间(并且没有相同的状态前缀)，我就不会担心产生相同的数字。例如，仅使用值1、2、3来为三个线程添加种子就可以了--甚至不需要为整个空间添加种子。另一个优势是:通过使用清晰可预测的种子，你很容易就会怀疑你在挑选任何跑动的想法(假设你想证明什么)。
- 这是微不足道的种子方式，意味着结果的“孩子”是高度不相关的。只是以一种广度的方式迭代；也就是说，如果你想要种子N x 623 int值，不要按顺序播种623值，而是选择第一个N并分发，然后再分配下一个N等等。即使播种机和子节点之间有某种相关性，各个子节点之间的相关性应该实际上是不存在的--这就是您所关心的。
- 我更喜欢在可能的情况下允许确定性执行的算法，因此依赖于urandom是没有吸引力的。这使得调试更容易。
- 最后，显然是-测试。这些PRNG是相当健壮的，但无论如何，眼球的结果和做一些相关测试的灵感来自于你所模拟的。大多数问题都应该是显而易见的--要么你的种子很糟糕，而且有明显的重复子序列，你的种子很好，然后质量就取决于PRNG的限制。
- 对于最终的执行，在完成测试之后，您可以使用urandom来创建623个状态值中的第一个状态值，以获得心灵的安宁和/或线程ID。
Stack Overflow用户
发布于 2013-02-17 18:14:35
我会跟着#1，种下每一颗来自于核武器的种子。这确保了各州是完全独立的(就种子数据而言)。通常，除非您有许多线程，否则会有大量的熵可用。而且，根据/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，那么如果您想使用/dev/ std::random_device("/dev/random")，通常可以使用它。
Stack Overflow用户
发布于 2013-02-17 17:47:42
您可以使用具有不同代数结构的PRNG来为不同的PRNG注入种子。例如，一些MD5散列序列。
但是我会选择第五种，如果它能用的话，那就很好了。如果没有，你仍然可以优化它。
关键是创建一个好的 PRNG比人们可能预期的要困难得多。一个好的线程应用程序的PRNG很可能仍然是研究的对象。
如果CPU的数量足够低，你就可以跳过青蛙了。例如，如果你有4个核心，用相同的值初始化所有，但是将核心1 PRNG提前1，2按3，然后当你需要一个新的数字时，总是提前4步。
https://stackoverflow.com/questions/14923902
复制相似问题
腾讯云开发者
