1

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

注意我使用的是相同的种子，它与线程数无关——所以结果应该是一样的！

这是 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 及其引擎，所以我并不清楚错误可能在哪里。

4

1 回答 1

4

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

例如，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 噪声都是示例。）

于 2013-11-08T13:52:24.993 回答