Boost随机数和OpenMP

Question

我从一个OpenMP并行代码部分收到了“总线错误”的信息。我在下面重新创建了一个简单版本的问题。该代码主要对函数uniform_distribution进行多次调用，该函数使用Boost的uniform_int_distribution生成介于0和20000之间的整数。

这篇文章（post）警告说有两个线程正在访问同一个对象。我猜这在我的情况下是指eng。（不幸的是，我不知道如何编写“适当的互斥包装器”，正如该文章建议的那样。）

我想到的一个可能的笨拙解决方案是，在#pragma for循环中创建一个本地eng，并将其作为参数传递给uniform_distribution。我不喜欢这个想法，因为在我的实际代码中，我调用了许多函数，并且传递本地eng会很麻烦。此外，我的担忧是，如果我在uniform_distribution中声明eng，则不同的线程将生成相同的随机数序列。所以我有两个要求：如何并行化？

1. 每个线程从其他线程中生成概率独立的随机数？
2. RNG上不存在竞争条件？

谢谢，非常感谢您的帮助。

#include <omp.h>
#include <boost/random/uniform_int_distribution.hpp>

boost::random::mt19937  eng;

int uniform_distribution(int rangeLow, int rangeHigh) {
    boost::random::uniform_int_distribution<int> unirv(rangeLow, rangeHigh);
    return unirv(eng);
}
int main()
{  
    # pragma omp parallel for private(eng)
    for (int bb=0; bb<10000; bb++)
        for (int i=0; i<20000; i++)
             int a = uniform_distribution(0,20000);

    return 0;
}

- covstat

Answer 1

我认为最方便的解决方案涉及一个thread_local随机数生成器和一种使用线程ID作为每个线程的唯一数字的种子，例如，您可以对系统时间和线程ID进行XOR运算以种植随机数生成器。以下是一个示例（使用C++11）：

#include <omp.h>
#include <boost/random/uniform_int_distribution.hpp>

#include <thread>
#include <ctime>

boost::random::mt19937& get_rng_engine() {
  thread_local boost::random::mt19937 eng(
    reinterpret_cast<unsigned int>(std::time(NULL)) ^ std::this_thread::get_id());
  return eng;
};

（注意：如果你要使用C++11，也可以使用<random>）

如果无法使用C++11，则可以使用boost::thread来实现类似的行为，在Boost页面上查看有关线程本地存储的信息。

- Mikael Persson

Answer 2

当您并行化代码时，必须考虑共享资源，它可能会导致数据竞争，进而最终可能会破坏您的程序。（注意：并非所有的数据竞争都会破坏您的程序。）

在您的情况下，正如您正确预期的那样，eng 是两个或多个线程共享的，这必须避免才能正确执行。

对于您的情况，一种解决方案是私有化：为共享资源创建每个线程的副本。您需要创建一个单独的 eng 副本。

有多种方法可以针对 eng 进行私有化：

(1) 尝试使用 threadprivate 指令（link）：例如，#pragma omp threadprivate(eng)。但是，一些编译器可能不支持此指令的非 POD 结构。

(2) 在没有可用的 threadprivate 的情况下，使用一个 eng 数组，并使用线程 ID 访问：声明为 eng[MAX_THREAD]。然后，使用线程 ID 访问：eng[omp_get_thread()]。

然而，第二种解决方案需要考虑“伪共享”，这可能会严重影响性能。最好保证eng[MAX_THREAD]中的每个项目都分配在单独的缓存行边界上，这通常是现代桌面CPU中的64字节。还有几种避免伪共享的方法。最简单的解决方案是使用填充：例如，在保存eng的struct中使用char padding[x]。

- minjang

---

一个私有子句实际上会创建一个变量的线程本地版本。与应用了threadprivate指令的变量不同，当线程加入时，它将未分配。然而，在OP的示例中，这不是问题。私有子句无法在此处起作用的原因是uniform_distribution中引用的eng是全局的，而不是线程特定的。 - jerry

是的，关于“private”的观点是正确的。我删掉了一句话。但是，OP所遇到的问题本质上是私有化问题。将线程本地化将是一个解决方案。您的第二个解决方案也是私有化的一种方式。 - minjang

