3.1 A new random number generator for Parallel and Distributed systems¶
Pseudo Random Number Generators, or PRNGs, are used in many different types of applications. Scientific applications that simulate a particular phenomena make use of PRNGs extensively. These types of applications often require PDC techniques to get the performance they need to run large simulations.
In this chapter we are going to justify the need for using correct random number generators that work in parallel code using either shared memory threads with openMP or processes with MPI. Then we will demonstrate one particular library that correctly generates a proper distribution of random numbers for code using either of these software libraries.
Properties of Pseudo Random Number Generators¶
How to use mathematics to generate a stream of random numbers has been studied extensively for quite some time, longer for the sequential single thread/processor case (since 1969) than for various PDC hardware and software libraries (as early as 1986). The mathematics involved in properly generating a stream of numbers from a given starting point called a seed are beyond the scope of this chapter. We will instead focus on the properties that these well-studied methods should possess.
For computational purposes, PRNGs create one random value at a time when requested. The entire set of numbers generated (in a for loop, for example) is often referred to as the stream of numbers.
A good sequential or parallel PRNG method must have these properties:
Uniformity: The numbers generated through the range of values requested are uniform.
Independence: Any value drawn next is independent of the previous value.
Efficiency: The generation of the next number should be fast.
Long Cycle length: For a large stream in a wide range, it should take a long time before numbers repeat.
Reproducibility: From a given starting seed, the same set, or stream of numbers should be generated. This property is helpful for debugging, but constant seed values should not be used in applications.
Really good parallel PRNGs require all of these properties, along with the following:
Fair Play: Regardless of the number of threads/processes (processing units, or PUs), the same set of values is generated as in the stream generated by a sequential algorithm with the same starting seed.
In this chapter we will use a freely available C++ PRNG library called trng (for Tina’s random number generator). The site for this library contains extensive documentation and additional code examples if you would like to delve deeper. The trng library, as you will discover, possesses the above properties.
Note
The code in the following sections is C++ code. Even if you have mainly coded in C, these examples are fairly straightforward and accessible, since they are written in C style for the most part.