node119.html

Design and building parallel program

variant of the random tree method called the <em> leapfrog
 </em>
method can be used to generate sequences that can be guaranteed not to
overlap for a certain period.
<P>
Let <em> n</em>
 be the number of sequences required.  Then we
define <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img1085.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1085.gif"> and <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img1086.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1086.gif"> as <em> a</em>
 and <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1087.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1087.gif">, respectively, so that we
have
<P><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1088.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1088.gif"><P>
Then, we create <em> n</em>
 different right generators <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1089.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1089.gif">..<IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1090.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1090.gif"> by
taking the first <em> n</em>
 elements of <em> L</em>
 as their starting values.
The name ``leapfrog method'' refers to the fact that the <em> i</em>
th
sequence <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1091.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1091.gif"> consists of <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img1092.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1092.gif"> and every <em> n</em>
th subsequent
element of the sequence generated by <em> L</em>
 (Figure <A HREF="node119.html#figlat5" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node119.html#figlat5">10.2</A>).
As this method partitions the elements of <em> L</em>
, each subsequence
has a period of at least <em> P/n</em>
, where <em> P</em>
 is the period of
<em> L</em>
.  (If <em> n</em>
 divides <em> P</em>
, then the period of a
subsequence is exactly <em> P/n</em>
.)  In addition, the
<em> n</em>
 subsequences are disjoint for their first <em> P/n</em>
 elements.
<P>
<P><A NAME=14895>&#160;</A><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1093.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1093.gif">
<BR><STRONG>Figure 10.2:</STRONG> <em> The leapfrog method with <em> n=3</em>
.  Each of the three right
generators selects a disjoint subsequence of the sequence constructed
by the left generator's sequence.</em><A NAME=figlat5>&#160;</A><BR>
<P>
<P>
<A NAME=14731>&#160;</A>
<P>
The generator for the <em> r</em>
th subsequence, <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1094.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1094.gif">, is defined by
<IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1095.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1095.gif"> and <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img1096.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1096.gif">.  We can compute these values as follows.
We first compute <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1097.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1097.gif"> and <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1098.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1098.gif">; these computations can be performed
in <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img1099.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1099.gif"> time by taking advantage of the identity
<P><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1100.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1100.gif"><P>
We then compute members of the sequence <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1101.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1101.gif"> as follows, to obtain
<em> n</em>
 generators, each defined by a triple <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img1102.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1102.gif">, for <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img1103.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1103.gif">.
<P><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1104.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1104.gif"><P>
<P>
The leapfrog method can be applied recursively: the subsequence
corresponding to a generator <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img1105.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1105.gif"> can be further subdivided
by a second application of the leapfrog method.  Doing this can be
useful when random numbers are required at several levels in a task
hierarchy.  However, the periods of the resulting sequences become
shorter, and their statistical properties are less certain.
<P>
<H2><A NAME=SECTION04233000000000000000>10.3.3 Modified Leapfrog</A></H2>
<P>
In other situations, we may know the maximum number, <em> n</em>
, of
<A NAME=14750>&#160;</A>
random values needed in a subsequence but not the number of
<A NAME=14751>&#160;</A>
subsequences required.  In this case, a variant of the leapfrog method
can be used in which the role of <em> L</em>
 and <em> R</em>
 are reversed so
that the elements of subsequence <em> i</em>
 are the contiguous elements
<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img1106.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1106.gif">..<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img1107.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1107.gif"> (Figure <A HREF="node119.html#figml" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node119.html#figml">10.3</A>), as follows:
<P><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1108.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1108.gif"><P>
It is not a good idea to choose <em> n</em>
 as a power of two, as this can
lead to serious long-term correlations.
<P>
<P><A NAME=14920>&#160;</A><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1109.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1109.gif">
<BR><STRONG>Figure 10.3:</STRONG> <em> Modified leapfrog with <em> n=3</em>
.  Each subsequence contains
three contiguous numbers from the main
sequence.</em><A NAME=figml>&#160;</A><BR>
<P>
<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>
<P><ADDRESS>
<I>&#169 Copyright 1995 by <A href="msgs0.htm#6" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/tppmsgs/msgs0.htm#6">Ian Foster</a></I>
</ADDRESS>
</BODY>