Потокобезопасная генерация случайных чисел для интеграции Монте-Карло

Question

Я пытаюсь написать что-то, что очень быстро вычисляет случайные числа и может применяться к нескольким потокам.Мой текущий код:

/* Approximating PI using a Monte-Carlo method. */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <omp.h>
#define N 1000000000  /* As lareg as possible for increased accuracy */

double random_function(void);

int main(void)
{
   int i = 0;
    double X, Y;
   double count_inside_temp = 0.0, count_inside = 0.0;
   unsigned int th_id = omp_get_thread_num();
   #pragma omp parallel private(i, X, Y) firstprivate(count_inside_temp)
   {
      srand(th_id);
      #pragma omp for schedule(static)
      for (i = 0; i <= N; i++) {
         X = 2.0 * random_function() - 1.0;
         Y = 2.0 * random_function() - 1.0;
         if ((X * X) + (Y * Y) < 1.0) {
        count_inside_temp += 1.0;
     }
  }
  #pragma omp atomic
      count_inside += count_inside_temp;
   }
   printf("Approximation to PI is = %.10lf\n", (count_inside * 4.0)/ N);
   return 0;
}

double random_function(void)
{
   return ((double) rand() / (double) RAND_MAX);
}

Это работает, но из наблюдения за менеджером ресурсов я знаю, что он не использует все потоки.Работает ли rand () для многопоточного кода?А если нет, то есть ли хорошая альтернатива?Большое спасибо.Jack

Answer 1

Безопасен ли rand() поток? Может быть, а может и нет:

Функция rand () не обязательно должна быть реентерабельной. Функция, которая не требует повторного входа, не обязана быть поточно-ориентированной. "

Одним тестом и хорошим упражнением в обучении было бы заменить вызов rand(), скажем, фиксированным целым числом и посмотреть, что произойдет.

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

1. Две функции: одна для установки начального начального числа (например, srand(seed)) и одна для извлечения следующего значения из последовательности (например, rand()). Состояние PRNG хранится внутри в виде глобальной переменной. Генерация нового случайного числа либо не будет поточно-ориентированной (трудно сказать, но выходной поток не будет воспроизводимым), либо будет медленной в многопоточном коде (в результате вы получите некоторую сериализацию вокруг значения состояния).
2. Интерфейс, в котором состояние PRNG предоставляется прикладному программисту. Здесь у вас обычно есть три функции: init_prng(seed), которая возвращает некоторое непрозрачное представление состояния PRNG, get_prng(state), которая возвращает случайное число и изменяет переменную состояния, и destroy_peng(state), которая просто очищает выделенную память и т. Д. , Все PRNG с этим типом API должны быть поточно-ориентированными и работать параллельно без блокировки (потому что вы отвечаете за управление (теперь локально для потока) переменной состояния.

Я обычно пишу на фортране и использую реализацию Ладда PRNG Mersenne Twister (эту ссылку стоит прочитать). Есть много подходящих PRNG в C, которые выставляют состояние под ваш контроль. PRNG выглядит хорошо, и использование этого (с вызовами инициализации и уничтожения внутри параллельной области и частных переменных состояния) должно дать вам приличное ускорение.

Наконец, часто бывает так, что PRNG могут работать лучше, если вы запрашиваете целую последовательность случайных чисел за один раз (например, компилятор может векторизовать внутренние компоненты PRNG). Из-за этого у библиотек часто есть что-то вроде get_prng_array(state) функций, которые возвращают массив, полный случайных чисел, как будто вы помещаете get_prng в цикл, заполняющий элементы массива - они просто делают это быстрее. Это будет вторая оптимизация (и потребуется дополнительный цикл for внутри параллельного цикла for. Очевидно, что вы не хотите исчерпывать пространство стека для каждого потока, делая это!