Random Number Library Parallel Generators

• Introduction
• Parallel Uniform Random Number Generator concept
• Named parameters
• Parallel seeding functions
• A 64-bit parallel linear congruential generator lcg64
• The WELL generators

Introduction

The Scalable Parallel Pseuo Random Number Generators Library (SPRNG) is a C-library that was designed to solve this challenge. As explained in detail in the SPRNG paper, there are several methods of creating independent parallel random number streams, using parametrization of the generator, or cycle division techniques.

Since the method to create independent streams depends on the choice of generator, no generic seeding can be implemented, but the seeding mechanism is specific to the generator. However, a common interface is possible, and we follow the design of the SPRNG library by requiring the following two parameters next to a global seed

• stream_number: the number of the current stream
• total_streams: the total number of streams required

Parallel Uniform Random Number Generator

In the following table,

• X denotes a model of the concept ParallelUniformRandomNumberGenerator.
• v is an object of type X.
• num and total are unsigned integral values saitsfying num < total.
• first and last input iterators with a value type convertible to unsigned int. first is required to be non-const.

ParallelUniformRandomNumberGenerator requirements
Expression	Return type	Note
seed(v,num,total)	void	default parallel seeding of v
seed(v,num,total,first,last)	void	parallel seeding of v from two iterators. The semantics is identical to that of the seeding of a UniformRandomNumberGenerator from a pair of iterators, with the only distinction that for identical elements in the range [first,last) and identical values of total but different values of num, independent non-overlapping sequences of random numbers will be produced by the generator.

Named parameter interface

ParallelUniformRandomNumberGenerator requirements
Expression	Return type	Note
X::max_streams	int	the maximum number of independent streams provided by X.
X(named parameters)	X	creates an object of type X with the named parameter arguments given in the table below.
v.seed(optional named parameters)	void	seeds v with the named parameter arguments given in the table below.
v.seed(first,last,optional named parameters)	void	seeds v with the range of values given by [first,last), and the named parameter arguments given in the table below.

Named parameters for seeding of a ParallelUniformRandomNumberGenerator
Parameter name	Default	Legal values
total_streams	1	0 <= total_streams < X::max_streams
stream_number	0	0 <= stream_number < total_streams
global_seed	0

Parallel uniform random number generators created with the same values of total_streams, global_seed but different values for stream_number will produce independent non-overlapping sequences of random numbers.

Header <boost/random/parallel/keyword.hpp>

#include <boost/parameter/keyword.hpp>

namespace boost {  namespace random { namespace parallel {
  
  BOOST_PARAMETER_KEYWORD(tag,stream_number)
  BOOST_PARAMETER_KEYWORD(tag,total_streams)
  BOOST_PARAMETER_KEYWORD(tag,global_seed)
  
} } }

Parallel seeding functions

Header <boost/random/parallel/seed.hpp>

Synopsis

namespace boost { namespace random { namespace parallel {
  
  template <class PRNG>
  void seed(PRNG& prng, unsigned int num, unsigned int total);
  
  template <class PRNG, class Iterator>
  void seed(PRNG& prng, unsigned int num, unsigned int total, Iterator& first, Iterator const& last);

  template <class PRNG, class SeedType>
  void seed(PRNG& prng, unsigned int num, unsigned int total, SeedType const& s);

} } }

Seeding functions

template <class PRNG>
void seed(PRNG& prng, unsigned int num, unsigned int total);

template <class PRNG, class Iterator>
void seed(PRNG& prng, unsigned int num, unsigned int total, Iterator& first, Iterator const& last);

template <class PRNG, class SeedType>
void seed(PRNG& prng, unsigned int num, unsigned int total, SeedType const& s);

Header <boost/random/parallel/mpi.hpp>

Synopsis

namespace boost { namespace random { namespace parallel {
  template <class PRNG>
  void seed(PRNG& prng, boost::parallel::mpi::communicator const& c)

  template <class PRNG, class SeedType>
  void seed(PRNG& prng, boost::parallel::mpi::communicator const& c, SeedType const& s)

  template <class PRNG, class Iterator>
  void seed(PRNG& prng, boost::parallel::mpi::communicator const& c, Iterator& first, Iterator const& last)

  template <class PRNG, class SeedType>
  void broadcast_seed( PRNG& prng, boost::parallel::mpi::communicator const& c, int root, SeedType s)

} } }

MPI seed functions

template <class PRNG>
void seed(PRNG& prng, boost::parallel::mpi::communicator const& c)

template <class PRNG, class SeedType>
void seed(PRNG& prng, boost::parallel::mpi::communicator const& c, SeedType const& s)

template <class PRNG, class Iterator>
void seed(PRNG& prng, boost::parallel::mpi::communicator const& c, Iterator& first, Iterator const& last)

template <class PRNG, class SeedType>
void broadcast_seed( PRNG& prng, boost::parallel::mpi::communicator const& c, int root, SeedType s)

64-bit linear congruential generator lcg64

Header <boost/random/parallel/lcg64.hpp>

namespace boost {
namespace random {

template<uint64_t a, uint64_t val>
class lcg64
{
  typedef uint64_t result_type;
  static const bool has_fixed_range = true;
  static const result_type min_value;
  static const result_type max_value;
  static const result_type max_streams = 146138719;
  
  lcg64(optional named parameters);
  template<class It> lcg64(It& first, It last,optional named parameters);

  void seed(optional named parameters);
  template<class It> void seed(It& first, It last,optional named parameters);
  result_type operator()();
  static bool validation(result_type);
};
}

typedef random::lcg64< /* ... */> lcg64a;
typedef random::lcg64< /* ... */> lcg64b;
typedef random::lcg64< /* ... */> lcg64c;
}

Description

This header provides a parallel 64-bit linear congruential generator template, and three well-tested choices of multipliers. As for other linear congruential generators, the recursion relation (n+1) := (a * x(n) + c) mod m is used. In this implementation, m=2⁶⁴ and the multiplier a, which is given as template parameter is different for the three generators . The prime additive constant c is chosen depending on the stream number, thus giving independent sequences for each stream.

The WELL generators

Header <boost/random/parallel/well.hpp>

namespace boost {
namespace random {

template<class UIntType, int statesize, UIntType val, class F1, class F2
       , class F3, class F4, class F5, class F6, class F7, class F8
       , int p1,  int p2,  int p3, UIntType mask=statesize-1, class RNG=mt19937>
class well
{
  typedef UIntType result_type;
  static const bool has_fixed_range = true;
  static const result_type min_value;
  static const result_type max_value;
 
  well(optional named parameters);
  template<class It> well(It& first, It last,optional named parameters);

  void seed(optional named parameters);
  template<class It> void seed(It& first, It last,optional named parameters);
  result_type operator()();
  static bool validation(result_type);
};
typedef well< /* ... */> well512a;
typedef well< /* ... */> well1024a;
}
}

Description

Instantiations of class template well model a pseudo-random number generator, whose algorithm is described in

"Improved Long-Period Generators Based on Linear Recurrences Modulo 2" , F. Panneton, P. L'Ecuyer and M. Matsumoto, submitted to ACM TOMS

Two well-tested and validated generators well512a and well1024a are provided as specializations.

The parallel seeding is based on cycle division:

• The single seed method calls a pseudo-random number generator (default: mt19937), which provides the random seeds for total_streams WELL generators.
• In the iterator method the state vector of all total_streams WELL generators is filled by a buffer.

---

Matthias Troyer, 2006-07-06