Open MPI logo

Open MPI Development Mailing List Archives

  |   Home   |   Support   |   FAQ   |   all Development mailing list

Subject: Re: [OMPI devel] RFC: Add an OPAL rand and srand
From: Joshua Ladd (joshual_at_[hidden])
Date: 2014-02-07 17:40:29


Yes. After batting this around a bit with Jeff and Mike, we came to the consensus that the interface should be more "rand_r", so that state is locally managed by the consumer. The ALFG offers a powerful yet simple way to do it. We may even expose it to users since it offers a very scalable and high quality parallel RNG.

Josh

From: devel [mailto:devel-bounces_at_[hidden]] On Behalf Of Paul Hargrove
Sent: Friday, February 07, 2014 5:31 PM
To: Open MPI Developers
Subject: Re: [OMPI devel] RFC: Add an OPAL rand and srand

Joshua,

This is for ticket #2928, right?

-Paul

On Fri, Feb 7, 2014 at 2:23 PM, Joshua Ladd <joshual_at_[hidden]<mailto:joshual_at_[hidden]>> wrote:
What: Add an internal random number generator to OPAL.

Why: OMPI uses rand and srand all over the place. Because the middleware is mucking with the RNG's global state, applications that use these library routines will not achieve reproducible results with the same seed.

How: I plan to put in an additive lagged Fibonacci generator seeded with a Tausworthe generator that itself is seeded by the user's seed. The short story here is that the ALFG has a toroidal state space, i.e. it can be decomposed into non-overlapping cycles with maximal period. It's well understood how to fully enumerate these cycles when, for a length k register composed of m-bit words, we view this as a k X m binary matrix. It was proven by Marsaglia et al. that this matrix has a canonical form that is uniquely determined by the values k and l (the two numbers that (almost) completely characterize an ALFG.) So, distinct seeds are guaranteed to map to distinct, non-overlapping, long period streams that have measurably very, very low inter- and intra-stream correlations. We used this for large scale Monte Carlo simulations back in my PhD days.

Will define a new type:

struct opal_rng_buffer_t {

uint32_t buff[127]; /* if people are going to pitch a fit over the size, we can go smaller, down to 7, but, obviously, this affects the quality of the streams */
int tap1;
int tap2;

};

and two functions:

/* User is responsible for defining his/her own opal_rng_buffer_t
  * or malloc-ing and managing the resources themselves.
 */
int opal_srand(opal_rng_buffer_t *buff, uint32_t seed);

/* Returns a 32-bit pseudo random integer */
uint32_t opal_rand(opal_rng_buffer_t *buff);

When: Should be in by the end of February. Code is written, but integration and testing always takes some time.

Joshua S. Ladd, PhD
HPC Algorithms Engineer
Mellanox Technologies

Email: joshual_at_[hidden]<mailto:joshual_at_[hidden]>
Cell: +1 (865) 258 - 8898<tel:%2B1%20%28865%29%20258%20-%208898>

_______________________________________________
devel mailing list
devel_at_[hidden]<mailto:devel_at_[hidden]>
http://www.open-mpi.org/mailman/listinfo.cgi/devel

--
Paul H. Hargrove                          PHHargrove_at_[hidden]<mailto:PHHargrove_at_[hidden]>
Future Technologies Group
Computer and Data Sciences Department     Tel: +1-510-495-2352
Lawrence Berkeley National Laboratory     Fax: +1-510-486-6900