* Re: Parallel_Simulation
2013-02-25 17:17 ` Parallel_Simulation Vincent LAFAGE
@ 2013-02-25 18:18 ` Shark8
2013-02-26 7:20 ` Parallel_Simulation Vincent LAFAGE
2013-02-25 18:30 ` Parallel_Simulation John B. Matthews
` (3 subsequent siblings)
4 siblings, 1 reply; 11+ messages in thread
From: Shark8 @ 2013-02-25 18:18 UTC (permalink / raw)
On Monday, February 25, 2013 11:17:23 AM UTC-6, Vincent LAFAGE wrote:
>
> Would you think of another way?
Well, you could forgo the independent RNG requirement and make a protected object that is say a stack filled with random values and is replenished as-needed.
OR you could have your different RNGs nested into the task itself (say the declaration area) -- then make the seed value take values from the protected object above.
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Parallel_Simulation
2013-02-25 18:18 ` Parallel_Simulation Shark8
@ 2013-02-26 7:20 ` Vincent LAFAGE
0 siblings, 0 replies; 11+ messages in thread
From: Vincent LAFAGE @ 2013-02-26 7:20 UTC (permalink / raw)
Le 25/02/2013 19:18, Shark8 a �crit :
> On Monday, February 25, 2013 11:17:23 AM UTC-6, Vincent LAFAGE wrote:
>>
>> Would you think of another way?
>
> Well, you could forgo the independent RNG requirement and make a protected object that is say a stack filled with random values and is replenished as-needed.
This was indeed my first attempt. But it turned out that the workers for
the computation were not so slow (quite optimized) compared to the
generator, and would dry the RNG stack quickly. So I try to explore the
more parallel way.
> OR you could have your different RNGs nested into the task itself (say the declaration area) -- then make the seed value take values from the protected object above.
Could be another interesting try.
Thanks!
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Parallel_Simulation
2013-02-25 17:17 ` Parallel_Simulation Vincent LAFAGE
2013-02-25 18:18 ` Parallel_Simulation Shark8
@ 2013-02-25 18:30 ` John B. Matthews
2013-02-26 7:13 ` Parallel_Simulation Vincent LAFAGE
2013-02-25 21:04 ` Parallel_Simulation Simon Wright
` (2 subsequent siblings)
4 siblings, 1 reply; 11+ messages in thread
From: John B. Matthews @ 2013-02-25 18:30 UTC (permalink / raw)
In article <kgg6b2$kma$1@ccpntc8.in2p3.fr>,
Vincent LAFAGE <lafage@ipno.in2p3.fr> wrote:
> Le 25/02/2013 13:40, John B. Matthews a écrit :
> > In article <kgfdsp$tb0$1@ccpntc8.in2p3.fr>,
> > Vincent LAFAGE <lafage@ipno.in2p3.fr> wrote:
> >
> >> I am interested in MonteCarlo simulation and I had translated a
> >> former F77 code to Ada with success, with the goal of
> >> parallelizing it, but one part in the algorithm still resists
> >> parallelization: the random number generator. I need the different
> >> worker to rely on independant random number generators.
> >>
> >> Then I found a precious example in
> >> RM-A-5-2 59., 60., 61.
> >> that compiles smoothly.
> >>
> >> I will now attempt to check the independance of the sequence
> >> generated by each thread. But this kind of check is always more
> >> subtle than expected.
> >>
> >> I wonder whether there is a statement about the independance of
> >> such generator, in particular in the gnat implementation?
> >
> > You should check your implementation's required documentation and
> > any statements on implementation advice. For example, GNAT includes
> > a comment in Ada.Numerics.Float_Random.ads, and the GNAT Reference
> > Manual says, "The generator period is sufficiently long for the
> > first condition here [A.5.2(47)] to hold true."
>
> Thanks for the advice, but the particular doesn't exactly fit my
> question. I understand that the sequence is long enough. But
> different seeds will in the end be different starting points along
> the same sequence (well, at least for congruential generators, I
> still have to confirm it for Mersenne Twister algorithm that is
> used). And this would in turn lead to fine correlations between the
> sequences.
>
> The best statement I have found until now is in gnat_rm-4.6.info:
>
> *67*. The minimum time interval between calls to the time-dependent
> Reset procedure that are guaranteed to initiate different random
> number sequences. See A.5.2(45).
> The minimum period between reset calls to guarantee distinct
> series of random numbers is one microsecond.
>
> So I need to assert the delay between the reset of each worker in
> RM-A-5-2 60 to be sure that there is at least one microsecond.
IIUC, the example in A.5.2(60) uses the version of Reset that is _not_
time-dependent; it initializes each Worker's generator to "a state
denoted by a single integer." As long as you're not using the
time-dependent version, I don't see how the minimum period would come
into play.
> Would you think of another way?
If you Reset a single instance of Discrete_Random in a time-dependent
way and use it to generate each Worker's Initiator, as suggested in
A.5.2(61), I don't see much chance of correlation.
--
John B. Matthews
trashgod at gmail dot com
<http://sites.google.com/site/drjohnbmatthews>
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Parallel_Simulation
2013-02-25 18:30 ` Parallel_Simulation John B. Matthews
@ 2013-02-26 7:13 ` Vincent LAFAGE
0 siblings, 0 replies; 11+ messages in thread
From: Vincent LAFAGE @ 2013-02-26 7:13 UTC (permalink / raw)
Le 25/02/2013 19:30, John B. Matthews a écrit :
> In article <kgg6b2$kma$1@ccpntc8.in2p3.fr>,
> Vincent LAFAGE <lafage@ipno.in2p3.fr> wrote:
>
>> Le 25/02/2013 13:40, John B. Matthews a écrit :
>>> In article <kgfdsp$tb0$1@ccpntc8.in2p3.fr>,
>>> Vincent LAFAGE <lafage@ipno.in2p3.fr> wrote:
>>>
>>>> I am interested in MonteCarlo simulation and I had translated a
>>>> former F77 code to Ada with success, with the goal of
>>>> parallelizing it, but one part in the algorithm still resists
>>>> parallelization: the random number generator. I need the different
>>>> worker to rely on independant random number generators.
>>>>
>>>> Then I found a precious example in
>>>> RM-A-5-2 59., 60., 61.
>>>> that compiles smoothly.
>>>>
>>>> I will now attempt to check the independance of the sequence
>>>> generated by each thread. But this kind of check is always more
>>>> subtle than expected.
>>>>
>>>> I wonder whether there is a statement about the independance of
>>>> such generator, in particular in the gnat implementation?
>>>
>>> You should check your implementation's required documentation and
>>> any statements on implementation advice. For example, GNAT includes
>>> a comment in Ada.Numerics.Float_Random.ads, and the GNAT Reference
>>> Manual says, "The generator period is sufficiently long for the
>>> first condition here [A.5.2(47)] to hold true."
>>
>> Thanks for the advice, but the particular doesn't exactly fit my
>> question. I understand that the sequence is long enough. But
>> different seeds will in the end be different starting points along
>> the same sequence (well, at least for congruential generators, I
>> still have to confirm it for Mersenne Twister algorithm that is
>> used). And this would in turn lead to fine correlations between the
>> sequences.
>>
>> The best statement I have found until now is in gnat_rm-4.6.info:
>>
>> *67*. The minimum time interval between calls to the time-dependent
>> Reset procedure that are guaranteed to initiate different random
>> number sequences. See A.5.2(45).
>> The minimum period between reset calls to guarantee distinct
>> series of random numbers is one microsecond.
>>
>> So I need to assert the delay between the reset of each worker in
>> RM-A-5-2 60 to be sure that there is at least one microsecond.
>
> IIUC, the example in A.5.2(60) uses the version of Reset that is _not_
> time-dependent; it initializes each Worker's generator to "a state
> denoted by a single integer." As long as you're not using the
> time-dependent version, I don't see how the minimum period would come
> into play.
Indeed.
>> Would you think of another way?
>
> If you Reset a single instance of Discrete_Random in a time-dependent
> way and use it to generate each Worker's Initiator, as suggested in
> A.5.2(61), I don't see much chance of correlation.
Thank you for your guidance and detailled answer!
Vincent
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Parallel_Simulation
2013-02-25 17:17 ` Parallel_Simulation Vincent LAFAGE
2013-02-25 18:18 ` Parallel_Simulation Shark8
2013-02-25 18:30 ` Parallel_Simulation John B. Matthews
@ 2013-02-25 21:04 ` Simon Wright
2013-02-25 21:40 ` Parallel_Simulation gautier_niouzes
2013-02-26 7:09 ` Parallel_Simulation Vincent LAFAGE
4 siblings, 0 replies; 11+ messages in thread
From: Simon Wright @ 2013-02-25 21:04 UTC (permalink / raw)
Vincent LAFAGE <lafage@ipno.in2p3.fr> writes:
> But different seeds will in the end be different starting points along
> the same sequence (well, at least for congruential generators, I still
> have to confirm it for Mersenne Twister algorithm that is used). And
> this would in turn lead to fine correlations between the sequences.
That will be true whether you initialize with 1,2,3... or with clock
values. The only way to get truly different PRNGs must be to use
different algorithms, surely?
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Parallel_Simulation
2013-02-25 17:17 ` Parallel_Simulation Vincent LAFAGE
` (2 preceding siblings ...)
2013-02-25 21:04 ` Parallel_Simulation Simon Wright
@ 2013-02-25 21:40 ` gautier_niouzes
2013-02-26 7:09 ` Parallel_Simulation Vincent LAFAGE
4 siblings, 0 replies; 11+ messages in thread
From: gautier_niouzes @ 2013-02-25 21:40 UTC (permalink / raw)
> I understand that the sequence is long enough.
> But different seeds will in the end be different starting points along
> the same sequence
In that case it should not be an issue if the sequence is (much) longer than the number of workers times the number of MC simulations, should it ?
______________________________________________________________________________
Gautier's Ada programming -- http://gautiersblog.blogspot.com/search/label/Ada
NB: follow the above link for a valid e-mail address
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Parallel_Simulation
2013-02-25 17:17 ` Parallel_Simulation Vincent LAFAGE
` (3 preceding siblings ...)
2013-02-25 21:40 ` Parallel_Simulation gautier_niouzes
@ 2013-02-26 7:09 ` Vincent LAFAGE
2013-02-28 11:47 ` Parallel_Simulation John B. Matthews
4 siblings, 1 reply; 11+ messages in thread
From: Vincent LAFAGE @ 2013-02-26 7:09 UTC (permalink / raw)
Le 25/02/2013 18:17, Vincent LAFAGE a écrit :
> Le 25/02/2013 13:40, John B. Matthews a écrit :
>> In article <kgfdsp$tb0$1@ccpntc8.in2p3.fr>,
>> Vincent LAFAGE <lafage@ipno.in2p3.fr> wrote:
>>
>>> I am interested in MonteCarlo simulation and I had translated a
>>> former F77 code to Ada with success, with the goal of parallelizing
>>> it, but one part in the algorithm still resists parallelization: the
>>> random number generator. I need the different worker to rely on
>>> independant random number generators.
>>>
>>> Then I found a precious example in
>>> RM-A-5-2 59., 60., 61.
>>> that compiles smoothly.
>>>
>>> I will now attempt to check the independance of the sequence
>>> generated by each thread. But this kind of check is always more
>>> subtle than expected.
>>>
>>> I wonder whether there is a statement about the independance of such
>>> generator, in particular in the gnat implementation?
>>
>> You should check your implementation's required documentation and any
>> statements on implementation advice. For example, GNAT includes a
>> comment in Ada.Numerics.Float_Random.ads, and the GNAT Reference Manual
>> says, "The generator period is sufficiently long for the first condition
>> here [A.5.2(47)] to hold true."
>
> Thanks for the advice,
> but the particular doesn't exactly fit my question.
Ooups...
Sorry I hastened to answer while I had not read carefully enough
A.5.2(47)
47. If the generator period is sufficiently long in relation to the
number of distinct initiator values, then each possible value of
Initiator passed to Reset should initiate a sequence of random
numbers that does not, in a practical sense, overlap the sequence
initiated by any other value. If this is not possible, then the
mapping between initiator values and generator states should be a
rapidly varying function of the initiator value.
I see the statement, but while Mersenne Twister algorithms provides
very, very long period (2^19937?), I would appreciate order of
magnitudes of the subperiods.
I guess I have to test,
And read much more m(__)m
Best regards
> I understand that the sequence is long enough.
> But different seeds will in the end be different starting points along
> the same sequence (well, at least for congruential generators, I still
> have to confirm it for Mersenne Twister algorithm that is used).
> And this would in turn lead to fine correlations between the sequences.
>
> The best statement I have found until now is in gnat_rm-4.6.info:
>
> *67*. The minimum time interval between calls to the time-dependent
> Reset procedure that are guaranteed to initiate different random number
> sequences. See A.5.2(45).
> The minimum period between reset calls to guarantee distinct series
> of random numbers is one microsecond.
>
> So I need to assert the delay between the reset of each worker in
> RM-A-5-2 60.
> to be sure that there is at least one microsecond.
>
> Would you think of another way?
>
> Best regards
> Vincent
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Parallel_Simulation
2013-02-26 7:09 ` Parallel_Simulation Vincent LAFAGE
@ 2013-02-28 11:47 ` John B. Matthews
0 siblings, 0 replies; 11+ messages in thread
From: John B. Matthews @ 2013-02-28 11:47 UTC (permalink / raw)
In article <kghn3m$36m$1@ccpntc8.in2p3.fr>,
Vincent LAFAGE <lafage@ipno.in2p3.fr> wrote:
> Sorry I hastened to answer while I had not read carefully enough
> A.5.2(47)
>
> 47. If the generator period is sufficiently long in relation to the
> number of distinct initiator values, then each possible value of
> Initiator passed to Reset should initiate a sequence of random
> numbers that does not, in a practical sense, overlap the
> sequence initiated by any other value. If this is not possible,
> then the mapping between initiator values and generator states
> should be a rapidly varying function of the initiator value.
>
> I see the statement, but while Mersenne Twister algorithms provides
> very, very long period (2^19937?), I would appreciate order of
> magnitudes of the subperiods.
I'm guessing that no overlap "in a practical sense" is based on the
very low probability:
<http://www.johndcook.com/blog/2012/04/16/random-number-sequence-overlap/>
> I guess I have to test,
> And read much more m(__)m
--
John B. Matthews
trashgod at gmail dot com
<http://sites.google.com/site/drjohnbmatthews>
^ permalink raw reply [flat|nested] 11+ messages in thread