
\documentstyle[11pt]{article}      

\begin{titlepage}

% preprint number
% \begin{flushright}
% SCCS-??? \\[2.5em]
% \end{flushright}

\begin{center}
{\LARGE \bf
A Random Number Generator for High Performance Fortran\\}
\bigskip
\bigskip
{\large 
P.D.~Coddington \\}  
\medskip
{\it
Northeast Parallel Architectures Center, Syracuse University,\\
111 College Place, Syracuse, NY 13244, U.S.A.\\}
\bigskip
{\large
C.~Stoner\\}
\smallskip
{\it
Computer Science Department, State University of New York at Buffalo,\\
Buffalo, NY, U.S.A.\\}
%
\bigskip
\bigskip
{\large September 6, 1994} \\
\end{center}
\bigskip
\bigskip


\begin{abstract}
\noindent
High Performance Fortran (HPF) is a high-level portable language 
with the aim of providing efficient implemention on all high-performance 
computers, including parallel, vector and sequential machines.
%
One of the goals of HPF is to utilize as much as possible the standard
intrinsic functions defined for Fortran 90, which is a subset of HPF.
However we argue that the definition of the intrinsic random number
function in Fortran 90 is inadequate for use in HPF, and we propose a
more practical interface.
%
HPF also puts many constraints upon the type of random number generator 
that can be used. 
We propose a parallel random number generator that satisfies all the 
necessary criteria. We have implemented this generator as a subroutine in 
HPF, and tested its randomness properties using a Monte Carlo simulation.
\end{abstract}

\end{titlepage}


\textwidth=6.0in
\textheight=8.5in
\topmargin=-0.5in
\oddsidemargin=0.25in


\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Introduction}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Random number generators are used in many areas of computer simulation.
In Fortran 90 the random number generator has been accorded the status
of an intrinsic function~\cite{F90defn}.

Here we address the problem of developing a random number generator for
use with High Performance Fortran (HPF)~\cite{HPF}.
HPF was developed with the goal of providing a high-level portable 
language that could be efficiently implemented on all high-performance 
computers, including parallel, vector and sequential machines.
HPF is based upon, and is a superset of, the Fortran~90
standard~\cite{F90}. As such, it is logical that HPF should utilize as 
much as possible the Fortran~90 definitions and interfaces for intrinsic
functions.
However the definition of the intrinsic random number generator in 
Fortran~90 is fundamentally flawed, and quite inadequate for use in HPF.
We propose a more practical interface that can be used for a random
number generator within HPF.
 
HPF also puts many constraints upon the type of random number generator 
that can be used. Obviously the random numbers must be generated using
a parallel algorithm, since HPF targets parallel and vector machines.
Many parallel algorithms for generating random numbers have been 
developed \cite{}.
However most fail at least one of the other criteria that HPF requires:

\begin{description}

\item{\bf Portability}
Since HPF is meant to be a portable language, a fundamental constraint
on any HPF intrinsic function is that it produce the same results on any
number of processors, and in particular, the same results as on a  
a sequential machine.  This eliminates many parallel algorithms that
basically run a separate sequential generator on each processor, since
this is dependent upon the number of processors.

\item{\bf Large Period}
As its name implies, High Performance Fortran is targeted at high-speed
computers, including parallel supercomputers that are expected to 
achieve Teraflop performance before the end of the decade. It is likely
that some simulations will soon be utilizing Teraflop-years of computer
time for ``Grand Challenge'' problems in such areas as condensed
matter physics~\cite{condmat} and lattice field theory~\cite{QCD},
which rely on Monte Carlo simulations~\cite{MonteCarlo} 
that make heavy use of random number generators. 
Such simulations may require on the order of $10^{18}$ random numbers, 
so the period of the random number generator will have to be at least 
as large.

\item{\bf Excellent Randomness Properties}
For many problems, in particular large scale Monte Carlo simulations,
the quality or randomness of the pseudo-random numbers used is crucial.
A poor random number generator can produce incorrect results, and this
has been noted many times in the computational science literature
\cite{KALLE,BARBER,PARISI,HOOGLAND,FILK,MILCHEV,FERRENBERG,GRASSBERGER,
CODDINGTON}.
Finding fast, high quality sequential random number generators is a
non-trivial task. Developing parallel algorithms, which have the added 
problem of possible inter-processor correlations, is an even more 
difficult task. 

\end{description}

