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: http://stackoverflow.com/questions/14923902/random-numbers-for-multiple-threads — Chris Beck, Aug 29 '15 at 03:56
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, Aug 29 '15 at 04:07
@1201ProgramAlarm `genRand` never let `n` be 0 if `n` was not seeded as 0. It also passes all of the Diehard tests from dieharder. — , Aug 29 '15 at 04:44

score 0 · Answer 1 · answered Aug 29 '15 at 01:20

If you have access to a cryptographic library then you can encrypt the padded initial seed with AES and split up the output among your PRNGs. For example, using counter mode with a 64-bit initial seed of [seed] you'd concatenate this until you goet a plaintext of 256 bits:

[seed][seed][seed][seed]

and your initialization vector would be [counter][seed] (you need a unique initialization vector but not necessarily a secure initialization vector, since nobody is trying to decrypt your output). This will produce a 256-bit output, the first 64 bits seed the first PRNG, the second 64 bits seed the second PRNG, etc.

There are other ways of doing this depending on what's provided in the crypto library, e.g. you could hash the initial seed, or you could produce random UUIDs until you've got enough bits to seed all of your PRNGs.

For this sort of purpose, you don't need an initialization vector. Just use consecutive numbers as your original seed, encrypt each in ECB mode (which doesn't use an IV) and use those outputs as your seeds for the individual generators. — Jerry Coffin, Sep 01 '15 at 18:55

score 0 · Accepted Answer · answered Aug 29 '15 at 22:49

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)

I'm staying with PCG. It's designed to have multiple 'kind's up to 2^63 and also performs well in statistical tests. — , Aug 30 '15 at 06:49
@xiver77 good luck. You might take a look at discussion http://stackoverflow.com/questions/28991299/parallel-montecarlo-reproducibility-or-real-randomness — Severin Pappadeux, Aug 30 '15 at 23:52

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

2 Answers2