📄 node119.html
字号:
<html><!DOCTYPE HTML PUBLIC "-//W3O//DTD W3 HTML 2.0//EN">
<!Converted with LaTeX2HTML 95.1 (Fri Jan 20 1995) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds >
<HEAD>
<TITLE>10.3 Distributed Random Generators</TITLE>
</HEAD>
<BODY>
<meta name="description" value="10.3 Distributed Random Generators">
<meta name="keywords" value="book">
<meta name="resource-type" value="document">
<meta name="distribution" value="global">
<P>
<BR> <HR><a href="msgs0.htm#2" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/tppmsgs/msgs0.htm#2"><img ALIGN=MIDDLE src="asm_color_tiny.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/asm_color_tiny.gif" alt="[DBPP]"></a> <A NAME=tex2html3417 HREF="node118.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node118.html"><IMG ALIGN=MIDDLE ALT="previous" SRC="previous_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/previous_motif.gif"></A> <A NAME=tex2html3425 HREF="node120.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node120.html"><IMG ALIGN=MIDDLE ALT="next" SRC="next_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/next_motif.gif"></A> <A NAME=tex2html3423 HREF="node116.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node116.html"><IMG ALIGN=MIDDLE ALT="up" SRC="up_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/up_motif.gif"></A> <A NAME=tex2html3427 HREF="node1.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node1.html"><IMG ALIGN=MIDDLE ALT="contents" SRC="contents_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/contents_motif.gif"></A> <A NAME=tex2html3428 HREF="node133.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node133.html"><IMG ALIGN=MIDDLE ALT="index" SRC="index_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/index_motif.gif"></A> <a href="msgs0.htm#3" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/tppmsgs/msgs0.htm#3"><img ALIGN=MIDDLE src="search_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/search_motif.gif" alt="[Search]"></a> <BR>
<B> Next:</B> <A NAME=tex2html3426 HREF="node120.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node120.html">10.4 Summary</A>
<B>Up:</B> <A NAME=tex2html3424 HREF="node116.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node116.html">10 Random Numbers</A>
<B> Previous:</B> <A NAME=tex2html3418 HREF="node118.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node118.html">10.2 Parallel Random Numbers</A>
<BR><HR><P>
<H1><A NAME=SECTION04230000000000000000>10.3 Distributed Random Generators</A></H1>
<P>
The techniques described here for constructing distributed random
<A NAME=14665> </A>
number generators are based on an adaptation of the linear
congruential algorithm called the <em> random tree
</em> method. We
first show how this method can be applied to a single generator to
construct a tree of generators in a deterministic and reproducible
fashion. This facility is particularly valuable in computations that
create and destroy tasks dynamically during program execution.
<P>
<H2><A NAME=SECTION04231000000000000000>10.3.1 The Random Tree Method</A></H2>
<P>
The random tree method employs two linear congruential generators,
<A NAME=14668> </A>
<em> L</em>
and <em> R</em>
, that differ only in the values used for
<A NAME=14671> </A>
<em> a</em>
.
<P><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1079.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1079.gif"><P>
<P>
<P><A NAME=14849> </A><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1080.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1080.gif">
<BR><STRONG>Figure 10.1:</STRONG> <em> The random tree method. Two generators are
used to construct a tree of random numbers. The right generator is
applied to elements of the sequence <em> L</em>
generated by the left
generator to generate new sequences <em> R</em>
, <em> R'</em>
,
<em> R''</em>
, etc.</em><A NAME=figlat3> </A><BR>
<P>
<P>
<A NAME=14686> </A>
Application of the left generator <em> L</em>
to a seed <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img1081.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1081.gif"> generates
one random sequence; application of the right generator <em> R</em>
to the
same seed generates a different sequence. By applying the right
generator to elements of the left generator's sequence (or vice
versa), a tree of random numbers can be generated. By convention, the
right generator <em> R</em>
is used to generate random values for use in
computation, while the left generator <em> L</em>
is applied to values
computed by <em> R</em>
to obtain the starting points <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1082.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1082.gif">, <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1083.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1083.gif">, etc.,
for new right sequences (Figure <A HREF="node119.html#figlat3" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node119.html#figlat3">10.1</A>).
<P>
The strength of the random tree method is that it can be used to
<A NAME=14693> </A>
generate new random sequences in a reproducible and noncentralized
fashion. This is valuable, for example, in applications in which new
tasks and hence new random generators must be created dynamically.
Before creating a new task, a parent task uses the left generator to
construct a new right generator, which it passes to its new offspring.
The new task uses this right generator to generate the random numbers
required for its computation. If it in turn must generate a new task,
it can apply the left generator to its latest random value to obtain a
new random seed.
<P>
A deficiency of the random tree method as described here is that there
is no guarantee that different right sequences will not overlap. The
period of <em> R</em>
is usually chosen to be near to <em> m</em>
, because
this maximizes the quality of the random numbers obtained by using the
generator. Hence, the starting points <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1084.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1084.gif"> returned by the left
generator are likely to be different points in the same sequence, in
which case we can think of <em> L</em>
as selecting random starting points
in the sequence constructed by <em> R</em>
. If two starting points happen
to be close to each other, the two right sequences that are generated
will be highly correlated.
<P>
<H2><A NAME=SECTION04232000000000000000>10.3.2 The Leapfrog Method</A></H2>
<P>
In some circumstances, we may know that a program requires a fixed
number of generators. (For example, we may require one generator for
<A NAME=14699> </A>
each task in a domain decomposition algorithm.) In this case, a
<A NAME=14700> </A>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -