Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.9k views
in Technique[技术] by (71.8m points)

multithreading - Parallel MonteCarlo: reproducibility or real randomness?

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

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

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/


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

1.4m articles

1.4m replys

5 comments

57.0k users

...