Parallel MonteCarlo: reproducibility or real rando

Question

I'm preparing a college exam in parallel computing. The main purpose is to speedup as much as possible a Montecarlo simulation about electron drift in earth magnetic field. I've already developed something with two layers of parallelization:

• MPI used to make te code run on several machines
• OpenMP to run parallel simulation inside the single computer

Now comes the question: I would like to keep on-demand the task execution. The fastest computer must be able to execute more work the the slower ones. The problem partition is done via master-worker cycle, so there is no actual struggle about achieving this result.

Since the number of tasks (a block of n electrons to simulate) executed by a worker is not prior defined I have two roads to follow:

1. every thread in every worker has is own RNG initialized with random generated seed (different generation method). The unbalancing of the cluster will change results, but in this approach the result is as casual as possible.

2. every electron has his own seed, granting reproducibility of the simulation despite of which worker runs the single task. Must have a better RNG.

Lets's poll about this. What's your suggestion?

Have fun

gf

Answer 1

What to poll about here?

Clearly, only approach #2 is a feasible one. Each source particle starts with it's own and stable seed. It makes result reproducible AND debuggable (for a lack of better word).

Well-known Monte Carlo code MCNP5+ used this scheme for good, runs on multi-cores and MPI. To implement it you'll need RNG with fast skip-ahead (a.k.a. leapfrog or discard) feature. And there are quite a few of them. They are based upon fast exponent computation, paper by F. Brown, "Random Number Generation with Arbitrary Stride", Trans. Am. Nucl. Soc. (Nov. 1994). Basically, skip-ahead is log(N) with Brown approach.

Simplest version which is about the same as MCNP5 one is here https://github.com/Iwan-Zotow/LCG-PLE63

More complicated (and slower, but higher quality) RNG is here http://www.pcg-random.org/