NHSE ReviewTM 1996 Volume Second Issue

Random Number Generators for Parallel Computers

| <- HREF="node2.html" Prev | Index | Next -> |
NHSE ReviewTM: Comments · Archive · Search

Section 1 -- Introduction  

Random number generators are widely used for simulations in computational science and engineering. Randomness is often present in the formulation of the problem, for example random noise or perturbations, and quantum processes. In addition, many algorithms are probabilistic, for example Monte Carlo simulation and stochastic optimization techniques such as simulated annealing or genetic algorithms. Random number generators are also used in many other applications, from slot machines to cryptography.

Since ``random'' numbers are in practice computed using deterministic algorithms, these are more accurately called pseudo-random number generators. In some simulations, the quality of the pseudo-random numbers (how closely they resemble truly random sequences) is not that important. However in many of the problems for which random numbers are most heavily used, such as Monte Carlo simulation, the quality of the random number generator is crucial. This is especially true in large-scale simulations on parallel supercomputers, which consume huge quantities of random numbers, and require parallel algorithms for random number generation.

As noted in a number of previous review articles [1, 2, 3, 4, 5, 6, 7], random number generators provided by computer vendors or recommended in some papers and computer science texts have often been of poor quality. Even generators that perform well in standard statistical tests for randomness have sometimes proven to be unreliable for certain applications, particularly in Monte Carlo simulations [8, 9, 10, 11, 12, 13, 14, 15, 16, 17]. The many problems caused in the past by inadequate random number generators on sequential and vector computers are likely to be repeated in a new generation of simulations using parallel computers, unless parallel random number generators are very carefully studied and tested, and the best algorithms made readily available to users.

The aim of this review is to provide up-to-date information and recommendations concerning the use of random number generators on parallel computers. A summary of the current state-of-the-art in the development of random number generators for parallel computers is presented, along with the results of theoretical evaluations and empirical tests of these generators. For each of the common algorithms used in parallel random number generators, we give examples of software implementations of the algorithm, and state any known problems with the algorithm or the implementation of the generator on current high-performance computers.

Since this review is aimed primarily at users who may not be interested in the theoretical details of the various algorithms for generating random numbers, many of the technical details have been omitted in order to keep the presentation as simple as possible. More detailed information can be found in a number of other reviews [1, 2, 3, 4, 5, 6, 7].

Copyright © 1996

| <- HREF="node2.html" Prev | Index | Next -> |
NHSE ReviewTM: Comments · Archive · Search

Paul Coddington, paulc@npac.syr.edu