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

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

$ 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, это не очень сложный процесс, и другие проблемы, такие как пропускная способность памяти, начинают играть определенную роль. Таким образом, только тень на 2x скорости на 8 ядер.

Ответ 2

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

Ответ 3

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

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

Ответ 4

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

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

Ответ 5

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

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

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