In Section~\ref{Parallel} we present a brief overview of parallel 
random number generators, and discuss candidate algorithms for a
random number generator for HPF, including our algorithm of choice,
a mixed linear congruential generator with sequence splitting.
% 
In Section~\ref{intrinsic} we discuss the problems with the definition
of the random number intrinsic function in Fortran~90, and propose 
a more practical interface that can be used within HPF.
%
In Section~\ref{implementation} we discuss the implementation of the
chosen parallel random number generator in HPF, and present results 
for timings and efficiency on parallel and sequential computers.
%
In Section~\ref{tests} we present the results of tests of the quality 
of the randomness of the generator.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Parallel Random Number Generators}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\subsection{Linear Congruential Generators}

Linear congruential generators (LCGs) are the oldest and most popular 
random number generators used today \cite{LEHMER,KNUTH,PARK}. 
They produce a sequence $X_{i}$ of random integers using the relation
%
\begin{equation}
X_{i} = a * X_{i-1} + b \quad \bmod M
\label{eqn:LCG}
\end{equation}
%
which we will denote by L($a,b,M$).
Because of their simplicity, much more is known theoretically about
the randomness properties of this type of generator than any other 
\cite{KNUTH}.
The period is $M$ for suitably chosen $a$ and $b$ ($M-1$ if $B=0$).


\subsection{The Leapfrog Method}

A simple way of generating the same sequence of random numbers for different
numbers of processors, is for processor $P$ of an $N$ processor machine 
to generate the sub-sequence 
$X_{P}, X_{P+N}, X_{P+2N}$, \ldots,
so that the sequence is spread across processors.
This is known as the leapfrog technique \cite{EVANS,FOX}.

Linear congruential generators are simple enough that it is possible to
specify analytically an arbitrary element in the sequence. By recursively
applying equation \ref{eqn:LCG}, it is easy to show \cite{FOX}
that the element $X_{P+N}$ is given by 
%
\begin{eqnarray}
X_{P+N} & = & A * X_{P} + B \quad \bmod M   \\
A & = & a^{N}                                           \nonumber \\ 
B & = & \sum^{N-1}_{k=0}a^{k} = (a^{N} - 1)/(a - 1)   \nonumber
\label{eqn:leapfrog}
\end{eqnarray}
%
Thus moving through the sequence with stride $N$, rather than 1, is 
simply accomplished by specifying a different multiplier and additive 
constant for the generator. The leapfrog method is consequently very 
easy to implement on a parallel machine.

One would expect 
that a large period (at least 48-bit) parallel linear congruential 
generator using the leapfrog method should be fine for most purposes.
However there is a problem -- linear congruential generators are known
to have correlations between elements in the sequence which are
a power of 2 apart~\cite{FILK,PERCUS}. 
Since for most parallel machines the number of processors is a power of 2,
this means that the numbers generated on a given processor may be more
strongly correlated than the sequence on a single processor. In fact 
this type of leapfrog linear congruential algorithm, when used on a 
vector machine, has given spurious results in some Monte Carlo 
calculations~\cite{KALLE,FILK}. 

It is possible that this problem could be avoided by leapfrogging by 
$N+1$ rather than $N$, thus avoiding power of 2 correlations, but this 
would mean that the parallel algorithm no longer produces the same
sequence of numbers as the sequential algorithm.


\subsection{Sequence Splitting}

Another way of parallelizing linear congruential generators is to split 
the sequence into non-overlapping parts, each of which is generated by
a different processor. This also utilizes the fact that this type of 
generator allows an arbitrary element of the sequence to be calculated.
One can therefore simply divide the period of the generator
by the number of processors, and jump ahead in the sequence by this 
amount for each processor~\cite{EVANS,LECUSPLIT}. 

This requires that the period of the generator be very large. 
A 32-bit generator is completely inadequate, and even a 48-bit 
generator may not be good enough on a fast massively parallel machine. 
A good 64-bit generator should work well, but perhaps better would be 
to use the combined linear congruential generator of 
L'Ecuyer~\cite{LECUYER}, which combined two 32-bit generators into a 
generator with about the same
period, and probably better randomess properties, than a 64-bit LCG.
A program for a generator of this type using sequence splitting 
is given in Ref.~\cite{LECUSPLIT}.

