NHSE Review^TM 1996 Volume Second Issue

Random Number Generators for Parallel Computers

| <- HREF="node18.html" Prev | Index | Next -> |
NHSE Review^TM: Comments · Archive · Search

Section 5 -- Conclusions and Recommendations 

There are very sound reasons for adopting such a skeptical stance. Developing a good, efficient algorithm for generating pseudo-random numbers on a computer is a very difficult problem, especially for parallel computers. The theoretical understanding of random number generators is rather limited, and no amount of empirical testing can ever determine how well a given generator will perform for a new application. There is a long and inglorious history of various random number generators being proposed, studied, tested, approved, advocated, widely used, and then being found to perform poorly in certain circumstances or for certain applications. Unfortunately, many generators have been (and continue to be) advocated, made available in software libraries, and widely used, even after they have been shown to be flawed.

If a generator is shown to fail a certain empirical test, that does not necessarily mean that it will also perform poorly for your application, or the results you spent many months gathering using that generator are now invalid. However, to avoid this possibility, it is strongly recommended that for any computation requiring random numbers, at least two very different random number generators should be used and the results compared, in order to check that the random number generator is not introducing a bias.

On a sequential computer, good generators to use are:

• a multiplicative lagged Fibonacci generator with a lag of at least 127, and preferably 1279 or more;
• a 48-bit or preferably 64-bit linear congruential generator that performs will in the Spectral Test and has a prime modulus;
• a 32-bit (or more) combined linear congruential generator, with well-chosen parameters, such as those recommended by L'Ecuyer;
• if speed is really an issue (but note the comment on this in Section 4.1), use an additive lagged Fibonacci generator with a lag of at least 1279 and preferably much greater, possibly combined with another generator, as in RANMAR, or using 3 or more lags.

All of the parallel random number generators covered in this review have some limitations or possible problems. There has also been very little empirical testing done on parallel random number generators, and few theoretical results are known. It is therefore much more difficult to recommend good parallel random number generators, but with that caveat, we will recommend:

• A combined linear congruential generator using sequence splitting;
• A lagged Fibonacci generator, although great care must be exercised in the initialization procedure, to ensure that the seed tables on each processor are random and uncorrelated.
  If your application does not require the same results for different numbers of processors, we recommend using a large-lag multiplicative (or additive) generator with a different (randomly initialized) lag table on each physical processor. This could be combined with another generator, as in RANMAR.
  Otherwise a small lag must be used due to memory constraints, as with the PGIHPF and VP_RNG generators, however we recommend using multiplication rather than addition.

Many of the past problems with random number generators have been caused in part by the rapid pace of improvement in computers. 32-bit LCGs were perfectly adequate for many years, but the speed of modern processors has rendered them obsolete. This has been noted in the documentation for most (but unfortunately not all) implementations of these generators, which are kept only for backward compatibility. Shift register generators became very popular because XOR was so much faster than addition and multiplication on processors available at that time, but that is no longer the case, and their relatively poor randomness properties now far outweigh their slight performance advantage. Early implementations of lagged Fibonacci generators used very small lags, even though larger lags were known to give better results, because of worries about memory constraints that are no longer a problem on current computers (except for data parallel implementations). Many comments on the quality of various generators have been made based on statistical tests performed many years ago, using samples of random numbers that are so small as to be almost irrelevant to the results of simulations done on current (and future) high-performance computers.

The improvement in computer performance continues unabated, of course, and it is crucial that the implementation and testing of random number generators keeps pace with these changes. By the year 2000 supercomputers will have Teraflop ( floating point operations per second) performance, and a Teraflop-year of computation ( flops) will become realizable for such problems as Monte Carlo simulation of lattice gauge theory and condensed matter physics [66]. Such large-scale Monte Carlo simulations will easily exhaust the period (of roughly ) of 64-bit LCGs or 32-bit combined LCGs. It will therefore be necessary in the near future to move to very long period generators such as large-lag LFGs or combined 64-bit LCGs or MRGs (which have periods large enough for a Petaflop-age-of-the-universe computation!).

Since faster computers and better algorithms are improving the precision of computer simulations at a rapid pace, it is important to continue to search for better random number generators, and to make more precise and varied tests of the randomness properties of these generators. This is particularly true for parallel computers, where satisfactory algorithms are still lacking.

• Recommended Random Number Generator Software

| <- HREF="node18.html" Prev | Index | Next -> |
NHSE Review^TM: Comments · Archive · Search