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

Я использовал функцию 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 тыс. Случайных чисел с помощью этой функции, вычисления их среднего значения, повторения 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.

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

введите описание изображения здесь

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

введите описание изображения здесь

3 потока:

введите описание изображения здесь

4 потока:

введите описание изображения здесь

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

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

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

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


c++ multithreading random openmp
person Alireza    schedule 15.05.2018    source источник
comment
Комментарии не подлежат расширенному обсуждению; этот разговор был перемещен в чат.   -  person Andy♦    schedule 15.05.2018
comment
Вы пробовали использовать лучшие семена для генераторов случайных чисел?   -  person François Andrieux    schedule 15.05.2018
comment
@ FrançoisAndrieux Что вы предлагаете? Я думал, что часы и номер потока являются случайными и поточно-ориентированными.   -  person Alireza    schedule 15.05.2018
comment
Хотя и не имеет прямого отношения: rand() не должен быть потокобезопасным (ср. POSIX stdlib.h)   -  person kvantour    schedule 15.05.2018
comment
Ваш тестовый код в том виде, в каком он написан, имеет состояние гонки на _1 _...   -  person Max Langhof    schedule 15.05.2018

Ответы (2)


arrow_upward
12
arrow_downward

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

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

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

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

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

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

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

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

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

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

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

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

person Max Langhof    schedule 15.05.2018
comment
Спасибо. Это кажется логичным, объявит ли SUM массив с размером количества потоков и назначит потоки для записи в их собственном SUM и суммирует их по завершении цикла, решит ли проблему? - person Alireza; 15.05.2018
comment
Да, это исправит, но вы можете получить количество потоков только в параллельной области, поэтому это немного неудобно (хотя и возможно). Но OMP также предоставляет предложения о сокращении, которые могут сделать это за вас. - person Max Langhof; 15.05.2018
comment
@Alireza, хотя это решение правильное, если оно не заполнено, оно имеет ужасную производительность из-за ложного совместного использования. Это хороший пример того, почему следует использовать идиоматическое решение (предложение о сокращении). - person Zulan; 15.05.2018
comment
Пробовал сократить предложение. Работал. Спасибо. - person Alireza; 15.05.2018
comment
Что касается атомарного, я бы рекомендовал #pragma atomic, а не std::atomic (https://stackoverflow.com/q/41309299/620382https://stackoverflow.com/q/41309299/620382) - person Zulan; 15.05.2018

arrow_upward
5
arrow_downward

Проблема не в вашем ГСЧ, а в вашем суммировании. Просто есть состояние гонки на 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)
person Zulan    schedule 15.05.2018
comment
Спасибо. Как и в первом ответе, проблема заключалась в том, что не использовалось предложение о сокращении. - person Alireza; 15.05.2018