User's Guide:Glossary

Next:References Previous:Test Suite


Explanation of Terms

Check-Pointing

Users may sometimes wish to save the states of random number streams into a file. This is typically done for the following two reasons:

  1. In case the system the user is working on is unreliable, the user may want to save the state of the calculations into a file, once in a while. If the system crashes, then the user can recover the state of the calculations from the file and continue from that point onwards, instead of repeating the entire calculations.

  2. Users may not wish to perform the entire calculations all at one time. This may either be because they are not sure if the calculations are worth continuing until they have obtained some intermediate results, or because system time is less expensive during certain times of the day. In the latter case they may perform the calculations every day during such cheaper periods.

In both the cases mentioned above, users will need to store the states of random number streams so that they can start from where they had left off the previous time. SPRNG provides a function that returns the state of a random number stream as an array of characters. Users can store this array into a file. They can later read the stored information back into a character array. SPRNG provides a function to obtain the saved state of the random number stream from this character array, thus enabling users to continue with their calculations.

Example

Header Files

The actual names of the SPRNG functions differ from those given in the SPRNG interface descriptions. We have defined certain macros in the files sprng.h and sprng_f.h. If the users include either of those files (the former file by C users and the latter by FORTRAN users) in their program, then the correct SPRNG function is automatically called.

Note to FORTRAN users on preprocessor directives: The header files contain preprocessing directives which most modern FORTRAN compilers are able to handle. These compilers typically require special flags and/or the filename to end in .F instead of .f in order to preprocess these directives. In case the latter case, users should copy files containing C preprocessor directives to a file with an extension of .F. The user's makefile may need to be changed to give instructions for handling these new files.

Those who are not familiar with the 'make' command can try adding the following lines to their makefile, instead of making any other change:

 
.SUFFIXES : .f .F 
 
.F.f :  
	@if [ -f $*.i ] ; then \ 
	rm $*.i ;\ 
	fi 
	$(CPP) -I$(SRCDIR) $*.F 
	@if [ -f $*.i ] ; then \ 
	mv $*.i  $*.f ;\ 
	fi 
Where $(CPP) is identical to that given in the sprng/SRC/make.PLAT file, where PLAT is the user's platform, and $(SRCDIR) is the SPRNG source directory. This same technique can be used in case the user's FORTRAN compiler does not call the preprocessor. This creates a regular FORTRAN file which the compiler can handle.

On the IBM SP2, please use the following code instead of that given above:

 
.SUFFIXES : .f .F 
 
.F.f:  
        $(CPP) -WF,-I$(SRCDIR) $*.F 
        @if [ -f F$*.f ] ; then \ 
        mv F$*.f  $*.f ;\ 
Including Header Files

A C user needs to include the header file sprng.h and a FORTRAN user sprng_f.h in order to use SPRNG. For example, FORTRAN users would type:

#include "sprng_f.h"

in their FORTRAN program files that make SPRNG calls. This statement causes the contents of the file sprng_f.h to appear instead of the statement #include "sprng_f.h" once the file has been preprocessed. This usage is demonstrated in the following examples:

C Example

FORTRAN users can also read the note on header files if they are not used to the C preprocessor.

Independence of Random Number Streams

Users will generally use several random number streams in their calculations. It is important for these streams to be uncorrelated, in order for the pseudorandom numbers to be effective at the desired variance reduction, which is, of course, the point of large Monte Carlo calculations. We refer to this property of streams being uncorrelated as the independence of streams. SPRNG provides random number streams that have been tested for their independence.

Initialization of Streams

We store the state of a random number stream in some memory location. Before we do this, it is necessary to allocate memory space. We then determine the initial state of the stream from the seed and other parameters of the generator. This process is known as initialization. Before a random number stream can be used, an initialization call has to be made. Usually the users need to call init_sprng to perform the initialization. The exceptions are (i) in the simple interface where default initialization is performed under certain conditions, (ii) when the unpack_sprng function is used that creates a stream with an appropriate state and (iii) when the user calls spawn_sprng, which performs the initialization itself.

Locality

By locality we mean that an operation performed on a stream should not involve communication between processors. For example, when we initialize or spawn streams, we need to ensure that the new streams produced are independent of the streams available on all other processors. SPRNG produces such independent streams without performing any communication with other processors. The only SPRNG function that could involve communication between processors is make_sprng_seed.

Macro Substitution

A SPRNG user may need to use preprocessing directives for macro substitution, which C users will be familiar with. A statement of the form:

#define macro replacement

replaces the text macro in the user's file with replacement. For example, the SPRNG header files define a macro:

#define SPRNG_DEFAULT 0

If users include a SPRNG header file and then type the word SPRNG_DEFAULT anywhere in their program, then this word is replaced by 0 once the program has been preprocessed. FORTRAN users can read more about the preprocessing directives in the note on this topic.

NULL Pointer

