Naive implementation of parallel Mersenne Twister (MT) pseudorandom number generator
  Home FAQ Contact Sign in
comp.lang.fortran only
 
Advanced search
POPULAR GROUPS

more...

comp.lang.fortran Profile…
 Up
Naive implementation of parallel Mersenne Twister (MT) pseudorandom number generator         


Author: mjm2114
Date: Apr 24, 2008 07:45

Hi there,
I have a question on a naive implementation of a parallel MT that I've
done using the fortran version of MT19937ar.f posted in Prof.
Matsumoto's website. (http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/
VERSIONS/FORTRAN/mt19937ar.f)

First, I setup an MT in the master node and seed it with a single
integer using subroutine init_genrand(seed). I then use the first 624
outputs from the master node to seed the MT in the first worker node...
Show full article (12.14Kb)
9 Comments
Re: Naive implementation of parallel Mersenne Twister (MT) pseudorandom number generator         


Author: Gordon Sande
Date: Apr 24, 2008 08:05

On 2008-04-24 11:45:55 -0300, mjm2114@columbia.edu said:
> Hi there,
> I have a question on a naive implementation of a parallel MT that I've
> done using the fortran version of MT19937ar.f posted in Prof.
> Matsumoto's website. (http://www.math.sci.hiroshima...
Show full article (13.34Kb)
no comments
Re: Naive implementation of parallel Mersenne Twister (MT) pseudorandom number generator         


Author: mjm2114
Date: Apr 24, 2008 08:22

Thanks for your reply. Maybe I wasn't clear. I take the first block of
624 outputs from the master node to seed the first worker node. I then
take the second block of 624 outputs from the master node to seed the
second worker node, and so forth. In this way, every worker node has
been initialized with a different array of seeds. The master node is
only used to produce seeds for the worker nodes, it is not used for
anything else.
no comments
Re: Naive implementation of parallel Mersenne Twister (MT) pseudorandom number generator         


Author: Gordon Sande
Date: Apr 24, 2008 09:01

On 2008-04-24 12:22:49 -0300, mjm2114@columbia.edu said:
> Thanks for your reply. Maybe I wasn't clear. I take the first block of
> 624 outputs from the master node to seed the first worker node. I then
> take the second block of 624 outputs from the master node to seed the
> second worker node, and so forth. In this way, every worker node has
> been initialized with a different array of seeds. The master node is
> only used to produce seeds for the worker nodes, it is not used for
> anything else.

Your description still makes it sound like each node will be only
a delayed version of a lower numbered node.

The internal state of the PRNG is usually called the seed. There may be
shortcut initial startups, labelled seeds, for those generators that have
large seeds like MT. Leads to confusion on the meaning of the words when
the adjectives are dropped. The purpose of a full seed is to pick up again
EXACTLY where you left off. Having the master step along and give seeds
to each slave just means that the slaves will exactly follow what the
master would have done. Exact reproducability of PRNGs is important for
debugging. That is what the saving and restoring of seeds is all about.
Show full article (1.51Kb)
no comments
Re: Naive implementation of parallel Mersenne Twister (MT) pseudorandom number generator         


Author: mjm2114
Date: Apr 24, 2008 09:39

On Apr 24, 12:01 pm, Gordon Sande worldnet.att.net> wrote:
> On 2008-04-24 12:22:49 -0300, mjm2...@columbia.edu said:
>
>> Thanks for your reply. Maybe I wasn't clear. I take the first block of
>> 624 outputs from the master node to seed the first worker node. I then
>> take the second block of 624 outputs from the master node to seed the
>> second worker node, and so forth. In this way, every worker node has
>> been initialized with a different array of seeds. The master node is
>> only used to produce seeds for the worker nodes, it is not used for
>> anything else.
>
> Your description still makes it sound like each node will be only
> a delayed version of a lower numbered node.
>
> The internal state of the PRNG is usually called the seed. There may be
> shortcut initial startups, labelled seeds, for those generators that have
> large seeds like MT. Leads to confusion on the meaning of the words when
> the adjectives are dropped. The purpose of a full seed is to pick up again
> EXACTLY where you left off. Having the master step along and give seeds
> to each slave just means that the slaves will exactly follow what the ...
Show full article (2.32Kb)
no comments
Re: Naive implementation of parallel Mersenne Twister (MT) pseudorandom number generator         


Author: Gordon Sande
Date: Apr 24, 2008 11:10