@minjang：感谢您的有益回答。我尝试了（1），但是threadprivate抱怨eng参数。您能否详细说明（2），并可能提供一个示例？恐怕我不太理解_false sharing_的评论。 - covstat

是的，对于一些OpenMP实现，'threadprivate'仅支持POD类型。对于第二个解决方案，首先只需声明'eng[MAX_THREAD]'，并查看它是否正常工作。然后，您可以稍后解决虚假共享问题。 - minjang

@minjang：你的建议，再加上Mikael Persson版本的种子，解决了问题。我现在对你的误共享评论很感兴趣。我的缓存行大小为64，sizeof(eng[0])为2504。这是否意味着误共享不会成为问题，还是我仍然应该担心？谢谢！ - covstat

首先，检查你的加速比是否良好。关于虚假共享，元素大小大于缓存行，但最好将元素分配在多个缓存行边界上。如果 eng[0] 的最后几个元素和 eng[1] 的前几个元素可以共享缓存行，则可能存在虚假共享。因此，在这种情况下，请添加一些填充以使其成为 64 的倍数，例如 char[56]。并且，使用编译器扩展（如 __declspec(align(64))）来分配这些数组。 - minjang

Answer 3

您有两个选项：

• 为每个线程使用单独的随机数生成器并以不同的方式进行种子设置
• 使用互斥

首先，互斥的示例：

# pragma omp parallel for
for (int bb=0; bb<10000; bb++)
{
    for (int i=0; i<20000; i++)
    {
        // enter critical region, disallowing simulatneous access to eng
        #pragma omp critical
        {
            int a = uniform_distribution(0,20000);
        }
        // presumably some more code...
    }
    // presumably some more code...
}

接下来，一个使用种子的线程本地存储示例：

# pragma omp parallel
{
    // declare and seed thread-specific generator
    boost::random::mt19937 eng(omp_get_thread_num());
    #pragma omp for
    for (int bb=0; bb<10000; bb++)
    {
        for (int i=0; i<20000; i++)
        {
            int a = uniform_distribution(0,20000, eng);
            // presumably some more code...
        }
        // presumably some more code...
    }
}

这两个片段只是举例说明，根据您的要求（比如安全相关、游戏或建模），您可能会选择其中一个。您可能还想更改确切的实现以适应您的使用。例如，如果您希望生成器可重复或更接近真正的随机数（是否可能取决于系统），则种子生成器的方式很重要。这同样适用于两种解决方案（尽管在互斥情况下获得再现性更加困难）。

线程本地生成器可能运行更快，而互斥情况应该使用更少的内存。

编辑：明确一点，仅当生成随机数不是线程工作的主要部分（即示例中存在//大概还有一些代码...并且不需要花费微不足道的时间来完成）时，互斥解决方案才有意义。关键部分只需要包括对共享变量的访问，稍微改变架构可以让您更好地控制它（在线程本地存储情况下，也可以避免传递eng引用）。

- jerry

---

虽然使用临界区提供了正确性，但它会有效地序列化代码，这不会带来性能改进。因此，我认为在这种简单的并行化情况下，使用临界区不是一个好的解决方案。 - minjang

@jerry：感谢你的回答。我尝试了两种方法；第一种解决了竞态条件，但没有性能提升（可能是因为我的测试代码太简单了），这正是minjang预测的。你的第二个答案与minjang的类似，但它似乎表现得很奇怪。我将继续尝试你的第二种方法。 - covstat

@covstat，关于Jerry的第二个解决方案，请尝试在omp for处放置private(eng)。这段代码仍然会共享eng。 - minjang

@minjang 在这个示例代码中，这绝对是正确的。然而，OP表示该示例是简化版本，我假设原始代码不仅仅在循环中计算随机数（这就是我所说的“//大概还有一些其他的代码...”）。根据实际情况，互斥的效果可能从无法测量到有效地串行化。 - jerry

@covstat 你看到了什么奇怪的结果？我认为 eng 应该是私有的，因为它在并行结构内声明，但听起来你的实现可能存在非 POD 线程本地数据的问题。老实说，我以前没有遇到过这种情况，但明显 minjang 遇到过。你使用的编译器/版本是什么？它实现了哪个 OpenMP 标准的版本？另外，出于好奇，你是如何修改 uniform_distribution 来接受生成器的？ - jerry