Generic Algorithms for Deterministic Random Number Generation in Dynamic-Multithreaded Platform

  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.