Using linear congruential generators for parallel random number generation

ABSTRACT

Linear congruential random number generators are widely used in simulation and Monte Carlo calculations. Because they are very fast, and because they have minimal state space, they remain attractive for use in parallel computing environments. We discuss their use as a source for many streams of pseudo-random numbers. Many authors have discussed splitting the stream of a single CRNG into many substreams; we show spectral calculations for this scheme and compare randomly and regularly spaced selection of starting points. Several authors have suggested using a common multiplier for all streams and a unique additive constant for each. The discrepancies of such schemes are no better than for splitting schemes; we show how they are in a sense equivalent. We also consider the use of distinct multipliers for each stream. Good multipliers are abundant for large enough moduli, but little is known about the multidimensional behavior of such generators. We discuss the use of improvement techniques and larger moduli to overcome the limitations of linear congruential generators.

REFERENCES

• 1: Beyer, W. A. (1972). Lattice Structure and Reduced Bases of Random Vectors Generated by Linear Recurrences. Applications of Number Theory to Numerical Analysis, ed. S. K. Zaremba, New York: Academic Press, 361--370.
• 2: Coveyou, R. R., and MacPherson, R. D. (1967). Fourier Analysis of Uniform Random Number Generators. Journal of the Association for Computing Machinery 14, 100--119.
• 3: David, H. A. (1981). Order Statistics (second edition), New York: John Wiley.
• 4: Durst, M. J. (1988). Improving Parallel Random Number Generators. Proceedings of the Statistical Computing Section, American Statistical Association, Alexandria, Virginia.
• 5: Fishman, G. S. (1978). Principles of Discrete Event Simulation. John Wiley, New York.
• 6: Fishman, G. S. (in press). Multiplicative Congruential Random Number Generators with Modulus 2^β: An Exhaustive Analysis for β = 32 and a Partial Analysis for β = 48. Mathematics of Computation.
• 7: Fishman, G. S., and Moore, L. R. (1982). A Statistical Evaluation of Multiplicative Congruential Random Number Generators with Modulus 2³¹- 1. Journal of the American Statistical Association 77, 129--136.
• 8: Halton, J. H. (in press). Pseudo-Random Trees. Journal of Computational Physics.
• 9: Knuth, D. E. (1981), The Art of Computer Programming. Vol. 2: Seminumerical Algorithms, 2nd edition, Reading, MA: Addison-Wesley, Chapter 3.
• 10: Marsaglia, G. (1968). Random Numbers Fall Mainly in the Planes. Proceedings of the National Academy of Sciences 61, 25--28.
• 11: Niederreiter, H. (1978). Quasi-Monte Carlo Methods and Pseudo-Random Numbers. Bulletin of the American Mathematics Society 84, 957--1041.
• 12: Percus, O. E., and Kalos, M. (1989). Random Number Generators for MIMD Parallel Processors. Journal of Parallel and Distributed Computation 6, 477--497.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo); Random number generation

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Design, Performance