# Parallel Random Number Generators

Posted by **Cleve Moler**,

This is the second of a multi-part series about the MATLAB random number generators. If you ask for `help rng`, you will get lots of information, including the fact that there are three modern generators.

'twister' Mersenne Twister 'combRecursive' Combined Multiple Recursive 'multFibonacci' Multiplicative Lagged Fibonacci

My previous post was about `twister`. Today's post is about the other two, `'combRecursive'` and `'multFibonacci'`, which are designed for parallel computing.

### Contents

#### Parallel computing demo

I frequently use the card game Blackjack to demonstrate parallel computing. At the same time I can demonstrate the random number generators. I regard Blackjack as a financial instrument, not unlike the stock of a publicly traded company. Simulating the size of an investment as a function of time is a typical application of the Monte Carlo technique.

Begin by opening a pool of workers.

parpool;

Starting parallel pool (parpool) using the 'local' profile ... connected to 2 workers.

Four players each play twenty thousand hands of Blackjack.

p = 4; n = 20000;

Collect the results in this array.

B = zeros(n,p);

A parallel `for` loop executes a Blackjack program that knows nothing about parallel computing.

parfor k = 1:p B(:,k) = cumsum(blackjacksim(n)); end

Plot the results.

plot(B) title(['Blackjack , $ ', int2str(sum(B(end,:)))]) xlabel('Number of hands') ylabel('Stake, ($)') axis([0 n -2500 2500])

#### Parallel streams

The card dealing calls the random number generator. It is essential that the different parallel workers have different, independent streams of random numbers. The default MATLAB generator `twister` does not offer this feature. Simply starting `twister` with different seeds on different workers does not provide statistically independent streams. So we turn to the other generators. To see which one is in use here, run a small `spmd`, "single program, multiple data" block.

spmd r = rng s = r.State' format short x = rand(1,7) end

Lab 1: r = Type: 'combRecursive' Seed: 0 State: [12x1 uint32] s = Columns 1 through 6 1720035765 2052922678 1637499698 3048064580 1173461082 2391850890 Columns 7 through 12 1862757735 2368998908 1385613640 1660833332 146924518 3104031825 x = 0.8789 0.6969 0.0409 0.4609 0.7528 0.2871 0.5241 Lab 2: r = Type: 'combRecursive' Seed: 0 State: [12x1 uint32] s = Columns 1 through 6 323405913 3817048408 3712601073 1070773748 1552739185 3267875480 Columns 7 through 12 1594297407 2533167732 3377045245 3413340742 2651847732 1248925296 x = 0.1072 0.3194 0.1048 0.6623 0.0878 0.3692 0.8035

We see that we have two workers, that they are both using the `combRecursive` generator, that they have the same `seed`, but different `states`, so they are generating different random numbers.

#### combRecursive

Also known as `mrg32k3a`. A 32-bit combined multiple recursive generator (CMRG), due to Pierre L'Ecuyer, at the Universite de Montreal, and his colleagues, described in the papers referenced below. This generator is similar to the CMRG implemented in the RngStreams package. It has a period of $2^{127}$, and supports up to $2^{63}$ parallel streams, via sequence splitting, and $2^{51}$ substreams each of length $2^{76}$. Here is a link to the C source code. combmrg2.c

The state of the backbone generator is a 2-by-3 array S that evolves at each step according to the linear recurrence expressed succinctly in MATLAB by

m1 = 2^32 - 209; m2 = 2^32 - 22853; x1 = mod(1403580*S(1,2)-810728*S(1,3),m1); x2 = mod(527612*S(2,1)-1370589*S(2,3),m2); S = [x1 S(1,1) S(1,2)) x2 S(2,1) S(2,2)];

A single precision random real `u` is then produced by

z = mod(x1-x2,m1); if z > 0, u = z/(m1+1); else, u = m1/(m1+1); end

The important feature of this generator is that it is possible to create different initial states for each worker in a parallel pool so that the resulting streams of random numbers are statistically independent.

#### multFibonacci

Also known as `mlfg6331_64`. A 64-bit multiplicative lagged Fibonacci generator (MLFG), developed by Michael Mascagni and Ashok Srinivasan at Florida State University. This generator, which has lags $l=63$ and $k=31$, is similar to the MLFG implemented in the SPRNG package. It has a period of approximately $2^{124}$. It supports up to $2^{61}$ parallel streams, via parameterization, and $2^{51}$ substreams each of length $2^{72}$.

The state of this generator is a length 63 vector of 64-bit integers S. The recurrence relation is

$$ x_n = x_{n-k} \times x_{n-l} (mod 2^{64}) $$

Each random double precision value is created using one 64-bit integer from the generator; the possible values are all multiples of $2^{-53}$ strictly within the interval (0,1).

Again, the important feature of this generator is that it is possible to create different initial states for each worker in a parallel pool so that the resulting streams of random numbers are statistically independent.

#### Which one?

Which one should you use? Most of the time, stick with the default and you'll be OK. You will get `'twister'` in serial computations and `'combRecursive'` on the workers in a parallel pool. You can use

rng('shuffle')

at the beginning of a session if you want different sequences of random numbers in different sessions. Otherwise, don't worry about setting the generator or the seed.

If you want to experiment, you can use `rng` to try different generators and different starting seeds on your computation. If you find a problem where it makes a significant difference, please let us know.

#### Thanks

Thanks again to Peter Perkins.

#### References

Pierre L'Ecuyer, R. Simard, E. J. Chen, and W. D. Kelton. "An Objected-Oriented Random-Number Package with Many Long Streams and Substreams." Operations Research, 50(6):1073-1075. 2002. <http://www.iro.umontreal.ca/~lecuyer/myftp/papers/streams00.pdf>

Pierre L'Ecuyer. "Good Parameters and Implementations for Combined Multiple Recursive Random Number Generators." Operations Research 47(1):159-164. 1999. <http://dx.doi.org/10.1287/opre.47.1.159>

Michael Mascagni and Ashok Srinivasan. "Parameterizing Parallel Multiplicative Lagged-Fibonacci Generators." Parallel Computing, 30: 899-916. 2004. <http://www.cs.fsu.edu/~asriniva/papers/mlfg.ps>

Michael Mascagni and Ashok Srinivasan. "SPRNG: A Scalable Library for Pseudorandom Number Generation." ACM Transactions on Mathematical Software, Vol 26 436-461. 2000. <http://www.cs.fsu.edu/~asriniva/papers/sprngacm.ps>

Get the MATLAB code

Published with MATLAB® R2014b

**18**views (last 30 days) | |

**Category:**- Algorithms,
- Random Numbers,
- Supercomputing

### Comments

To leave a comment, please click here to sign in to your MathWorks Account or create a new one.

## Recent Comments