📄 node13.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=tex2html1990 HREF="node12.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node12.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=tex2html1996 HREF="node14.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node14.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=tex2html1994 HREF="node6.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node6.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=tex2html1998 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=tex2html1999 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=tex2html1997 HREF="node14.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node14.html">2 Designing Parallel Algorithms</A>
<B>Up:</B> <A NAME=tex2html1995 HREF="node6.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node6.html">1 Parallel Computers and Computation</A>
<B> Previous:</B> <A NAME=tex2html1991 HREF="node12.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node12.html"> Exercises</A>
<BR><HR><P>
<H1><A NAME=SECTION02270000000000000000> Chapter Notes</A></H1>
<P>
Kauffman and Smarr [<A HREF="node132.html#KS93" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#KS93">169</A>] discuss the impact of high-performance
computing on science. Levin [<A HREF="node132.html#Levin" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Levin">189</A>] and several U.S. government
reports [<A HREF="node132.html#Pre87" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Pre87">232</A>,<A HREF="node132.html#Pre89" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Pre89">233</A>,<A HREF="node132.html#NSF91" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#NSF91">215</A>] describe the so-called Grand
<A NAME=693> </A>
Challenge problems that have motivated recent initiatives in
high-performance computing. The computational requirements in
Table <A HREF="node7.html#tabchammp" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node7.html#tabchammp">1.1</A> are derived from the project plan for the
<A NAME=695> </A>
CHAMMP climate modeling program, which has adapted a range of climate
models for execution on parallel computers [<A HREF="node132.html#DOE1" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#DOE1">287</A>]. Dewitt and
<A NAME=697> </A>
Gray [<A HREF="node132.html#dewittpardbs" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#dewittpardbs">79</A>] discuss developments in parallel databases.
<A NAME=699> </A>
Lawson [<A HREF="node132.html#Lawson" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Lawson">186</A>] discusses industrial real-time applications of
parallel computing. Worlton [<A HREF="node132.html#Worlton" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Worlton">299</A>], Meindl [<A HREF="node132.html#Meindl" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Meindl">201</A>], and
Hennessy and Joupp [<A HREF="node132.html#Henn" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Henn">147</A>] discuss trends in processor design and
<A NAME=704> </A>
sequential and parallel computer architecture. Ullman [<A HREF="node132.html#Ullman" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Ullman">286</A>]
provides a succinct explanation of the <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img159.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img159.gif"> complexity results.
<P>
Goldstine and von Neumann [<A HREF="node132.html#Neumann" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Neumann">121</A>] provide an early exposition
<A NAME=707> </A>
of the von Neumann computer. Bailey [<A HREF="node132.html#Bailey" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Bailey">22</A>] explains how this
model derived from the automation of algorithms performed previously
<A NAME=709> </A>
by ``human computers.'' He argues that highly parallel computers are
stimulating not only new algorithmic approaches, but also new ways of
thinking about problems. Many researchers have proposed abstract
machine models for parallel computing [<A HREF="node132.html#C93" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#C93">67</A>,<A HREF="node132.html#FW78" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#FW78">99</A>,<A HREF="node132.html#Val90a" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Val90a">288</A>].
Snyder [<A HREF="node132.html#Snyder" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Snyder">268</A>] explains why the multicomputer is a good choice.
<A NAME=712> </A>
Early parallel computers with a multicomputer-like architecture
<A NAME=713> </A>
include the Ultracomputer [<A HREF="node132.html#Schwartz" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Schwartz">252</A>] and the Cosmic
<A NAME=715> </A>
Cube [<A HREF="node132.html#Cosmic" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Cosmic">254</A>]. Athas and Seitz [<A HREF="node132.html#AS88" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#AS88">18</A>] and
Seitz [<A HREF="node132.html#Seitz" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Seitz">255</A>] discuss developments in this area. Almasi and
Gottlieb [<A HREF="node132.html#AG94" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#AG94">11</A>] and Hwang [<A HREF="node132.html#Hwa93" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Hwa93">156</A>] provide good introductions
to parallel computer architectures and interconnection networks.
<A NAME=721> </A>
Hillis [<A HREF="node132.html#Hil85" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Hil85">150</A>] describes SIMD computers. Fortune and
Wylie [<A HREF="node132.html#FW78" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#FW78">99</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>] discuss the PRAM model.
<A NAME=725> </A>
Comer [<A HREF="node132.html#Comer" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Comer">63</A>] discusses LANs and WANs.
<A NAME=727> </A>
Kahn [<A HREF="node132.html#Kahn72" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Kahn72">162</A>] describes the ARPANET, an early WAN.
The chapter notes in Chapter <A HREF="node26.html#chapperf" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node26.html#chapperf">3</A> provide additional
references on parallel computer architecture.
<P>
The basic abstractions used to describe parallel algorithms have been
developed in the course of many years of research in operating
systems, distributed computing, and parallel computation. The use of
channels was first explored by Hoare in Communicating Sequential
<A NAME=730> </A>
Processes (CSP) [<A HREF="node132.html#CSP" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#CSP">154</A>] and is fundamental to the occam programming
<A NAME=732> </A>
language [<A HREF="node132.html#Pou86" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Pou86">231</A>,<A HREF="node132.html#occam2" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#occam2">280</A>]. However, in CSP the task and channel
structure is static, and both sender and receiver block until a
communication has completed. This approach has proven too restrictive
for general-purpose parallel programming. The
<A NAME=734> </A>
task/channel model introduced in this chapter is described by Chandy
and Foster [<A HREF="node132.html#FM1" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#FM1">102</A>], who also discuss the conditions under which the model
can guarantee deterministic execution [<A HREF="node132.html#FM2" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#FM2">51</A>].
<P>
<A NAME=737> </A>
Seitz [<A HREF="node132.html#Cosmic" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Cosmic">254</A>] and Gropp, Lusk, and Skjellum [<A HREF="node132.html#GLS94" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#GLS94">126</A>]
describe the message-passing model (see also the chapter notes in
Chapter <A HREF="node94.html#chapmpi" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node94.html#chapmpi">8</A>). Ben Ari [<A HREF="node132.html#BA90" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#BA90">32</A>] and Karp and
<A NAME=742> </A>
Babb [<A HREF="node132.html#KarpBabb" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#KarpBabb">165</A>] discuss shared-memory programming. Hillis and
Steele [<A HREF="node132.html#HS86" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#HS86">151</A>] and Hatcher and Quinn [<A HREF="node132.html#DPC" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#DPC">136</A>] describe
data-parallel programming; the chapter notes in Chapter <A HREF="node82.html#chaphpf" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node82.html#chaphpf">7</A>
<A NAME=747> </A>
provide additional references. Other approaches that have generated
<A NAME=748> </A>
considerable interest include Actors [<A HREF="node132.html#Agha" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Agha">5</A>], concurrent logic
<A NAME=750> </A>
programming [<A HREF="node132.html#Strand" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Strand">107</A>], functional programming [<A HREF="node132.html#Henderson" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Henderson">146</A>],
<A NAME=753> </A>
Linda [<A HREF="node132.html#Linda" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Linda">48</A>], and Unity [<A HREF="node132.html#Unity" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Unity">54</A>]. Bal et al. [<A HREF="node132.html#Bal" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Bal">23</A>]
<A NAME=757> </A>
provide a useful survey of some of these approaches. Pancake and
Bergmark [<A HREF="node132.html#Pancake" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Pancake">218</A>] emphasize the importance of deterministic
<A NAME=759> </A>
execution in parallel computing.
<P>
<P>
Here is a
<A HREF="msgs0.htm#7" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/tppmsgs/msgs0.htm#7">Web Tour</A>
providing access to additional information on parallel applications,
parallel computer architecture, and parallel programming models.
<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=tex2html1990 HREF="node12.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node12.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=tex2html1996 HREF="node14.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node14.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=tex2html1994 HREF="node6.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node6.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=tex2html1998 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=tex2html1999 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=tex2html1997 HREF="node14.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node14.html">2 Designing Parallel Algorithms</A>
<B>Up:</B> <A NAME=tex2html1995 HREF="node6.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node6.html">1 Parallel Computers and Computation</A>
<B> Previous:</B> <A NAME=tex2html1991 HREF="node12.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node12.html"> Exercises</A>
<BR><HR><P>
<P><ADDRESS>
<I>© 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>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -