Parallel Random Numbers: As Easy as 1, 2, 3
D. E. Shaw Research, New York, NY 10036, USA
Conference for High Performance Computing, Networking, Storage and Analysis (SC11), 2011
@article{salmon2011parallel,
title={Parallel Random Numbers: As Easy as 1, 2, 3},
author={Salmon, J.K. and Moraes, M.A. and Dror, R.O. and Shaw, D.E.},
year={2011}
}
Most pseudorandom number generators (PRNGs) scale poorly to massively parallel high-performance computation because they are designed as sequentially dependent state transformations. We demonstrate that independent, keyed transformations of counters produce a large alternative class of PRNGs with excellent statistical properties (long period, no discernable structure or correlation). These counter-based PRNGs are ideally suited to modern multicore CPUs, GPUs, clusters, and special-purpose hardware because they vectorize and parallelize well, and require little or no memory for state. We introduce several counter-based PRNGs: some based on cryptographic standards (AES, Threefish) and some completely new (Philox). All our PRNGs pass rigorous statistical tests (including TestU01’s BigCrush) and produce at least 2^64 unique parallel streams of random numbers, each with period 2^128 or more. In addition to essentially unlimited parallel scalability, our PRNGs offer excellent single-chip performance: Philox is faster than the CURAND library on a single NVIDIA GPU.
October 28, 2011 by hgpu
