Notes for Intel® oneAPI Math Kernel Library Vector Statistics

Download PDF
ID 772987
Date 12/04/2020
Public
Document Table of Contents
Document Table of Contents x
Notes for Intel® oneAPI Math Kernel Library Vector Statistics
Notes for Intel® oneAPI Math Kernel Library Vector Statistics x
Introduction Randomness and Scientific Experiment Random Numbers Figures of Merit for Random Number Generators Vector Statistics Structure Testing of Basic Random Number Generators Testing of Distribution Random Number Generators Bibliography Notices and Disclaimers
Introduction x
What's New About Vector Statistics About This Document Conventions
Figures of Merit for Random Number Generators x
Uniform Probability Distribution and Basic Pseudo- and Quasi-Random Number Generators Figures of Merit for General (Non-Uniform) Distribution Generators
Vector Statistics Structure x
Why Vector Type Generators? Basic Random Number Generators Random Streams and RNGs in Parallel Computation Generating Methods for Random Numbers of Non-Uniform Distribution Accurate and Fast Modes of Random Number Generation Example of VS Use
Random Streams and RNGs in Parallel Computation x
Initializing a BRNG Creating and Initializing Random Streams Creating Random Stream Copy and Copying Stream State Saving and Restoring Random Streams Independent Streams. Block-Splitting and Leapfrogging Block-Splitting Method Option 1 Option 2 Leapfrog Method Abstract Basic Random Number Generators. Abstract Streams
Generating Methods for Random Numbers of Non-Uniform Distribution x
Inverse Transformation Acceptance/Rejection Mixture of Distributions Special Properties
Testing of Basic Random Number Generators x
BRNG Implementations and Categories Interpreting Test Results BRNG Test Descriptions BRNG Properties and Testing Results
Interpreting Test Results x
One-Level (Threshold) Testing Two-Level Testing
BRNG Test Descriptions x
3D Spheres Test Birthday Spacing Test Bitstream Test Rank of 31x31 Binary Matrices Test Rank of 32x32 Binary Matrices Test Rank of 6x8 Binary Matrices Test Count-the-1's Test (Stream of Bits) Count-the-1's Test (Stream of Specific Bytes) Craps Test Parking Lot Test Self-Avoiding Random Walk Test Template Test
BRNG Properties and Testing Results x
MCG31m1 R250 MRG32k3a MCG59 WH MT19937 SFMT19937 MT2203 SOBOL NIEDERREITER Philox4x32-10 ARS5
Testing of Distribution Random Number Generators x
Interpreting Test Results Description of Distribution Generator Tests Continuous Distribution Random Number Generators Discrete Distribution Random Number Generators
Description of Distribution Generator Tests x
Confidence Test Distribution Moments Test Chi-Squared Goodness-of-Fit Test Performance
Continuous Distribution Random Number Generators x
Uniform (VSL_RNG_METHOD_UNIFORM_STD/VSL_RNG_METHOD_UNIFORM_STD_ACCURATE) Gaussian (VSL_RNG_METHOD_GAUSSIAN_BOXMULLER) Gaussian (VSL_RNG_METHOD_GAUSSIAN_BOXMULLER2) Gaussian (VSL_RNG_METHOD_GAUSSIAN_ICDF) GaussianMV (VSL_RNG_METHOD_GAUSSIANMV_BOXMULLER) GaussianMV (VSL_RNG_METHOD_GAUSSIANMV_BOXMULLER2) GaussianMV  (VSL_RNG_METHOD_GAUSSIANMV_ICDF) Exponential (VSL_RNG_METHOD_EXPONENTIAL_ICDF/VSL_RNG_METHOD_EXPONENTIAL_ICDF_ACCURATE) Laplace (VSL_RNG_METHOD_LAPLACE_ICDF) Weibull (VSL_RNG_METHOD_WEIBULL_ICDF/ VSL_RNG_METHOD_WEIBULL_ICDF_ACCURATE) Cauchy (VSL_RNG_METHOD_CAUCHY_ICDF) Rayleigh (VSL_RNG_METHOD_RAYLEIGH_ICDF/ VSL_RNG_METHOD_RAYLEIGH_ICDF_ACCURATE) Lognormal (VSL_RNG_METHOD_LOGNORMAL_ BOXMULLER2/VSL_RNG_METHOD_LOGNORMAL_BOXMULLER2_ACCURATE) Lognormal (VSL_RNG_METHOD_LOGNORMAL_ICDF/VSL_RNG_METHOD_LOGNORMAL_ICDF_ACCURATE) Gumbel (VSL_RNG_METHOD_GUMBEL_ICDF) Gamma (VSL_RNG_METHOD_GAMMA_GNORM/ VSL_RNG_METHOD_GAMMA_GNORM_ACCURATE) Beta (VSL_RNG_METHOD_BETA_CJA/ VSL_RNG_METHOD_BETA_CJA_ACCURATE) ChiSquare (VSL_RNG_METHOD_CHISQUARE_CHI2GAMMA)
Discrete Distribution Random Number Generators x
Uniform (VSL_RNG_METHOD_UNIFORM_STD) UniformBits (VSL_RNG_METHOD_UNIFORMBITS_STD) UniformBits32 (VSL_RNG_METHOD_UNIFORMBITS32_STD) UniformBits64 (VSL_RNG_METHOD_UNIFORMBITS64_STD) Bernoulli (VSL_RNG_METHOD_BERNOULLI_ICDF) Geometric (VSL_RNG_METHOD_GEOMETRIC_ICDF) Binomial (VSL_RNG_METHOD_BINOMIAL_BTPE) Hypergeometric (VSL_RNG_METHOD_HYPERGEOMETRIC_H2PE) Poisson (VSL_RNG_METHOD_POISSON_PTPE) Poisson (VSL_RNG_METHOD_POISSON_POISNORM) PoissonV (VSL_RNG_METHOD_POISSONV_POISNORM) NegBinomial (VSL_RNG_METHOD_NEGBINOMIAL_NBAR) Multinomial (VSL_RNG_METHOD_MULTINOMIAL_MULTPOISSON)
Notes for Intel® oneAPI Math Kernel Library Vector Statistics

Independent Streams. Block-Splitting 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:

  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 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 xnskip rather than with the current element x0.

Function vslSkipAheadStream supports number of skipped elements up to 263.

Function vslSkipAheadStreamEx extends it by providing support for number of skipped elements greater than 263.

Before calling this function, you should represent the number of skipped elements in the following format:

For example, if you want to skip 2128 elements you should represent them as follows:

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 263.

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

(vslSkipAheadStream)

Block-Splitting

(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 quasi-random vectors Supported -
NIEDERREITER Supported to pick out individual components of quasi-random vectors Supported -
PHILOX4X32X10 - Supported Supported
ARS5 - Supported 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 );
}
...
Parent topic: Random Streams and RNGs in Parallel Computation
Level Two Title