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

15:00
Jeudi
4
Sep
2014
Organisé par : 

Arnaud Legrand

Intervenant : 

Stéfano Mohr

Équipes : 
Mots clés : 
Information détaillée : 

Grand amphithéatre

Résumé : 

  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.