📄 node25.html
字号:
<html><!DOCTYPE HTML PUBLIC "-//W3O//DTD W3 HTML 2.0//EN">
<!Converted with LaTeX2HTML 95.1 (Fri Jan 20 1995) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds >
<HEAD>
<TITLE> Chapter Notes</TITLE>
</HEAD>
<BODY>
<meta name="description" value=" Chapter Notes">
<meta name="keywords" value="book">
<meta name="resource-type" value="document">
<meta name="distribution" value="global">
<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=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>
<H1><A NAME=SECTION023110000000000000000> Chapter Notes</A></H1>
<P>
In this chapter, we have focused on the software engineering question
of developing a parallel algorithm design from a given problem
specification. We have assumed some familiarity with program
design---from, for example, previous study in sequential programming.
A classic article by Parnas and Clements [<A HREF="node132.html#Parnas4" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Parnas4">222</A>] describes the
benefits (and difficulties) of a rational design process. The chapter
notes in Chapters <A HREF="node26.html#chapperf" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node26.html#chapperf">3</A> and <A HREF="node39.html#chapmod" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node39.html#chapmod">4</A> provide
additional references to material on the related topics of performance
analysis and modularity.
<P>
Relatively few authors have addressed the particular problems that
arise when designing algorithms for realistic scalable parallel
computers. Numerous books discuss parallel algorithm design in the
<A NAME=2229> </A>
context of the idealized PRAM model; see, for example,
Akl [<A HREF="node132.html#Akl89" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Akl89">8</A>], Gibbons and Reitter [<A HREF="node132.html#GR90" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#GR90">119</A>], and
JáJá [<A HREF="node132.html#JaJa92" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#JaJa92">157</A>]. However, these techniques are for the
most part not directly applicable to multicomputers. The books by Fox
et al. [<A HREF="node132.html#Fox88" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Fox88">111</A>,<A HREF="node132.html#Fox94" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Fox94">113</A>] and Kumar et al. [<A HREF="node132.html#Kumar" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Kumar">181</A>] provide
relevant material. Carriero and
<A NAME=2237> </A>
Gelernter [<A HREF="node132.html#Linda" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Linda">48</A>] give an introduction to parallel program
design in the Linda language. They distinguish between agenda,
result, and specialist parallelism, which can be thought of as domain
decomposition and two different forms of functional parallelism,
respectively. See also the references in Chapter <A HREF="node131.html#chapbiblio" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node131.html#chapbiblio">12</A>.
<P>
<A NAME=2240> </A>
The mapping problem has received considerable attention in the
computer science and scientific computing literature. Bokhari shows
that it is <em> NP
</em>-complete [<A HREF="node132.html#Bokhari" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Bokhari">39</A>]. The recursive
<A NAME=2243> </A>
coordinate bisection algorithm is due to Berger and
Bokhari [<A HREF="node132.html#Bokhari2" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Bokhari2">33</A>], and the unbalanced recursive bisection
algorithm is due to Jones and Plassmann [<A HREF="node132.html#JP94" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#JP94">161</A>]. A related
algorithm is the recursive spectral bisection algorithm of Pothen,
<A NAME=2246> </A>
Simon, and Liou [<A HREF="node132.html#Pothen" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Pothen">230</A>], which uses connectivity information to
identify partitions of unstructured meshes with low communication
requirements, at the cost of an eigenvalue computation. This
algorithm has proven very effective, although more expensive than the
other recursive algorithms. Simon [<A HREF="node132.html#Simon" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Simon">258</A>] and
Williams [<A HREF="node132.html#Williams" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Williams">293</A>] compare different algorithms for partitioning
unstructured meshes, including coordinate bisection, graph bisection,
and spectral bisection. Barnard and Simon [<A HREF="node132.html#BS94" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#BS94">28</A>] describe a less
expensive multilevel version of spectral bisection. The mesh in
Figure <A HREF="node17.html#figfem" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node17.html#figfem">2.9</A> is generated using the finite octree technique of
Shephard and Georges [<A HREF="node132.html#Shep" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Shep">256</A>]. Fox et al. [<A HREF="node132.html#Fox88" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Fox88">111</A>] and Nicol
and Saltz [<A HREF="node132.html#nicolsaltz90" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#nicolsaltz90">213</A>] describe the use of cyclic
decompositions. Lin and Keller [<A HREF="node132.html#linkeller87" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#linkeller87">190</A>] describe a local
algorithm. The local algorithm described in the text is termed a <em>
<A NAME=2256> </A>
receiver-initiated
</em> strategy. In an alternative <em>
sender-initiated
</em> strategy, workers with excess work send it to
<A NAME=2258> </A>
other workers. Tantawi and Towsley [<A HREF="node132.html#TT85" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#TT85">279</A>] compare
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -