Using Pseudo-random number repeatably in a fine-grain multithreaded simulation

Dmitry Savin, PhD student

Problem description

Particle transport Monte Carlo simulations are a key tool for High Energy Physics experiments, including the LHC experiments at CERN. All Monte Carlo (MC) simulations depend vitally on Pseudo-Random Number Generators (PRNGs) used to sample many distributions.

Each LHC experiments generates 5-10 Billion sampled physics events a year using around 10^18 sampled values from PRNGs. PRNGs take 1-5% of CPU time. PRNGs used must possess very large periods, fast execution, the ability to create a large number of streams, and very good correlation properties between streams and sampled values. It must be possible to reproduce a simulated event any time, for reexamination or debugging.

The transition from event-level parallelism in Geant4 to dynamical multithreading in GeantV requires associating the random generator states not with the threads but with the tracks, which are shuffled between "baskets" based on their type and energy. Maintaining reproducibility after such transition requires a drastic change in the way the random generators are used. We suggest solutions based on Scalable Pseudo Random Number Generators and on pedigrees introduced in Cilk Plus, which are first tested in Geant4.

Methods & motivation

Scalable Parallel Pseudo Random Number Generators Library [2]
Motivation: For independent simulation of several particles it is necessary to create independent random number streams, which must be spawn in a deterministic way to ensure reproducibility.
Description: Parallel Pseudo Random Number Generators Library implements several random number generators (48 bit Linear Congruential, 64 bit Linear Congruential, modified Additive Lagged Fibonacci, Multiplicative Lagged Fibonacci, Combined Multiple Recursive, and Prime Modulus Linear Congruential) which have large periods and big numbers of streams. It also enables the spawning of new streams while ensuring their independence.

Counter-based Pseudo Random Number Generators [3]

Motivation: Most pseudorandom number generators (PRNGs) scale

poorly to massively parallel high-performance computation because they are designed as sequentially dependent state transformations. Independent, keyed transformations of counters produce a large alternative class of PRNGs that require little memory for state and can be easily forwarded.

Description: Counter-based PRNGs consist of an increment for the transition function transition function and a hash function for the output function. Using a well-established cryptography function like AES or Threefish ensures good quality of the pseudo random numbers stream, while simpler functions like Philox give better performance.

Pedigree-based Pseudo Random Number Generators [1]

Motivation: In an application with a very big number of dynamic threads that use only a few random numbers SPRNG may be inefficient. Random number generation based on the spawn pedigree allows to overcome this hurdle.

Description: Pedigrees store the deterministic state independent of order of operations that represents the spawn history. This state can be used for a counter-based generator to produce independent random number streams.

Timeline

April 20 – May 30 (Before the official coding time):

Familiarize myself with CLHEP random generators, SPRNG library, DotMix from CilkPlus and geant4 track manipulation.

May 30 – June 26 (Official coding period starts):

Implement a invocation tree like described in [1]:
- each node holds
  - an integer value E
  - a 'hash' value "H"
  - a unique pointer to an RNG state
- Each node generates up to N child nodes, using its 'energy' state E and its RNG (state)
  - E_i = floor( s * v * E ) // FIXME compresses E towards 0
  - where s = constant double (parameter) damping factor < 1/N
  - v = [0,1) variate obtained from the RNG
  - the RNG state of the child node is a deterministic function of the current state
- Each node generates the hash value for its daughter node 'i'
  - H_i = HashFunc( H, i )
Demonstrate the independence of the tree traversing order.
Provide the interface for hash calculation based on the rank of a track in the invocation tree by different generators
Prepare report

June 26 – July 30:

Discuss results with mentor

June 30 – July 24:

Associate additional PRNG information with track in a geant4 simulation:

in user actions (optional)
in the toolkit

Implement backends:
- reproducing the current behavior for testing purposes
- based on pedigrees (as the period milestone)
Prepare report

July 24 – July 28:

Discuss results with mentor

July 28 – August 21:

Alongside the generators based on pedigrees add:
- counter-based [3]
- SPRNG [2] (optional)

Write and run tests to assess the suitability of each generator for geant4:

check the physical results
check the performance overhead

Provide documentation
Final report

References

Deterministic parallel random-number generation for dynamic-multithreading platforms, Charles E. Leiserson et al.
M. Mascagni and A. Srinivasan (2000), "Algorithm 806: SPRNG: A Scalable Library for Pseudorandom Number Generation," ACM Transactions on Mathematical Software, 26: 436-461.
J. K. Salmon, M. A. Moraes, R. O. Dror, and D. E. Shaw, “Parallel Random Numbers: As Easy as 1, 2, 3” in Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis on - SC ’11, 2011, pp 1-12.