The main goal of this project is to develop the new standard library for scalable pseudorandom number generation. Such a library is an essential tool for deploying computationally intensive Monte Carlo applications on scalable platforms. This project incorporates recent, state-of-the-art, developments in the mathematics and computer science of parallel pseudorandom number generation with several on-going computational Monte Carlo projects. In this way this effort incorporates both scalable library development and technology transfer from the start. Thus, the final result will be an efficient library with an existing, active, user base. From the technical point-of-view the library is intended to satisfy the following demands:
1) Provide a practically infinite number of parallel pseudorandom number streams with favorable statistical properties within and among streams, and a facility to produce statistically significant new results.
2) Allow the pseudorandom number streams to be also absolutely reproduced, for computational verification, independent of the number of processors used in the computation and of the loading produced by sharing of the parallel computer.
3) Allow for the dynamic creation of new unique pseudorandom number streams on a parallel machine without interprocessor communication to support branching simulations.
4) Facilitate portability between serial and parallel platforms and among the most commonly used workstations, scalable platforms, networks of workstations, and supercomputers.
5) Provide several types pseudorandom numbers all with good statistical properties in a computationally inexpensive and scalable manner.
A scalable pseudorandom number generation tool for Monte Carlo must allow the computational scientist to use her computational environment as a numerical laboratory for discovering and verifying new results. For such a tool to permit true numerical experimentation it must support reproducibility, isolation of the effects of the pseudorandom number generator, and be extensible to new methods of pseudorandom number generation. This must all take place seamlessly over a variety of scalable platforms. Several new mathematical and computer science results serve as the theoretical foundation for this project's approach.
New mathematical results on parameterized pseudorandom number generators have provided three different mathematical methods that can be uniformly incorporated in the library. These are the: i) additive lagged-Fibonacci; ii) prime modulus linear congruential; and iii) maximal-period shift-register generators. Particular parameterizations of these generators can be employed to assure statistically independent streams of random numbers for parallel Monte Carlo applications including stochastic processes with branching.
Given parameterized generators, one can map an enumeration of the generators onto a binary tree in a canonical way. The mapping to the binary tree then permits the assignment and dynamic allocation of pseudorandom number streams in a parallel environment without the need for interprocessor communication. The cost for this independence is that the generators are not all used in parametric order necessitating a very large number of generators. This is possible for the three generators listed above.
Coding, implementation and optimization of these generators on a variety of architectures from workstation, through vector to parallel machines is being carried out using the canonical binary tree mapping. Special attention is being given to uniprocessor efficiency and scalability. In addition, where applicable, theoretical results are guiding the enumeration of the generators to ensure that statistically independent streams of pseudorandom numbers will be generated 'locally' on a given processor for applications which include stochastic branching.
Testing of the generators on all platforms including cross-examination of statistical independence for parallel streams is being performed. Standard libraries of statistical tests are being implemented for serial testing and are being modified for parallel testing. Also, testing on physical models from statistical mechanics and quantum physics with advanced Monte Carlo algorithms is being used to validate the performance in actual applications.
An important application of the extensive testing routines is to support the extensibility of the package. It is felt that the incorporation of new results in pseudorandom number generation as well as the 'legacy' generators used by many computational Monte Carlo groups in essential. Testing is the only way to verify an implementation and to check for new correlations that arise in a parallel setting.
Large-scale calculations will be used to demonstrate the usefulness of the package and power of Monte Carlo approach in general will be carried out on examples of large-scale simulations in quantum and statistical mechanics. This will be done within the project and through collaborations to demonstrate the effectiveness of this new tool to the community.