What is a good way to seed parallel pseudo random number generators?

Question

The PRNG I wrote has a period of 2^64. When I use a spinlock to protect it from 4 threads, It runs twice slower than when there is a single thread. A mutex appears better at making things slower. So I decided to have separate generators per thread, but the problem here is that when the seeds are too close, The same series of random numbers will appear again and again each in a different thread. I'm not 100% sure how bad this will affect my simulation, but I'd like to avoid having very closely seeded PRNGs.

Maybe my original question was too less specified to get an easy solution. Below I posted the PRNG that I'm using. It performs very well in statistical tests such as Diehard or FIPS, but I really cannot prove why as I'm no expert in this area. I need a way to find good seeds for 4 or more generators running in parallel. With 2 seeds, the worst pair of seeds are the same seeds so that 2 threads are getting the same sequence of random numbers. The best pair of seeds will produce two sequences with no overlapping part.

I see that it gets harder to find the 'best' set of seeds as the number of parallel generators or the number of random numbers generated or both get greater. There will be at least 4 threads and at least a billion random numbers generated per task.

I simplest solution I can reach is periodic reseeding. Sometimes I may get a bad set of seeds, but it will soon get replaced by a better one after a periodic reseed.

Is there a general solution to my problem that can be applied to any PRNG? Or at least something available to the generator I'm currently using? I can possibly change my PRNG, if there's one which is specifically designed and well suited for parallel random number generation.

static thread_local unsigned long long n;

void seedRand(unsigned long long s)
{
  n = s;
}

unsigned genRand(void)
{
  n *= 123456789;
  n ^= n >> 3;
  n ^= n << 5;
  return n ^= n >> 7;
}

I think this might be a duplicate of this: stackoverflow.com/questions/14923902/… — Chris Beck
Your getRand function is not a good RNG. One problem is when n becomes zero it will stay zero. If your compiler version is new enough, just use one of the RNGs provided with the standard library. These can take 2 seed values so each thread can provide it's own distinct value for the second seed parameter and generate distinct sequences. — 1201ProgramAlarm
@1201ProgramAlarm genRand never let n be 0 if n was not seeded as 0. It also passes all of the Diehard tests from dieharder. — xiver77

Severin Pappadeux Severin Pappadeux · Accepted Answer · 2015-08-29T22:49:12

I can possibly change my PRNG, if there's one which is specifically designed and well suited for parallel random number generation

well, if you're willing to change RNG, there are generators which have fast (logarithmic over of number of calls skipped) skip-ahead (a.k.a leap-frog).

They by design guarantee not to overlap. Say, your simulation per thread requires 10^9 RNG calls and could run on 8 threads, then you start with single seed, and first thread is skipped by 0, second thread is skipped by 10^9, and thread number N is skipped by (N-1)* 10^9.

Reasonable acceptable one (which is reimplementation of MCNP5 fortran code) is here https://github.com/Iwan-Zotow/LCG-PLE63, but most likely is won't pass Diehard.

A bit more complex one (and it passed Diehard, I believe) is here http://www.pcg-random.org/

Both based upon fast exponentiation, paper by F. Brown, "Random Number Generation with Arbitrary Stride," Trans. Am. Nucl. Soc. (Nov. 1994)

What is a good way to seed parallel pseudo random number generators?

2 Answers