10.2 Parallel Random Numbers

  We can distinguish three general approaches to the generation of   random numbers on parallel computers: centralized, replicated, and distributed. In the centralized approach, a sequential generator is encapsulated in a task from which other tasks request random numbers. This avoids the problem of generating multiple independent random sequences, but is unlikely to provide good performance. Furthermore, it makes reproducibility hard to achieve: the response to a request depends on when it arrives at the generator, and hence the result computed by a program can vary from one run to the next.

In the replicated approach, multiple instances of the same   generator are created (for example, one per task). Each generator uses either the same seed or a unique seed, derived, for example, from a task identifier. Clearly, sequences generated in this fashion are not guaranteed to be independent and, indeed, can suffer from serious correlation problems. However, the approach has the advantages of efficiency and ease of implementation and should be used when appropriate.

In the distributed approach, responsibility for generating a single sequence is partitioned among many generators, which can then   be parceled out to different tasks. The generators are all derived from a single generator; hence, the analysis of the statistical properties of the distributed generator is simplified. As only distributed generators are at all difficult to implement on parallel computers, we focus on this topic in the rest of this chapter.