📄 node38.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=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>
<H1><A NAME=SECTION024120000000000000000> Chapter Notes</A></H1>
<P>
<A NAME=4315> </A>
The observation commonly referred to as Amdahl's law was first
<A NAME=4316> </A>
formulated in [<A HREF="node132.html#Amdahl" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Amdahl">12</A>]. Asymptotic analysis of parallel
<A NAME=4318> </A>
algorithms is discussed in many computer science texts, such as those
by Akl [<A HREF="node132.html#Akl89" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Akl89">8</A>], Leighton [<A HREF="node132.html#Leighton" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Leighton">187</A>], and Smith [<A HREF="node132.html#Smi93" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Smi93">267</A>].
Cook [<A HREF="node132.html#Cook" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Cook">64</A>] discusses problems for which no efficient parallel
algorithms have been discovered.
<P>
Many different approaches to performance modeling have been proposed,
each appropriate for different purposes. See, for example, the papers
by Culler et al. [<A HREF="node132.html#C93" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#C93">67</A>], Eager et al. [<A HREF="node132.html#EZL89" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#EZL89">89</A>], Flatt and
Kennedy [<A HREF="node132.html#FK89" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#FK89">97</A>], Karp and Flatt [<A HREF="node132.html#KF90" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#KF90">167</A>], and Nussbaum and
Agarwal [<A HREF="node132.html#NA91" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#NA91">216</A>]. Patel [<A HREF="node132.html#Patel" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Patel">224</A>] discusses the modeling of
shared-memory computers. The book by Kumar et
<A NAME=4329> </A>
al. [<A HREF="node132.html#Kumar93" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Kumar93">179</A>] provides many example models and a more detailed
treatment of the concept of isoefficiency. Gustafson et
<A NAME=4331> </A>
al. [<A HREF="node132.html#Gus88" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Gus88">129</A>,<A HREF="node132.html#GMB88" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#GMB88">130</A>] introduce the concept of scaled speedup.
Singh, Hennessy, and Gupta [<A HREF="node132.html#SHG93" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#SHG93">259</A>], Sun and Ni [<A HREF="node132.html#SN93" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#SN93">274</A>], and
Worley [<A HREF="node132.html#Wor90" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Wor90">297</A>,<A HREF="node132.html#Wor91" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Wor91">298</A>] discuss various constraints on the
scalability of parallel programs. Lai and Sahni [<A HREF="node132.html#LS84" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#LS84">183</A>] and Quinn
and Deo [<A HREF="node132.html#QD86" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#QD86">237</A>] discuss speedup anomalies in search problems.
<A NAME=4338> </A>
Faber et al. [<A HREF="node132.html#FUW" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#FUW">93</A>] argue against the concept of superlinear
<A NAME=4340> </A>
speedup. Fromm et al. [<A HREF="node132.html#FHH83" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#FHH83">115</A>], Harrison and Patel [<A HREF="node132.html#HP90" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#HP90">134</A>],
<A NAME=4343> </A>
and Thomasian and Bay [<A HREF="node132.html#TB86" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#TB86">284</A>] use queuing models to study
performance of parallel systems. Kleinrock [<A HREF="node132.html#Klein" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Klein">173</A>] reviews
techniques used for performance analysis of networks and discusses
issues that arise in high-speed (gigabit/sec) WANs.
<P>
The chapter notes in Chapter <A HREF="node6.html#chap1" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node6.html#chap1">1</A> provide references on
<A NAME=4347> </A>
parallel computer architecture. Feng [<A HREF="node132.html#Fen81" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Fen81">94</A>] provides a tutorial
on interconnection networks. Hypercube networks have been used in a
<A NAME=4349> </A>
variety of multicomputers such as the Cosmic Cube [<A HREF="node132.html#Cosmic" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Cosmic">254</A>],
<A NAME=4351> </A>
nCUBE-2 [<A HREF="node132.html#nCU90" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#nCU90">212</A>],
<A NAME=4353> </A>
Intel iPSC,
<A NAME=4354> </A>
and Thinking Machines
<A NAME=4355> </A>
CM2 [<A HREF="node132.html#Thi90a" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Thi90a">281</A>]. The Intel DELTA and Intel Paragon [<A HREF="node132.html#Sup91" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Sup91">276</A>] use
<A NAME=4358> </A>
two-dimensional mesh networks. The Cray T3D and MIT
<A NAME=4359> </A>
J machine [<A HREF="node132.html#D92" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#D92">72</A>] use a three-dimensional torus. Adams, Agrawal,
<A NAME=4361> </A>
and Siegel [<A HREF="node132.html#AAS87" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#AAS87">2</A>] survey multistage interconnection networks,
and Harrison [<A HREF="node132.html#Harrison2" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Harrison2">133</A>] discusses the analytic modeling of these
networks. Various forms of multistage network have been used in the
<A NAME=4364> </A>
BBN Butterfly [<A HREF="node132.html#BBN89" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#BBN89">31</A>], NYU Ultracomputer [<A HREF="node132.html#GGK83" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#GGK83">123</A>], IBM
<A NAME=4367> </A>
RP3 [<A HREF="node132.html#PBG85" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#PBG85">226</A>], and IBM SP [<A HREF="node132.html#S94" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#S94">271</A>]. The IBM SP uses a
<A NAME=4370> </A>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -