c++ - 并行RNG中的错误

Question

我并行生成一系列随机数，但是根据调用的线程数，我会得到不同的结果。由此得出的结论是我在某个地方犯了错误!

注意我使用的是相同的种子，它与线程数无关-因此结果应该相同!

这是MWE，它会生成一个介于0..1之间的数字，如果生成的变量大于0.5，则会增加一个变量:

#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>

#include "omp.h"


#include <random>
typedef std::uniform_real_distribution<double> distr_uni;

#define max_threads 1

using namespace std;

int main(int argc, char* argv[])
{
    int reservoir_counter, accepted_tube=0;
    double r;

    omp_set_num_threads(max_threads);
    #pragma omp parallel
    {
        mt19937 eng(0);
        distr_uni uniform(0, 1);


        #pragma omp for private(r, reservoir_counter) reduction(+:accepted_tube)
        for(reservoir_counter=0; reservoir_counter<100000; reservoir_counter++)
        {
            r = uniform(eng);
            if(r>0.5)
            {
                accepted_tube++;
            }
        }
    }
    cout << accepted_tube << endl;
    return 0;
}

当我设置 max_threads=1时，我得到50027，但是当 max_threads=60(在支持它的机器上。)时，我得到50440。

有人可以发现我显然存在的错误吗？我已经在并行区域内声明了敏感的RNG及其引擎，因此我对错误可能在哪里并不十分清楚。

Answer 1

随机数生成器，特别是Mersenne Twister(上面您正在使用的)，通常是非常连续的生物。每次调用随机数生成器都有将种子更新为下一个内部状态的副作用。它们生成一个随机数序列，以便对RNG的第N次调用相对于种子产生一个已知值。因此，您对unique(eng)的调用会产生副作用，我相信这会导致OMP并行循环中出现未指定的行为。 (如果草率的话，快速的Google搜索似乎可以确认这一点。)

例如，IBM的文档使用以下措辞:在评估这些表达式时不执行任何同步，并且评估的副作用可能导致不确定的值。

您应该能够轻松地检验该假设。编写循环的并行和串行版本，仅此而已:

for (i = 0; i < N; i++)
    a[i] = uniform(eng);

这将记录 uniform(eng)生成的值的确切顺序。对于串行循环中的顺序RNG，此顺序非常确定。给定相同的起始种子，第N个项目始终具有相同的值。对于并行版本，在 eng周围没有额外的锁定或其他同步的情况下，我怀疑您会得到重复的值。如果添加锁，我怀疑您会获得相同的一组值，但顺序不确定。

如果您想在并行的 for构造中确定性地使用大量随机数，那么我想到的唯一安全的方法就是将这些预生成为一个大数组，或者基于循环索引。这些方法都缺乏大多数典型RNG引擎带来的顺序依赖性。

您可以尝试将顺序的RNG封装在锁中，但是即使您从RNG可靠地生成了相同的序列，您仍将以不确定的顺序访问随机数。这是因为RNG输出序列到循环迭代号的映射可能会根据线程到达RNG的顺序而改变。

对于此特定示例(计算大于0.5的值的数量)，顺序无关紧要，因为您要进行一次巨大的缩减。您可以自由地重新排序添加数字序列的顺序。这就是OpenMP希望您减少的原因。对于其他计算，顺序可能会有所作为，包括没有明显顺序依赖性的计算。例如，考虑随机抖动。这是一个非常简单的版本。 (假设[0,0.5)上的分布均匀。)

for (i = 0; i < N; i++)
   a[i] = b[i] + uniform(eng) > 1 ? 1 : 0;

您获得的确切抖动取决于随机数到循环索引的确切映射。如果您使用串行RNG，那么即使您在RNG上加了锁以使其可靠，也会引入原始算法所缺乏的串行依赖性。

编辑:正如上面其他人所指出的，在这种特定情况下，RNG被声明为在并行块本地，因此从技术上讲，它们不受种族的限制。我错过了那种微妙之处，但这并没有改变我的核心观点。基本问题仍然存在:顺序程序中的随机值集与并行程序中的随机值集不匹配，因为顺序RNG并未在串行程序和并行程序之间以相同的方式顺序调用。

如果在并行块本地声明RNG，以便为T个线程获得T个并行实例，则每个并行线程将看到相同的初始随机数序列。如果所有线程都重复相同的次数(这很可能)，那么将看到N / T个随机数重复了T次，而不是N个唯一的随机数。

我在编辑上方的核心观点仍然成立。为了在同一程序的并行和串行版本中获得相同的结果，并行循环中的操作不会产生副作用。从像Mersenne Twister这样的串行RNG中提取随机数本质上具有副作用。您要么需要在循环外部生成随机数，要么使用其他没有副作用的方法。 (散列循环迭代数和Perlin噪声都是示例。)