2
$\begingroup$

Having multiple streams of pseudo-random numbers known to be independent and with a uniform distribution I want to do Monte Carlo simulations in parallel.

In other words, one thread will have a full-period independent and uniformly distributed stream of pseudo-random numbers. Each thread will consume these numbers in four different functions (a,b,c,d).

My concern is about the distribution across threads for each function. Thread.1 func_a.1, thread.2 func_a.2... and so on. Do I still need to make sure this distribution is indeed uniform across func_a1, func_a2, etc? Failing to do so can make my simulation have flaws?

In summary,if I start using the pseudo-random numbers in a "random" fashion, rejection sampling. Can I still be sure of the normal distribution among the different parts?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ It has be over a decade that I have looked at these but AFAIR the quality of random numbers you need for a parallel Monte Carlo simulation is a quite well-studied topic. I think you might get more relevant answers on Computational Science since these fall under numerical analysis. $\endgroup$ – Kaveh Nov 14 '13 at 23:33
4
$\begingroup$

Do not use a single stream of random numbers generated in one thread (or process) and consumed in other threads (or processes). In general, you must instead use several random number streams for your calculations, one for each thread/process. It is extremely important for these streams to be uncorrelated, in order for the pseudorandom numbers to be effective at the desired variance reduction, which is, of course, the point of large Monte Carlo calculations.

You may want to take advantage of the Scalable Parallel Random Number Generators Library (SPRNG), which is a parallel library (but you may also use it sequentially as well) providing these and other additional properties; it is particularly well suited for parallel Monte Carlo simulations.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks! I gave it a thought and came to the same conclusion. Another question regarding the same issue. Having independent streams per thread. In each thread I have four functions that consume random numbers. If func_a(rn_1) is true func_b(rn_#) else func_c(rn_#). Then func_d(rn_#). Note that rn_# is the next available random number. (I mixed both ideas in my original question, but ultimately this is the issue I am concerned about) Would I be thinning my stream of random numbers by picking them depending on the conditions? $\endgroup$ – mrei Nov 21 '13 at 15:54
  • $\begingroup$ If you pick random numbers generated by same PRNG within the same thread this may or may not work, depending strictly on your application. Bear in mind that random numbers provided by the same PRNG may be highly predictable (their sequence is known in advance once you fix the seed), so, for best results, I would use more than one PRNG in that thread as well. $\endgroup$ – Massimo Cafaro Nov 21 '13 at 19:22
1
$\begingroup$

It was already mentioned that it is important to use independent streams. Which is not guaranteed if you, e.g., use the naive approach of just seeding each of your PRNG with a different number. However, for Mersenne-Twister there exists a special implementation called Dynamic Creator where it is possible to draw seeds that give some guarantees regarding independence of the generated random numbers: http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/DC/dc.html

(Note: The next two sections describe techniques that I am quite sure are also used in the mentioned Library (SPRNG), but its also easy to just implement them with other frameworks, e.g., using the generators from the STL in C++.)

If you know how many independent streams and how many random numbers you need (which one usually does) you can use jump ahead for fast skipping of numbers accordingly. So if you want N random numbers per stream you initialize each stream with the same seed and skip 0, N, 2*N, ... numbers.

Last but not least you can generate N_cores*N_numbers random numbers and divide them up into packages of N_numbers numbers for your according cores / threads. (This is called Leapfrogging) However, this can be problematic if you draw many numbers, as autocorellation within the single stream will become corellation between the thus generated "parallel streams".

PS: In the blog article Finding the Best 64-bit Simulation PRNG a detailed overview regarding which PRNGs to use in practice is given (implementations in C)

PPS: I know this question is old. Yet, the last time I searched around regarding this subject it would have been nice to find at least some more detailed answers then use framework X ^^ so hopefully this is useful to someone.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.