Random Number Generators for Parallel Computers
| <- HREF="node1.html" Prev | Index | Next -> |
NHSE ReviewTM: Comments
· Archive
· Search
Random number generators use iterative deterministic algorithms for producing
a sequence of pseudo-random numbers that approximate a truly random sequence.
Ideally the sequence should be uniformly distributed, uncorrelated,
reproduceable, portable, easily changed by adjusting an initial seed value,
easily split into many independent subsequences,
have a large period of repetition, pass all empirical tests for randomness,
and be generated rapidly using limited computer memory.
Parallel random number generators should in addition have
no correlations between the sequences on different processors,
produce the same sequence for different numbers of processors,
and not require any data communication between processors.
Developing random number generators that satisfy all of these requirements is
a very difficult problem, particularly for parallel computers.
The main algorithms used for sequential random number generators are
the following:
-
Linear congruential generators - these work well if the parameters
are properly chosen, the modulus is a prime number, and the state used is at
least 48 bits, and preferably 64 bits. Do not use 32-bit versions.
-
Lagged Fibonacci generators - implementations using multiplication
are the best, addition or subtraction
can be used if speed is a major concern, XOR should not be used. The lags
used must satisfy certain requirements, and should be as large
as possible, with the largest lag being at least 127 for multiplication and
1279 for addition, and preferably much larger.
Care must be taken in initializing the seed tables, to
ensure the entries are random and uncorrelated.
-
Shift register generators - these are not recommended since they
have comparatively poor randomness properties.
-
Combined generators - combinations of two linear congruential
generators, or a lagged Fibonacci generator and a linear congruential or
other generator, work well in practice if two good generators are used.
The main techniques used for parallelizing random number generators
involve distributing the sequences of random numbers produced by a
sequential generator among the processors in the following different ways:
-
Leapfrog - The sequence is partitioned among the processors in a
cyclic fashion, like a deck of cards dealt to card players.
-
Sequence splitting - The sequence is partitioned among processors
in a block fashion, by splitting it into non-overlapping contiguous sections.
-
Independent sequences - For some generators, the initial seeds can
be chosen in such a way as to produce long period independent subsequences
on each processor.
Random number generators, particularly for parallel computers,
should not be trusted.
It is strongly recommended that all simulations be done with two or
more different generators, and the results compared to check whether
the random number generator is 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 well 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 crucial,
an additive lagged Fibonacci generator
with a lag of at least 1279 and preferably much greater, and
possibly combined with another generator, as in RANMAR,
or using 3 or more lags rather than 2.
All of the parallel random number generators covered in this review
have some limitations or possible problems.
Recommended generators to use on a parallel computer are:
-
Combined linear congruential generators using sequence splitting;
-
Lagged Fibonacci generators using independent sequences,
with careful initialization to ensure
the seed tables on each processor are random and uncorrelated.
If you do not require the same results for different numbers of processors,
a multiplicative or additive generator with a large lag can be used,
with different lag tables on each physical processor.
Otherwise a different lag table is used on each abstract processor,
requiring a small lag due to memory constraints,
in which case we recommend using multiplication rather than addition.
Some
software implementing these recommended generators
is available from the
National HPCC Software Exchange (NHSE).
More work needs to be done on developing better random number generators
for parallel computers, and subjecting these generators to more thorough
empirical testing.
Copyright © 1996
| <- HREF="node1.html" Prev | Index | Next -> |
NHSE ReviewTM: Comments
· Archive
· Search
Paul Coddington, paulc@npac.syr.edu