On 2008-04-24 13:39:01 -0300, mjm2114@columbia.edu said:
> On Apr 24, 12:01 pm, Gordon Sande worldnet.att.net> wrote:
>> On 2008-04-24 12:22:49 -0300, mjm2...@columbia.edu said:
>>
>>> Thanks for your reply. Maybe I wasn't clear. I take the first block...
Show full article (2.95Kb)
no comments
Re: Naive implementation of parallel Mersenne Twister (MT) pseudorandom number generator         


Author: glen herrmannsfeldt
Date: Apr 24, 2008 11:37

Gordon Sande wrote:
(snip)
> The internal state of the PRNG is usually called the seed. There may be
> shortcut initial startups, labelled seeds, for those generators that have
> large seeds like MT. Leads to confusion on the meaning of the words when
> the adjectives are dropped. The purpose of a full seed is to pick up again
> EXACTLY where you left off. Having the master step along and give seeds
> to each slave just means that the slaves will exactly follow what the
> master would have done. Exact reproducability of PRNGs is important for
> debugging. That is what the saving and restoring of seeds is all about.

Probably you are right, but the use of the word 'seed' doesn't
make that obvious. A seed grows into a tree, but one normally
doesn't expect to store a whole tree back into a seed and create
and exact copy of the tree.

What you call 'shortcut initial startup' seems more appropriate
for the word 'seed'. Since the early PRNGs had a one word seed
the distinction wasn't needed at the time.

http://en.wikipedia.org/wiki/Random_seed

Doesn't seem to distinguish 'full seed' from 'seed'.
Show full article (1.12Kb)
no comments
Re: Naive implementation of parallel Mersenne Twister (MT) pseudorandom number generator         


Author: Gordon Sande
Date: Apr 24, 2008 12:52

On 2008-04-24 15:42:02 -0300, glen herrmannsfeldt ugcs.caltech.edu> said:
> Gordon Sande wrote:
> (snip)
>
>> The internal state of the PRNG is usually called the seed. There may be
>> shortcut initial startups, labelled seeds, for those generators that have
>> large seeds...
Show full article (2.30Kb)
no comments
Re: Naive implementation of parallel Mersenne Twister (MT) pseudorandom number generator         


Author: Gerry Ford
Date: Apr 24, 2008 15:41

columbia.edu> wrote in message
news:6c9d2875-8019-42d0-9389-40850ad575a7@x35g2000hsb.googlegroups.com...
> Hi there,
> I have a question on a naive implementation of a parallel MT that I've
> done using the fortran version of MT19937ar.f posted in Prof.
> Matsumoto's website. (http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/
> VERSIONS/FORTRAN/mt19937ar.f)
>
> First, I setup an MT in the master node and seed it with a single
> integer using subroutine init_genrand(seed). I then use the first 624
> outputs from the master node to seed the MT in the first worker node
> using subroutine init_by_array(array_of_seeds,624). I continue in the
> same manner for all subsequent worker nodes, taking the next 624
> outputs from the master node and using them to seed the MT in all
> worker nodes. Once this is done, I have a different MT ready for use
> in all the worker nodes. Do you think this is a good approach? I know
> that the all blocks of 624 seeds used to set up the worker node MTs
> have some correlation (since they are adjacent blocks produced by the
> same MT), but given the equidistribution properties and the gigantic
> period of the algorithm, wouldn't these correlations be insignificant ...
Show full article (3.14Kb)
no comments
Re: Naive implementation of parallel Mersenne Twister (MT) pseudorandom number generator         


Author: e p chandler
Date: Apr 24, 2008 17:25

On Apr 24, 3:52 pm, Gordon Sande worldnet.att.net> wrote:
> In the case of the "one word internal state" a case could be made
> that the seed could take states that were not internally possible
> but that the reported internal state would be a seed as well. This
> was for the situation where the 31 bits had to end in "01" (3 mod 8)
> so some of bits in a 32 bit seed could be invalid. Seed is a curious
> uasge at best but seems to be rather well establshed.

True only if the additive constant is ZERO.
> The OP seemed to be saying that each word in the many word internal
> state was a seed so in an attempt to draw his attention to the whole
> thing I used "full seed" on the fly. Better suggestions are welcome. ;-)

I'll stay away from this. :-(. IMO it's more important to make sure
that ALL bits of the initial state are initialized AND that all bits
are initialized properly. [For a counter example look at how MS
Basic's RANDOMIZE n works in version 5.x]

[Sorry it's been years since I've read about GFSR routines. Back then
not all the bits could be zero. Now it seems that an excess of zero
bits in the intial state is bad.... Too complex for me to understand
anyway. :-(.]
Show full article (1.20Kb)
no comments