The only disadvantages of this type of generator are that it does not 
produce the same sequence on different numbers of processors, and it is 
relatively slow on a processor which does not have 64-bit integer 
arithmetic.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Lagged Fibonnaci Generators}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Lagged Fibonacci generators (LFGs) have become increasingly popular,
since they offer a simple method of obtaining very large periods,
by utilizing more than just the previous value of the sequence
\cite{KNUTH,MARSAGLIA}. The period can be made arbitrarily large by
increasing the number of previous elements which are saved 
(the {\it lag}), and increasing the lag has also been shown to improve 
the randomness properties of the generator \cite{MARSAGLIA,CODDINGTON}. 
The sequence is defined by
%
\begin{equation}
X_{i} = X_{i-p} \odot X_{i-q}  \quad \bmod M \\
\label{eqn:LFG}
\end{equation}
%
which we will denote by F($p,q,\odot$), where $p$ and $q$ are the lags,
$p > q$, and $\odot$ is any binary arithmetic operation, such as 
$+, -, *$ or $\oplus$ (the bitwise exclusive OR function XOR).
The arithmetic operations are done modulo any large integer value $M$,
or modulo 1 if the $X$'s are represented as floating point numbers 
in the interval [0,1), as can be done if the operation is $+$ or $-$.
The modulus function is not required when using XOR.
Multiplication is done on the set of odd integers.
For $b$-bit precision $X$'s, the period is 
$(2^{p}-1)2^{b-1}$, or $(2^{p}-1)2^{b-3}$ for multiplication, 
for suitably chosen lags \cite{KNUTH,MARSAGLIA,TSAY}.
This method requires storing (in a {\it lag table}) the $p$ previous
values in the sequence. 


\subsection{Parallel method}

The simplest method of using lagged Fibonacci generators in parallel
is to just run the same sequential generator on each processor, but 
with different initial lag tables 
(or {\it seed tables})~\cite{CHIU,PETERSON}. 
The lag tables on each processor should be initialized using a
{\it different} parallel generator, for example
a leapfrog or sequence splitting linear congruential generator. 
This should guarantee statistical independence between processors
for a generator with a long lag. as long as the initial seed tables
are random (i.e. a good generator is used to initialize the seed 
tables). 

This is arguably the best parallel random number generator known.
It is used in the Connection Machine Scientific Software Library 
(CMSSL)~\cite{CMSSL}, where the interface to the routine allows the 
user to specify the lags, so in principle the routine can be extremely 
good, however in the documentation they suggest using lags which are 
much too small.

One deficiency of this method is that is does not produce the same 
sequence for different numbers of processors. This can be achieved 
by a simple variation of this method, which is also provided in the 
CMSSL.
The idea is to assign a different lag table to every 
{\it virtual processor} (i.e. distributed array element),
rather than every processor~\cite{CMSSL}. It is thus independent of 
the number of processors, however for a large lag table the memory 
requirement may be exorbitant. If multiplication is used in the 
lagged Fibonacci generator, a small lag will still give good 
results \cite{MARSAGLIA,CODDINGTON}.
This generator could therefore be useful for debugging small scale 
problems.


\subsection{Vector method}

The second method is straightforward vectorization of the basic 
lagged Fibonacci algorithm. As long as the vector length is smaller 
than both $p$ and $q$, a vector of new results can be obtained
independently \cite{ANDERSON,PETERSON2}. This parallelism can also 
be utilized if the elements of the vector are distributed over multiple
processors. The problem with using this method on a distributed memory 
machine rather than a vector or shared memory machine, is that the 
results are then not distributed properly to be used for the next 
update, and substantial communication is required to obtain values 
which are not in the local memory of the processors. This should be 
contrasted with the other algorithms described above, for which 
{\it no} communication is required.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Shift Register Generators}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Shift register (or Tausworthe) generators 
\cite{TAUSWORTHE,KIRKPATRICK,KNUTH,MARSAGLIA,CHIU,HOOGLAND}
are generally used in a form where they can be considered as special
cases of the lagged Fibonacci generator, 
where the operation used is XOR.
They can therefore be parallelized in the same way as the lagged 
Fibonacci generators.

Because XOR is such a simple operation, it gives the worst randomness
properties of any operation for an LFG 
\cite{MARSAGLIA,CODDINGTON}. 
However this simplicity means that there is a substantial amount of
theoretical knowledge on shift register generators 
\cite{GOLOMB,NIEDERREITER},
whereas there is very little (apart from the period) is known about
general lagged Fibonacci generators.


\subsection{The Leapfrog Method}

