Skip to Main content Skip to Navigation
Conference papers

Generic Deterministic Random Number Generation in Dynamic-Multithreaded Platforms

Abstract : On dynamic multithreaded platforms with on-line scheduling such as work-stealing, randomized computations raise the issue of repro-ducibility. Compliant with de facto standard sequential Deterministic Random Number Generators (DRNGs) noted R, we propose a parallel DRNG implementation for finite computations that provides determinis-tic parallel execution. It uses the stateless sub-stream approach, enabling the use of efficient DRNG such as Mersenne Twister or Linear Congru-ential. We demonstrate that if R provides fast jump ahead in the random sequence, the re-seeding overhead is small, polylog in expectation, inde-pendently 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 compares favorably to the linear overhead of DotMix re-seedings.
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/hal-01102365
Contributor : Jean-Louis Roch <>
Submitted on : Monday, January 12, 2015 - 4:04:31 PM
Last modification on : Tuesday, May 11, 2021 - 11:36:25 AM
Long-term archiving on: : Saturday, September 12, 2015 - 1:40:31 AM

File

genparDRNG-europar-hal.pdf
Files produced by the author(s)

Identifiers

Collections

CNRS | INRIA | LIG | UGA

Citation

Stefano Mor, Jean-Louis Roch, Nicolas Maillard. Generic Deterministic Random Number Generation in Dynamic-Multithreaded Platforms. Euro-Par 2014 Parallel Processing - 20th International Conference, Aug 2014, Porto, Portugal. pp.427 - 438, ⟨10.1007/978-3-319-09873-9_36⟩. ⟨hal-01102365⟩

Share

Metrics

Record views

466

Files downloads

625