Multiple Stream Generator#
It is often advantageous to be able to generate variates from multiple, independent, streams. For example, when running a simulation in parallela on several processors.
There are four ways of generating multiple streams using the routines available in AOCL-RNG library:
Different Seeds Method#
A different sequence of variates can be generated from the same base generator by initializing the generator using a different set of seeds. Among four listed methods for creating multiple streams, this is the least satisfactory because the statistical properties of the base generators are only guaranteed within sequences, not between sequences. For example, sequences generated from different starting points may overlap if the initial values are not far enough apart. The potential for overlapping sequences is reduced if the period of the generator being used is large. Although there is no guarantee of the independence of the sequences, due to its extremely large period, using the Mersenne Twister and SFMT with random starting values is unlikely to lead to problems, especially if the number of sequences required is small. This is the only way in which multiple sequences can be generated with AOCL-RNG library using the Mersenne Twister and SFMT as the base generator.
If the statistical properties of different sequences must be provable then one of the other methods should be adopted.
Different Generators Method#
Independent sequences of variates can be generated using different base generators for each sequence. For example, sequence 1 can be generated using the NAG basic generator, sequence 2 using the MRG32K3A generator, sequence 3 using the Mersenne Twister generator. The Wichmann-Hill generator implemented in the library is in fact a series of 273 independent generators. The particular sub-generator being used can be selected using the SUBID variable under initialization functions. Therefore, in total, 278 independent streams can be generated with each using an independent generator (273 Wichmann-Hill generators, and 5 additional base generators).
Skip-Ahead Method#
This is also known as Block-splitting method. Independent sequences of variates can be generated from a single base generator through the use of skipping-ahead or block-splitting. This method consists of splitting the sequence into k non-overlapping blocks, each of length n, where n is larger than the maximum number of variates required from any of the sequences. For example:
where \(x_1, x_2\), is the sequence produced by the generator of interest. Each of the k blocks provide an independent sequence.
The skipping-ahead algorithm therefore requires the sequence to be advanced a large number of places. Due to their form this can be done efficiently for LCG and MCG. AOCL-RNG library provides skipping-ahead for the NAG Basic generator, the Wichmann-Hill generators and MRG32K3A generator.
C Generate 3 * 100 values from the Uniform distribution
C Multiple streams generated using the Skip Ahead method
INTEGER LSTATE,N
PARAMETER (LSTATE=16,N=100)
INTEGER I,INFO,NSKIP
INTEGER SEED(1),STATE1(LSTATE),STATE2(LSTATE),STATE3(LSTATE)
DOUBLE PRECISION X1(N),X2(N),X3(N)
DOUBLE PRECISION A,B
C Set the seed
SEED(1) = 1234
C Set the distributional parameters
A = 0.0D0
B = 1.0D0
C Initialize the STATE1 vector
CALL DRANDINITIALIZE(1,1,SEED,1,STATE1,LSTATE,INFO)
C Copy the STATE1 vector into other state vectors
DO 20 I = 1,LSTATE
STATE2(I) = STATE1(I)
STATE3(I) = STATE1(I)
20 CONTINUE
C Calculate how many places we want to skip, this
C should be >> than the number of variates we
C wish to generate from each stream
NSKIP = N * N
C Advance each stream, first does not need changing
CALL DRANDSKIPAHEAD(NSKIP,STATE2,INFO)
CALL DRANDSKIPAHEAD(2*NSKIP,STATE3,INFO)
C Generate 3 sets of N variates from the Univariate distribution
CALL DRANDUNIFORM(N,A,B,STATE1,X1,LDX,INFO)
CALL DRANDUNIFORM(N,A,B,STATE2,X2,LDX,INFO)
CALL DRANDUNIFORM(N,A,B,STATE3,X3,LDX,INFO)
C Print the results
DO 40 I = 1,N
WRITE(6,*) X1(I),X2(I),X3(I)
40 CONTINUE
Leap-Frog Method#
Independent sequences of variates can be generated from a single base generator through the use of leap-frogging. This method involves splitting the sequence from a single generator into k disjoint subsequences. For example:
each subsequence provides an independent stream.
The leap-frog algorithm therefore requires the generation of every kth variate of a sequence. Due to their form this can be done efficiently for LCG and MCG. The library provides leap-frogging for the NAG Basic generator, the Wichmann-Hill generators and MRG32K3A generator.
C Generate 3 * 100 values from the Uniform distribution
C Multiple streams generated using the Leap Frog method
INTEGER LSTATE,N
PARAMETER (LSTATE=16,N=100)
INTEGER I,INFO
INTEGER SEED(1),STATE1(LSTATE),STATE2(LSTATE),STATE3(LSTATE)
DOUBLE PRECISION X1(N),X2(N),X3(N)
DOUBLE PRECISION A,B
C Set the seed
SEED(1) = 1234
C Set the distributional parameters
A = 0.0D0
B = 1.0D0
C Initialize the STATE1 vector
CALL DRANDINITIALIZE(1,1,SEED,1,STATE1,LSTATE,INFO)
C Copy the STATE1 vector into other state vectors
DO 20 I = 1,LSTATE
STATE2(I) = STATE1(I)
STATE3(I) = STATE1(I)
20 CONTINUE
C Update each stream so they generate every 3rd value
CALL DRANDLEAPFROG(3,1,STATE1,INFO)
CALL DRANDLEAPFROG(3,2,STATE2,INFO)
CALL DRANDLEAPFROG(3,3,STATE3,INFO)
C Generate 3 sets of N variates from the Univariate distribution
CALL DRANDUNIFORM(N,A,B,STATE1,X1,LDX,INFO)
CALL DRANDUNIFORM(N,A,B,STATE2,X2,LDX,INFO)
CALL DRANDUNIFORM(N,A,B,STATE3,X3,LDX,INFO)
C Print the results
DO 40 I = 1,N
WRITE(6,*) X1(I),X2(I),X3(I)
40 CONTINUE
Comparative Analysis
Different Seeds Method should be avoided in most of the cases.
Different Generators Method is only really of any practical use when using Wichmann-Hill Generator, and is then still limited to 273 streams.
Both Skipping-ahead and Leap-frogging work using the sequence from a single generator and both guarantee that the different sequences will not overlap and both can be scaled to an arbitrary number of streams.
Leap-frogging requires no
a-prioriknowledge about the number of variates being generated, whereas skip-ahead requires the user to know the maximum number (approximately) of variates required from each stream.Skipping-ahead requires no
a-prioriinformation on the number of streams required. In contrast leap-frogging requires the user to know the maximum number of streams required, prior to generating the first value.It is known that, dependent on the number of streams required, leap-frogging can lead to sequences with poor statistical properties, especially when applied to LCG.
For more complicated generators like MRG32K3A, leap-frogging can increase the time required to generate each variate compared to skipping-ahead. The additional time required by skipping-ahead occurs at the initialization stage, and not at the variate generation stage. Therefore in most instances skipping-ahead would be the preferred method for generating multiple sequences.
A LCG has the form \(x_{i+1}\ =\ a_1 x_i\ mod\ m1\). The recursive nature of a LCG means that
\[\begin{split}\begin{align} x_{i+v}& = a_1 x_{i+v−1}\ mod\ m_1 \\ & = a_1(a_1 x_{i+v−2}\ mod\ m1)\ mod\ m_1 \\ & = a_2 x_{i+v−2}\ mod\ m_1 \\ & = a_1^v x_i\ mod\ m_1 \\ \end{align}\end{split}\]The sequence can be quickly advanced v places by multiplying the current state \((x_i)\) by \(a_1^v\ mod\ m_1\), hence allowing skipping-ahead. Leap-frogging is implemented by using \(a_k\), where k is the number of streams required, in place of \(a_1\) in the standard LCG recursive formula.
In a LCG the multiplier \(a_1\) is constructed so that the generator has good statistical properties in, for example, the spectral test. When using leap-frogging to construct multiple streams this multiplier is replaced with \(a_k\), and there is no guarantee that this new multiplier will have suitable properties especially as the value of k depends on the number of streams required and so is likely to change depending on the application. This problem can be emphasized by the lattice structure of LCGs.
Note that, due to rounding, a sequence generated using leap-frogging and a sequence constructed by taking every kth value from a set of variates generated without leap-frogging may differ slightly. These differences should only affect the least significant digit.