Given the growing interest in parallel processing through GPUs or multiple processors, there is a clear need for a proper use of (uniform) random number generators in this environment. We were discussing the issue yesterday with Jean-Michel Marin and briefly looked at a few solutions:
- given p parallel streams/threads/processors, starting each generator with a random seed provides no guarantee for independence between the sequences;
- since most random generators are periodic with humongous periods T, starting the i-th sequence at
should see no overlap between the sequences if p is not enormous. But finding the (iT/p)-th value of the sequence is not necessarily feasible;
- using a single starting seed
, allocating each new value 
to the i-th processor if 
is ensuring independence between the sequences, but it sounds contradictory with parallel computing requirements. However, if the p-step version 
of the generator can be derived [and coded], we simply need to start the i-th sequence at 
and use transforms of this starting point by . This is actually a well-known method that goes under the name of the leapfrog technique, proposed by Bowman and Robinson in 1987 at a SIAM conference (taking place in Philadelphia, of all places!). There are subsequent papers in the literature that cast doubt on the performances of this technique, but I do not see why… Since the original pseudo-random generator is assumed to be correct, (a) taking a subsequence from the main sequence should preserve the uniformity and independence, and (b) the subsequence should have a long enough period if p remains within hundreds..
Obviously, we did not do any serious search in the recent literature and there are many other approaches to be found in the computer literature, including the scalable parallel random number generation (SPRNG) packages of Michael Mascagni (including an R version) and Matsumoto’s dynamic creator, a C program that provides starting values for independent streams when using the Mersenne twister.
This entry was posted on October 28, 2010 at 9:09 am and is filed under R, Statistics with tags Mersenne twister, Monte Carlo methods, parallel processing, random number generation, SPRNG. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.
Given the growing interest in parallel processing through GPUs or multiple processors, there is a clear need for a proper use of (uniform) random number generators in this environment. We were discussing the issue yesterday with Jean-Michel Marin and briefly looked at a few solutions:
Xi'an's Og 
March 13, 2012 at 12:13 am
[…] cool illustration of the new challenges posed by parallel implementations (like the development of proper random generators). […]
December 28, 2010 at 12:17 pm
[…] Here is the poster presented at MCMSki III next week by Pierre Jacob about our joint paper on parallelisation: […]
October 28, 2010 at 4:14 pm
L’Ecuyer & al propose a package as well:
http://www.iro.umontreal.ca/~lecuyer/myftp/streams00/
it’s based on the MRG32k3a, the period is around 3*10^57, and it shows good statistical properties. It provides convenient functions to jump to the next substream, so it seems to be a good candidate for parallel computation.
Also, in Nvidia’s CUDA SDK (available freely on their website), there are many examples including a parallel implementation of the Mersenne Twister.