Почему этот генератор случайных чисел не поддерживает потоки? - PullRequest
Новая
       27

Почему этот генератор случайных чисел не поддерживает потоки?

0 голосов
/ 15 мая 2018

Я использовал функцию rand() для генерации псевдослучайных чисел между 0,1 для целей моделирования, но когда я решил запустить мой код C ++ параллельно (через OpenMP), я заметил, что rand() не является потоком-безопасен и тоже не очень равномерный.

Поэтому я перешел к использованию (так называемого) более равномерного генератора, представленного во многих ответах на другие вопросы.Это выглядит так: 

double rnd(const double & min, const double & max) {
    static thread_local mt19937* generator = nullptr;
    if (!generator) generator = new mt19937(clock() + omp_get_thread_num());
    uniform_real_distribution<double> distribution(min, max);
    return fabs(distribution(*generator));
}

Но я видел много научных ошибок в моей исходной задаче, которую я моделировал.Проблемы, которые были связаны как с результатами rand(), так и со здравым смыслом.

Поэтому я написал код для генерации 500 000 случайных чисел с помощью этой функции, вычисления их среднего значения и повторения этого 200 раз, и построения результатов. 

double SUM=0;
for(r=0; r<=10; r+=0.05){   
    #pragma omp parallel for ordered schedule(static)
    for(w=1; w<=500000; w++){   
        double a;
        a=rnd(0,1);
        SUM=SUM+a;
    } 
    SUM=SUM/w_max;
    ft<<r<<'\t'<<SUM<<'\n';
    SUM=0;
}

Мы знаем, что если бы вместо 500k я мог делать это бесконечное время, это должна быть простая строка со значением 0,5.Но с 500k у нас будут колебания около 0,5.

При запуске кода с одним потоком, результат приемлем:

enter image description here

Но вот результат с 2 потоками:

enter image description here

3 потока:

enter image description here

4 потока:

enter image description here

У меня сейчас нет 8-поточного процессора, но результаты даже стоили того.

Как вы можете видеть, они оба неоднородны и сильно колеблются вокруг своего среднего значения.

Так что этот псевдослучайный генератор также небезопасен?

Или я ошибаюсь?где-нибудь?

Ответы [ 2 ]

0 голосов
/ 15 мая 2018

Проблема не в вашем RNG, а в вашем суммировании. На SUM есть просто состояние гонки. Чтобы исправить это, используйте сокращение, например, изменить прагму на: 

#pragma omp parallel for ordered schedule(static) reduction(+:SUM)

Обратите внимание, что использование thread_local с OpenMP технически не определено. Вероятно, это будет работать на практике, но взаимодействие между концепциями потоков OpenMP и C ++ 11 недостаточно четко определено (см. Также этот вопрос ). Так что безопасной альтернативой OpenMP для вас будет: 

static mt19937* generator = nullptr;
#pragma omp threadprivate(generator)
0 голосов
/ 15 мая 2018

Я бы сделал три замечания о результатах теста:

  • Он имеет гораздо более сильную дисперсию, чем должно обеспечивать среднее значение хорошего случайного источника. Вы сами это заметили, сравнив с результатами одного потока.

  • Расчетное среднее уменьшается с количеством потоков и никогда не достигает исходного значения 0,5 (т. Е. Это не только более высокая дисперсия, но и измененное среднее).

  • В данных имеется временная связь, особенно заметная в случае с 4 потоками.

Все это объясняется состоянием гонки, присутствующим в вашем коде: вы присваиваете SUM из нескольких потоков. Увеличение значения double не является атомарной операцией (даже на x86, где вы, вероятно, получите атомарные операции чтения и записи в регистры). Два потока могут считывать текущее значение (например, 10), увеличивать его (например, оба добавляют 0,5) и затем записывать значение обратно в память. Теперь у вас есть два потока, которые пишут 10,5 вместо правильных 11.

Чем больше потоков пытается записать в SUM одновременно (без синхронизации), тем больше их изменений теряется. Это объясняет все наблюдения:

  • Как сильно нити соприкасаются друг с другом в каждом отдельном заезде, определяет, сколько результатов будет потеряно, и это может варьироваться от бега к бегу.

  • Среднее ниже с большим количеством гонок (например, с большим количеством потоков), потому что больше результатов теряется. Вы никогда не сможете превысить статистический средний 0,5, потому что вы только когда-либо теряете записи.

  • По мере того, как потоки и планировщик "оседают", дисперсия уменьшается. Это аналогично тому, почему вы должны «прогревать» свои тесты при тестировании.

Излишне говорить, что это неопределенное поведение. Он просто демонстрирует благоприятное поведение на процессорах x86, но это не то, что стандарт C ++ гарантирует вам. Насколько вы знаете, отдельные байты типа double могут записываться в разные потоки одновременно, что приводит к полному мусору.

Правильным решением было бы локально добавить парные потоки, а затем (с синхронизацией) добавить их вместе в конце. У OMP есть пункты сокращения для этой конкретной цели.

Для целочисленных типов вы можете использовать std::atomic<IntegralType>::fetch_add(). std::atomic<double> существует, но (до C ++ 20) упомянутая функция (и другие) доступны только для целочисленных типов.

...