node10.html

Design and building parallel program

(Figure <A HREF="node10.html#fignb" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node10.html#fignb">1.12</A>(a)).  Hence, each task has one inport and one
outport.  Each task first initializes both a buffer (with the value of
its local datum) and an accumulator that will maintain the result of
the computation.  It then repeatedly
<OL><LI>
sends the value contained in its buffer on its outport,
<LI>
receives a datum on its inport into its buffer,
<LI>
computes the interaction between this datum and its local datum, and
<LI>
uses the computed interaction to update its local accumulator.
</OL>
This send-receive-compute cycle is repeated <em> N-1</em>
 times, causing
the <em> N</em>
 data to flow around the ring.  Every task sees every datum
and is able to compute all <em> N-1</em>
 interactions involving its datum.
The algorithm involves <em> N-1</em>
 communications per task.
<P>
It turns out that if interactions are symmetric, we can halve both the
number of interactions computed and the number of communications by
refining the communication structure.  Assume for simplicity that
<em> N</em>
 is odd.  An additional <em> N</em>
 communication channels are
created, linking each task to the task offset <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img134.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img134.gif">
around the ring (Figure <A HREF="node10.html#fignb" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node10.html#fignb">1.12</A>(b)).  Each time an interaction
<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img135.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img135.gif"> is computed between a local datum <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img136.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img136.gif"> and an incoming
datum <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img137.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img137.gif">, this value is accumulated not only in the accumulator for
<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img138.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img138.gif"> but also in another accumulator that is circulated with <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img139.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img139.gif">.
After <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img140.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img140.gif"> steps, the accumulators associated with the
circulated values are returned to their home task using the new
channels and combined with the local accumulators.  Hence, each
symmetric interaction is computed only once: either as <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img141.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img141.gif"> on
the node that holds <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img142.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img142.gif"> or as <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img143.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img143.gif"> on the node that holds
<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img144.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img144.gif">.
<P>
<A NAME=608>&#160;</A>
<P>
<H2><A NAME=SECTION02243000000000000000>1.4.3 Search</A></H2>
<P>
<A NAME=exsearch1>&#160;</A>
<P>
<A NAME=611>&#160;</A>
The next example illustrates the dynamic creation of tasks and
channels during program execution.  Algorithm <A HREF="node10.html#algsearch" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node10.html#algsearch">1.1</A>
explores a search tree looking for nodes that correspond to
``solutions.''  A parallel algorithm for this problem can be
structured as follows.  Initially, a single task is created for the
root of the tree.  A task evaluates its node and then, if that node is
not a solution, creates a new task for each <tt> search</tt> call
(subtree).  A channel created for each new task is used to return to
the new task's parent any solutions located in its subtree.  Hence,
new tasks and channels are created in a wavefront as the search
progresses down the search tree (Figure <A HREF="node10.html#figtree" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node10.html#figtree">1.13</A>).
<P>
<P><A NAME=algsearch>&#160;</A><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img145.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img145.gif"><P>
<P>
<P><A NAME=1054>&#160;</A><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img146.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img146.gif">
<BR><STRONG>Figure 1.13:</STRONG> <em> Task structure for the search example.  Each circle
represents a node in the search tree and hence a call to the <tt>
search</tt> procedure.  A task is created for each node in the tree as it
is explored.  At any one time, some tasks are actively engaged in
expanding the tree further (these are shaded in the figure); others
have reached solution nodes and are terminating, or are waiting for
their offspring to report back with solutions.  The lines represent
the channels used to return solutions.</em><A NAME=figtree>&#160;</A><BR>
<P><H2><A NAME=SECTION02244000000000000000>1.4.4 Parameter Study</A></H2>
<P>
<A NAME=exdatabase>&#160;</A>
<P>
<A NAME=625>&#160;</A>
In so-called embarrassingly parallel problems, a computation
consists of a number of tasks that can execute more or less
independently, without communication.  These problems are usually easy
to adapt for parallel execution.  An example is a parameter study,
in which the same computation must be performed using a range of
<A NAME=626>&#160;</A>
different input parameters.  The parameter values are read from an
input file, and the results of the different computations are written
to an output file.
<P>
<P><A NAME=1071>&#160;</A><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img147.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img147.gif">
<BR><STRONG>Figure 1.14:</STRONG> <em> Task structure for parameter study problem.  Workers (W)
request parameters from the input task (I) and send results to the
<A NAME=1065>&#160;</A>
output task (O).  Note the many-to-one connections: this program is
<A NAME=1066>&#160;</A>
nondeterministic in that the input and output tasks receive data from
workers in whatever order the data are generated.  Reply channels,
represented as dashed lines, are used to communicate parameters from
the input task to workers.</em><A NAME=figmerge>&#160;</A><BR>
<P>
<P>
If the execution time per problem is constant and each processor has
the same computational power, then it suffices to partition available
problems into equal-sized sets and allocate one such set to each
processor.  In other situations, we may choose to use the task
structure illustrated in Figure <A HREF="node10.html#figmerge" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node10.html#figmerge">1.14</A>.  The input and output
tasks are responsible for reading and writing the input and output
files, respectively.  Each worker task (typically one per processor)
repeatedly requests parameter values from the input task, computes
using these values, and sends results to the output task.  Because
execution times vary, the input and output tasks cannot expect to
receive messages from the various workers in any particular order.
Instead, a many-to-one communication structure is used that allows
them to receive messages from the various workers in arrival order.
<P>
The input task responds to a worker request by sending a parameter to
that worker.  Hence, a worker that has sent a request to the input
task simply waits for the parameter to arrive on its reply channel.
<A NAME=633>&#160;</A>
In some cases, efficiency can be improved by <em> prefetching
 </em>,
<A NAME=635>&#160;</A>
that is, requesting the next parameter before it is needed.  The
worker can then perform computation while its request is being
processed by the input task.
<P>
<A NAME=636>&#160;</A>
Because this program uses many-to-one communication structures, the
order in which computations are performed is not necessarily
determined.  However, this nondeterminism affects only the allocation
of problems to workers and the ordering of results in the output file,
not the actual results computed.
<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=tex2html1954 HREF="node9.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node9.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=tex2html1962 HREF="node11.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node11.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=tex2html1960 HREF="node6.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node6.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=tex2html1964 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=tex2html1965 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=tex2html1963 HREF="node11.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node11.html">1.5 Summary</A>
<B>Up:</B> <A NAME=tex2html1961 HREF="node6.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node6.html">1 Parallel Computers and Computation</A>
<B> Previous:</B> <A NAME=tex2html1955 HREF="node9.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node9.html">1.3 A Parallel Programming Model</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>