Independent Streams. BlockSplitting and Leapfrogging
One of the basic requirements for random number streams is their mutual independence and lack of intercorrelation. Even if you want random number samplings to be correlated, such correlation should be controllable.
You can get independent streams using various methods. This document discusses the following methods supported by VS:
 Using different parameter sets. For each stream, you may use the same type of generators (for example, linear congruential generators), but choose their parameters in such a way as to produce independent random number sequences. For example, the Mersenne Twister generator has 6024 parameter sets, which ensure that the resulting subsequences are independent (see [Matsum2000] for details). Another example is WH generator that can create up to 273 random number streams. The produced sequences are independent according to the spectral test (see [Knuth81] for the spectral test details).
 Blocksplitting. Split the original sequence intoknonoverlapping blocks, wherekis the number of independent streams. Each of the streams generates random numbers only from the corresponding block. This method is known as blocksplitting or skippingahead.
 Leapfrogging. Split the original sequence intokdisjoint subsequences, wherekis the number of independent streams, in such a way that the first stream would generate the random numbersx_{1}, x_{k +1},x_{2k+1},x_{3k+1}, ..., the second stream would generate the random numbersx_{2},x_{k +2},x_{2k+2},x_{3k+2}, ..., and, finally, the kth stream would generate the random numbersx_{k},x_{2k},x_{3k}, ... However, multidimensional uniformity properties of each subsequence deteriorate seriously askgrows. The method is useful ifkis fairly small.
Karl Entacher presents data on inadequate subsequences produced by some commonly used linear congruential generators [Ent98].
VS permits you to use any of the above methods. Leapfrog and skipahead (blocksplit) methods are considered below in more detail.
BlockSplitting Method
VS implements blocksplitting through
vslSkipAheadStream
and
vslSkipAheadStreamEx
functions:
vslSkipAheadStream( stream, nskip )vslSkipAheadStreamEx( stream, n, nskip )
The functions change the current state of the stream
stream
so that with the further call of the generator the output subsequence begins with the element
x_{nskip}
rather than with the current element
x_{0}
.
Function
vslSkipAheadStream
supports number of skipped elements up to 2^{63}.
Function
vslSkipAheadStreamEx
extends it by providing support for number of skipped elements greater than 2^{63}.
Before calling this function, you should represent the number of skipped elements in the following format:
Number of skipped elements = nskip[0] + nskip[1] * 2^{64}+nskip[2] * 2^{128
}+ ... + nskip[n1] * 2^{64*(n1)} ,
For example, if you want to skip 2^{128} elements you should represent them as follows:
Number of skipped elements = 0 * 2^{0}* 2^{64
}+ 1 * 2^{128}
Then you should call the
vslSkipAheadStreamEx
function.
VSLStreamStatePtr stream; MKL_UINT64 nskip[3]; nskip[0]=0; nskip[1]=0; nskip[2]=1; vslNewStream( &stream, brng, seed ); vslSkipAheadStreamEx( stream, 3, nskip);
You can use either
vslSkipAheadStream
or
vslSkipAheadStreamEx
to skip numbers of elements smaller than 2^{63}.
Thus, if you wish to split the initial sequence into nstreams blocks of
nskip
size each, use the following sequence of operations:
Option 1
VSLStreamStatePtr stream[nstreams]; int k; for ( k=0; k<nstreams; k++ ) { vslNewStream( &stream[k], brng, seed ); vslSkipAheadStream( stream[k], nskip*k ); }
Option 2
VSLStreamStatePtr stream[nstreams]; int k; vslNewStream( &stream[0], brng, seed ); for ( k=0; k<nstreams1; k++ ) { vslCopyStream( &stream[k+1], stream[k] ); vslSkipAheadStream( stream[k+1], nskip ); }
Leapfrog Method
VS implements the leapfrog method through function
vslLeapfrogStream
:
vslLeapfrogStream( stream, k, nstreams )
The function changes the stream
stream
so that the further call of the generator generates the output subsequence
x_{k}, x_{k+nstreams}, x_{k+2nstreams}, ...
rather than the output sequence
x_{0}, x_{1}, x_{2}, ...
. Thus, if you wish to split the initial sequence into nstreams subsequences, the following sequence of operations should be implemented:
VSLStreamStatePtr stream[nstreams]; int k; for ( k=0; k<nstreams; k++ ) { vslNewStream( &stream[k], brng, seed ); vslLeapfrogStream( stream[k], k, nstreams ); }
Blocksplitting and leapfrog methods make programming with vector random number generators easier both in parallel applications and in sequential programs.
Not all VS BRNGs support both these methods of generating independent subsequences. The Leapfrog method is supported only when a BRNG provides a more efficient implementation than generation of the full sequence to pick out a required subsequence. The following table specifies the methods supported by different BRNGs:
BRNG
 Leapfrog
 BlockSplitting
( vslSkipAheadStream )
 BlockSplitting
( vslSkipAheadStreamEx )


MCG31m1
 Supported
 Supported
 

R250
 
 
 

MRG32k3a
 
 Supported
 Supported

MCG59
 Supported
 Supported
 

WH
 Supported
 Supported
 

MT19937
 
 Supported
 

SFMT19937
 
 Supported
 

MT2203
 
 
 

SOBOL
 Supported to pick out individual components of quasirandom vectors
 Supported
 

NIEDERREITER
 Supported to pick out individual components of quasirandom vectors
 Supported
 

PHILOX4X32X10
 
 Supported
 Supported

ARS5
 
 Supported
 Supported

ABSTRACT
 
 
 

NONDETERMINISTIC
 
 
 

To initialize
nstreams
independent streams for the MT2203 set of generators, you can use the following code sequence:
... #define nstreams 6024 ... VSLStreamStatePtr stream[nstreams]; int k; for ( k=0; k< nstreams; k++ ) { vslNewStream( &stream[k], VSL_BRNG_MT2203+k, seed ); } ...