📄 node123.html

📁 Design and building parallel program
💻 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>11 Hypercube Algorithms</TITLE>
</HEAD>
<BODY>
<meta name="description" value="11 Hypercube Algorithms">
<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=tex2html3463 HREF="node122.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node122.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=tex2html3471 HREF="node124.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node124.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=tex2html3469 HREF="node114.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node114.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=tex2html3473 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=tex2html3474 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=tex2html3472 HREF="node124.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node124.html">11.1 The Hypercube Template</A>
<B>Up:</B> <A NAME=tex2html3470 HREF="node114.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node114.html">Part III: Resources</A>
<B> Previous:</B> <A NAME=tex2html3464 HREF="node122.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node122.html"> Chapter Notes</A>
<BR><HR><P>
<H1><A NAME=SECTION04300000000000000000>11 Hypercube Algorithms</A></H1>
<P>
<A NAME=chapcube>&#160;</A>
<P>
<A NAME=14931>&#160;</A>
In Chapter <A HREF="node14.html#chap2" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node14.html#chap2">2</A>, we pointed out that the communication
requirements of a reduction operation can be structured as a series of
pairwise exchanges, one with each neighbor in a <em> hypercube
 </em>
(butterfly) structure.  This structure allows a computation requiring
all-to-all communication among <em> P</em>
 tasks to be performed in just
<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img1117.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1117.gif"> steps, rather than <em> P</em>
 steps as might be expected from a
superficial analysis.
<P>
It turns out that the hypercube structure can be used to implement
<A NAME=14936>&#160;</A>
many other parallel algorithms requiring all-to-all communication;
that is, algorithms in which each task must communicate with every
other task.  In this chapter, we review three such algorithms: vector
reduction, matrix transposition, and sorting.  The purpose of this
<A NAME=14937>&#160;</A>
discussion is both to describe some useful algorithms and to introduce
<A NAME=14938>&#160;</A>
the concept
<A NAME=14939>&#160;</A>
of a parallel algorithm <em> template</em>.  A template is a basic program
form that a programmer can augment with application-specific
information to implement a particular parallel algorithm.  The
hypercube communication structure described in this chapter is one of
the most useful templates in parallel computing.
<P>
After studying this chapter, you should have a good understanding of
the hypercube communication structure and how it is used to implement
all-to-all communication in parallel algorithms.  You should also be
familiar with the concept of a template and the role templates
play in parallel algorithm design and programming.
<P>

<HR>
<UL> 
<LI> <A NAME=tex2html3475 HREF="node124.html#SECTION04310000000000000000" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node124.html#SECTION04310000000000000000">11.1 The Hypercube Template</A>
<LI> <A NAME=tex2html3476 HREF="node125.html#SECTION04320000000000000000" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node125.html#SECTION04320000000000000000">11.2 Vector Reduction</A>
<LI> <A NAME=tex2html3477 HREF="node126.html#SECTION04330000000000000000" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node126.html#SECTION04330000000000000000">11.3 Matrix Transposition</A>
<LI> <A NAME=tex2html3478 HREF="node127.html#SECTION04340000000000000000" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node127.html#SECTION04340000000000000000">11.4 Mergesort</A>
<LI> <A NAME=tex2html3479 HREF="node128.html#SECTION04350000000000000000" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node128.html#SECTION04350000000000000000">11.5 Summary</A>
<LI> <A NAME=tex2html3480 HREF="node129.html#SECTION04360000000000000000" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node129.html#SECTION04360000000000000000"> Exercises</A>
<LI> <A NAME=tex2html3481 HREF="node130.html#SECTION04370000000000000000" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node130.html#SECTION04370000000000000000"> Chapter Notes</A>
</UL>
<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=tex2html3463 HREF="node122.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node122.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=tex2html3471 HREF="node124.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node124.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=tex2html3469 HREF="node114.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node114.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=tex2html3473 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=tex2html3474 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=tex2html3472 HREF="node124.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node124.html">11.1 The Hypercube Template</A>
<B>Up:</B> <A NAME=tex2html3470 HREF="node114.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node114.html">Part III: Resources</A>
<B> Previous:</B> <A NAME=tex2html3464 HREF="node122.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node122.html"> Chapter Notes</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>
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -