Segment of entropy generator and parallel random number

Question

I have a loop where I add noise to some points; they are subsequently used as the basis for some statistical tests.

The input is quite large, so I would like to parallelize it using openMP in order to speed things up. The problem arises when I want to have several PRNGs. I have my own PRNG class based on the NR modulo method (rand4, I think), but I'm not sure how to properly PRNG seeds to provide the proper entropy

Normalliy I would do something like this

prng.initTimer(); 

But if I have a prng array, one per worker thread, then I can’t just call initTimer for each instance - the timer may not change, and close timers can introduce correlation.

I need to protect against natural correlations, and not from malicious intruders (this is experimental data), so I need to have a safe way of seeding the rng array.

I thought just to use

 prng[0].initTimer() for(int i=1; i<numRNGs; i++) prng[i].init(prng[0].getRandNum()); 

Then call my loop, but I'm not sure if this will lead to correlations in the modular method.

Answer 1

I think it depends on the properties of your PRNG. The usual advantages of PRNG are lower entropy in the lower bits and lower entropy for the first values ​​of n . Therefore, I think that you should check your PRNG for such weaknesses and change your code accordingly.

Some of the diehard tests may provide useful information, but you can also check the first values ​​of n and their statistical properties, such as the sum and, and compare them with the expected values.

For example, run PRNG and sum the first 100 values ​​modulo 11 of your PRNG, repeat this R times. If the total amount is very different from the expected (5 * 100 * R), your PRNG suffers from one or two of the disadvantages mentioned above.

Unaware of PRNG, I would feel safer using something like this:

 prng[0].initTimer(); // Throw the first 100 values away for(int i=1; i < 100; i++) prng[0].getRandNum(); // Use only higher bits for seed values (assuming 32 bit size) for(int i=1; i<numRNGs; i++) prng[i].init(((prng[0].getRandNum() >> 16) << 16) + (prng[0].getRandNum() >> 16)); 

But, of course, this is speculation about PRNG. With perfect PRNG, your approach should work just as it is.

Answer 2

PRNG sowing does not require the creation of independent threads. You should sow only the first instance (call its link) and initialize the remaining instances by quickly forwarding the reference instance. This only works if you know how many random numbers each stream consumes and a fast forward algorithm is available.

I don’t know much about your rand4 (googled it, but didn’t come up with anything concrete), but you should not assume that you can create independent flows only by seeding. You probably want to use another (best) PRNG. Take a look at WELL . It is fast, has good statistical properties and was developed by well-known specialists. WELL 512 and 1024 are one of the fastest PRNGs, and both have huge periods. You can initialize multiple instances of WELL with separate seeds to create independent threads. Due to the huge period, there is an almost zero chance that your PRNGs will generate overlapping streams of random numbers.

If your PRNGs are triggered frequently, beware of false exchanges. This article by Herb Sutter explains how false sharing can kill multi-core performance. Packing multiple PRNGs into an adjacent array is an almost perfect recipe for a false exchange. To avoid a false exchange, add an add-on between PRNG or allocate PRNG to the heap / free storage. In a later case, each RNG must be allocated individually using some sort of aligned distributor. Your compiler should provide a version of the built-in malloc. Check the docs (well, a Google search is really faster than reading manuals). Visual C ++ has _aligned_malloc , GCC has memalign and posix_memalign . The aliment value must be a multiple of the size of the processor cache line. A common practice is to align along 128 byte boundaries. For a portable solution, you can use the aligned TBB cache allocator.

Answer 3

If you select PRNG using a sequence of numbers from the same type of PRNG, all of them will produce the same sequence of numbers offset from each other. If you want them to produce different numbers, you will need to align them using a sequence of pseudo-random numbers from another PRNG.

Alternatively, if you use a Unix-like system with /dev/random , you can simply read from this device to get a sequence of random numbers to use as your seeds.