User's Guide:Details:Creating New SPRNG Generators

Next:Testing Previous:Message Passing

Creating New Generators in SPRNG Format

We have made it easy for developers to create new parallel random number generators in SPRNG format. The developer just needs to make a copy of the file .template.c in the sprng/SRC directory and modify the functions init_rng and get_rng_dbl which initialize a random number stream and return a double precision random number respectively. All other features of SPRNG are automatically implemented.

SPRNG Scheme
We shall first explain the philosophy behind the SPRNG parallelization scheme which should enable others to develop generators along the same lines.
SPRNG generators maintain a set of independent streams. Each stream is identified by a unique integer in [0,MAX_STREAMS) where MAX_STREAMS is the number of independent streams available. When a user performs an initialization, one of these streams is returned. Typically on each process the user will initialize a stream identified by the same number as the process rank.
The user also specifies a seed during initialization. The initialization routine should return different sequences for different seeds. This may be done in various ways. For instance, the same stream could be returned but with a different starting state. Alternatively, the developer can shuffle the set of streams in different ways depending on the seed, so that the same stream is identified by different integers with different seeds.
The user also specifies a "parameter". Generators can normally be used used with different sets of parameters. For example, the multiplier is a parameter for the 48 bit Linear Congruential Generator with prime addend, while the lags are parameters for the modified Lagged Fibonacci Generator. The developer must prepare a list of NPARAMS parameter sets that are known to produce highly random streams. Each of these is identified with an integer in [0,NPARAMS). The user will request an initialization with a parameter specified by a number. The parameter set corresponding to that number must be then used. In order to help the user remember the parameter better, we have define macros that give a name to each parameter. For example, SPRNG_DEFAULT is defined to be 0. So if users ask for the SPRNG_DEFAULT parameter, then they will get a stream initialized with the first parameter in the list, such as the multiplier 0x2875a2e7b175 for the 48 bit Linear Congruential Generator.

Modifying the template
We explain below the changes that need to be made to the file .template.c in the sprng/SRC directory in order to create a new generator. We shall also give an example of the 64 bit Linear Congruential Generator with prime addend. This example is written for a 64 bit machine in order to simplify the presentation. The actual SPRNG generator differs due to optimizations, and also because it is generalized to cover 32 bit systems too. The locations where changes need to be made to .template.c are indicated by comments starting with /*** in order to make it easy for the developer to perform a search.
Preliminary steps:
Define a string indicating the generator type. This string will be used while printing out the information about the random number streams.
Example 1:
 
 
#define GENTYPE "64 Bit Linear Congruential Generator" 
 
Define the number of valid parameters.
Example 1:
 
 
#define NPARAMS 3		/*** number of valid parameters ***/ 
 
Define the number of independent streams. If users try to use more than these streams, then they will get warning messages stating that the independence of streams is not guaranteed.
Example 1:
 
 
int MAX_STREAMS = (1<<19);  /*** Maximum number of independent streams ***/ 
 
Modify the structure rngen. Such a structure is associated with each stream initialized. This structure maintains information about the state of the stream and also other information needed for spawning new streams. Developers should not change anything above the line that states: /*** declare other variables here ***/ before they understand the purpose of these variables. While the data structure itself should be modified in the preliminary stages, the assignment of values to these variables will be done during the initialization. We however mention some aspects of these assignments at this stage itself since it is difficult to explain the purpose of the variables without actually mentioning what kinds of values they will contain.
Each random number stream needs to store its state in scalar variables or arrays. Developers should declare their scalar variables below the line that states/*** declare other variables here ***/.
Example 1:
 
 
struct rngen 
{ 
  char *gentype; 
  int stream_number; 
  int nstreams; 
  int init_seed; 
  int parameter; 
  int narrays; 
  int *array_sizes; 
  int **arrays; 
  int spawn_offset; 
  /*** declare other variables here ***/ 
  unsigned long multiplier; 
  unsigned long prime; 
  unsigned long state; 
}; 
 
Certain generators such as the lagged Fibonacci Generator require arrays to store their information. In that case developers can make use of the variables narrays, array_sizes, and arrays. narrays is the number of arrays that are required. Often this will be just 1. If no array is required then this will be 0. array_sizes lists the size of each array. For example, if we have two arrays with the first one consisting of 24 integers and the second one consisting of 17 integers, then narrays = 2, array_sizes[0] = 24, array_sizes[1] = 17. arrays is a pointer to the actual set of arrays. arrays[0] in our example is an array of 24 integers and arrays[1] is of 17 integers. Developers are not restricted to using integer types. For example, if they wish to use a double precision type with 13 elements, then they can declare a variable:
double *r
and set the corresponding array_size[i] to 13*sizeof(double)/sizeof(int) in the initialization routine. Then in that routine they can set r = (double *) arrays[i]. While this may not be great from a software engineering point of view, we feel that people in scientific computing are used to even worse practises!
Next the developer has to modify the functions that perform the initialization and produce the actual random number.
init_rng: This function follows the specifications for init_sprng. We have written code that allocates all the memory required. The developer still has to write code to initialize some of the data, though. This function returns a pointer to the memory location where the data concerning the newly initialized stream is located. Though the data structure is of type rngen, we convert the pointer to a pointer to an int when we return it. The developer has to perform the following actions:
Specify the number of arrays as explained earlier.
Example 1:
 
 
  genptr->narrays = 0;		/* number of arrays needed by your generator */ 
 
Specify the sizes of the arrays as explained earlier.
Example (not for the Linear Congruential Generator):
 
 
  		/* initialize ...array_sizes to the sizes of the arrays */ 
array_sizes[0] = 24; 
array_sizes[1] = 17; 
 
Initialize the data in the arrays arrays[1], ..., arrays[narrays-1] and in the scalar variables based on the requirements of your generator. The initial values will typically depend on the argument gennum.
Example 1:
 
 
  genptr->multiplier = PARAMLIST[param]; 
  genptr->prime = get_prime(gennum); 
  genptr->state = 0xffffffffffffffff^(((unsigned long) seed<<33)|gennum); 
 
where get_prime(i) is a function that returns the i th prime, and PARAMLIST is an array of multipliers defined as follows:
 
 
unsigned long PARAMLIST[NPARAMS] = {5015080152056721395UL, 2447899643824353475UL, 
				  10678851390245329133UL}; 
 
get_rng_dbl: The argument to this function is a pointer to the data structure that stores the information concerning a random number stream. This function returns a random double precision number in (0,1).
Example 1: We first multiply the current state by the multiplier and add the addend to get the new state. We then multiply this by 2^-64 to get the desired random number:
 
 
/* Returns a double precision random number */ 
 
double get_rn_dbl(int *igenptr) 
{ 
    struct rngen *genptr = (struct rngen *) igenptr; 
 
    genptr->state = genptr->state*genptr->multiplier + genptr->prime; 
			  /* modulo 64 is automatic in 64 bit arithmetic */ 
    return genptr->state*FLT_MULT;			 
}  
 
where we had defined the macro FLT_MULT to be 2^-64 earlier:
 
 
#define FLT_MULT 5.4210108624275222e-20 /* 2^(-64) */ 
 
Further Optimization
If developers want faster implementations of the functions that return random integers and random single precision numbers, then they can modify get_rn_int and get_rn_flt respectively.
Developers may also wish to modify print_rng if they wish to print more information than we have provided.