Plenary Lecture
Random Number Generators with Multiple Streams for Parallel Computers
Professor Pierre L'Ecuyer
Canada Research Chair in Stochastic Simulation and Optimization
DIRO, Universite de Montreal
Canada
&
Inria International Chair
Inria-Rennes, France
E-mail: lecuyer@iro.umontreal.ca
Abstract: We discuss the design of software libraries that can provide multiple streams of independent uniform random numbers for simulation in parallel computing environments. These multiple streams are typically defined as disjoint segments of the sequence of numbers produced by a single random number generator (RNG), and which should behave approximately as the realizations of independent random variables uniformly distributed over the interval (0, 1) [2, 4, 5]. These numbers can be transformed appropriately to simulate random variables from other distributions, stochastic processes, and other types of random objects. Thousands or even millions of independent streams of random numbers are sometimes required in parallel computing applications. Multiple streams are also very convenient when running simulations on a single processor, for example to maintain proper synchronization when comparing similar systems with common random numbers (CRNs) and in simulation-based optimization via sample average approximation (SAA) [1, 3, 6, 7].
We give special attention to parallel processing situations where each processor has a limited amount of fast-access private memory, such as for discrete graphical processing units (GPUs) and general-purpose GPUs (GPGPUs).
We introduce clRNG, an API and library for uniform random number generation in OpenCL. Streams of random numbers can be seen as virtual random number generators. They can be created on the host computer in unlimited numbers, and then used either on the host or on other computing devices by work items to generate random numbers. Each stream also has equally-spaced substreams, which are useful in certain settings. We provide examples showing the usefulness of streams and substreams in this context, and how the clRNG library can be used.
This is based on joint work with David Munger and Nabil Kemerchou.
References
[1] A. M. Law. Simulation Modeling and Analysis. McGraw-Hill, New York, Fifth edition, 2014.
[2] P. L'Ecuyer. Uniform random number generation. Annals of Operations Research, 53:77-120, 1994.
[3] P. L'Ecuyer. Variance reduction's greatest hits. In Proceedings of the 2007 European Simulation and Modeling Conference, pages 5-12, Ghent, Belgium, 2007. EUROSIS.
[4] P. L'Ecuyer. Random number generation. In J. E. Gentle, W. Haerdle, and Y. Mori, editors, Handbook of Computational Statistics, pages 35-71. Springer-Verlag, Berlin, second edition, 2012.
[5] P. L'Ecuyer, B. Oreshkin, and R. Simard. Random numbers for parallel computers: Requirements and methods, 2014. http://www.iro.umontreal.ca/~lecuyer/myftp/papers/parallel-rng-imacs.pdf.
[6] P. L'Ecuyer, R. Simard, E. J. Chen, and W. D. Kelton. An object-oriented random-number package with many long streams and substreams. Operations Research, 50(6):1073-1075, 2002.
[7] A. Shapiro, D. Dentcheva, and A. Ruszczynski, editors. Lecture Notes on Stochastic Programming: Modeling and Theory. SIAM, Philadelphia, 2009.
Brief Biography of the Speaker: Pierre L'Ecuyer is a Professor in the Departement d'Informatique et de Recherche Operationnelle at the Universite de Montreal. He holds the Canada Research Chair in Stochastic Simulation and Optimization since 2004 and an Inria International Chair (at Inria-Rennes, France) for 2013-2018. He obtained the Canadian Operational Research Society Award of Merit in 2014, the INFORMS Simulation Society Distinguished Service Award in 2011, the INFORMS Simulation Society Outstanding Research Publication Award twice, in 1999 and 2009, a Killam Research Fellowship in 2001-03, the Urgel-Archambault Prize from ACFAS in 2002, Steacie Fellowship from the Natural Sciences and Engineering Research Council of Canada (NSERC) in 1995-97, and was elected INFORMS Fellow in 2006.
He has published over 240 scientific articles and book chapters in various areas, including random number generation, quasi-Monte Carlo methods, e ciency improvement in simu- lation, sensitivity analysis and optimization for discrete-event simulation models, simulation software, stochastic dynamic programming, and applications in finance, manufacturing, telecommunications, reliability, and service center management. He also developed software libraries and systems for the theoretical and empirical analysis of random number generators and quasi-Monte Carlo point sets, and for general discrete-event simulation. His work impinges on the areas of mathematics, statistics, operations research, economics, and computer science.
He was Editor-in-Chief for the ACM Transactions on Modeling and Computer Simulation until June 2013. He is currently Associate Editor for ACM Transactions on Mathematical Software, Statistics and Computing, Cryptography and Communications, and International Transactions in Operational Research. He has been a referee for over 130 different scientific journals, plus many books and conference proceedings.
He was a professor in the Departement d'Informatique at Universite Laval (Quebec) from 1983 to 1990 and is at the Universite de Montreal since then. He has been a visiting scholar (for several months) at Stanford University (USA), INRIA-Rocquencourt (France), Ecole des Mines (France), Waseda University (Tokyo), University of Salzburg (Austria), North Carolina State University (USA), INRIA-Rennes (France), and Universite de Savoie in Chambery (France). He is a member of the CIRRELT and GERAD research centers, in Montreal.
He is a competitive cyclist in road racing, with four titles of Canadian Champion and ten titles of Quebec Champion.