Certain SPRNG functions return a NULL pointer in case of error. FORTRAN users can consider a NULL pointer as the integer constant 0.

Portability

SPRNG is portable to a variety of serial and parallel platforms. Exactly the same sequence of random numbers are produced on all the machines. SPRNG also provides executables to check if the SPRNG libraries have ported correctly to the platform the user is working on. The section on installation contains further details on these executables.

Quality of Parallel Random Number Streams

Parallel random number streams must satisfy all the criteria for an acceptable serial random number stream. For example, they must be sufficiently uniform, have a large period and there should be no correlation between the numbers in the sequence. In addition, parallel streams should be uncorrelated with each other.

Random Number Streams

Given a random number generator and its initial state, each call to the generator produces the next random number in the sequence. We refer to each such sequence of random numbers as a random number stream.

Reproducibility

SPRNG can be used to produce a totally reproducible stream of parallel pseudorandom numbers, independent of the number of processors used in the computation and of the loading produced by sharing of the parallel computer. Such reproducibility is important during debugging and also in checking codes ported to new platforms.

Seed

We use the term seed with a slightly different meaning than is conventionally used. This term does not refer to the starting state of the random number stream. Rather, it is an encoding of the starting state. Distinct streams initialized with the same seed will have different starting states. This provides users the convenience of being able to use the same seed for distinct streams, and still obtaining different initial states.

There is a large set of possible starting states for each stream. We restrict the user to choosing from 231 of those. The user can specify a particular seed (which is an integer) based on which SPRNG determines a particular starting state for the stream. Seeds that are close to each other may produce very different starting states.

It is recommended that the user use the same seed while initializing all the streams in one particular computational run. In order to get a different sequence in a different run, the user can change this common seed.

Spawning Random Number Streams

Sometimes it is necessary to create new random number streams. This situation is best explained with the help of an example.

Consider the following Monte Carlo application in neutronics. Here independent neutron paths are generated based on the outcome of many probabilistic events. Statistics are collected along the paths and estimates for quantities of interest are computed. These estimates have a standard error that scales with the reciprocal of the square root of the number of "independent neutron paths". The computational catch is that during a flight a neutron may collide with a heavy nucleus thereby producing new neutrons. These new neutrons, along with their initial conditions, are put into a computational queue for later processing. An efficient parallel implementation demands that this queue be distributed. In order to ensure reproducibility, each neutron in the queue must also have information so that a unique and deterministic stream of pseudorandom numbers will be used regardless of which processor it eventually executes on. We also desire that the pseudorandom numbers streams that are allocated for each neutron be independent of the stream of any other neutron.

In order to satisfy the requirements of problems such as the one above, we provide a SPRNG function that spawns new, independent random number streams based on the information available from an existing stream. In the neutron collision problem above, new streams would be spawned for each neutron that results from the collision based on the stream of the original neutron that collided. SPRNG further guarantees that the streams produced are independent of any other stream that exists.

Standard Error

SPRNG error and warning messages are sent to the standard error. Users should note that redirecting the standard output to a file does not redirect the standard error too. The following example demonstrates how to redirect standard error to a file filename in the Bourne and Korn shells:

a.out 2> filename

where a.out is the user's executable. If the user wishes to redirect standard output and standard error to the same file, they can issue the following command:

a.out > filename 2>&1

The above can be accomplished in the C shell by the following command:

a.out >& filename

State of a stream

In order to generate random numbers from a stream, SPRNG needs to store information about that stream in memory. This can be considered the state of that stream. As we progress along the random number sequence, this state of the stream too keeps changing.

In the simplest case, we may just need to know the previous random number generated in order to produce the next. In this case, the state of the stream could be identical to the integer version of the random number generated. In order to produce a double precision number, we could divide the state by an appropriate value to get a floating point number in the range [0,1). In a more complicated case, for example with the 48 bit Linear Congruential Generator, the state consists of the multiplier, the prime addend and a 48 bit integer. We return the 31 high order bits as the integer random number. This example was given to demonstrate that the state of a stream is not always identical to the integer random number generated. The state of the Lagged Fibonacci Generator, for instance, requires far more memory and consists of several elements of the sequence.

It should be noted that the state of the stream changes in the same manner, irrespective of whether the integer or the double precision generator was called.

Stream ID

A single process may have several different random number streams available. These different streams are distinguished by unique ID's, which are implemented as pointers to memory locations where states of the respective streams are stored. Since standard FORTRAN 77 does not have a pointer type, we can store a pointer as an integer of the same size as a C pointer. We have defined a macro called SPRNG_POINTER in the file sprng_f.h that automatically defines an integer of the correct size on platforms on which SPRNG is supported. A FORTRAN programmer can then use the type SPRNG_POINTER just as if it were a FORTRAN data type. However, if the flag -DPOINTERSIZE was used in building SPRNG FORTRAN executables, then this flag should also be used in compiling the user's program for this feature to work correctly.