SPLASH 2014
Mon 20 - Fri 24 October 2014 Portland, Oregon, United States
Thu 23 Oct 2014 13:52 - 14:15 at Salon F - Concurrency Chair(s): David Grove

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 Oct

Displayed time zone: Tijuana, Baja California change

13:30 - 15:00
ConcurrencyOOPSLA at Salon F
Chair(s): David Grove IBM Research
13:30
22m
Talk
Atlas: Leveraging Locks for Non-volatile Memory Consistency
OOPSLA
Dhruva Chakrabarti HP Labs, Hans-J. Boehm Google, Kumud Bhandari Rice University
Link to publication
13:52
22m
Talk
Fast Splittable Pseudorandom Number Generators
OOPSLA
Guy L. Steele Jr. Oracle Labs, Doug Lea State University of New York (SUNY) Oswego, Christine H. Flood Red Hat
Link to publication
14:15
22m
Talk
Multithreaded Test Synthesis for Deadlock Detection
OOPSLA
Malavika Samak Indian Institute of Science, Bangalore, Murali Krishna Ramanathan Indian Institute of Science, Bangalore
Link to publication
14:37
22m
Talk
Symbolic Execution of Multithreaded Programs from Arbitrary Program Contexts
OOPSLA
Tom Bergan University of Washington, Dan Grossman University of Washington, Luis Ceze University of Washington
Link to publication