Параллельная генерация случайных чисел

Я пишу параллельную программу, используя open mp, в которой я генерирую матрицу случайных чисел с плавающей запятой, а затем выполняю ряд вычислений. В настоящее время я хочу сделать шаг, на котором я генерирую матрицу, работающую параллельно, но у меня есть проблема, заключающаяся в том, что функция rand() не предназначена для одновременного запуска. Я не хочу использовать блокировки для обеспечения мьютекса на rand, потому что это единственное, что делается в цикле, и, вероятно, было бы более эффективно запускать его последовательно. Есть ли способ сделать этот шаг эффективно параллельно?

Здесь, если текущий код для этой части (без мьютекса на rand);

#pragma omp parallel default(private)
{
    int i= omp_get_thread_num();
    for(int j=0; j<cols; j++)
        matrix[i][j]= rand()%1000 + (float)(rand()%100)/(float)(rand()%1000);
}

c++ random openmp
person njvb    schedule 20.11.2010    source источник
comment
PRNG генерируют последовательную последовательность чисел из фиксированного начального числа. Этот порядок (повторяемость) важен для вас или вам действительно нужен случайный?   -  person Ben Jackson    schedule 20.11.2010
comment
Неважно, расположены ли они в каком-либо определенном порядке, проблема, с которой я столкнулся, заключалась в том, что когда я запускал ее последовательно, я получил довольно хороший разброс по моему диапазону, но когда я изменил его на параллельный, в целом числа были меньше 10, а когда Я суммирую строки, почти все из них в сумме дают 0 (у меня никогда не было минусов с последовательностью). Это заставляет меня думать, что есть какая-то проблема параллелизма с вызовом функции.   -  person njvb    schedule 20.11.2010
comment
Подождите секунду — в среднем раз в тысячу итераций rand() % 1000 будет равно нулю, так как же вы можете на него делить?   -  person TonyK    schedule 20.11.2010
comment
Да, матрица и столбцы должны быть общими, а не частными — я предполагаю, что этот код предназначен только для демонстрационных целей.   -  person Jonathan Dursi    schedule 20.11.2010
comment
да, они общие, но все они записываются в разные элементы матрицы, а строки и столбцы являются константами, поэтому в любом случае у них не должно быть условий гонки. Я заметил, что изменение i на omp вместе с rand_r по строкам устранило состояние гонки со странным выводом. @TonyK да, и это давало мне информацию об этой должности.   -  person njvb    schedule 20.11.2010
comment
@Jonathan Dursi: Если этот код предназначен только для демонстрационных целей, то он демонстрирует, что user381261 небрежен. Вы не можете позволить себе быть небрежным, когда пишете параллельные программы.   -  person TonyK    schedule 22.11.2010

Ответы (4)


arrow_upward
4
arrow_downward

Если вы используете C++, вам следует рассмотреть возможность использования библиотеки Boost. классы случайных чисел. Вы можете создать уникальный экземпляр PRNG для каждого потока. Если вам требуется повторяемость, вы можете инициализировать каждый экземпляр в своем основном потоке повторяющимися начальными значениями.

ОБНОВЛЕНИЕ: оказалось, что после того, как я написал это, был выпущен C++11, и он включал более современную библиотеку для генерации случайных чисел. Он включает в себя std::uniform_int_distribution и std::std::uniform_real_distribution, оба из которых основаны на генераторе, таком как std::mersenne_twister_engine (или конкретная конфигурация std::mt19937). Например:

#include <random>
#include <iostream>

int main() {
    std::mt19937 gen;  // Uses default seed value to generate repeatable sequence
    std::uniform_int_distribution<int> d20(1,20);
    std::uniform_real_distribution<float> prob(0.0, 1.0);

    std::cout << d20(gen) << std::endl;
    std::cout << prob(gen) << std::endl;

    return 0;
}
person andand    schedule 20.11.2010

arrow_upward
4
arrow_downward

Я думаю, вы ищете rand_r(), который явно принимает текущее состояние ГСЧ в качестве параметра. Затем у каждого потока должна быть собственная копия начальных данных (хотите ли вы, чтобы каждый поток начинался с одного и того же начального числа или разных, зависит от того, что вы делаете, здесь вы хотите, чтобы они были разными или вы будете получать одну и ту же строку снова и снова).

Здесь обсуждается rand_r() и безопасность потоков: является ли rand_r настоящим потокобезопасным? .

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

#pragma omp parallel default(none) shared(matrix, cols)
{
    int i= omp_get_thread_num();
    unsigned int myseed = i;
    for(int j=0; j<cols; j++)
        matrix[i][j]= rand_r(&myseed)%1000 + (float)(rand_r(&myseed)%100)/(float)(rand_r(&myseed)%1000 + 1);
}

Теперь каждый поток изменяет исключительно свое состояние (rand_r() — это чистая функция), и вы должны быть свободны дома.

person Jonathan Dursi    schedule 20.11.2010
comment
Вот ответ, который нам нужен! Спасибо. - person David Guyon; 13.09.2019

arrow_upward
0
arrow_downward

Если псевдослучайный метод достаточно хорош (см. комментарий Бена), то вы можете создать свой собственный PRNG (например, Mersenne Twister, а не слабый метод по модулю, используемый в большинстве систем) и реализовать один независимый генератор для каждого потока. если вы сделаете это, вы ДОЛЖНЫ убедиться, что у каждого генератора разные начальные числа.

person winwaed    schedule 20.11.2010

arrow_upward
0
arrow_downward

Настоящая проблема заключается в том, если вам нужна воспроизводимость, которая часто требуется при тестировании. С заданным начальным числом сгенерируйте последовательность начальных значений потока. Затем каждый поток будет использовать собственное начальное число для генерации чисел.

Тот факт, что rand() не является потокобезопасным, вряд ли является проблемой. Существует множество доступных алгоритмов, и тривиально создать один экземпляр (состояние) для каждого потока, просто начните с http://en.wikipedia.org/wiki/Random_number_generation#Computational_methods, например. Блокировка для каждого вызова rand() была бы катастрофой параллелизма.

person Remus Rusanu    schedule 20.11.2010