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
[#!ANDERSON!#,#!Coddington!#],
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

This method requires the ability to jump ahead in the sequence by a given amount.

Another simple method for parallelizing random number generators is
for processor of an processor machine to generate the
sub-sequence

so that the sequence is spread across processors in the same way as a deck of cards is dealt in turn to players in a card game. This is known as the leapfrog technique, since each processor leap-frogs by in the sequence. In order to use this method we need to be able to easily jump ahead in the sequence. Linear congruential generators are simple enough that it is possible to specify analytically an arbitrary element in the sequence. By recursively applying equation 6.1, it is easy to show that the element is given by

with

Thus moving through the sequence with stride , rather than 1, is simply accomplished by specifying a different multiplier and additive constant for the generator.

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
machine.
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

(6.6) | |||

and,

(6.7) | |||

and so on.

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.