node25.html

Design and building parallel program

sender-initiated and receiver-initiated strategies and show that the
former gives better performance if workers are often idle and that
the latter performs better when load is heavy.  Other relevant papers
include those by Berman and Snyder [<A HREF="node132.html#BS87" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#BS87">34</A>];
Chowdhury [<A HREF="node132.html#chowdhury90" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#chowdhury90">61</A>]; Cybenko [<A HREF="node132.html#Cyb89" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Cyb89">68</A>]; Hac [<A HREF="node132.html#Hac89" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Hac89">131</A>];
Heath, Rosenberg, and Smith [<A HREF="node132.html#HRS88" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#HRS88">141</A>]; Kumar, Grama, and
Rao [<A HREF="node132.html#KGR94" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#KGR94">180</A>]; Lo [<A HREF="node132.html#Lo88" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Lo88">191</A>]; and Sadayappan and
Ercal [<A HREF="node132.html#SE87" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#SE87">250</A>].  Dijkstra, Feijen, and Gasteren [<A HREF="node132.html#DSG83" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#DSG83">81</A>],
Rokusawa et al. [<A HREF="node132.html#RICN88" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#RICN88">246</A>], and Kumar et al. [<A HREF="node132.html#Kumar93" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Kumar93">179</A>] describe
distributed termination-detection algorithms.
<A NAME=2271>&#160;</A>
<P>
Real atmosphere models are of course more complex than the system
considered in Section <A HREF="node20.html#secclim" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node20.html#secclim">2.6</A>.  Washington and
Parkinson [<A HREF="node132.html#Wash" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Wash">292</A>] provide a good introduction to the numerical
methods and algorithms used in climate modeling on sequential
<A NAME=2274>&#160;</A>
computers.  A workshop held at the European Center for Medium-range
Weather Forecasting surveyed issues involved in executing weather and
climate models on parallel computers [<A HREF="node132.html#ECMWF2" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#ECMWF2">155</A>].  The parallel
version of the Community Climate Model is described by Drake et
al. [<A HREF="node132.html#Drake" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Drake">86</A>].  Michalakes [<A HREF="node132.html#Mich" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Mich">206</A>] analyzes load imbalances in
climate models and Foster and Toonen [<A HREF="node132.html#FosterToonen" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#FosterToonen">109</A>] describe
load-balancing algorithms.
<P>
Banerjee [<A HREF="node132.html#Banerjee" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Banerjee">26</A>] describes parallel algorithms for VLSI
<A NAME=2280>&#160;</A>
design.  Wimer et al. [<A HREF="node132.html#Wimer2" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Wimer2">294</A>] and Arvindam et
al. [<A HREF="node132.html#Arvindam" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Arvindam">17</A>] describe branch-and-bound search algorithms and
<A NAME=2283>&#160;</A>
domain-specific optimizations that can improve performance on
floorplanning problems.  Reinefeld and Schnecke [<A HREF="node132.html#RS94" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#RS94">243</A>] describe
the algorithm variant in which workers redundantly expand several tree
levels before selecting nodes for local expansion.  Kumar et
al. [<A HREF="node132.html#Kumar93" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Kumar93">179</A>,<A HREF="node132.html#Kumar" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Kumar">181</A>,<A HREF="node132.html#Rao" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Rao">239</A>] provide a wealth of material on the
design, implementation, and analysis of parallel search algorithms.
<A NAME=2286>&#160;</A>
Quinn [<A HREF="node132.html#Quinn" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Quinn">234</A>] also examines branch-and-bound search and describes
<A NAME=2288>&#160;</A>
and analyzes the performance of four different load balancing
strategies.  For a general introduction to search algorithms, see
Nilsson [<A HREF="node132.html#Nil80" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Nil80">214</A>], Pearl [<A HREF="node132.html#Pea84" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Pea84">225</A>], and Kumar and
Kanal [<A HREF="node132.html#KK88" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#KK88">164</A>].
<P>
Hehre et al. [<A HREF="node132.html#Hehre" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Hehre">142</A>] provide an introduction to <em> ab
<A NAME=2293>&#160;</A>
initio
 </em> quantum 
<A NAME=2294>&#160;</A>
chemistry.  Feyereisen and Kendall [<A HREF="node132.html#FK91" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#FK91">96</A>] describe a replicated
data algorithm for the Fock matrix construction problem.  Colvin et
al. [<A HREF="node132.html#Colvin" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Colvin">62</A>] describe an algorithm based on domain decomposition
techniques.  An algorithm that uses distributed data structures and a
centralized task scheduler is described by Harrison et
al. [<A HREF="node132.html#Tilson" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Tilson">108</A>,<A HREF="node132.html#Harrison" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Harrison">135</A>].
<P>


<P>

Here is a
<A HREF="msgs0.htm#8" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/tppmsgs/msgs0.htm#8">Web Tour</A>

providing access to additional information on parallel program design
and software engineering.
<P>
<A NAME=4421>&#160;</A>
<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=tex2html2143 HREF="node24.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node24.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=tex2html2149 HREF="node26.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node26.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=tex2html2147 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=tex2html2151 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=tex2html2152 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=tex2html2150 HREF="node26.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node26.html">3 A Quantitative Basis for Design</A>
<B>Up:</B> <A NAME=tex2html2148 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=tex2html2144 HREF="node24.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node24.html"> Exercises</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>