Next: Parallel Computing in Up: 7 Independent Parallelism Previous: 7.4 Statistical Gravitational Lensing

# 7.5 Parallel Random Number Generators

Many important algorithms in science and engineering are of the Monte Carlo type. This means that they employ pseudorandom number generators to simulate physical systems which are inherently probabilistic or statistical in nature. At other times, Monte Carlo  is used to getting a fast approximation to what is actually a large, deterministic computation. Examples of this are Lattice Gauge  computations (Section 4.3) and Simulated Annealing  methods (Sections 11.1.4 and 11.4).

Figure 7.13: A Comparison of the Sequential and Concurrent Generation of Random Numbers

Even for a sequential algorithm, the question of correlations between members of the pseudorandom number sequence is nontrivial. In the parallel case, at least for the popular linear congruential algorithm, it is easy for the parallel algorithm to exactly mimic what a sequential algorithm would do. This means that the parallel case can be reduced to the well-understood sequential case.

The fundamental idea is that the processors of an N processor concurrent computer each compute only the Nnumber of the sequential random number sequence. The parallel sequences are staggered and interleaved so that the parallel computer exactly reproduces the sequential sequence. Figure 7.13 illustrates what happens in the parallel case versus the sequential case for a four-processor concurrent computer.

Chapter 12 of [Fox:88a] has an extensive discussion of the parallel algorithm. This reference also has a discussion of what to do to achieve exact matching between parallel and sequential computations in more complex applications. We extend this work from the linear congruential method of [Fox:88a] to the so-called shift register sequences, which have longer periods and less correlations than the congruential method [Chiu:88b], [Ding:88d]. As an illustration, we use Ding's Fibonacci additive random number generator developed for the QCD calculations on the Mark IIIfp, as previously described in Section 4.3. This uses the sequence

This has a period longer than . The assembly language code for Equation 7.12 on the Mark IIIfp took to generate a floating-point random number normalized to the range [0,1).

Next: Parallel Computing in Up: 7 Independent Parallelism Previous: 7.4 Statistical Gravitational Lensing

Guy Robinson
Wed Mar 1 10:19:35 EST 1995