parallel RNG

[ViralBShah]

How should parallel RNG be addressed? Codes that do parallel RNG:

This is an MPI code that does not seem to be maintained:
http://sprng.cs.fsu.edu/

A derivative of Mersenne Twister:
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/DC/dc.html

At the very least,when randomize() is called, it should include the processor's number along with time to select a different seed on every processor.

[JeffBezanson]

I don't fully understand what needs to be done here. By default, processors start with different seeds. To seed each process you can do @bcast srand(seeds[myid()]).

[StefanKarpinski]

I think that will work for an initial cut. The real issue is making sure that entire distribute simulations/computations are deterministically reproducible from a single initial seed value. That means that the computation can't depend on race conditions regarding which processor gets to some point first, or even how many processors there are. For now we can definitely punt on this.

[JeffBezanson]

I guess we need a hook for when processors are added so you can do custom initialization on the machine. And if we do checkpointing we need to save the random state.

[ViralBShah]

Isn't it good enough that they read from /dev/urandom for now?

-viral

On Jul 13, 2011, at 11:37 AM, JeffBezanson wrote:

I don't fully understand what needs to be done here. By default, processors start with different seeds. To seed each process you can do @bcast srand(seeds[myid()]).

Reply to this email directly or view it on GitHub:
#94 (comment)

[StefanKarpinski]

The hard part isn't getting distributed simulations to be random, it's getting them to be repeatable. Using /dev/urandom helps making things really random, but helps repeatability not at all. Let's worry about this when we have an actual use case. I have done simulations like this in the past, so the problem makes sense to me, but I don't necessarily know what a good solution is.

[ViralBShah]

Well you can make them repeatable by just saving the seed. Doesn't seem to be difficult.

A related issue is that if you have a bunch of virtual machines being booted up for your computation, is it likely that their entropy pools are similar?

[ViralBShah]

We already seed the RNG from /dev/urandom or system time. Hence, this is not really a major issue for now.

[StefanKarpinski]

This is not at all a resolved issue. The problem with parallel RNG is not making all the machines behave differently, but to make pseudorandom behavior across many machines exactly repeatable. This won't get addressed until we have an actual example to see why it's a problem, but we shouldn't close it because it will be an issue at some point.

[ViralBShah]

You can set a different seed on each machine for repeatable behavior, which is what you have to do in the 1p case as well. How is this specific to parallel rng?

-viral

On 09-Jan-2012, at 2:11 AM, Stefan Karpinskireply@reply.github.com wrote:

This is not at all a resolved issue. The problem with parallel RNG is not making all the machines behave differently, but to make pseudorandom behavior across many machines exactly repeatable. This won't get addressed until we have an actual example to see why it's a problem, but we shouldn't close it because it will be an issue at some point.

---

Reply to this email directly or view it on GitHub:
#94 (comment)

[StefanKarpinski]

Because in a complex distributed computation the same exact work won't always happen on the same machines. Trust me, this is a more complicated issue. If you must close it, fine, but we will encounter this problem at some point. I'll pose a simple example: let's say we want to do a distributed parallel Buffon's needle that can be repeatably run on any number of machines. How do you do that?

[ViralBShah]

I agree, that when you change the number of nodes, it is a problem. But, for the same number of nodes, there is no issue. My only point was that for the immediate purposes of this issue, it was resolved. I am quite sure that even SPRNG and others do not offer this feature.

I suggest that we create a new issue when we run into this problem, or reopen this one then.

-viral

On Jan 9, 2012, at 2:52 AM, Stefan Karpinski wrote:

Because in a complex distributed computation the same exact work won't always happen on the same machines. Trust me, this is a more complicated issue. If you must close it, fine, but we will encounter this problem at some point. I'll pose a simple example: let's say we want to do a distributed parallel Buffon's needle that can be repeatably run on any number of machines. How do you do that?

---

Reply to this email directly or view it on GitHub:
#94 (comment)

[ViralBShah]

Ok, here's a proposition. The user calls a routine called sdrand (for set distributed random seeds). The argument to it is the maximum number of processors that the user ever expects to use - say 100 or 1000 or whatever. The routine then seeds the RNG uniformly within the RNG's interval for that many processors. Now, if the user uses up to the specified number of processors, reproducible results are possible.

-viral

On Jan 9, 2012, at 2:52 AM, Stefan Karpinski wrote:

Because in a complex distributed computation the same exact work won't always happen on the same machines. Trust me, this is a more complicated issue. If you must close it, fine, but we will encounter this problem at some point. I'll pose a simple example: let's say we want to do a distributed parallel Buffon's needle that can be repeatably run on any number of machines. How do you do that?

---

Reply to this email directly or view it on GitHub:
#94 (comment)

[StefanKarpinski]

This doesn't work because if the data distribution is different, the same
calls to the rng will be on different nodes and therefore change the
results. Why can't we just leave this issue open until we find ourselves in
a position to tackle the issue — hopefully with a real-world use-case to
drive it.

On Sun, Jan 8, 2012 at 10:07 PM, Viral B. Shah <
reply@reply.github.com

wrote:

Ok, here's a proposition. The user calls a routine called sdrand (for set
distributed random seeds). The argument to it is the maximum number of
processors that the user ever expects to use - say 100 or 1000 or whatever.
The routine then seeds the RNG uniformly within the RNG's interval for that
many processors. Now, if the user uses up to the specified number of
processors, reproducible results are possible.

-viral

On Jan 9, 2012, at 2:52 AM, Stefan Karpinski wrote:

Because in a complex distributed computation the same exact work won't
always happen on the same machines. Trust me, this is a more complicated
issue. If you must close it, fine, but we will encounter this problem at
some point. I'll pose a simple example: let's say we want to do a
distributed parallel Buffon's needle that can be repeatably run on any
number of machines. How do you do that?

---

Reply to this email directly or view it on GitHub:
#94 (comment)

---

Reply to this email directly or view it on GitHub:
#94 (comment)