next up previous

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

Here we only mention a generalized approach that works within limits. Further details can be found in [20]. Consider an LGC with the property that each X has two successors, a ``left'' successor, , and a ``right'' successor, . These are generated as follows:

Figure 7 shows the action of these operations with respect to a starting seed . Taken separately, the and sequences are simple LCGs that traverse the set in different order. Alternatively (and the method in which these generators are typically used), the rule produces a pseudo-random leap-ahead for the sequence, thus deterministically producing a seed for a new, spawned, subsequence of the ``right'' cycle. With such a mechanism that uses only local information from a process, reproducibility can be established. Frederickson gives a formula for the selection of the constants in the succession rules that satisfies a particular independence criterion, given some constraints. The interested reader is referred to Frederickson, et al., 1984 [20] for further enlightenment.

Figure 7: Tree Generated from "Left" and "Right" Generators.

(See exercises 8 and 8.)