| <- HREF="node14.html" Prev | Index | Next -> |
NHSE ReviewTM: Comments
· Archive
· Search
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 leapfrogs by N in the sequence
[47, 48, 49, 50, 4].
In order to use this method we need to be able to easily jump ahead
in the sequence. This can be done quite easily for linear congruential
generators, and merely involves replacing the multiplier a and the
additive constant c by new values 
and 
respectively (both modulo M)
[47, 48, 49, 50].
Jumping ahead in the sequence can also be done for
combined LCGs [6, 51]
and shift-register generators [52],
but is not practical for LFGs using addition or multiplication,
since the computations are much more complex, making it too slow
for practical use.
A 48-bit LCG using the leapfrog technique has been used on vector machines such as the CRAY and CYBER-205 [47, 4, 8], and for the intrinsic random number generator function used in IBM's XL HPF High Performance Fortran release (which offers the option of a 32-bit or a 48-bit LCG - beware that the totally inadequate 32-bit LCG is the default!) [61].
A potentially serious problem with the leapfrog method for LCGs is that
although the
multiplier a may be chosen to perform well in the Spectral Test,
there is no guarantee that will also have good spectral properties,
particularly since N will in general be arbitrary.
This method could work well in situations for which N is fixed
(for example, if an application is always run on the same number of
processors), since it would be possible to choose a multiplier so that both
a and do well in the Spectral Test.
However it is not possible to choose a multiplier for which has
good spectral properties for any value of N, so this algorithm is not
recommended as a general-purpose generator.
There is another potential problem with this type of generator. As mentioned in Section 5.1, linear congruential generators using a modulus that is a power of 2 are known to have correlations between elements in the sequence that are a power of 2 apart. For many parallel computers the number of physical processors is a power of 2, and this is also often the case for the number of abstract processors, i.e. the size of the arrays used in a simulation. This means that the pseudo-random numbers generated on a given processor may be more strongly correlated than the sequence on a single processor. In fact the leapfrog linear congruential algorithm used on the CRAY and CYBER-205, which has a power of 2 modulus, has produced spurious results in some Monte Carlo calculations [8, 11]. This problem can be avoided by using a prime modulus.
For these reasons, we do not recommend the leapfrog method, although it may be adequate for many applications. If you do use this type of generator, at least be sure that the LCG is 48-bit or higher (32-bit or higher for a combined LCG) and preferably has a prime modulus.
| <- HREF="node14.html" Prev | Index | Next -> |
NHSE ReviewTM: Comments
· Archive
· Search