📄 node130.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=tex2html3554 HREF="node129.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node129.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=tex2html3560 HREF="node131.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node131.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=tex2html3558 HREF="node123.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node123.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=tex2html3562 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=tex2html3563 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=tex2html3561 HREF="node131.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node131.html">12 Further Reading</A>
<B>Up:</B> <A NAME=tex2html3559 HREF="node123.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node123.html">11 Hypercube Algorithms</A>
<B> Previous:</B> <A NAME=tex2html3555 HREF="node129.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node129.html"> Exercises</A>
<BR><HR><P>
<H1><A NAME=SECTION04370000000000000000> Chapter Notes</A></H1>
<P>
<A NAME=15270> </A>
Leighton [<A HREF="node132.html#Leighton" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Leighton">187</A>] discusses basic properties of hypercubes and
describes many parallel algorithms that use a hypercube communication
structure. The recursive halving vector reduction algorithm
considered in Section <A HREF="node125.html#secvecred" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node125.html#secvecred">11.2</A> is described 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>] and the hybrid algorithm by van de
<A NAME=15274> </A>
Geijn [<A HREF="node132.html#Geijn91" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Geijn91">289</A>]. Vector broadcast algorithms are described by
Bertsekas and Tsitsiklis [<A HREF="node132.html#BT89" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#BT89">35</A>] and
Johnsson and Ho [<A HREF="node132.html#JH89" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#JH89">160</A>]. The parallel mergesort algorithm, often
<A NAME=15278> </A>
called bitonic mergesort, is due to Batcher [<A HREF="node132.html#Batcher" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Batcher">30</A>];
Akl [<A HREF="node132.html#Akl89" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Akl89">8</A>] provides a good description. Fox et al. [<A HREF="node132.html#Fox88" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Fox88">111</A>]
describe a multicomputer implementation of this algorithm and of the
variant discussed in Exercise <A HREF="node129.html#exbsort" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node129.html#exbsort">4</A>. Other algorithms that
are conveniently formulated in terms of a hypercube communication
<A NAME=15283> </A>
structure include the fast Fourier
transform [<A HREF="node132.html#AGCM90" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#AGCM90">20</A>,<A HREF="node132.html#Bai90" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Bai90">21</A>,<A HREF="node132.html#FW" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#FW">110</A>,<A HREF="node132.html#Loa92" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Loa92">192</A>,<A HREF="node132.html#Swarz" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Swarz">277</A>], parallel
<A NAME=15285> </A>
prefix [<A HREF="node132.html#RS90" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#RS90">238</A>], and various computer vision [<A HREF="node132.html#RS90" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#RS90">238</A>] and linear
algebra computations [<A HREF="node132.html#Johnsson" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Johnsson">159</A>]. See also the book by Kumar et
al. [<A HREF="node132.html#Kumar93" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Kumar93">179</A>] and papers by Bertsekas et al. [<A HREF="node132.html#BOS91" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#BOS91">36</A>],
McBryan and van der Velde [<A HREF="node132.html#MdV87" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#MdV87">197</A>], and Saad and
Schultz [<A HREF="node132.html#SS88" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#SS88">248</A>,<A HREF="node132.html#SS89" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#SS89">249</A>].
<P>
<A NAME=15293> </A>
The book by Kumar et al. [<A HREF="node132.html#Kumar93" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Kumar93">179</A>] describes parallel versions of
<A NAME=15295> </A>
several sorting algorithms, including quicksort [<A HREF="node132.html#Quicksort" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Quicksort">153</A>], one
of the most commonly used sorting algorithms on sequential computers.
Their parallel quicksort algorithm partitions processors according to
the number of elements lesser than or greater than the pivot at each
step. Fox et al. [<A HREF="node132.html#Fox88" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Fox88">111</A>] describe an alternative parallel
quicksort algorithm that uses regular processor partitions. They
address load imbalance by performing some preliminary processing to
identify pivots that approximately bisect the input sequence.
Knuth [<A HREF="node132.html#Knuth3" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Knuth3">174</A>] and Aho et al. [<A HREF="node132.html#AHU" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#AHU">7</A>] are good references for
sequential sorting algorithms. In addition to standard algorithms
such as mergesort and quicksort, Knuth describes various specialized
algorithms designed to exploit certain properties of the data to be
sorted. Kumar et al. [<A HREF="node132.html#Kumar93" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Kumar93">179</A>] explain how many of these can be
adapted for parallel computers. For example, if data are highly
redundant (that is, they have many identical items), we can count items on
each node, then do a global sum to obtain total counts. If the input
<A NAME=15301> </A>
data distribution is known, a parallel bucketsort can be used. Each
processor knows the location of each bucket and sends its data to the
appropriate location.
<P>
<P>
Here is a
<A HREF="msgs0.htm#18" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/tppmsgs/msgs0.htm#18">Web Tour</A>
providing access to additional information on modular programming,
parallel program design, and templates.
<P>
<A NAME=15309> </A>
<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=tex2html3554 HREF="node129.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node129.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=tex2html3560 HREF="node131.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node131.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=tex2html3558 HREF="node123.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node123.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=tex2html3562 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=tex2html3563 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=tex2html3561 HREF="node131.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node131.html">12 Further Reading</A>
<B>Up:</B> <A NAME=tex2html3559 HREF="node123.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node123.html">11 Hypercube Algorithms</A>
<B> Previous:</B> <A NAME=tex2html3555 HREF="node129.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node129.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 + -