如何并行生成随机数？

Question

我想使用openMP并行生成伪随机数,如下所示:

int i;
#pragma omp parallel for
for (i=0;i<100;i++)
{
    printf("%d %d %d\n",i,omp_get_thread_num(),rand());
} 
return 0; 

我已经在Windows上测试了它,并且我获得了巨大的加速,但每个线程生成了完全相同的数字.我已经在Linux上测试了它并且我得到了巨大的减速,8核处理器上的并行版本比顺序慢了大约10倍,但是每个线程生成了不同的数字.

有没有办法同时加速和不同的数字？

编辑27.11.2010
我想我已经用乔纳森杜尔西的一个想法解决了这个问题.似乎下面的代码在linux和windows上运行得很快.数字也是伪随机的.你怎么看待这件事？

int seed[10];

int main(int argc, char **argv) 
{
int i,s;
for (i=0;i<10;i++)
    seed[i] = rand();

#pragma omp parallel private(s)
{
    s = seed[omp_get_thread_num()];
    #pragma omp for
    for (i=0;i<1000;i++)
    {
        printf("%d %d %d\n",i,omp_get_thread_num(),s);
        s=(s*17931+7391); // those numbers should be choosen more carefully
    }
    seed[omp_get_thread_num()] = s;
}
return 0; 
} 

PS.:我还没有接受任何答案,因为我需要确定这个想法是好的.

Answer 1

我将在这里发布我发布到并发随机数生成的内容:

我想你正在寻找rand_r(),它明确地将当前的RNG状态作为参数.然后每个线程都应该拥有自己的种子数据副本(无论你是希望每个线程都使用相同的种子开始,还是不同的,取决于你正在做什么,这里你希望它们不同,或者你得到同一行一次又一次).这里有一些关于rand_r()和线程安全的讨论:rand_r 是否真的是线程安全的？.

所以说你希望每个线程的种子都以它的线程号开始(这可能不是你想要的,因为每次你运行相同数量的线程时它会给出相同的结果,但仅作为一个例子):

#pragma omp parallel default(none)
{
    int i;
    unsigned int myseed = omp_get_thread_num();
    #pragma omp for
    for(i=0; i<100; i++)
            printf("%d %d %d\n",i,omp_get_thread_num(),rand_r(&myseed));
}

编辑:只是在云雀上,检查以上是否会获得任何加速.完整的代码是

#define NRANDS 1000000
int main(int argc, char **argv) {

    struct timeval t;
    int a[NRANDS];

    tick(&t);
    #pragma omp parallel default(none) shared(a)
    {
        int i;
        unsigned int myseed = omp_get_thread_num();
        #pragma omp for
        for(i=0; i<NRANDS; i++)
                a[i] = rand_r(&myseed);
    }
    double sum = 0.;
    double time=tock(&t);
    for (long int i=0; i<NRANDS; i++) {
        sum += a[i];
    }
    printf("Time = %lf, sum = %lf\n", time, sum);

    return 0;
}

其中tick和tock只是包装器gettimeofday(),而tock()以秒为单位返回差异.打印Sum只是为了确保没有任何优化,并展示一个小点; 你会得到不同数量的线程,因为每个线程都有自己的threadnum作为种子; 如果您使用相同数量的线程一次又一次地运行相同的代码,则会得到相同的总和,原因相同.无论如何,计时(在没有其他用户的8核nehalem盒子上运行):

$ export OMP_NUM_THREADS=1
$ ./rand
Time = 0.008639, sum = 1074808568711883.000000

$ export OMP_NUM_THREADS=2
$ ./rand
Time = 0.006274, sum = 1074093295878604.000000

$ export OMP_NUM_THREADS=4
$ ./rand
Time = 0.005335, sum = 1073422298606608.000000

$ export OMP_NUM_THREADS=8
$ ./rand
Time = 0.004163, sum = 1073971133482410.000000

所以加速,如果不是很好; 正如@ruslik指出的那样,这不是一个计算密集型的过程,而其他问题如内存带宽也开始发挥作用.因此,在8个核心上只有2倍加速的阴影.

Answer 2

您不能rand()从多个线程使用C 函数; 这会导致未定义的行为.有些实现可能会给你锁定(这将使它变慢); 其他人可能会允许线程破坏彼此的状态,可能会导致程序崩溃或只是给出"坏"的随机数.

要解决此问题,请编写自己的PRNG实现或使用允许调用者存储并将状态传递给PRNG迭代器函数的现有实现.

Answer 3

获取每个线程根据其线程ID设置不同的种子,例如srand(omp_get_thread_num() * 1000);