c - 使用 OMP 中的线程生成相同的随机数

Question

我正在尝试使用 OMP 对某些代码进行多线程处理。目前，我的顺序版本使用 rand() 生成一组具有一致种子的随机数，以便它们每次运行时返回相同的结果。我想并行化我的代码，但 rand() 不是线程安全的。有人可以告诉我如何使用在线程上工作的随机数生成器，这样我就可以在每次测试时生成相同的数据集，类似于使用 rand() 的种子。我的并行代码如下:

    long linkCnt;
    long j;
    long t;
    srand(randInit);

    linkCnt=0; //Keep track of # of outgoing edges
 #pragma omp parallel for schedule(runtime) private(t)
    for(j = 0; j < G->N; j++)
    {

        if(i == j){
            t = NO_CONN;
        } else {
            t = (rand() % ((MAX_EDGE_WEIGTH-1) * 2)+1); //50% of having no connection
            if(t > MAX_EDGE_WEIGTH){
                //t = INF; //Like no connection
                t = NO_CONN; //Like no connection
            } else {
                linkCnt++;
                G->visited[j] = VISITED; //Do this to find isolated nods that have no incomming edge
            }
        }

        G->node[i][j] = t;
    }

Answer 1

这里似乎有几个问题被混淆了。

首先，rand() 函数的非线程安全性质意味着从不同线程同时调用 rand() 可能会产生与 if 不同的值它是按顺序调用的。用一个简单的例子来解释这一点可能是最简单的，所以让我们看一下 PCG 的 32 位版本，因为它很好而且很简单。它有一个 32 位状态，并生成如下 32 位数字:

static uint32_t state = ...;

static uint32_t generate(void) {
  uint32_t s = state;
  uint32_t v = ((s >> ((s >> 28) + 4)) ^ s) * (277803737U);
  v ^= v >> 22;
  state = state * 747796405U + 1729U;
  return v;
}

现在考虑一下如果两个线程大致同时调用 generate() 会发生什么。也许它们都获得相同的状态值，因此两次生成相同的随机数。也许一个人会在另一个人读取状态之前更新状态，因此他们会得到不同的值。

我们可以通过使用互斥体保护 generate() 函数来消除这个问题，或者在 32 位 PGC 的情况下(这就是为什么 I use it 用于可再现数字)，使用原子。如果我们这样做，那么我们总是会以相同的顺序得到相同的数字。

问题的第二部分是当调用者的顺序在代码中混淆时会发生什么。假设您有两个线程(称为 A 和 B)，它们每个都必须运行循环的两次迭代。即使您从线程安全源获取随机数，调用顺序也可能是 AABB、ABAB、ABBA、BBAA、BABA 或 BAAB，每个顺序都会导致您的代码生成不同的结果。

有几种简单的方法可以解决这个问题。首先，您可以使用同步原语来确保每次迭代都按照您想要的顺序调用generate。最简单的方法可能是使用队列，但是您会浪费大量时间进行同步，并且会失去一些并行机会(并且您必须大幅重组代码)。

如果迭代次数相对较少，您可以考虑提前生成一个数组。认为:

int i;
int nums[LEN];
for (i = 0 ; i < LEN ; i++)
  nums[i] = generate();
#pragma omp parallel for ...
for (i = 0 ; i < LEN ; i++) {
  do_stuff(nums[i]);
}

不过，更好的解决方案可能是完全放弃生成随机数的想法，而是使用散列。 https://burtleburtle.net/bob/hash/integer.html有一些选择。一个例子是这样的

for (int i = 0 ; i < LEN ; i++) {
  do_stuff(hash(i));
}

当然，您可以添加一些盐，甚至可以使用 rand() 来生成盐。