Random number generation on parallel processors

ABSTRACT

Recent development of high speed supercomputers has enabled us to perform large scale Monte Carlo simulations which need a tremendous amount of random numbers. There are two types of supercomputers, i.e. pipeline type and processor array type, and we will confine ourselves in this paper to the random number generation on a computer of the latter type. It is desired that not only a sequence of random numbers generated on each processor is of good quality but also sequences generated on different processors are uncorrelated. If we use a linear congruential method on a 32-bit supercomputer, the whole period may be consumed in several seconds to several minutes. Random numbers with a much longer period can be generated by a GFSR algorithm. Using this algorithm, we will propose a method to generate uncorrelated series of random numbers on parallel processors.

REFERENCES

• 1: Fushimi, M.(1983). A reciprocity theorem on the random number generation based on m-sequences and its applications (in Japanese). Transactions of the Information Processing Society of Japan 24, 576--579.
• 2: Fushimi, M. (1989). An equivalence relation between Tausworthe and GFSR sequences and applications. Applied Mathematics Letters 2, 135--137.
• 3: Fushimi, M. and Tezuka, S.(1983). The k-distribution of the generalized feedback shift register pseudorandom numbers. Communications of the ACM 26, pp. 516--523.
• 4: Golomb, S. W.(1967): Shift Register Sequences. Holden-Day, San Francisco.
• 5: Hoshino, T., et al. (1983). PACS: A parallel microprocessor array for scientific calculations. ACM Transactions on Computer System 1, 195--221.
• 6: Lewis, T. G. and Payne, W. H.(1973): Generalized feedback shift register pseudorandom number algorithms. Journal of the ACM 21, 456--468.
• 7: Oyanagi, Y. (1984). Random number generation in large-scale Monte Carlo calculations. In RIMS Kokyuroku 537, Research Institute for Mathematical Sciences, Kyoto University, Japan, 112--122.
• 8: Oyanagi, Y. (1988). Vectorization of Lewis-Payne random number generation on HITAC S810 and S820. In Proceedings of a Japan Society for the Promotion of Science Seminar: Trends in Supercomputing (Y. Kanada and C. K. Yuen, eds.) World Scientific, Singapore, 47--50.
• 9: Tausworthe, R. C.(1965). Random numbers generated by linear recurrence modulo two. Mathematics of Computation 19, 201--209.
• 10: Wichmann, B. A. and Hill, I. D. (1982). Algorithm AS 183: An efficient and portable pseudo-random number generation. Applied Statistics 31, 188--190.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Random number generation

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**
  C.5 COMPUTER SYSTEM IMPLEMENTATION

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Algorithms, Design, Performance