1. Introduction:
SPRNG is a set of libraries for scalable and transferrable pseudo random number generation, and has been developed keeping in mind the requirements of users like us involved in parallel Monte Carlo simulations
We know that Monte Carlo Calculations consume a large fraction of all supercomputing cycles. The accuracy of these computations is critically influenced by the quality of the random number generators used. While the issue of random number generation in sequential calculations has been studied, even though on less powerful computers, there has been comparatively less work done in the context of parallel Monte Carlo applications. SPRNG seeks to fill this gap by implementing parallel random number generators that satisfy the requirements given below.
Users like us generally desire the following from any parallel random number generator:
Quality: Provide “high quality” pseudo random number in a computationally inexpensive and scalable manner.
Reproducibility: Provide totally reproducible streams of parallel pseudo random numbers, independent of the number of processors used in the computation and of the loading produced by sharing of the parallel computer.
Locality: Allowing for the creation of unique pseudo random number streams on a parallel machine with minimal inter-processor communication.
Portability: Should be portable between serial and parallel platforms and must be available on the most commonly used workstations and supercomputers.
SPRNG authors, intended to provide pseudo random number generators that satisfy the above requirements.
2. Literature Review:
The ability to generate satisfactory sequences of random numbers is one of the key links between Computer Science and Statistics. Most computer systems have random number generators available, and for most purposes they work well. But many of the standard random number generators (RNGs) are not good enough for increasingly sophisticated Monte Carlo uses, such as geometric probability, estimating distributed functions.
There are many pseudo random number generators exists. One among them is Parallel pseudo random number generation. These methods are based on Parameterization of the generators.
2.1 Linear Congruential Generator: It is mostly commonly used pseudo random generator. These generators use a linear transformation on the ring of residues of some modules m, to produce a sequence of integers.
Xn = a*Xn-1 + b mod m
There are the most widely used RNGs and they work remarkably well for most general purposes. But for some purposes they are not satisfactory; points in n-space produced by Congruential RNG’s fall on a lattice with huge unit cell volume.
Prime Modulus: Parameterization when ‘m’ prime. First we need to determine the family of a’s then obtain the maximal period (m-1)
If given permittivity, α=ai (mod m)
Single reference, Primitive element'a' & explicit enumeration of the relative prime to m-1 produces jth primitive element:
PROBLEMS:
Overall efficiency – Where to minimize the cost of computing Lj or to minimize the cost of modular multiplication modulo ‘m’?
2.2 Lagged-Fibonacci Generators:
Additive lagged-Fibonacci generators can be parameterized through its initial valu It is the most popular generator for serial as well as scalable machines. These generators with j=5, K=17 and m=32 was the standard PRNGs.
These are popular for many reasons:
1. Easy to implement.
2. Cheap to compute
3. It does well on statistical tests
Pros and Cons: It is optimal unfortunately there is no proof for this result and improvement of this analytical is open challenge?
But, this is good for Floating point numbers which avoids the constant conversion from integer to float. However, care must be taken to maintain the uniqueness of the parallel streams.
3. Analysis of the current techniques:
These authors have developed a library [SPRNG] of parallel random number generators for Scalable Parallel Random Number Generators; the library collects the top five RNGs into single, easy-to-use package that runs on almost any computing architecture. Because of extensibility of library, researchers won’t have to start from the scratch. Also, one can take the advantages of the high quality random number generators available within this library. Before the existing of SPRNG the RNGs were not only difficult to find but also many were not performing up to the standard necessary with more powerful computers. But these authors solved these problems with SPRNG.
But, one still need to test these generators with their own application. Even in this case SPRNG made it easier. These authors modified the generators in SPRNG to run on almost any parallel computing architecture. The program that written is almost compatible in FORTRAN, C and Java Because of which we can easily change among the generators in the library with a change at Run time.
Since, SPRNG uses entire families of RNGs; the code written for single processors can run in parallel i.e., on several processors at a time.
4. Opinion:
The SPRNG library has many generators available so far today and in the future I wish this library to add generators like WELL and Mersenne Twister generator since these are currently considered the best random number generator today. Also, the SPRNG library currently implemented in C++ and uses the FORTRAN 77 interfaces. As we know the growth and popularity of Java, its good idea to replace there interfaces from low level language like FORTRAN to Java.
We know that, quasirandom numbers are uniform in distribution and are effective at error reduction on Monte Carlo application like Numerical integration. The SPRNG should be designed such that library provides model for quasirandom numbers for parallel and distributed systems.
Moreover, this library is focused on systems like scalable and distributed but nowhere cryptographic systems. As we know that the generation of random numbers is critical to cryptographic systems. Symmetric cyphers such as DES [Data Encryption Standards], RC2 and RC5 all requires a randomly selected encryption key. Also, public-key algorithms like RSA, DSA and Diffie-Hellman begin with randomly generated values when generating prime numbers.
At a higher level, SSL and other cryptographic protocols use random challenges in the authentication process to stop replay attacks. This poses a challenge for software developers like we implementing cryptography.
A new kind of generator should be implemented such that it modifies the approach of construction and utilization of pseudo-random number generators. Since, attacks like brute-force may cause because of its fixed seed size i.e., 192 bits
5. Results:
Usage of Library:
#include <cstdio
#define SIMPLE_SPRNG /* simple interface */
#include "sprng.h" /* SPRNG header file */
using namespace std;
int main(){
double rn; int i;
printf(" Printing 3 random numbers in [0,1):\n");
for (i=0;i<3;i++) {
rn = sprng(); /* generate double precision random number */
printf("%f\n",rn);
} return 0;}
$> ./simple-simple Spri
Printing 3 random numbers in [0,1):
0.014267
0.749392
0.007316
Statistical Test: The SPRNG test suites consists the entire test described by the Knuth. These tests are modified such that these test to test for parallel correlation.
Ex: eqi-distance.lcg 4 2 0 03 1 2 1 00
Mprirun –np 2 equidistance.lcg 4 2 0 0 3 1 2 1 00
This performs equidistance test with 48 bit Linear Congruential generator
Result: KS value: 0.601252 KS value prob: 17.50
Hence, It’s b/w 2.5% and 97.5% It is passed.
6. CONCLUSION: This paper is all about pseudo random number generation through parameterization. The described library is based on this parameterization PRNGs. In detail they have described about test suites – physical as well statistical. The authors has taken care more in constructing generators and are based on recursions, which are so simple. Also, they designed the library such that one can implement their own generators by providing rapid prototyping tools. As well, parallel and serial tests of randomness which make there SPRNG library unique among tools for Monte Carlo.