Generic Deterministic Random Number Generation in Dynamic-Multithreaded Platforms
| Autor: | Jean-Louis Roch, Stefano Drimon Kurz Mor, Nicolas Maillard |
|---|---|
| Přispěvatelé: | Association of Computer Electronics and Electrical Engineers (ACEEE), Institute of Doctors Engineers and Scientists, Instituto de Informática da UFRGS (UFRGS), Universidade Federal do Rio Grande do Sul [Porto Alegre] (UFRGS), Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), PrograMming and scheduling design fOr Applications in Interactive Simulation (MOAIS), Laboratoire d'Informatique de Grenoble (LIG), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Fernando M. A. Silva and Ines de Castro Dutra and Vìtor Santos Costa, Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG), Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF) |
| Jazyk: | angličtina |
| Rok vydání: | 2014 |
| Předmět: |
Random number generation
Computer science Computation Dynamic-Multithreading Mersenne twister Parallel computing Cilk Generic DotMix Randomized algorithm Scheduling (computing) Multithreading [INFO.INFO-DC]Computer Science [cs]/Distributed Parallel and Cluster Computing [cs.DC] computer computer.programming_language Random Numbers |
| Zdroj: | Springer Lecture Notes in Computer Science, volume 8632 Euro-Par 2014 Parallel Processing-20th International Conference Euro-Par 2014 Parallel Processing-20th International Conference, Aug 2014, Porto, Portugal. pp.427-438, ⟨10.1007/978-3-319-09873-9_36⟩ Lecture Notes in Computer Science ISBN: 9783319098722 Euro-Par |
| DOI: | 10.1007/978-3-319-09873-9_36⟩ |
| Popis: | International audience; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|