Skip to main content
SpringerLink
Log in

Pseudo-random streams for distributed and parallel stochastic simulations on GP-GPU

  • Article
  • Published:
Journal of Simulation

Abstract

Random number generation is a key element of stochastic simulations. It has been widely studied for sequential applications purposes, enabling us to reliably use pseudo-random numbers in this case. Unfortunately, we cannot be so enthusiastic when dealing with parallel stochastic simulations. Many applications still neglect random stream parallelization, leading to potentially biased results. In particular parallel execution platforms, such as Graphics Processing Units (GPUs), add their constraints to those of Pseudo-Random Number Generators (PRNGs) used in parallel. This results in a situation where potential biases can be combined with performance drops when parallelization of random streams has not been carried out rigorously. Here, we propose criteria guiding the design of good GPU-enabled PRNGs. We enhance our comments with a study of the techniques aiming to parallelize random streams correctly, in the context of GPU-enabled stochastic simulations.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Figure 1
Figure 2
Figure 3
Figure 4
Figure 5
Figure 6
Figure 7

Similar content being viewed by others

References

  • Bradley T et al (2011). GPU Computing Gems Emerald Edition Chapter 16—Parallelization Techniques for Random Numbers Generators. Elsevier: Amsterdam, pp 231–246.

    Book  Google Scholar 

  • Coddington P (1996). Random number generators for parallel computers. Technical Report 2, NHSE.

  • De Matteis A and Pagnutti S (1988). Parallelization of random number generators and long-range correlations. Numerische Mathematik 53 (5): 595–608.

    Article  Google Scholar 

  • Entacher K and Hechenleitner B (2003). Pitfalls when using parallel streams in omnet++ simulations. In: Hofmann U and Miloucheva I (eds). Interdomain Performance and Simulation (IPS) Workshop. IST: Salzburg, Austria.

    Google Scholar 

  • Haramoto H et al (2008). Efficient jump ahead for f2-linear random number generators. INFORMS Journal on Computing 20 (3): 385–390.

    Article  Google Scholar 

  • Hechenleitner B (2004). Defects in random number routines of well-known network simulators and appropriate improvements PhD Thesis.

  • Hellekalek P (1998a). Don’t trust parallel monte carlo! In: Proceedings of Parallel and Distributed Simulation PADS98. IEEE, New York, pp 82–89.

    Google Scholar 

  • Hellekalek P (1998b). Good random number generators are (not so) easy to find. Mathematics and Computers in Simulation 46 (5–6): 485–505.

    Article  Google Scholar 

  • Hill D (2003). Urng: A portable optimization technique for software applications requiring pseudo-random numbers. Simulation Modelling Practice and Theory 11 (7–8): 643–654.

    Article  Google Scholar 

  • Hill D (2010). Practical distribution of random streams for stochastic high performance computing. In: IEEE International Conference on High Performance Computing & Simulation (HPCS 2010), pp 1–8, Invited paper.

  • Hoberock J and Bell N (2010). Thrust: A parallel template library, http://www.meganewtons.com/Version 1.3.0.

  • Karimi K, Dickson N and Hamze F (2010). A performance comparison of cuda and opencl, http://arxiv.org/abs/1005.2581v3 submitted.

  • Khronos OpenCL Working Group (2010). The opencl specification. Specification 1.1, Khronos Group.

  • Kirk D and Hwu W (2010). Programming Massively Parallel Processors. Morgan Kaufmann: Los Altos, CA.

    Google Scholar 

  • Langdon W (2008). A fast high quality pseudo random number generator for graphics processing units. In: IEEE CEC 2008, Hong Kong. IEEE: Hong Kong, pp 459–465.

    Google Scholar 

  • Langdon W (2009). A fast high quality pseudo random number generator for nvidia cuda. In: GECCO’09, Vol. 10, ACM Press: New York, pp 2511–2514.

    Google Scholar 

  • L'Ecuyer P (1996). Maximally equidistributed combined Tausworthe generators. Mathematics of computation 65 (213): 203–213.

    Article  Google Scholar 

  • L'Ecuyer P (2010). Pseudorandom Number Generators. In: Encyclopedia of Quantitative Finance. John Wiley & Sons: Hoboken, NJ.

  • L'Ecuyer P and Simard R (2007). Testu01: A c library for empirical testing of random number generators. ACM Transactions on Mathematical Software 33 (4), 22: 1–40.

    Article  Google Scholar 

  • Maigne L et al (2004). Parallelization of Monte Carlo simulations and submission to a grid environment. Parallel Processing Letters 14 (2): 177–196.

    Article  Google Scholar 

  • Marsaglia G (2003). Xorshift rngs. Journal of Statistical Software 8 (14): 1–6.

    Article  Google Scholar 

  • Marsaglia G, Narasimhan B and Zaman A (1990). A random number generator for pc's. Computer Physics Communications 60 (3): 345–349.

    Article  Google Scholar 

  • Marsaglia G and Zaman A (1991). A new class of random number generators. Annals of Applied Probability 3 (3): 462–480.

    Article  Google Scholar 

  • Mascagni M and Srinivasan A (2004). Parameterizing parallel multiplicative lagged-Fibonacci generators. Parallel Computing 30 (7): 899–916.

    Article  Google Scholar 

  • Matsumoto M and Nishimura T (1998). Mersenne twister: A 623-dimensionally equidistributed uniform pseudorandom number generator. ACM Transactions on Modeling and Computer Simulations: Special Issue on Uniform Random Number Generation 8 (1): 3–30.

    Article  Google Scholar 

  • Matsumoto M and Nishimura T (2000). Dynamic creation of pseudorandom number generators. In: Niederreiter H and Spanier J (eds.) Monte Carlo and Quasi-Monte Carlo Methods 1998. Springer: New York, pp 56–69.

    Chapter  Google Scholar 

  • NVIDIA (2010a). CUDA CURAND Library. NVDIA Corporation, Technical Report.

  • NVIDIA (2010b). NVIDIA CUDA Programming Guide Version 3.2, NVIDIA Corporation. Technical Report.

  • Park S and Miller K (1988). Random number generators: Good ones are hard to find. Communications of the ACM 31 (10): 1192–1201.

    Article  Google Scholar 

  • Passerat-Palmbach J, Mazel C, Bachelet B and Hill D (2011). Shoverand: A model-driven framework to easily generate random numbers on gp-gpu. In: Smari WW and McIntire JP (eds). IEEE: Istanbul, Turkey, IEEE International Conference on High Performance Computing & Simulation, pp 41–48.

  • Passerat-Palmbach J, Mazel C, Mahul A and Hill D (2010). Reliable initialization of gpu-enabled parallel stochastic simulations using mersenne twister for graphics processors. In ESM 2010, pp 187–195. ISBN: 978-90-77381-57-1.

  • Passerat-Palmbach J, Caux J, Siregar P and Hill DRC (2011). Warp-level parallelism: Enabling multiple replications in parallel on GPU. In: Proceedings of the European Simulation and Modeling Conference 2011, 24–26 October, Guimarães; Portugal, pp 76–83.

  • Reuillon R, Traore MK, Passerat-Palmbach J and Hill DR (2011). Parallel stochastic simulations with rigorous distribution of pseudo-random numbers with distme: Application to life science simulations. Concurrency and Computation: Practice and Experience, http://dx.doi.org/10.1002/cpe.1883.

  • Rukhin A et al (2001). A statistical test suite for random and pseudorandom number generators for cryptographic applications. Technical Report, NIST.

  • Saito M (2010). A variant of mersenne twister suitable for graphics processors, http://arxiv.org/abs/1005.4973, submitted.

  • Saito M (2011). Tiny mersenne twister (tinymt). http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/TINYMT/index.html, accessed 14 September 2011.

  • Saito M and Matsumoto M (2008). Simd-oriented fast mersenne twister: A 128-bit pseudorandom number generator. In: Keller A, Heinrich S and Niederreiter H (eds). Monte Carlo and Quasi-Monte Carlo Methods 2006, Vol. 2, Springer: Berlin, Heidelberg, pp 607–622.

    Chapter  Google Scholar 

  • Sussman M, Crutchfield W and Papakipos M (2006). Pseudorandom number generation on the GPU. In: Proceedings of the 21st ACM SIGGRAPH/EUROGRAPHICS Symposium on Graphics Hardware. ACM; New York, NY, pp 87–94.

  • Tausworthe R (1965). Random numbers generated by linear recurrence modulo two. Mathematics of Computation 19 (90): 201–209.

    Article  Google Scholar 

  • Traore M and Hill D (2001). The use of random number generation for stochastic distributed simulation: Application to ecological modeling. In: Proceedings of 13th SCS-European Simulation Symposium, SCS; Marseille, France, pp 555–559.

    Google Scholar 

  • Wu P and Huang K (2006). Parallel use of multiplicative congruential random number generators. Computer Physics Communications 175 (1): 25–29.

    Article  Google Scholar 

  • Zhmurov A, Rybnikov K, Kholodov Y and Barsegov V (2010). Efficient pseudo-random number generators for biomolecular simulations on graphics processors Technical Report, CERN.

Download references

Author information

Authors and Affiliations

  1. Clermont Université, Clermont-Ferrand, France

    J Passerat-Palmbach, C Mazel & D R C Hill

  2. Université Blaise Pascal, Aubiere, France

    J Passerat-Palmbach, C Mazel & D R C Hill

  3. ISIMA, Institut Supérieur d’Informatique, de Modélisation et de leurs Applications, Aubiere, France

    J Passerat-Palmbach, C Mazel & D R C Hill

Authors
  1. J Passerat-Palmbach
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. C Mazel
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. D R C Hill
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to J Passerat-Palmbach.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Passerat-Palmbach, J., Mazel, C. & Hill, D. Pseudo-random streams for distributed and parallel stochastic simulations on GP-GPU. J Simulation 6, 141–151 (2012). https://doi.org/10.1057/jos.2012.8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/jos.2012.8

Keywords

Search

Navigation