The leapfrog method is not viable with a general lagged Fibonacci
generator, since calculating $X_{P+kN}$ is not possible without 
communicating values from other processors, which would make the 
generator too slow.
However shift register generators are simple enough to allow analytic 
recursion of equation~\ref{eqn:LFG}, and it can easily be shown 
\cite{GOLOMB,ALURU} that for any integer $N$ which is a power of 2,
%
\begin{equation}
X_{i} = X_{i-p} \oplus X_{i-q} = X_{i-Np} \oplus X_{i-Nq} \\
\label{eqn:SRleapfrog}
\end{equation}
%
If each processor saves the previous $p$ values in the sequence it
generates (i.e. saves the usual $p$-element lag table), then using 
the leapfrog method it will have in its local memory the elements
$X_{P-N}, X_{P-2N}, \ldots, X_{P-qN}, \ldots, X_{P-pN}$, and thus
will have the values necessary to calculate the next element $X_{P}$
without any communication. 

Note that this method will only work when the number of processors 
is a power of 2.
Shift register generators probably suffer from the same long-range
power-of-2 correlations as do LCGs, 
however this is not known theoretically, and good 
statistical tests are lacking for this generator.
Possibly more damaging are the short range correlations which are
known to occur for shift register generators, which would 
translate to inter-processor correlations for a leapfrog algorithm.
An extremely large lag would be required in order to reduce these
correlations to an acceptable level
($p=9689, q=4187$ is probably adequate).

% CAN THIS BE DONE USING A MULTIPLE TAP SHIFT REGISTER GENERATOR?
% SHOULD BE POSSIBLE.


\subsection{The DAP Generator}

A parallel shift register algorithm has been developed for the AMT DAP, 
a very fine grained, bit serial, massively parallel processor 
array \cite{SMITH}.




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Other Generators}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Other parallel random number generators have been proposed and implemented,
however they generally do not have a sound enough theoretical background, 
or enough testing done on them, to be used with confidence for
computational science applications.


\subsection{The Cellular Automata Generator}

This is a generalization of the shift register generator, based on cellular
automata rules~\cite{WOLFRAM}. A parallel version is provided by 
by Thinking Machines~\cite{CMF}. 


\subsection{Pseudorandom Trees}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{The Intrinsic Function Interface}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Implementation and Performance}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Randomness Tests}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

One good practical test of a random number generator is to use it for
Monte Carlo simulation of the two dimensional Ising model
\cite{MONTECARLO}. This simple model has been solved exactly for a
finite lattice~\cite{FISHER}, so that values of the energy and the
specific heat (the variance of the energy) of the system calculated 
from the Monte Carlo simulation can be 
compared with the known exact values.
Many different Monte Carlo algorithms can be used to simulate the Ising
model. Here we will concentrate on the three most widely used methods:
the original Metropolis algorithm~\cite{MONTECARLO} which updates a 
single site of the lattice at a time; the Swendsen-Wang 
algorithm~\cite{SW} which forms clusters of sites to be updated
collectively; and the Wolff algorithm~\cite{WOLFF} which updates a 
single cluster of sites.
The Swendsen-Wang and Wolff cluster update algorithms are extremely
efficient and allow very precise Monte Carlo simulations of the Ising
model, easily reducing statistical errors to better than one part 
in $10^5$ on small lattices.
This precision provides us with a very effective practical test of the
randomness of a pseudo-random number generator, and in particular its 
suitability for Monte Carlo simulation.

We have developed parallel algorithms for all three Monte Carlo methods
used in tests of sequential generators \cite{FERRENBERG,CODDINGTON}.
The Metropolis algorithm is a very regular and can be easily and
efficiently parallelized using standard domain decomposition on both 
SIMD and MIMD machines~\cite{FOX}.
The parallel Swendsen-Wang program used on the MIMD machines was the 
local label propagation or self-labeling algorithm
\cite{MIMD,CPE,TAMAYO}. 
This program has been used for high precision Monte Carlo studies of 
Ising and Potts spin models~\cite{POTTS}. 
A SIMD Swendsen-Wang algorithm was also used~\cite{SIMD}.
We have recently developed parallel Wolff algorithms for both
SIMD and MIMD machines \cite{PARWOLFF}. Since the SIMD Wolff algorithm
uses the random number generator in essentially the same way as the 
SIMD Swendsen-Wang algorithm, only the MIMD Wolff algorithm was used.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Conclusion}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{Acknowledgements}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

