Independent Streams. Leapfrogging and Block-Splitting

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:

  1. 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).

  2. Block-splitting. Split the original sequence into k non-overlapping blocks, where k is the number of independent streams. Each of the streams generates random numbers only from the corresponding block. This method is known as block-splitting or skipping-ahead.

  3. Leapfrogging. Split the original sequence into k disjoint subsequences, where k is the number of independent streams, in such a way that the first stream would generate the random numbers x1, xk+1, x2k+1, x3k+1, ..., the second stream would generate the random numbers x2, xk+2, x2k+2, x3k+2, ..., and, finally, the k-th stream would generate the random numbers xk, x2k, x3k, ... However, multidimensional uniformity properties of each subsequence deteriorate seriously as k grows. The method is useful if k is 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 skip-ahead (block-split) methods are considered below in more detail.

Block-Splitting Method

VS implements block-splitting through function vslSkipAheadStream:

vslSkipAheadStream( stream, nskip )

The function changes the current state of the stream stream so that with the further call of the generator the output subsequence begins with the element xnskip rather than with the current element x0. 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<nstreams-1; 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 xk, xk+nstreams, xk+2nstreams, ... rather than the output sequence x0, x1, x2, ... . 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 );
}

Note

Block-splitting 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

Block-Splitting

MCG31m1

Supported

Supported

R250

-

-

MRG32k3a

-

Supported

MCG59

Supported

Supported

WH

Supported

Supported

MT19937

-

Supported

SFMT19937

-

Supported

MT2203

-

-

SOBOL

Supported to pick out individual components of quasi-random vectors

Supported

NIEDERREITER

Supported to pick out individual components of quasi-random vectors

Supported

PHILOX4X32X10

-

Supported

ARS5

-

Supported

ABSTRACT

-

-

NON-DETERMINISTIC

-

-

BRNG

Leapfrog

Block-Splitting

MCG31m1

Supported

Supported

R250

-

-

MRG32k3a

-

Supported

MCG59

Supported

Supported

WH

Supported

Supported

MT19937

-

Supported

SFMT19937

-

Supported

MT2203

-

-

SOBOL

Supported to pick out individual components of quasi-random vectors

Supported

NIEDERREITER

Supported to pick out individual components of quasi-random vectors

Supported

PHILOX4X32X10

-

Supported

ARS5

-

Supported

ABSTRACT

-

-

NON-DETERMINISTIC

-

-

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 );
}
...
For more complete information about compiler optimizations, see our Optimization Notice.
Select sticky button color: 
Orange (only for download buttons)