Как генерировать случайные числа параллельно?

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 (), который явно принимает текущее состояние ГСЧ в качестве параметра. Тогда каждый поток должен иметь свою собственную копию начальных данных (хотите ли вы, чтобы каждый поток начинался с одного и того же начального или другого, зависит от того, что вы делаете, здесь вы хотите, чтобы они были разными, или вы получите ту же строку опять и опять). Здесь обсуждается 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 () возвращает разницу в секундах. Сумма печатается только для того, чтобы убедиться, что ничего не оптимизировано, и для демонстрации небольшой точки; вы получите разные числа с разными номерами потоков, потому что каждый поток получает свой собственный номер потока в качестве начального числа; если вы снова и снова запускаете один и тот же код с одним и тем же количеством потоков, вы получите одну и ту же сумму по той же причине. В любом случае, время (работающее на 8-ядерном Nehalem Box без других пользователей):

$ 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-кратное ускорение на 8 ядер.

Answer 2

Вы не можете использовать функцию C rand() из нескольких потоков;это приводит к неопределенному поведению.Некоторые реализации могут дать вам блокировку (что сделает ее медленной);другие могут позволить потокам перекрывать состояние друг друга, возможно, вывести из строя вашу программу или просто дать «плохие» случайные числа.

Чтобы решить проблему, либо напишите свою собственную реализацию PRNG, либо используйте существующую, которая позволяет вызывающей сторонесохранить и передать состояние функции итератора PRNG.

Answer 3

Получите каждый поток, чтобы установить различное начальное число на основе его идентификатора потока, например, srand(omp_get_thread_num() * 1000);

Answer 4

Кажется, что rand имеет глобальное общее состояние между всеми потоками в Linux и состояние локального хранилища потоков для него в Windows. Общее состояние в Linux вызывает замедление из-за необходимой синхронизации.

Я не думаю, что в библиотеке C есть портативный способ использовать параллель RNG в нескольких потоках, поэтому вам нужен другой. Вы можете использовать Mersenne Twister . Как сказал marcog, вам нужно по-разному инициализировать семя для каждого потока.

Answer 5

В 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 различных псевдослучайных чисел без блокировки мьютекса или условий гонки.

Answer 6

Случайные числа могут генерироваться очень быстро, поэтому обычно память является узким местом.Распределяя эту задачу между несколькими потоками, вы создаете дополнительные накладные расходы на связь и синхронизацию (а синхронизация кэшей разных ядер недешева).

Было бы лучше использовать один поток с лучшей random() функцией.