We would like to thank John Apostolakis, Tom Haupt, Ken Hawick, and
Tim Kutz for their help and for useful discussions.

Work supported in part by the Center for Research on Parallel 
Computation with NSF cooperative agreement No. CCR-9120008, and by
ARPA under contract No. DABT63-91-K-0005.
NSE??
HPFA??
Chris Stoner was supported by the Research Experience for 
Undergraduates Program in High-Performance Computing conducted by the 
Northeast Parallel Architectures Center (NPAC) at Syracuse University,
which is funded primarily by the National Science Foundation through 
NSF Grant CDA-9200577, with additional funding provided by
the GE Foundation Faculty for the Future Program,
NPAC, and Syracuse University.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{thebibliography}{00}
%
\bibitem{ALURU}
S.~Aluru, G.M.~Prabhu and J.~Gustafson,
A random number generator for parallel computers,
{\it Parallel Comput.} {\bf 18} (1992) 839.
%
\bibitem{ANDERSON}
S.L.~Anderson, 
Random Number Generators on Vector Supercomputers and Other
Advanced Architectures,
{\it SIAM Rev.} {\bf 32} (1990) 221.
%
\bibitem{SIMD}
J.~Apostolakis, P.~Coddington and E.~Marinari,
New SIMD algorithms for cluster labeling on parallel computers,
{\it Int. J. Mod. Phys. C}, {\bf 4}, 749 (1993).
%
\bibitem{PARWOLFF}
S.-J.~Bae, S.H.~Ko and P.D.~Coddington,
Parallel Wolff Cluster Algorithms,
in preparation.
%
\bibitem{CPE}
C.F.~Baillie and P.D.~Coddington,
Cluster identification algorithms for spin models -- sequential and parallel,
{\it Concurrency: Practice and Experience} {\bf 3} (1991) 129.
%
\bibitem{POTTS}
C.F.~Baillie and P.D.~Coddington,
Comparison of cluster algorithms for 2-D Potts models,
{\it Phys. Rev. B} {\bf 43} (1991) 10617;
P.D.~Coddington and C.F.~Baillie,
Empirical relations between static and dynamic exponents for
Ising model cluster algorithms,
{\it Phys. Rev. Lett.} {\bf 68} (1992) 962.
%
\bibitem{BARBER}
M.N.~Barber {\it et al.}, 
% ?????????
{\it Phys. Rev.} {\bf B 32} (1985) 1720;
%
\bibitem{MONTECARLO}
K.~Binder ed., 
{\it Monte Carlo Methods in Statistical Physics}, 
(Springer-Verlag, Berlin, 1986);
K.~Binder and D.W.~Heermann, {\it Monte Carlo Simulation in Statistical 
Physics}, (Springer-Verlag, Berlin, 1988);
H.~Gould and J.~Tobochnik,
{\it An Introduction to Computer Simulation Methods, Vol. 2},
(Addison-Wesley, Reading, Mass., 1988).
%
% \bibitem{BOWMAN}
% K.O.~Bowman and M.T.~Robinson,
% Studies of random number generators for parallel processing,
% {\it Proc. 2nd Conference on Hypercube Multiprocessors}, M.T.~Heath ed.,
% (SIAM, Philadelphia, 1987), p.~445.
%
% \bibitem{BRENT}
% R.P.~Brent,
% Uniform random number generators for supercomputers,
% Proc. of the 5th Australian Supercomputer Conference,
% Melbourne, 1992, p.~95.
%
% \bibitem{CELMASTER}
% W.~Celmaster and K.J.M.~Moriarty,
% A method for vectorized random number generators,
% {\it J. Comput. Phys.} {\bf 64} (1986) 271.
%
\bibitem{CHIU}
T.-W.~Chiu,
Shift-register sequence random number generators on the hypercube 
concurrent computers,
{\it Proc. of the 3rd Conference on Hypercube Concurrent Computers and 
Applications}, G.~Fox ed., (ACM Press, New York, 1988), p.~1421.
%
\bibitem{CODDINGTON}
P.D.~Coddington,
Analysis of Random Number Generators Using Monte Carlo Simulation,
{\it Int. J. Mod. Phys. C}, to appear.
NPAC technical report SCCS-526.
%
\bibitem{MIMD}
P.D.~Coddington and C.F.~Baillie,
Cluster algorithms for spin models on MIMD parallel computers,
{\it Proc. of the 5th Annual Distributed Memory Computing Conference},
Charleston (April 1990), eds. D.W.~Walker and Q.F.~Stout
(IEEE Computer Society Press, Los Alamitos, California, 1990).
%
% \bibitem{COMPAGNER}
% A.~Compagner and A.~Hoogland, 
% Maximum-length sequences, cellular automata and random numbers,
% {\it J. Comp. Phys} {\bf 71} (1987) 391.
%
\bibitem{EVANS}
W.~Evans and B.~Sugla,
Parallel random number generation,
{\it Proc. of the 4th Conference on Hypercube Concurrent Computers and 
Applications}, (Golden Gate Enterprises, Los Altos, CA, 1989), p.~415.
%
\bibitem{FERRENBERG}
A.M.~Ferrenberg, D.P.~Landau and Y.J.~Wong,
Monte Carlo simulations: Hidden errors from ``good'' random number generators,
{\it Phys. Rev. Lett.} {\bf 69} (1992) 3382.
%
% \bibitem{FILIPPONE}
% S.~Filippone, P.~Santangelo and M.~Vitaletti,
% A vectorized long-period shift-register random number generator,
% ?????????
%
\bibitem{FILK}
T.~Filk, M.~Marcu and K.~Fredenhagen,
Long range correlations in random number generators and their influence
on Monte Carlo simulations,
{\it Phys. Lett.} {\bf B165} (1985) 125.  
%
\bibitem{FISHER}
A.E.~Ferdinand and M.E.~Fisher, 
% ?????,
{\it Phys. Rev.} {\bf 185} (1969) 832.
%
\bibitem{FISHMAN}
G.S.~Fishman,
Multiplicative congruential random number generators with modulus $2^\beta$:
an exhaustive analysis for $\beta \! = \! 32$ and a partial analysis for 
$\beta \! = \! 48$,
{\it Math. Comp.} {\bf 54} (1990) 331.
%
\bibitem{FOX}
G.~Fox {\it et al.},
Chapter 12 of {\it Solving Problems on Concurrent Processors, Vol.~1},
(Prentice-Hall, Englewood Cliffs, 1988).
%
\bibitem{GOLOMB}
S.W.~Golomb, 
{\it Shift Register Sequences},
(Holden-Day, San Francisco, 1967).
%
\bibitem{GRASSBERGER}
% P.~Grassberger, 
% ???????
% {\it J. Phys. A: Math. Gen.} {\bf 26} (1993) 2769; 
P.~Grassberger, 
On correlations in ``good'' random number generators,
Wuppertal University preprint WUB 93-03.
%
\bibitem{HOOGLAND}
A.~Hoogland, A.~Compagner and H.W.J.~Bl\"ote, 
Smooth finite-size behavior of the three-dimensional Ising model,
{\it Physica} {\bf 132A} (1985) 593.
%
\bibitem{JAMES}
F.~James, 
A review of pseudorandom number generators,
{\it Comp. Phys. Comm.} {\bf 60} (1990) 329.
%
\bibitem{KALLE}
C.~Kalle and S.~Wansleben,
Problems with the random number generator RANF implemented on the 
CDC CYBER 205,
{\it Comp. Phys. Comm.} {\bf 33} (1984) 343.
%
\bibitem{KIRKPATRICK}
S.~Kirkpatrick and E.~Stoll,
A very fast shift-register sequence random number generator,
{\it J. Comput. Phys.} {\bf 40} (1981) 517.
%
\bibitem{KNUTH}
D.E.~Knuth,
{\it The Art of Computer Programming Vol. 2: Seminumerical Methods}
(Addison-Wesley, Reading, Mass., 1981).
%
\bibitem{LECUYER}
P.~L'Ecuyer,
Efficient and portable combined random number generators,
{\it Comm. ACM} {\bf 31:6} (1988) 742.
%
\bibitem{LECUREV}
P.~L'Ecuyer,
Random numbers for simulation,
{\it Comm. ACM} {\bf 33:10} (1990) 85.
%
\bibitem{LECUSPLIT}
P.~L'Ecuyer and S.~Co\^te\',
Implementing a random number package with splitting facilities,
{\it ACM Trans. Math. Soft.} {\bf 17} (1991) 98.  % ???
%
\bibitem{LEHMER}
D.H.~Lehmer,
Mathematical methods in large-scale computing units,
{\it Ann. Comput. Lab. Harvard U.} {\bf 26} (1951) 141.
%
\bibitem{MARSAGLIA}
G.A.~Marsaglia, 
A current view of random number generators,
in {\it Computational Science and Statistics: The Interface},
ed. L.~Balliard (Elsevier, Amsterdam, 1985).
%
\bibitem{TSAY}
G.A.~Marsaglia and L.H.~Tsay,
Matrices and the structure of random number sequences,
{\it Linear Algebra Appl.} {\bf 67} (1985) 147.
%
\bibitem{MILCHEV}
A.~Milchev, K.~Binder, D.W.~Heermann,
Fluctuations and lack of self-averaging in the kinetics of domain growth,
{\it Z. Phys.} {\bf B 63} (1986) 521.
%
\bibitem{NIEDERREITER}
H.~Neiderreiter, 
{\it Bull. Amer. Math. Soc.} {\bf 84} (1978) 957.
%
\bibitem{PARASOFT}
{\it Express Reference Manual}, 
{\it Express C User's Guide}, and
{\it Express Fortran User's Guide}, 
Parasoft Corporation, 2500 E. Foothill Blvd., Pasadena CA 91107 (1990).
%
\bibitem{PARISI}
G.~Parisi and F.~Rapuano, 
Effects of the random number generator on computer simulations,
{\it Phys. Lett.} {\bf 157B} (1985) 301.
%
\bibitem{PARK}
S.K.~Park and K.W.~Miller,
Random number generators: Good ones are hard to find,
{\it Comm. ACM} {\bf 31:10} (1988) 1192.
%
\bibitem{KALOS}
O.E.~Percus and M.H.~Kalos,
Random number generators for MIMD parallel processors,
{\it J. Par. Dist. Comput.} {\bf 6} (1989) 477.
%
\bibitem{PERCUS}
O.E.~Percus and J.K.~Percus, 
Long range correlations in linear congruential generators,
{\it J. Comput. Phys.} {\bf 77} (1988) 267.  
%
\bibitem{PETERSON}
W.P.~Peterson, 
Some vectorized random number generators for uniform, normal, and 
Poisson distributions for the CRAY X-MP,
{\it J. Supercomput.} {\bf 1} (1988) 327.
%
\bibitem{PETERSON2}
W.P.~Peterson, 
Lagged Fibonacci series random number generators for the NEC SX-3,
{\it Int. J. High Speed Comput.}, to appear.
%
\bibitem{SMITH}
K.A.~Smith, S.F.~Reddaway, and D.M.~Scott,
Very high performance pseudo-random number generator on DAP,
{\it Comp. Phys. Comm} {\bf 37} (1985) 239.
%
\bibitem{SW}
R.H.~Swendsen and J.-S.~Wang, 
Nonuniversal critical dynamics in Monte Carlo simulations,
{\it Phys. Rev. Lett.} {\bf 58} (1987) 86.
%
\bibitem{TAMAYO}
M.~Flanigan and P.~Tamayo,
A parallel cluster labeling method for Monte Carlo dynamics,
{\it Int. J. Mod. Phys. C}, {\bf 3}, 1235 (1992).
%
\bibitem{TAUSWORTHE}
R.C.~Tausworthe, 
Random numbers generated by linear recurrence modulo two,
{\it Math. Comput.} {\bf 19} (1965) 201.
%
\bibitem{CMF}
{\it CM Fortran User's Guide}, 
(Thinking Machines Corporation, Reading, Mass., 1992). 
%
\bibitem{CMSSL}
{\it CM Scientific Software Library}, 
(Thinking Machines Corporation, Reading, Mass., 1992). 
%
\bibitem{FINNS}
I.~Vattulainen {\it et al.}, 
A comparative study of some pseudorandom number generators,
University of Helsinki preprint HU-TFT-93-22, hep-lat 9304008.
%
\bibitem{WOLFF}
U. Wolff, 
% ????,
{\it Phys. Rev. Lett.} {\bf 62} (1989) 361.
%
\bibitem{WOLFRAM}
S.~Wolfram, 
Random Sequence Generation by Cellular Automata,
{\it Adv. Appl. Math.} {\bf 7} (1986) 123.
%
\bibitem{ZIFF}
R.M.~Ziff,
Reduction of correlations in shift-register sequence random number
generators using multiple feedback taps,
in preparation.
%
\end{thebibliography}

\end{document}
