Fast Splittable Pseudorandom Number Generators
We describe a new algorithm SPLITMIX for an object-oriented and splittable pseudorandom number generator (PRNG) that is quite fast: 9 64-bit arithmetic/logical operations per 64 bits generated. A conventional linear PRNG object provides a generate method that returns one pseudorandom value and updates the state of the PRNG, but a splittable PRNG object also has a second operation, split, that replaces the original PRNG object with two (seemingly) independent PRNG objects, by creating and returning a new such object and updating the state of the original object. Splittable PRNG objects make it easy to organize the use of pseudorandom numbers in multithreaded programs structured using fork-join parallelism. No locking or synchronization is required (other than the usual memory fence immediately after object creation). Because the generate method has no loops or conditionals, it is suitable for SIMD or GPU implementation.
We derive SPLITMIX from the DOTMIX algorithm of Leiserson, Schardl, and Sukha by making a series of program transformations and engineering improvements. The end result is an object-oriented version of the purely functional API used in the Haskell library for over a decade, but SPLITMIX is faster and produces pseudorandom sequences of higher quality; it is also far superior in quality and speed to java.util.Random, and has been included in Java JDK8 as the class java.util.SplittableRandom.
We have tested the pseudorandom sequences produced by SPLITMIX using two standard statistical test suites (DieHarder and TestU01) and they appear to be adequate for “everyday” use, such as in Monte Carlo algorithms and randomized data structures where speed is important.
Thu 23 OctDisplayed time zone: Tijuana, Baja California change
13:30 - 15:00
ConcurrencyOOPSLA at Salon F
Chair(s): David Grove IBM Research
|Atlas: Leveraging Locks for Non-volatile Memory Consistency|
Dhruva Chakrabarti HP Labs, Hans-J. Boehm Google, Kumud Bhandari Rice UniversityLink to publication
|Fast Splittable Pseudorandom Number Generators|
Guy L. Steele Jr. Oracle Labs, Doug Lea State University of New York (SUNY) Oswego, Christine H. Flood Red HatLink to publication
|Multithreaded Test Synthesis for Deadlock Detection|
Malavika Samak Indian Institute of Science, Bangalore, Murali Krishna Ramanathan Indian Institute of Science, BangaloreLink to publication
|Symbolic Execution of Multithreaded Programs from Arbitrary Program Contexts|
Tom Bergan University of Washington, Dan Grossman University of Washington, Luis Ceze University of WashingtonLink to publication