A Brief on Parallel Random Number Generators

Parallel computing is important on any of the NERSC platforms today. One of the easiest kinds of computing to parallelize is Monte Carlo computation, in which many replicates of a stochastic simulation contribute to a final answer. The process of parallelizing such an application is so straightforward that Monte Carlo programs are sometimes referred to as "embarrassingly parallel" programs. This is because their structure usually consists of a set of code executions differing only in the sequences of pseudo-random numbers they use.

However, stochastic simulation is always only as good as the (pseudo-)random numbers one uses in it, and there are non-trivial pitfalls in writing a parallel version of such a code. This note will describe why naive use of random numbers in a parallel code may cause problems, and will describe manageable ways around this problem.

Cross-Platform Difficulties

While there are a few random number generators that have found enough favor to be available on multiple platforms, there is no "lingua-franca". The natural tendency of system vendors to invent their own "better mousetraps" causes most generators to differ. This, coupled with differences in arithmetic algorithms, operand precisions, and compiler optimizations, makes cross-platform compatibility a significant problem. However, there are ways to address these issues. First, there ARE a few common generators, and some new packages are showing up that have been built especially for multiple-platform use. Second, most vendor-supplied and all public-domain generators have published algorithms, none is difficult, and most can be implemented efficiently in high level languages, such as Fortran 90. Third, many compilers can be made to avoid using special instructions that diminish (or increase!) arithmetic precision from some norm. Fourth, the obvious norm to seek is compliance with the IEEE standard for floating point arithmetic. This may not be a problem if, for instance, you want random integers, but even then operand size differences between systems may cause trouble. Careful choice of a generator, and attention to these operational details, can give acceptable portability.

Difficulties in Parallel Use of Random Numbers

In the serial world, one gets used to simply making a call like X = RANF(), and it is tempting to think this might work in a parallel code as well. After all (one might reason), RANF and the C function random() just return random numbers, so why shouldn't the numbers resulting from a call in a parallel program be equally random?

One problem is that in the Single-Program, Multiple Data (SPMD) scheme of parallelism used on NERSC's MPP distributed-memory platforms, each processor gets an independent copy of all program variables, including any seeds for random variables. This would mean that each processor would get exactly the same sequence of numbers, resulting in a number of identical runs. This is surely not what anyone would want.

A different problem occurs on shared-memory platforms. There, the results of a naive approach are at best non-reproducible, since the order in which processors demand numbers from a single, shared generator may vary from run to run. There is even the possibility of "race conditions" where one processor is using a seed while another is updating it, which could result in some numbers being handed out more than once, or an otherwise unrepeatable sequence being generated. These race conditions could be eliminated by the use of software locks on the seed variables (at considerable computational cost), but the order-indeterminacy would remain.

Some users of production codes would be willing to accept indeterminacy in their results. But a non-reproducible code is almost impossible to debug, since one could not at will produce the exact sequence of events that led to an execution problem.

Stream-Based Random Number Generation

A better solution is to design codes so that one provides for separate, independent "streams" of random numbers. These streams may simply be assigned to a processor or task, or they can be assigned in some way that is finer-grained than the level of parallelism. For instance, in a neutron-tracking code, one might provide a different stream of numbers for each particle that is followed.

There is no generally accepted perfect way to generate an arbitrarily large number of distinct streams of random numbers, especially if identical behavior is desired across platforms; but three solutions are currently available on NERSC platforms, differing in their portability and simplicity.

erand48: Maintaining Your Own Seeds

SGI/Cray provides one useful tool in the form of erand48 and related routines. These demand that the user manage and store distinct state information for each stream of numbers; this "seed" is passed into the generator, transformed, and passed back on return along with the generated number. Seed management and generation is left completely up to the user. It is possible to generate seeds that are more or less randomly scattered around the period of erand48, which should be sufficient for many applications.

PRANF: Portable slow RANF-compatible generation

The PRANF code suite, developed ten years ago for a variety of applications, provides the generator of SGI/Cray's RANF together with a set of seed generation routines. The user decides on the number of streams and calls an initialization routine, which sets starting points roughly (but not exactly) uniformly around the sequence of RANF. This suite is extremely portable (requiring only integer arithmetic to modulus 4096) and offers maximal compatibility with the legacy RANF generator, but is also very slow. For more information on this code, including a download location for Fortran-90 source, see The PRANF Portable Parallel Random Number Generator.

SPRNG: An Industrial-Strength Multi-Platform Library

The Scalable Parallel Random Number Generators (SPRNG) library provides what is possibly the best solution available right now. In addition, it has been compiled for many platforms (though it is not truly portable code). It includes a variety of generators and a "spawn" facility to generate new streams. Unfortunately, the user must select among the various generators (which are by no means of equal quality) with little guidance. NERSC User Services is experimenting with the SRPNG library, and further guidance in its use, based on our efforts, is available in Using SPRNG at NERSC. Currently, work is under way to test it.