并发随机数生成

Question

我正在使用OpenMP编写并行程序，其中我生成了一个随机浮点数矩阵，然后对其进行一系列计算。我目前想让生成矩阵的步骤并行运行，但是遇到了一个问题，即rand（）函数不适合并发运行。我不想使用锁来对rand提供互斥，因为这是循环中唯一要做的事情，按顺序运行可能更有效。有没有什么方法可以高效地并行执行此步骤？以下是当前代码的部分（没有rand上的互斥锁）：

#pragma omp parallel default(private)
{
    int i= omp_get_thread_num();
    for(int j=0; j<cols; j++)
        matrix[i][j]= rand()%1000 + (float)(rand()%100)/(float)(rand()%1000);
}

- njvb

---

伪随机数生成器（PRNGs）从固定的种子生成一致的数字序列。对于您来说，这个顺序（可重复性）很重要吗？还是您真的想要“随机”的结果？ - Ben Jackson

无论它们以任何特定顺序排列都没关系，我遇到的问题是当我按顺序运行时，我的范围内分布得相当好，但当我将其改为并行时，通常数字小于10，并且当我总结行时，几乎所有行的总和都为0（我从未在顺序中得到负数）。这让我想到函数调用存在某种并发问题。 - njvb

等一下——平均每千次迭代，rand() % 1000 将为零，那么你怎么能除以它呢？ - TonyK

是的，矩阵和列需要共享，而不是私有的 - 我假设这段代码只是为了演示目的。 - Jonathan Dursi

是的，它们是共享的，但它们都写入矩阵的不同元素，而行和列是常量，因此它们不应该有任何竞争条件。然而，我注意到将i更改为omp for以及在行上使用rand_r可以消除奇怪输出的竞争条件。@TonyK 是的，它给我那个位置提供了inf。 - njvb

@Jonathan Dursi：如果这段代码只是为了演示目的，那么它展示的就是user381261很草率。当你编写并行程序时，你不能承担粗心大意的风险。 - TonyK

Answer 1

我认为你需要使用rand_r()，它明确地将当前的RNG状态作为参数传递。 然后，每个线程应该有自己的种子数据副本（是否希望每个线程以相同的种子开始或不同取决于你正在做什么，在这里你希望它们是不同的，否则你会一遍又一遍地得到相同的行）。关于rand_r()和线程安全的讨论可以在这里找到：whether rand_r is real thread safe?。

所以说，假设你想让每个线程都以其线程编号作为种子开始（这可能不是你想要的，因为它会在每次使用相同数量的线程运行时给出相同的矩阵，但这只是一个例子）：

#pragma omp parallel default(none) shared(matrix, cols)
{
    int i= omp_get_thread_num();
    unsigned int myseed = i;
    for(int j=0; j<cols; j++)
        matrix[i][j]= rand_r(&myseed)%1000 + (float)(rand_r(&myseed)%100)/(float)(rand_r(&myseed)%1000 + 1);
}

现在每个线程都在独自修改自己的状态（rand_r()是一个纯函数），你应该没问题了。

- Jonathan Dursi

---

那就是我们需要的答案！谢谢。 - David Guyon

Answer 2

如果您正在使用C++，应考虑使用Boost库随机数类。 您可以为每个线程创建唯一的PRNG实例。 如果需要可重复性，则可以在主线程中使用可重复生成的种子值初始化每个实例。

更新：事实证明，在我写完这篇文章后，C++11发布了一个更现代的用于生成随机数的库。它包括{{link2：std::uniform_int_distribution}}和{{link3：std::std::uniform_real_distribution}}，两者都依赖于生成器，例如{{link4：std::mersenne_twister_engine}}（或特定配置std::mt19937）。例如：

#include <random>
#include <iostream>

int main() {
    std::mt19937 gen;  // Uses default seed value to generate repeatable sequence
    std::uniform_int_distribution<int> d20(1,20);
    std::uniform_real_distribution<float> prob(0.0, 1.0);

    std::cout << d20(gen) << std::endl;
    std::cout << prob(gen) << std::endl;

    return 0;
}

- andand

---

这个现代库在C++11中发布时默认是线程安全的，还是需要使用互斥锁来保护生成器？ - Al Bundy

@AlBundy，我不确定，但我会怀疑它是否是这样。通过确保每个生成器仅与一个线程相关联（这是上面答案的基础），并且每个分布依次仅与一个生成器相关联（在创建它们时保证）。可以以不同的方式对每个生成器进行种子处理，以确保它们生成不同的序列，从而避免使用线程锁。 - andand

Answer 3

如果伪随机数足够好（参见Ben的评论），那么您可以创建自己的伪随机数生成器（例如Mersenne Twister而不是大多数系统使用的弱模方法），并为每个线程实现一个独立的生成器。如果您这样做，一定要确保每个生成器都有不同的种子。

- winwaed

Answer 4

一个真正的问题是如果你想要可重复性，这在测试中经常需要。使用给定的种子生成一系列线程种子。然后每个线程将使用自己的种子来生成数字。

rand()不是线程安全的事实几乎不是问题。有大量的算法可用，并且对于每个线程滚动一个实例（状态）是微不足道的，只需从http://en.wikipedia.org/wiki/Random_number_generation#Computational_methods开始即可。为每个rand()调用加锁将是一场并发灾难。

- Remus Rusanu