Generic Deterministic Random Number Generation in Dynamic-Multithreaded PlatformsReportar como inadecuado

Generic Deterministic Random Number Generation in Dynamic-Multithreaded Platforms - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 Association of Computer Electronics and Electrical Engineers ACEEE 2 UFRGS - Instituto de Informática da UFRGS 3 Université Grenoble Alpes Saint Martin d-Hères 4 MOAIS - PrograMming and scheduling design fOr Applications in Interactive Simulation Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d-Informatique de Grenoble

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.

Keywords : Generic DotMix Cilk Dynamic-Multithreading Random Numbers

Autor: Stefano Mor - Jean-Louis Roch - Nicolas Maillard -



Documentos relacionados