如何並行生成隨機數字？

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; 

我測試過它的窗戶，我得到了極大的加速，但是產生的每個線程完全一樣的數字。我已經在Linux上測試過它，並且我得到了巨大的減速，8核處理器上的並行版本比順序版慢了10倍，但是每個線程產生了不同的數字。

有沒有辦法讓加速和不同的數字？

編輯2010年11月27日
我想我已經用從喬納森·德西后的想法解決它。看起來下面的代碼在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

我會在這裏發佈我張貼到Concurrent random number generation：

我認爲你正在尋找rand_r（），其中明確接受當前RNG狀態作爲參數。然後每個線程應該擁有它自己的種子數據副本（無論您希望每個線程開始使用相同的種子還是不同的種子取決於您在做什麼，在這裏您希望它們與衆不同或者您會得到相同的行一次又一次）。這裏有一些關於rand_r（）和線程安全的討論：whether rand_r is real thread safe?。

所以說你想讓每個線程的線程號開始（這可能不是你想要的，因爲每次你使用相同數量的線程運行時，它會得到相同的結果，爲例）：

#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; 
} 

其中蜱和滴答只是包裝到gettimeofday()，和滴答（）返回秒的差別。總和印刷只是爲了確保沒有什麼東西能夠被優化，並且表現出一個小點;你會得到不同數量的線程數，因爲每個線程都有自己的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

獲取每個線程以基於其線程ID設置不同的種子，例如， srand(omp_get_thread_num() * 1000);

Answer 3

隨機數可以非常快地生成，所以通常內存將成爲瓶頸。通過在多個線程之間分配這個任務，您會創建額外的通信和同步開銷（並且不同內核的高速緩存的同步並不便宜）。

使用單一線程和更好的random()函數會更好。

Answer 4

看起來好像rand在Linux上的所有線程之間具有全局共享狀態，而在Windows上具有線程本地存儲狀態。由於必要的同步，Linux上的共享狀態會導致您的速度變慢。

我不認爲在C庫中有一種可移植的方式在多線程上使用RNG並行，所以你需要另一個。您可以使用Mersenne Twister。正如marcog所說的，你需要以不同的方式爲每個線程初始化種子。

Answer 5

您不能使用多線程中的C rand()函數;這會導致未定義的行爲。一些實現可能會給你鎖定（這會讓它變慢）;其他人可能會允許線程摧毀對方的狀態，可能會導致程序崩潰或者給出「壞」的隨機數字。

要解決此問題，請編寫自己的PRNG實現或使用允許調用方存儲並將狀態傳遞給PRNG迭代器函數的現有方法。

Answer 6

在Linux/UNIX可以使用

long jrand48(unsigned short xsubi[3]); 

其中xsubi [3]編碼的隨機數發生器的狀態，是這樣的：

#include<stdio.h> 
#include<stdlib.h> 
#include <algorithm> 
int main() { 
    unsigned short *xsub; 
#pragma omp parallel private(xsub) 
    { 
    xsub = new unsigned short[3]; 
    xsub[0]=xsub[1]=xsub[2]= 3+omp_get_thread_num(); 
    int j; 
#pragma omp for 
    for(j=0;j<10;j++) 
     printf("%d [%d] %ld\n", j, omp_get_thread_num(), jrand48(xsub)); 
    } 
} 

編譯

g++-mp-4.4 -Wall -Wextra -O2 -march=native -fopenmp -D_GLIBCXX_PARALLEL jrand.cc -o jrand 

（將g ++ - mp-4.4替換爲需要調用g ++版本4.4或4.3的任何東西） 並且您得到

$ ./jrand 
0 [0] 1344229389 
1 [0] 1845350537 
2 [0] 229759373 
3 [0] 1219688060 
4 [0] -553792943 
5 [1] 360650087 
6 [1] -404254894 
7 [1] 1678400333 
8 [1] 1373359290 
9 [1] 171280263 

即10個不具有任何互斥鎖定或競爭條件的僞隨機數。