Algorithm 806: SPRNG: A Scalable Libraryfor Pseudorandom Number GenerationMICHAEL MASCAGNIFlorida State UniversityandASHOK SRINIVASANIndian Institute of Technology—BombayIn this article we present background, rationale, and a description of the Scalable ParallelRandom Number Generators (SPRNG) library. We begin by presenting some methods forparallel pseudorandom number generation. We will focus on methods based on parameteriza-tion, meaning that we will not consider splitting methods such as the leap-frog or blockingmethods. We describe, in detail, parameterized versions of the following pseudorandomnumber generators: (i) linear congruential generators, (ii) shift-register generators, and (iii)lagged-Fibonacci generators. We briefly describe the methods, detail some advantages anddisadvantages of each method, and recount results from number theory that impact ourunderstanding of their quality in parallel applications. SPRNG was designed around theuniform implementation of different families of parameterized random number generators. Wethen present a short description of SPRNG. The description contained within this document ismeant only to outline the rationale behind and the capabilities of SPRNG. Much moreinformation, including examples and detailed documentation aimed at helping users withputting and using SPRNG on scalable systems is available at http://sprng.cs.fsu.edu. In thisdescription of SPRNG we discuss the random-number generator library as well as the suite oftests of randomness that is an integral part of SPRNG. Random-number tools for parallelMonte Carlo applications must be subjected to classical as well as new types of empirical testsof randomness to eliminate generators that show defects when used in scalable environments.The SPRNG software was developed with funding from DARPA Contract Number DABT63-95-C-0123 for ITO: Scalable Systems and Software, entitled A Scalable Pseudorandom NumberGeneration Library for Parallel Monte Carlo Computations. This DARPA project was acollaboration between David Ceperley, Lubos Mitas, Faisal Saied, and Ashok Srinivasan of theUniversity of Illinois at Urbana-Champaign and the first author’s research group at theUniversity of Southern Mississippi and the Florida State University. Work on SPRNG is nowfunded by an ASCI level 3 grant from Lawrence Livermore, Los Alamos, and Sandia NationalLaboratories.Authors’ addresses: M. Mascagni, Department of Computer Science, Florida State University,203 Love Building, Tallahassee, FL 32306-4530; email: [email protected]; A. Srinivasan,Department of Mathematics, Indian Institute of Technology—Bombay, Bombay, Powai, Mum-bai, 400 076, India; email: [email protected] to make digital/hard copy of part or all of this work for personal or classroom useis granted without fee provided that the copies are not made or distributed for profit orcommercial advantage, the copyright notice, the title of the publication, and its date appear,and notice is given that copying is by permission of the ACM, Inc. To copy otherwise, torepublish, to post on servers, or to redistribute to lists, requires prior specific permissionand/or a fee.© 2001 ACM 0098-3500/00/0900–0436 $5.00ACM Transactions on Mathematical Software, Vol. 26, No. 3, September 2000, Pages 436–461.Categories and Subject Descriptors: D.3.2 [Programming Languages]: Language Classifica-tions—C; C11; Fortran; G.4 [Mathematics of Computing]: Mathematical Software—Algorithm design and analysis; Documentation; Efficiency; Parallel and vector implementa-tions; Reliability and robustnessGeneral Terms: Algorithms, Design, Documentation, Experimentation, Performance, Reliabil-ity, StandardizationAdditional Key Words and Phrases: Parallel random-number generators, random-numbersoftware, linear congruential generator, lagged-Fibonacci generator, random-number tests1. INTRODUCTIONMonte Carlo computations have consumed and continue to consume a largefraction of all the available high-performance computing cycles. Whilemuch work has been done on numerical software in areas such as numeri-cal linear algebra and the numerical solution of differential equations,there is a dearth of good software tools for Monte Carlo computations,despite their ubiquity and importance. In particular, defects in pseudoran-dom-number generators can cause erroneous results in the Monte Carlocomputation. To make matters worse, many of the popular pseudorandom-number generators in use, particularly those supplied by vendors, havebeen found to be defective in the context of real applications. Parallelismfurther complicates this state of affairs. The random-number software wedescribe in detail below was developed to rectify this situation. Apart fromthe implementation of good generators, we have designed a user-friendly,standard interface which others can use for their implementation of newparallel pseudorandom number generators (PPRNGs).Monte Carlo applications are widely perceived as embarrassingly paral-lel.1The truth of this notion depends, to a large extent, on the quality ofthe parallel random-number generators used. It is widely assumed thatwith N processors executing N copies of a Monte Carlo calculation, thepooled result will achieve a varianceN times smaller than a single instanceof this calculation in the same amount of time. This is true only if theresults in each processor are statistically independent. In turn, this will betrue only if the streams of random numbers generated in each processor areindependent.Here we present an overview of the Scalable Parallel Random NumberGenerators (SPRNG) library. This library was designed to support parallelMonte Carlo applications on scalable and distributed architectures. Webegin by briefly presenting several methods of parallel pseudorandom-number generation and discuss pros and cons for each method. If thereader is interested in background material on plain old serial pseudoran-dom-number generation consult the following references by Knuth [1998],L’Ecuyer [1990; 1994; 1998], Niederreiter [1992], Park and Miller [1988],1Monte Carlo enthusiasts prefer the term “naturally parallel” to the somewhat derogatory“embarrassingly parallel” coined by computer scientists.Algorithm 806: SPRNG • 437ACM Transactions on Mathematical Software, Vol. 26, No. 3, September 2000.and Tezuka [1995], while a good overview of parallel pseudorandom-number generation can be found in a recent work by the present