Random number generators use iterative deterministic algorithms for
producing a sequence of pseudo-random numbers that
approximate a truly random sequence.
Probably the most commonly-used algorithms for sequential
random number generators are Linear Congruential Generators (LCGs).
LCGs produce a sequence of random integers using the relation
Many different parallel random number generators have been proposed
but most of them use the same basic concept, which is to parallelize a
sequential generator by taking the elements of the sequence of
pseudo-random numbers it generates and distributing them among the
processors in some way.
One of the method to achieve this goal is to split
the sequence into non-overlapping contiguous sections, 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. Alternatively, the length
of each section of numbers could be chosen much larger than could be
used by any processor. If the length of the sections is , then
processor would generate the sequence
Another simple method for parallelizing random number generators is
for processor of an processor machine to generate the
In the mpiJava Potts model and Ising model simulations, we use the
parallel MLCG using leapfrog algorithm as shown in Figure 6.1.
The leapfrog method is consequently very easy to implement on a parallel
The idea is to take a standard linear congruential algorithm, and have
every processor compute the Nth iterate of that algorithm (where
N is the number of processors.) [#!FoxBook88!#].
Each node computes random numbers using Eq. 6.2 and
and in Eq. 6.3 are calculated only once and
stored. The nodes are given a staggered start, so that their sequences don't
overlap. Let the seed, or 0th random number, be denoted by . Using
this as a seed, a sequential computer would compute the sequence:
The seeds in the nodes are set as follows (subscripts denote position
in the random number sequence, superscript denote processing node):
This defines the staggered start. The node now use Eq. 6.2
to compute the next member of each of their sequences. Therefore
If the seeds are set up properly (staggered) the processors leapfrog over one another, and it is just as good as having used the basic algorithm on a sequential machine.