Comments:
Flow chart.
««« the write up in the pattern is a bit weak in its discussion of parallel random number generators. I suggest the following text insted »»
Random numbers are challenging for a parallel computation. First off, the period of the pseudo random number generator must be larger than the sequence used in the computation. Random number generators are parameterized and in a quality generator, the programmer can choose parameters that produce the required period.
Even if the period is long enough, the generator must be thread safe producing correct results regardless of simultaneous access by multiple threads.
Even with these issues correctly resolved, there are special problems that arise with parallel random number generators. Randomly picking seeds is not an option since they can lead to overlapping subsequences of random numbers. Thinking of the problem naively, the sequence of numbers are generated by an inherently serial finite state machine. This has led some programmers to dodge the issue by having a single thread generate all the needed numbers which are then used by the other threads.
But there are ways around this problem.
1. Use a family of generators with parameters that can be proven to produce statistically uncorrelated numbers. Example: the Wichmann-Hill generators which have 273 parameter sets proven to generate uncorrelated sequences.
2. Generate interleaved sets of random numbers by the leap-frog method … i.e. for 3 threads, the first thread computes values in the psedo-random sequence, 0, 3, 6, … the second thread 1, 4, 7, … and the third thread 2, 5, 8 …
3. Carefully pick seeds so you provide a block of contiguous values … e.g. with three threads, the first thread gets the first third, the second thread the second third, and the last thread the remaining values in the sequence. This approach is supported in SPRNG.
The first method is often the easiest approach to use. The other two methods, if used carefully, can generate the same pseudo random sequence regardless of the number of threads. This is irrelevant mathematically, but it is very convenient when debugging your program and validating the results.
Creating your own random number generator is risky. The programming is straightforward. You look up some simple formulas and a set of parameters and write the code. But validating the statistical properties of your generators and validating that the results are uncorrelated among parallel threads is very complex. Hence standard libraries should be used such as MKL or SPRNG.