RANDOM_MPI
Random Numbers using MPI

RANDOM_MPI is a FORTRAN77 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.

Related Data and Programs:

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

MPI a directory of example FORTRAN77 programs which illustrate the use of MPI for doing parallel programming in a distributed memory environment, using message passing.

MPI_STUBS is a FORTRAN77 library which contains "stub" MPI routines, allowing a user to compile, load, and possibly run an MPI program on a serial machine.

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

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

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

SATISFIABILITY_MPI is a FORTRAN77 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 FORTRAN77 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.f, the source code.

Examples and Tests:

RANDOM_MPI_STUBS is a test of the program using the MPI_STUBS library. Here, the program will be running on a single processor (and with a "fake" version of MPI).

• random_mpi_stubs.csh, commands to compile, link and run the program.
• random_mpi_stubs_output.txt, the output file.

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 FORTRAN77 source codes.