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.
Type de document :
Communication dans un congrès
Fernando M. A. Silva and Ines de Castro Dutra and Vìtor Santos Costa. Euro-Par 2014 Parallel Processing - 20th International Conference, Aug 2014, Porto, Portugal. Springer Lecture Notes in Computer Science, volume 8632, 8632, pp.427 - 438, 2014, Lecture Notes in Computer Science. 〈10.1007/978-3-319-09873-9_36〉
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01102365
Contributeur : Jean-Louis Roch <>
Soumis le : lundi 12 janvier 2015 - 16:04:31
Dernière modification le : jeudi 11 janvier 2018 - 01:48:45
Document(s) archivé(s) le : samedi 12 septembre 2015 - 01:40:31

Fichier

genparDRNG-europar-hal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Stefano Mor, Jean-Louis Roch, Nicolas Maillard. Generic Deterministic Random Number Generation in Dynamic-Multithreaded Platforms. Fernando M. A. Silva and Ines de Castro Dutra and Vìtor Santos Costa. Euro-Par 2014 Parallel Processing - 20th International Conference, Aug 2014, Porto, Portugal. Springer Lecture Notes in Computer Science, volume 8632, 8632, pp.427 - 438, 2014, Lecture Notes in Computer Science. 〈10.1007/978-3-319-09873-9_36〉. 〈hal-01102365〉

Partager

Métriques

Consultations de la notice

163

Téléchargements de fichiers

156