NHSE ReviewTM 1996 Volume Second Issue

Random Number Generators for Parallel Computers

| <- HREF="node15.html" Prev | Index | Next -> |
NHSE ReviewTM: Comments · Archive · Search

Sequence Splitting 

Another method for parallelizing random number generators is to split the sequence into non-overlapping contiguous sections, each generated by a different processor [4, 6, 7]. For example, one could 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 possibly be used by any processor. If the length of the sections is L, then processor P would generate the sequence

X_(PL), X_(PL+1), X_(PL+2), ...

This method also requires the ability to quickly jump ahead in the sequence by a given amount. It is therefore restricted primarily to the same type of generators as the leapfrog method, however in this case it is also possible to use additive lagged Fibonacci generators. Although jumping ahead using additive LFGs is too slow to do every time a number is generated (which is required for leapfrog), it may be fast enough to be feasible for sequence splitting, which only needs to be done once, in the initialization of the generator. A parallel generator of this type has been implemented by Brent [7], who presents an initialization method that takes O(r log n) time to jump ahead n for a lag r. An implementation using sequence splitting of a combined linear congruential generator has been given by L'Ecuyer and Côté [51].

A possible problem with this method is that although the sequences on each processor are disjoint (i.e. there is no overlap), this does not necessarily mean that they are uncorrelated. In fact it is known that linear congruential generators with modulus a power of 2 have long-range correlations that may cause problems, since the sequences on each processor are separated by a fixed number of iterations (L). Other generators may also have subtle long-range correlations that could be amplified by using sequence splitting.

A disadvantage of this type of generator is that it does not produce the same sequence for different numbers of processors. However in a data parallel programming model (for example, as used by High Performance Fortran [53]) it is possible to split the sequence among ``abstract processors'', or distributed data elements, such that the sequences will be the same for any number of physical processors. For a combined LCG, this requires only two integer values per array element to store the state of the generator, which should not be too great a memory requirement. This method appears capable of providing a very good parallel random number generator, particularly for data parallel languages such as HPF [54].

Copyright © 1996

| <- HREF="node15.html" Prev | Index | Next -> |
NHSE ReviewTM: Comments · Archive · Search

Paul Coddington, paulc@npac.syr.edu