Naive implementation of parallel Mersenne Twister (MT) pseudorandom number generator
in [Fortran]
|
Prev: Naive implementation of parallel Mersenne Twister (MT) pseudorandom number generator
Next: Naive implementation of parallel Mersenne Twister (MT) pseudorandomnumber generator
From: Gordon Sande on 24 Apr 2008 12:01 On 2008-04-24 12:22:49 -0300, mjm2114(a)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. It would be easy to form the conclusion that you are rather confused about what the role of the seed is. Neither your initial nor followup posting serve to dispell that. For MT, "THE SEED" is all of the 600+ words. It is not an array of seeds. How else do you think they achieve their immense cycle length?
From: Gordon Sande on 24 Apr 2008 14:10 On 2008-04-24 13:39:01 -0300, mjm2114(a)columbia.edu said: > On Apr 24, 12:01 pm, Gordon Sande <g.sa...(a)worldnet.att.net> wrote: >> On 2008-04-24 12:22:49 -0300, mjm2...(a)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. >> >> It would be easy to form the conclusion that you are rather confused >> about what the role of the seed is. Neither your initial nor followup >> posting serve to dispell that. For MT, "THE SEED" is all of the 600+ >> words. It is not an array of seeds. How else do you think they achieve >> their immense cycle length? > > Thanks again for your comments. You are correct, my terminology was > confusing. > If we consider "seed" as synonymous with internal state then MT has a > seed of 624 32-bit integers. Seed is either a quickie starting value or it is the internal state so that the sequence can restarted exactly. The first notion is not very useful in the long run for serious users even if it is popular with casual users. > To initialize the internal state of an MT in each worker node I use a > contiguous chunk of outputs from the MT in the master node. This chunk > happens to have length 624 (recommended by MT literature) but is is > not going to be the same as the initial internal state in the worker > MT (algorithm takes care of this), nor is it equal to the previous > internal state in the master node (because this previous state was > only used to create the last number in the chunk). Hope this clears > things up. Now I have no idea what you are doing so have no comment beyond "protection by obscuriity" is well known to not be a successful strategy. Many who resort to it have ad hoc schemes that are technicaly deficient. You may not be one of those but I can not tell from what I have seen. > thanks again for your comments > > Manuel
From: Gordon Sande on 24 Apr 2008 15:52
On 2008-04-24 15:42:02 -0300, glen herrmannsfeldt <gah(a)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 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'. > > -- glen 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. 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 seem to recall that MT has a starting routine that accepts starting values to generate its initial state so users do not have to supply 600+ words of initial state. It also has the abiity to report and use the the whole thing. At least that is my recollection from looking at it some time ago. The F90 intrinsics are defined to take a multiword seed so they follow this strange but common usage. They seem to equate the seed with the internal state. |