Generating random numbers in parallel

This is a discussion on Generating random numbers in parallel within the C++ Programming forums, part of the General Programming Boards category; Hi I generate a series of random numbers in parallel (using OpenMP ), but depending on what number of threads ...

  1. #1
    Registered User
    Join Date
    Aug 2009
    Posts
    140

    Generating random numbers in parallel

    Hi

    I generate a series of random numbers in parallel (using OpenMP), but depending on what number of threads I invoke, I get a different result. From that I conclude that I have made an error somewhere!

    Here is the MWE, which generates a number between 0..1 and increments a variable if the generated variable is larger than 0.5:

    Code:
    #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;
    }

    When I set max_threads=1 I get 50027, but when max_threads=60 (on a machine that supports it....) I get 50440.

    The sensitive RNG and its engine I have declared within the parallelized area, so it's not really clear to me where the error can possibly be.

    Can someone spot my error that is apparently there?
    Last edited by Niels_M; 11-08-2013 at 05:59 AM.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    I've not used the new fancy RNGs, but am I correct in believing that eng(0) seeds your RNG (so that your results are repeatable)? If so, I would expect your single-threaded version to use 100,000 numbers starting from <0>, but your 60-threaded version to re-use the first 16,667 numbers 60 times (as each thread would be seeded to <0>, right?) and so get a different result.

  3. #3
    Registered User
    Join Date
    Aug 2009
    Posts
    140
    Quote Originally Posted by tabstop View Post
    I've not used the new fancy RNGs, but am I correct in believing that eng(0) seeds your RNG (so that your results are repeatable)? If so, I would expect your single-threaded version to use 100,000 numbers starting from <0>, but your 60-threaded version to re-use the first 16,667 numbers 60 times (as each thread would be seeded to <0>, right?) and so get a different result.
    Ahh, of course. You are correct, don't know why I didn't realize that.

    Do you agree with my overall structure of the program? I.e., that each thread gets its own engine in order to avoid "scrambling" them together?

  4. #4
    Registered User
    Join Date
    Jun 2005
    Posts
    6,259
    Quote Originally Posted by Niels_M View Post
    Do you agree with my overall structure of the program? I.e., that each thread gets its own engine in order to avoid "scrambling" them together?
    Well, no. Pseudorandom number generators tend to be sequential (i.e. the (N-1)th value needs to be produced before the Nth) which means they can't be broken into parallel pieces.

    You'll somehow need to anticipate the required starting condition (e.g. the first random value to be produced) for every thread.
    Right 98% of the time, and don't care about the other 3%.

  5. #5
    Registered User
    Join Date
    Aug 2009
    Posts
    140
    Quote Originally Posted by grumpy View Post
    Well, no. Pseudorandom number generators tend to be sequential (i.e. the (N-1)th value needs to be produced before the Nth) which means they can't be broken into parallel pieces.

    You'll somehow need to anticipate the required starting condition (e.g. the first random value to be produced) for every thread.
    I meant that if I seed every engine uniquely, then my approach seems correct (?)

  6. #6
    Registered User
    Join Date
    Jun 2005
    Posts
    6,259
    Quote Originally Posted by Niels_M View Post
    I meant that if I seed every engine uniquely, then my approach seems correct (?)
    You're the one expecting the same output, regardless of number of threads. Seeding each "engine" separately (where, by engine, I assume you mean each thread) will not achieve that.
    Right 98% of the time, and don't care about the other 3%.

  7. #7
    Registered User
    Join Date
    Apr 2013
    Posts
    1,279
    You need to create a separate program cycle the RNG through the number of cycles expected for each thread to determine the starting seed for each thread if you want the multiple threads to use the same set of pseudo random numbers as a single thread.

  8. #8
    Registered User
    Join Date
    Jun 2005
    Posts
    6,259
    Quote Originally Posted by rcgldr View Post
    You need to create a separate program cycle the RNG through the number of cycles expected for each thread to determine the starting seed for each thread if you want the multiple threads to use the same set of pseudo random numbers as a single thread.
    Which is my point. That's the way to ensure the same output, I agree. Having to do a substantial portion of calculations sequentially and in advance negates a lot of the benefits of using threads.

    Such is the nature of trying to make a sequential process (in the sense that later results depend on earlier ones) into a multithreaded process.
    Right 98% of the time, and don't care about the other 3%.

  9. #9
    Registered User
    Join Date
    Apr 2013
    Posts
    1,279
    Quote Originally Posted by grumpy View Post
    Having to do a substantial portion of calculations sequentially and in advance negates a lot of the benefits of using threads.
    Depends if the multi-threaded process(es) will get used repeatedly, using the same seeds as the values determined from the single sequential run.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help generating random numbers
    By com64 in forum C Programming
    Replies: 2
    Last Post: 09-26-2007, 11:15 PM
  2. Need Help Generating Random Numbers In C++
    By slickwilly440 in forum C++ Programming
    Replies: 11
    Last Post: 09-18-2005, 01:38 PM
  3. Generating Random Numbers
    By Flakster in forum C++ Programming
    Replies: 14
    Last Post: 08-22-2005, 12:50 PM
  4. Generating Random Numbers
    By pizzapie in forum C++ Programming
    Replies: 17
    Last Post: 09-23-2004, 02:46 AM
  5. Generating Random Numbers
    By knight543 in forum C++ Programming
    Replies: 3
    Last Post: 01-11-2002, 05:55 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21