| |
|
|
| |
| |
| |
We now mention some tests of parallel random number generators.
Exponential sums: The exponential sum (Fourier transform of the density) of a sequence 
is:
For a random sequence 
(for 
).
This fact can be used to test correlation within, and
between, random number sequences [13, 16]. Consider two
random sequences X and Y and define the exponential sum
cross-correlation:
In each term of this sum, we find the difference between an element of
each sequence at a fixed offset apart. If this difference were
uniformly distributed, then we should have: 
Parallel spectral test: Percus and Kalos [14] have developed a version of the spectral test for parallel linear congruential generators.
Interleaved tests: We create a new random sequence by interleaving several random sequences, and test this new sequence for randomness using standard sequential tests.
Fourier transform test: Generate a two dimensional array of random numbers with each row in the array consisting of consecutive random numbers from one particular sequence. The two dimensional Fourier transform can be performed. For a truly uncorrelated set of sequences the coefficients (except the constant term) should be close to 0.
Blocking test: In the blocking test we add random numbers from several streams as well as from within a stream. If the streams are independent, then the distribution of these sums will approach the normal distribution.
We now give some test results for the LCG with (parameterized) prime
addend and a modified version of the LFG. Both of these
generators performed acceptably in the sequential tests with 
random numbers. Preliminary results from other tests of PPRNG can also
be found in the paper by Coddington [37].
We first tested the generators by interleaving about 1000 pairs of
random sequences each containing about 
PRNs. Both the
generators passed this tests. Next we simulated parallelism on the
Ising model by using a different random sequence for
each lattice site in the Metropolis algorithm. The LCG (with
identical seeds) failed badly as can be seen from the dashed line in
Fig. 
. We then generalized the statistical
tests, interleaving 256 sequences at a time. The LCG again failed,
demonstrating the effectiveness of these tests in detecting
non-random behavior. The modified LFG passed these tests.
Figure: Plot of the actual error versus the internally estimated standard deviation
of the energy
error for Ising model simulations with the Metropolis algorithm on a lattice with a
different Linear Congruential sequence at each lattice site. The
dashed line shows the results when all the Linear Congruential
sequences were started with the same seeds but with different additive constants.
The solid line shows the
results when the sequences were started with different seeds.
We expect around 95% of the points to be below the dotted
line (which represents an error of two standard deviations) with a good generator.
In the tests mentioned above, we had started each parameterized LCG
with the same seed but used different additive constants. Even when we
discarded the first million random numbers from each sequence, the
sequences were still correlated. However, when we started the streams
from different, systematically spaced seeds, the LCG passed all
statistical tests (including parallel ones) with up to 
-
numbers. We finally repeated the parallel Metropolis
algorithm simulation with random numbers, and both
generators performed acceptably, as can be seen from the solid line in
Fig. .
Apart from verifying the quality of two particular generators, our results illustrate that it is commonplace for generators to pass some test and fail others. It is important to test parallel generators the way they will be seeded, since correlations in the seeding can lead to correlations in the resulting sequences.
The National Center for Supercomputing Applications
University of Illinois at Urbana-Champaign
ashoks@ncsa.uiuc.edu
Last modified: September 16, 1997