node16.html

Design and building parallel program

be required to avoid replication of data.  This is often a sign that a
domain decomposition approach should be considered instead.
<P>
<A NAME=1133>&#160;</A>
While domain decomposition forms the foundation for most parallel
algorithms, functional decomposition is valuable as a different way of
thinking about problems.  For this reason alone, it should be
considered when exploring possible parallel algorithms.  A focus on
the computations that are to be performed can sometimes reveal
structure in a problem, and hence opportunities for optimization, that
would not be obvious from a study of data alone.
<P>
As an example of a problem for which functional decomposition is most
appropriate, consider Algorithm <A HREF="node10.html#algsearch" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node10.html#algsearch">1.1</A>.  This explores a
search tree looking for nodes that correspond to ``solutions.''  The
algorithm does not have any obvious data structure that can be
decomposed.  However, a fine-grained partition can be obtained as
described in Section <A HREF="node10.html#exsearch1" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node10.html#exsearch1">1.4.3</A>.  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 leaf, creates a new task for each <tt> search</tt>
call (subtree).  As illustrated in Figure <A HREF="node10.html#figtree" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node10.html#figtree">1.13</A>, new tasks
are created in a wavefront as the search tree is expanded.
<P>
<A NAME=1138>&#160;</A>
<P>
<P><A NAME=2389>&#160;</A><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img162.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img162.gif">
<BR><STRONG>Figure 2.3:</STRONG> <em> Functional decomposition in a computer model of
climate.  Each model component can be thought of as a separate task,
to be parallelized by domain decomposition.  Arrows represent
exchanges of data between components during computation: the
atmosphere model generates wind velocity data that are used by the
ocean model, the ocean model generates sea surface temperature data
that are used by the atmosphere model, and so on.</em><A NAME=figenv>&#160;</A><BR>
<P>
<P>
<A NAME=1143>&#160;</A>
Functional decomposition also has an important role to play as a
program structuring technique.  A functional decomposition that
partitions not only the computation that is to be performed but also
the code that performs that computation is likely to reduce the
complexity of the overall design.  This is often the case in computer
models of complex systems, which may be structured as collections of
simpler models connected via interfaces.  For example, a simulation of
<A NAME=1144>&#160;</A>
the earth's climate may comprise components representing the
atmosphere, ocean, hydrology, ice, carbon dioxide sources, and so on.
<A NAME=1145>&#160;</A>
While each component may be most naturally parallelized using domain
decomposition techniques, the parallel algorithm as a whole is simpler
if the system is first decomposed using functional decomposition
techniques, even though this process does not yield a large number of
tasks (Figure <A HREF="node16.html#figenv" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node16.html#figenv">2.3</A>).  This issue is explored in
Chapter <A HREF="node39.html#chapmod" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node39.html#chapmod">4</A>.
<A NAME=1148>&#160;</A>
<P>
<H2><A NAME=SECTION02323000000000000000>2.2.3 Partitioning Design Checklist</A></H2>
<P>
<A NAME=secrules1>&#160;</A>
<P>
<A NAME=1151>&#160;</A>
The partitioning phase of a design should produce one or more possible
<A NAME=1152>&#160;</A>
decompositions of a problem.  Before proceeding to evaluate
communication requirements, we use the following checklist to ensure
that the design has no obvious flaws.  Generally, all these questions
should be answered in the affirmative.
<P>
<OL><LI>
Does your partition define at least an order of magnitude more tasks
than there are processors in your target computer?  If not, you
have little flexibility in subsequent design stages.
<P>
<LI>
Does your partition avoid redundant computation and storage
requirements?  If not, the resulting algorithm may not be scalable to
deal with large problems.
<P>
<LI>
Are tasks of comparable size?  If not, it may be hard to
allocate each processor equal amounts of work.
<P>
<LI>
Does the number of tasks scale with problem size?  Ideally, an
increase in problem size should increase the number of tasks rather
than the size of individual tasks.  If this is not the case, your
parallel algorithm may not be able to solve larger problems when more
processors are available.
<P>
<LI>
Have you identified several alternative partitions?  You can maximize
flexibility in subsequent design stages by considering alternatives
now.  Remember to investigate both domain and functional
decompositions.
<P>
</OL>
<P>
Answers to these questions may suggest that, despite careful thought
in this and subsequent design stages, we have a ``bad'' design.  In
this situation it is risky simply to push ahead with implementation.
We should use the performance evaluation techniques described in
Chapter <A HREF="node26.html#chapperf" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node26.html#chapperf">3</A> to determine whether the design meets our
performance goals despite its apparent deficiencies.  We may also wish
to revisit the problem specification.  Particularly in science and
engineering applications, where the problem to be solved may involve a
simulation of a complex physical process, the approximations and
numerical techniques used to develop the simulation can strongly
influence the ease of parallel implementation.  In some cases, optimal
sequential and parallel solutions to the same problem may use quite
different solution techniques.  While detailed discussion of these
issues is beyond the scope of this book, we present several
illustrative examples of them later in this chapter.
<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=tex2html2035 HREF="node15.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node15.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=tex2html2043 HREF="node17.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node17.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=tex2html2041 HREF="node14.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node14.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=tex2html2045 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=tex2html2046 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=tex2html2044 HREF="node17.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node17.html">2.3 Communication</A>
<B>Up:</B> <A NAME=tex2html2042 HREF="node14.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node14.html">2 Designing Parallel Algorithms</A>
<B> Previous:</B> <A NAME=tex2html2036 HREF="node15.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node15.html">2.1 Methodical Design</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>