7
$\begingroup$

Consider the following scenario: I want to perform a large Monte Carlo simulation across a compute cluster with several nodes. To avoid excessive transmission of data, I am going to generate random data for my simulation on the individual nodes. Using Python, I would like to do this using numpy.random functions.

I need to ensure that the individual nodes generate different random data (if they generate the same they will just be replicating each other's work). I can do this by selecting different seeds for the RNGs on the individual nodes. But how do I select these seeds to ensure that the resulting random number sequences do not accidentally intersect somewhat across different nodes?

If I simply generate random seed numbers for my compute nodes on one node submitting the workloads to the compute nodes, I could theoretically end up in the situation where the compute nodes generate random number sequences that intersect somewhat in the RNGs' space of possible random number sequences, attempted illustrated here:

node 1  |-------************----------------------------------------------|
node 2  |----------------------------------************-------------------|
node 3  |---************--------------------------------------------------|

The ***s illustrate the sequence of random numbers generated by each node and their starting point is given by the (randomly generated) seed given to each of them at the beginning of their work. I realise that the space of possible random number sequences is probably enormous and the probability of this happening is probably quite low, but how do I ensure that it cannot happen (assuming that the nodes' collective demand for random numbers does not exhaust the space fo possible random sequences)?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ In addition to overlapping sequences (which I think has a fairly small probability of failure), there is another issue I remember reading about (iro.umontreal.ca/~lecuyer/myftp/papers/parallel-rng-imacs.pdf, p.12) that copies of an RNG started from (accidentally) similar seeds will produce unusually correlated sequences and should not be assumed to be independent. $\endgroup$
    – Kirill
    Commented Sep 5, 2016 at 23:12

3 Answers 3

Reset to default
13
$\begingroup$

To the best of my knowledge, Numpy does not support independent streams. Indeed, getting independent streams from the Mersenne Twister (Pythons RNG) is notoriously difficult although it can be done.

Consider using the RandomGen package. It is fully compatible with Numpy, and provides you with the PCG64 generator, supporting up to $2^{63}$ independent streams. Arguably enough for most datacenters. See the documentation for details.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ I was not aware of RandomState. It sounds very attractive that it drops right into NumPy. $\endgroup$
    – Thomas Arildsen
    Commented Sep 5, 2016 at 23:10
  • 2
    $\begingroup$ For completeness, I'll add that "counter based RNGs" are also very appropriate for parallel computing thesalmons.org/john/random123 altough there is no Python implementation that I know of. $\endgroup$
    – Pierre de Buyl
    Commented Sep 27, 2016 at 12:26
  • 1
    $\begingroup$ The RandomState package appears to be dead now. Its replacement is the RandomGen package. Also, this package now appears to support ThreeFry and Philox, which reference the "1, 2, 3" paper mentioned in the previous comment... $\endgroup$
    – Praveen
    Commented Feb 22, 2019 at 0:01
5
$\begingroup$

It is not a problem if one processor generates a number that has already appeared on a different processor. It would, however, be a problem if the two generated whole sequences that are similar. This is unlikely, if you start with different random seeds, since the number of numbers you get from a RNG before it starts to repeat itself (the cycle length) is so enormously large that randomly chosen starting points are very unlikely to lead to overlapping sequences.

But if you wanted to avoid this for sure, then why not the following procedure: let's assume you have two processors, then let every processor generate the same sequence from the same seed, and let processor zero only take the 0th, 2nd, 4th, ... element of this sequence, and processor one the 1st, 3rd, 5th, ... element. If you have $P$ processors, let the $p$th processor take element $x_i$ of the random number sequence if $i = p \mod P$. This guarantees a cycle length for each process that is maximal, and you will for sure not get any overlapping sequences.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Re: your first paragraph - exactly my point. I was asking about guaranteeing that this does not happen. Your solution would work in principle, but let's say you generate a lot of random numbers. Although generating them all on all nodes is perhaps faster than broadcasting them all across the network, it still seems very clumsy and could take prohibitively much memory and time. $\endgroup$
    – Thomas Arildsen
    Commented Sep 5, 2016 at 23:07
  • $\begingroup$ I think your suggestion is usually called the leap-frog technique, it's about $p$ times slower, and (iro.umontreal.ca/~lecuyer/myftp/papers/parallel-rng-imacs.pdf, p.12) there are better, more robust ways to create streams. $\endgroup$
    – Kirill
    Commented Sep 5, 2016 at 23:14
  • 2
    $\begingroup$ My suggestion will definitely be far faster than broadcasting numbers :-) Communication is sooo slow compared to how cheap it is to compute random numbers. Also, generating numbers requires $O(1)$ memory, since you only ever store the last one and some minimal internal state; it doesn't cost anything in terms of memory to create a few million or billion numbers. $\endgroup$
    – Wolfgang Bangerth
    Commented Sep 6, 2016 at 1:47
  • $\begingroup$ That is of course a good point - each node does not have to store all those random numbers before it selects its chunk of them. Point taken. It actually seems an attractively simple yet crude technique to ensure that the nodes do not overlap. $\endgroup$
    – Thomas Arildsen
    Commented Sep 6, 2016 at 2:49
  • $\begingroup$ The leapfrogging will certainly work, with the disadvantages of time consumption and the fact that you have to decide on the maximum number of nodes at the beginning. The problem is much more complicated than simply not getting the same numbers however. You want the streams to be statistically independent, which in general cannot be guaranteed by just changing the seeding. $\endgroup$
    – LKlevin
    Commented Sep 6, 2016 at 7:38
1
$\begingroup$

This exact problem (not generating the same random number sequences) is described in John D. Cook's blog post Random number generator seed mistakes.

The solution is simply to ensure that processes are started with an unique seed. Which you also mention as a possibility in your question. I think your figure might be a bit misleading as most random number generators will not produces random sequences that overlap in the way shown.

From John's post:

In this case it would have been better to seed each process with sequential seeds: give the first process seed 1, the second seed 2, etc. The seeds don’t have to be random; they just have to be unique. If you’re using a good random number generator, the outputs of 1,000 processes seeded with 1, 2, 3, ..., 1000 will be independent.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ It is important to note that John's comment is only valid for ideal random number generators, and not true for a number of otherwise reputable RNGs such as Ranlux. Sequential seeds can give correlated streams for the first hundreds of numbers (see this paper for instance). In the specific case of Pythons RNG, it would be better to simply use the default seeding, as this is based on /dev/urandom to fill the state. $\endgroup$
    – LKlevin
    Commented Sep 9, 2016 at 10:31
  • 1
    $\begingroup$ @LKlevin Unfortunately, random initialisation does not sound very reproducible. Doesn't that require me to save a very large state of the RNG as opposed to just seeding it with a random number? $\endgroup$
    – Thomas Arildsen
    Commented Sep 14, 2016 at 15:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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