next up previous

5 Vectorization and Access via Multiple Processors: LCGs     continued...

Thus for any k, for all i for which bit i in the base-two representation of k is a one. Therefore we can leap ahead by k cycle steps with no more than multiplies. Once is computed, the N seeds can be determined by the procedure:

With these seeds, each of the N processes will generate random numbers from nearly equally-spaced points on the cycle. As long as no process needs more than k random numbers, a condition easily met for some applications, then no overlap will occur. Everything just said for MIMD processes applies equally well to SIMD programs, where the number of random number streams needed is (usually) known at run time.

The development of the leap ahead technique just described assumed that c = 0 in the LCG rule. For , Leap ahead can still be accomplished in a similar way, if one constructs the -long array of partial sums of the form: where, as before, j is a power of two. The details are left as an exercise for the reader.

The second and more difficult case to consider is when we do not know at the beginning of program execution how many processes (generators) we will need. The splitting of processes in such programs are data driven and in most cases occur as the result of prior Monte Carlo trials taken many steps earlier. The problem is to spawn new LCG seeds in a way that is both reproducible and which yields independent new streams.