Skip ahead in random streams using integers on a cluster.

Skip ahead in random streams using integers on a cluster.

Hi Everybody!

For the implementation of a Monte-Carlo simulation algorithm on a linux cluster we are using the Intel Math Kernel Library.

To obtain different and independent streams on the node of the cluster we use block-skipping or leap-frogging.

In total we need in the order of 10^10 random numbers. We are using the Whichmann-Hill (WH) and MRG32k3a random number generators which have period lengths of 2^80 and 2^191. The period length is therefore large enough.

Since we have in the order of 100 processors, we need to have a block skipping or leapfrogging size which is also in the order of 10^10.

Unsigned 32 bit integers can represent numbers up to ~4*10^9, signed 32bit integers up to half of this, ~2*10^9. The block skipping size is therefore out of reach for 32 bit integers.

The Math Kernel Library's vlsSkipAheadStream function takes a signed integer as input argument for the block skipping size. It is therefore not possible to access the large period lengths the random number generators offer on a parallel machine.

Was the MKL interface designed with this issue in mind? If so, what is the rationale behind it? If not, is this considered to be a bug?

Are there work-arounds other than using WH, which offers leap frogging?

Thank you for your help.

Regards,
Michael

MKL 8.0.1p6
Debian Linux 3.1

3 posts / 0 new
Last post
For more complete information about compiler optimizations, see our Optimization Notice.

Hello Michael

Thank you for your question. VSL supports parallel computations and provides number of methods to create independent random streams.The first one is to use the same type of basic generator and to choose its parameters which provide independence of the streams. The library contains MT2203 generator with allows creating up to 1024 random streams. The other example is the Wichmann-Hill generator which admits up to 273 independent random sequences. For example, initialization of 100 WH-based streams can be done in the following way:

#define nstreams 100

VSLStreamStatePtr stream[nstreams];
int k;
for ( k=0; k< nstreams; k++ )
{
vslNewStream( &stream[k], VSL_BRNG_WH+k, seed );
}

VSL also supports block methods for parallel computing, leap-frogging and skipping-ahead. First method splits original sequence into k disjoint subsequences, where k is number of processors (for example, k=100).Second one splits original stream into non-overlapping blocks of size nskip.

Current version of the library allows maximum size of the block ~2*10^9. If you need to provide one processor with larger block of random numbers (for example, 10^10) you may apply the SkipAhead method suitable number of times (for example, 5). This procedure is used for each processor. Another way is to provide k blocks of maximum size to k processors. When all random numbers are completed processors are provided with new blocks of maximum size. In the second approach each processor processes non-continuous subsequences of random numbers.

More details about support of parallel computations in the library can be found in VslNotes.pdf, http://www.intel.com/software/products/mkl/docs/vslnotes.pdf and MKL Reference Manual, http://www.intel.com/software/products/mkl/docs/WebHelp/mklrefman.htm.

We work on opportunity to extend maximum size of block in SkipAhead method.
Relevant changes will be included in future releases of the library. Thank you.

Thank you, your comment was very helpful.

Regards,
Michael

Leave a Comment

Please sign in to add a comment. Not a member? Join today