node38.html

Design and building parallel program

bidirectional multistage network constructed from 4 <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img726.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img726.gif"> 4
crossbars
<A NAME=4371>&#160;</A>
(a modified 4-ary <em> n</em>
-fly) similar to that illustrated in
Figure <A HREF="node33.html#figperfx" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node33.html#figperfx">3.18</A>.  Seitz [<A HREF="node132.html#Seitz1" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Seitz1">253</A>,<A HREF="node132.html#Seitz" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Seitz">255</A>] provides an
introduction to multicomputers and their interconnection networks.
Dally [<A HREF="node132.html#Dally" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Dally">69</A>] discusses networks and the concept of bisection
<A NAME=4376>&#160;</A>
width, while Leighton [<A HREF="node132.html#Leighton" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Leighton">187</A>] provides a more detailed and
theoretical treatment.  Dally and Seitz [<A HREF="node132.html#Dally1" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Dally1">70</A>,<A HREF="node132.html#Dally2" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Dally2">71</A>] discuss
routing techniques.  The material in Example <A HREF="node33.html#experfbfly" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node33.html#experfbfly">3.8</A> is
based on work by Foster and Worley [<A HREF="node132.html#FW" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#FW">110</A>].  Ethernet was designed
by Metcalfe and
<A NAME=4381>&#160;</A>
Boggs [<A HREF="node132.html#MB76" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#MB76">205</A>]; Shoch, Dalal, and Redell [<A HREF="node132.html#SDR" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#SDR">257</A>] describe its
evolution.
<P>
<A NAME=4384>&#160;</A>
Miller and Katz [<A HREF="node132.html#Miller91a" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Miller91a">208</A>], Foster, Henderson, and
Stevens [<A HREF="node132.html#fosterclimate" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#fosterclimate">103</A>], and Pool et al. [<A HREF="node132.html#IOPool" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#IOPool">229</A>] discuss
<A NAME=4388>&#160;</A>
the I/O requirements of scientific and engineering applications.  Del
Rosario and Choudhary [<A HREF="node132.html#dC94" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#dC94">76</A>] discuss problems and prospects for
parallel I/O.  Henderson, Nickless, and Stevens [<A HREF="node132.html#HNS94" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#HNS94">145</A>] discuss
application I/O requirements and describe a flexible I/O architecture
for parallel computers.  Plank and Li [<A HREF="node132.html#PL94" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#PL94">228</A>] discuss
checkpointing.  Bordawekar, del Rosario, and
<A NAME=4392>&#160;</A>
Choudhary [<A HREF="node132.html#BoRCmappingIO" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#BoRCmappingIO">41</A>] explain the utility of a two-phase I/O
strategy.  A special issue of the <em> Journal of Parallel and
Distributed Computing</em> [<A HREF="node132.html#JPDC" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#JPDC">60</A>] discusses various aspects of
parallel I/O, as do Aggarwal and Vitter [<A HREF="node132.html#aggarwalsorting" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#aggarwalsorting">4</A>] and
Katz, Gibson, and Patterson [<A HREF="node132.html#katzdiskarch" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#katzdiskarch">168</A>].  DeWitt and
<A NAME=4398>&#160;</A>
Gray [<A HREF="node132.html#dewittpardbs" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#dewittpardbs">79</A>] discuss parallel database machines.
<A NAME=4400>&#160;</A>
Gibson [<A HREF="node132.html#gibsonbook" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#gibsonbook">120</A>] examines the design and performance analysis
of redundant disk arrays (RAID disks).  Hennessy and
Patterson [<A HREF="node132.html#HP90" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#HP90">134</A>] provide a good description of I/O system
performance analysis and design.
<P>
The parallel versions of Floyd's shortest-path
algorithm [<A HREF="node132.html#Floyd62" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Floyd62">98</A>] are due to Jenq and Sahni [<A HREF="node132.html#Jenq" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Jenq">158</A>], while
the parallel version of Dijkstra's single-source
algorithm [<A HREF="node132.html#Dijkstra59" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Dijkstra59">80</A>] is described by Paige and
Kruskal [<A HREF="node132.html#Paige" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Paige">217</A>].  Our analysis of these algorithms follows Kumar
and Singh [<A HREF="node132.html#KumarS" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#KumarS">182</A>], who also present analyses that take into
account bandwidth limitations on hypercube and two-dimensional mesh
architectures.  Bertsekas and Tsitsiklis [<A HREF="node132.html#BT89" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#BT89">35</A>] describe a
pipelined variant of Floyd 2 that improves performance by allowing
iterations to proceed concurrently, subject only to dataflow
constraints.  Aho, Hopcroft, and Ullman [<A HREF="node132.html#AHU" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#AHU">7</A>] and Cormen,
Leiserson, and Rivest [<A HREF="node132.html#Cormen" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Cormen">65</A>] provide good introductions to
sequential graph algorithms.  Quinn and Deo [<A HREF="node132.html#QD84" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#QD84">236</A>] and Das, Deo,
and Prasad [<A HREF="node132.html#Das1" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Das1">73</A>,<A HREF="node132.html#Das2" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Das2">74</A>] describe parallel graph algorithms.  Ranka
and Sahni's [<A HREF="node132.html#RS90" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#RS90">238</A>] book on parallel algorithms for image
processing and pattern recognition includes relevant material.
<P>


<P>

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

providing access to additional information on performance analysis and
the architecture and performance of parallel and distributed computer
systems.
<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=tex2html2309 HREF="node37.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node37.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=tex2html2315 HREF="node39.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node39.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=tex2html2313 HREF="node26.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node26.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=tex2html2317 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=tex2html2318 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=tex2html2316 HREF="node39.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node39.html">4 Putting Components Together</A>
<B>Up:</B> <A NAME=tex2html2314 HREF="node26.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node26.html">3 A Quantitative Basis for Design</A>
<B> Previous:</B> <A NAME=tex2html2310 HREF="node37.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node37.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>