ошибка в параллельном ГСЧ
Я генерирую серию случайных чисел параллельно, но в зависимости от того, какое количество потоков я вызываю, я получаю другой результат. Из этого я делаю вывод, что где-то допустил ошибку!
НОТА Я использую одно и то же семя, которое не зависит от количества потоков — поэтому результаты должны быть одинаковыми!
Вот MWE, которое генерирует число от 0 до 1 и увеличивает переменную, если сгенерированная переменная больше 0,5:
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include "omp.h"
#include <random>
typedef std::uniform_real_distribution<double> distr_uni;
#define max_threads 1
using namespace std;
int main(int argc, char* argv[])
{
int reservoir_counter, accepted_tube=0;
double r;
omp_set_num_threads(max_threads);
#pragma omp parallel
{
mt19937 eng(0);
distr_uni uniform(0, 1);#pragma omp for private(r, reservoir_counter) reduction(+:accepted_tube)
for(reservoir_counter=0; reservoir_counter<100000; reservoir_counter++)
{
r = uniform(eng);
if(r>0.5)
{
accepted_tube++;
}
}
}
cout << accepted_tube << endl;
return 0;
}
Когда я установил max_threads=1 Я получаю 50027, но когда max_threads=60 (на машине, которая его поддерживает ….) Я получаю 50440.
Может кто-то заметить мою ошибку, которая, по-видимому, там? Чувствительный ГСЧ и его двигатель, который я объявил в параллельной области, поэтому мне не совсем понятно, где может быть ошибка.
Решение
Генераторы случайных чисел, особенно Mersenne Twister (который вы используете выше), как правило, очень серийные существа. Каждый вызов генератора случайных чисел имеет побочный эффект обновления начального числа до следующего внутреннего состояния. Они генерируют случайное число последовательность, такой, что N-й вызов RNG производит известное значение относительно начального числа. Таким образом, ваши звонки unique(eng) имеют побочные эффекты, которые, как я считаю, приводит к неопределенному поведению в параллельном цикле OMP. (Быстрый, но небрежный поиск в Google, кажется, подтверждает это.)
Например, документация IBM использует эту фразеологию: Синхронизация не выполняется при оценке этих выражений, и оцененные побочные эффекты могут привести к неопределенным значениям.
Вы должны легко проверить эту гипотезу. Напишите параллельные и последовательные версии цикла, который не делает ничего, кроме этого:
for (i = 0; i < N; i++)
a[i] = uniform(eng);
Это записывает точную последовательность значений, произведенных uniform(eng), Для последовательного ГСЧ в последовательном цикле этот порядок является очень детерминированным. N-й предмет всегда имеет одинаковое значение при одинаковом начальном семени. Для параллельной версии, без дополнительной блокировки или другой синхронизации вокруг engЯ подозреваю, что вы получите повторные значения. Если вы добавите блокировку, я подозреваю, что вы получите тот же набор значений, но в неопределенном порядке.
Если вы хотите использовать большое количество случайных чисел детерминистически в параллельной for Если говорить о конструкции, то единственные безопасные способы, которые я могу придумать, — это предварительно сгенерировать их в большой массив или вычислить хеш-функцию на основе индекса цикла. Ни у одного из этих подходов отсутствует зависимость упорядочения, которую несут большинство типичных двигателей ГСЧ.
Вы мог Попробуйте обернуть последовательный ГСЧ в замок, но вы все равно будете посещать случайные числа в неопределенном порядке, даже если вы надежно сгенерируете ту же последовательность из ГСЧ. Это связано с тем, что отображение выходной последовательности ГСЧ на номера итераций цикла может меняться в зависимости от порядка поступления потоков в ГСЧ.
Для этого конкретного примера (считая количество значений выше 0,5) порядок не имеет значения, потому что вы идете в одно, огромное сокращение. Вы можете свободно изменить порядок, в котором вы добавляете последовательность чисел. Вот почему OpenMP хочет, чтобы вы объявляли сокращения. Для других вычислений порядок вполне может иметь значение, включая вычисления без очевидной последовательной зависимости. Например, рассмотрим стохастическое дизеринг. Вот действительно простая версия. (Предположим, равномерное распределение по [0,0.5).)
for (i = 0; i < N; i++)
a[i] = b[i] + uniform(eng) > 1 ? 1 : 0;
Точное колебание, которое вы получите, зависит от точного отображения случайных чисел в циклические индексы. Если вы используете последовательный ГСЧ, то вы вводите последовательную зависимость, которой не было в исходном алгоритме, даже если вы устанавливаете блокировку ГСЧ, чтобы сделать его надежным.
Редактировать: Как уже указывалось выше, в этом конкретном случае RNG были объявлены локальными для параллельного блока, поэтому технически они не были подвержены гонкам. Я упустил эту тонкость, но это не меняет моей сути. Основная проблема остается: набор случайных значений в последовательной программе не совпадает с набором случайных значений в параллельной программе, потому что последовательный ГСЧ не вызывался последовательно одинаковым образом между последовательной и параллельной программами.
Если вы объявляете RNG локальными для параллельного блока, чтобы получить T параллельных экземпляров для T потоков, то каждый параллельный поток будет видеть одинаковую начальную последовательность случайных чисел. Если все потоки повторяются одинаковое количество раз (что вероятно), то вместо N уникальных случайных чисел вы увидите N / T случайных чисел, повторенных T раз.
Мои основные пункты выше редактирования все еще остаются в силе. Чтобы получить одинаковые результаты для параллельной и последовательной версии одной и той же программы, операции в параллельном цикле не могут иметь побочных эффектов. Извлечение случайных чисел из серийного RNG, такого как Mersenne Twister, по своей природе имеет побочные эффекты. Вам нужно либо генерировать случайные числа вне цикла, либо использовать какой-то другой метод, который не имеет побочных эффектов. (Хеширование числа итераций цикла и шум Перлина — оба примера.)
Другие решения
Других решений пока нет …