Arnaud Legrand
Stéfano Mohr
Grand amphithéatre
On dynamic multithreaded platforms with on-line scheduling such as
work-stealing, randomized computations raise the issue of
reproducibility. Compliant with de facto standard sequential
Deterministic Random Number Generators (DRNGs) noted R, we propose a
parallel DRNG implementation for finite computations that provides
deterministic parallel execution. It uses the stateless sub-stream
approach, enabling the use of efficient DRNG such as Mersenne
Twister or Linear Congruential. We demonstrate that if R provides
fast jump ahead in the random sequence, the re-seeding overhead is
small, polylog in expectation, independently from the parallel
computation’s depth. Experiments bench- mark the performance of
randomized algorithms employing our solution against the stateful
DRNG DotMix, tailored to the Cilk Plus dynamic multithreading
runtime. The overhead of our implementation ParDRNG<R> compares
favorably to the linear overhead of DotMix re-seedings.