Am I doing right to generate random number for a openmp accelerated program?

Question

I need to build a binary tree, and when branching the tree from list of points, I need to randomly pick a branch point, and I want to use openMP to accelerate my program, below is how I am doing it. It seems that the random engine gg would be shared and accessed by all threads, will this make the number it generated less random or slow down my program due to data race? If so, how could I avoid that? should I declare the std::mt19937_64 gg inside the build function?

#include<random>
#include<omp.h>
std::mt19937_64 gg(std::random_device {}());
int main()
{
    omp_set_num_threads(128);
    #pragma omp parallel
    {
        #pragma omp single nowait
        buildFromPoints(0, 0, 1000000);
    }
    return 0;
}
void buildFromPoints(int idx, int lower, int upper)
{
    std::uniform_int_distribution<int> distr(lower, upper - 1);
    int povotIdx = distr(gg);
    // do sth with the random pivotIdx
    if (problemSizeIsSmall)
    {
        buildFromPoints(subPara1, subPara2, subPara3);
        buildFromPoints(subPara4, subPara5, subPara6);
    }
    else
    {
        #pragma omp task
        {
            // sub-tree left
            buildFromPoints(subPara1, subPara2, subPara3);
        }
        #pragma omp task
        {
            // sub-tree right
            buildFromPoints(subPara4, subPara5, subPara6);
        }
    }
}

score 0 · Answer 1 · edited May 23 '17 at 12:30

As far as I know, random engines are not thread safe when used with distributions, since the distribution changes their state. One solution is to declare them using the new C++11 thread storage duration specifier thread_local, like

thread_local std::mt19937_64 gg(std::random_device {}());

Be aware though that not all standard library implementations support thread_local: g++'s libstdc++ supports it, but clang libc++ does not. And I am pretty sure VS does not support it either.

If you cannot use thread_local, then I suggest defining your random number generator local to your function. If you still want to keep it global, then you have to protect it with a mutex, but I don't think it's worth the overhead and slow-down.

More details about thread_local: What does the thread_local mean in C++11?

Am I doing right to generate random number for a openmp accelerated program?

1 Answers1