RANDOM_MPI
Random Numbers using MPI

RANDOM_MPI is a C++ program which demonstrates one way to generate the same sequence of random numbers for both sequential execution and parallel execution under MPI.

A simpler approach to random numbers would simply let each processor choose a seed. Or the master processor could choose distinct seeds. However, this is not ideal since it will not match the sequential program and it does not avoid the possibility that two of the random sequences will quickly overlap because of a bad choice of seed.

Notice that if we have 10 processors available under MPI, we do not want each processor to generate the same random number sequence. Instead, we want each of the processors to generate a part of the sequence, so that all the parts together make up the same set of values that a sequential program would have computed.

We assume we are using a linear congruential random number generator or "LCRG", which takes an integer input and returns a new integer output:

U = ( A * V + B ) mod C

We do this by computing a new LCRG which can compute every P'th entry of the original one.

Our LCRG works with integers, but it is easy to turn each integer into a real number between [0,1].

The particular scheme for computing the parameters of the new LCRG is implemented in the UNIFORM library.

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Related Data and Programs:

ASA183 is a C++ library which implements the Wichman-Hill pseudorandom number generator.

HEAT_MPI is a C++ program which solves the 1D Time Dependent Heat Equation using MPI.

MPI is a directory of C++ examples which illustrate the use of the MPI application program interface for carrying out parallel computatioins in a distributed memory environment.

MPI_SYSX, a directory of example C++ programs which illustrate the use of PBS scripts for submitting MPI jobs on System X.

QUAD_MPI is a C++ program which approximates an integral using a quadrature rule, and carries out the computation in parallel using MPI.

RANDOM_MPI is available in a C version and a C++ version and a FORTRAN77 version and a FORTRAN90 version.

SATISFIABILITY_MPI is a C++ program which demonstrates, for a particular circuit, an exhaustive search for solutions of the circuit satisfiability problem, using MPI to carry out the calculation in parallel.

UNIFORM is a C++ library which computes elements of a uniform pseudorandom sequence.

Reference:

1. Peter Arbenz, Wesley Petersen,
   Introduction to Parallel Computing - A practical guide with examples in C,
   Oxford University Press,
   ISBN: 0-19-851576-6,
   LC: QA76.58.P47.
2. Stan Openshaw, Ian Turton,
   High Performance Computing and the Art of Parallel Programming: an Introduction for Geographers, Social Scientists, and Engineers,
   Routledge, 2000,
   ISBN: 0415156920.
3. Peter Pacheco,
   Parallel Programming with MPI,
   Morgan Kaufman, 1996,
   ISBN: 1558603395,
   LC: QA76.642.P3.
4. Michael Quinn,
   Parallel Programming in C with MPI and OpenMP,
   McGraw-Hill, 2004,
   ISBN13: 978-0071232654,
   LC: QA76.73.C15.Q55.

Source Code:

• random_mpi.C, the source code.

Examples and Tests:

RANDOM_MPI_SYSX is a test of the program using the MPI library on System X, using 4 processors.

• random_mpi_sysx.sh, BASH commands to compile, link and load the source code on System X.
• random_mpi_sysx_output.txt, the output file.

List of Routines:

• MAIN is the main program for RANDOM_MPI.
• CONGRUENCE solves a congruence of the form ( A * X = C ) mod B.
• I4_GCD finds the greatest common divisor of I and J.
• LCRG_ANBN computes the "N-th power" of a linear congruential generator.
• LCRG_EVALUATE evaluates an LCRG, y = ( A * x + B ) mod C.
• POWER_MOD computes ( A^N ) mod M.

You can go up one level to the C++ source codes.