📄 node10.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>1.4 Parallel Algorithm Examples</TITLE>
</HEAD>
<BODY>
<meta name="description" value="1.4 Parallel Algorithm Examples">
<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=tex2html1954 HREF="node9.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node9.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=tex2html1962 HREF="node11.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node11.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=tex2html1960 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=tex2html1964 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=tex2html1965 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=tex2html1963 HREF="node11.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node11.html">1.5 Summary</A>
<B>Up:</B> <A NAME=tex2html1961 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=tex2html1955 HREF="node9.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node9.html">1.3 A Parallel Programming Model</A>
<BR><HR><P>
<H1><A NAME=SECTION02240000000000000000>1.4 Parallel Algorithm Examples</A></H1>
<P>
We conclude this chapter by presenting four examples of parallel
algorithms. We do not concern ourselves here with the process by
which these algorithms are derived or with their efficiency; these
<A NAME=524> </A>
issues are discussed in Chapters <A HREF="node14.html#chap2" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node14.html#chap2">2</A> and <A HREF="node26.html#chapperf" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node26.html#chapperf">3</A>,
respectively. The goal is simply to introduce
parallel algorithms and their description in terms of tasks and
channels.
<P>
The first two algorithms described have an SPMD structure,
the third creates tasks dynamically during program execution, and
the fourth uses a fixed number of tasks but has different tasks
perform different functions.
<P>
<H2><A NAME=SECTION02241000000000000000>1.4.1 Finite Differences</A></H2>
<P>
<A NAME=exfd> </A>
<P>
<P><A NAME=973> </A><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img108.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img108.gif">
<BR><STRONG>Figure 1.11:</STRONG> <em> A parallel algorithm for the one-dimensional finite
difference problem. From top to bottom: the one-dimensional vector
<em> X</em>
, where <em> N=8</em>
; the task structure, showing the 8 tasks,
each encapsulating a single data value and connected to left and right
neighbors via channels; and the structure of a single
task, showing its two inports and
outports.</em><A NAME=figvc> </A><BR>
<P>
<P>
We first consider a one-dimensional finite difference problem,
in which we have a vector <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img109.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img109.gif"> of size <em> N</em>
and must compute
<IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img110.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img110.gif">, where
<P><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img111.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img111.gif"><P>
That is, we must repeatedly update each element of <em> X</em>
, with no
element being updated in step <em> t+1</em>
until its neighbors have been
updated in step <em> t</em>
.
<P>
A parallel algorithm for this problem creates <em> N</em>
tasks, one for
each point in <em> X</em>
. The <em> i</em>
th task is given the value
<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img112.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img112.gif"> and is responsible for computing, in <em> T</em>
steps, the
values <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img113.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img113.gif">. Hence, at step
<em> t</em>
, it must obtain the values <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img114.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img114.gif"> and <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img115.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img115.gif">
from tasks <em> i-1</em>
and <em> i+1</em>
. We specify this data transfer by
defining channels that link each task with ``left'' and ``right''
neighbors, as shown in Figure <A HREF="node10.html#figvc" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node10.html#figvc">1.11</A>, and requiring that at step
<em> t</em>
, each task <em> i</em>
other than task 0 and task <em> N-1</em>
<P>
<OL><LI>
sends its data <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img116.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img116.gif"> on its left and right outports,
<LI>
receives <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img117.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img117.gif"> and <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img118.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img118.gif"> from its left and right inports,
and
<LI>
uses these values to compute <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img119.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img119.gif">.
</OL>
Notice that the <em> N</em>
tasks can execute independently, with the only
<A NAME=575> </A>
constraint on execution order being the synchronization enforced by
the receive operations. This synchronization ensures that no data
value is updated at step <em> t+1</em>
until the data values in
neighboring tasks have been updated at step <em> t</em>
. Hence, execution
is deterministic.
<P>
<H2><A NAME=SECTION02242000000000000000>1.4.2 Pairwise Interactions</A></H2>
<P>
<A NAME=exinteractions> </A>
<P>
<P><A NAME=1008> </A><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img120.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img120.gif">
<BR><STRONG>Figure 1.12:</STRONG> <em> Task structures for computing pairwise interactions
for <em> N=5</em>
. (a) The unidirectional ring used in the simple,
nonsymmetric algorithm. (b) The unidirectional ring with additional
channels used to return accumulated values in the symmetric algorithm;
the path taken by the accumulator used for task 0 is shown as a solid
line.</em><A NAME=fignb> </A><BR>
<P>
<P>
<A NAME=584> </A>
Our second example uses a similar channel structure but requires a
more complex communication algorithm. Many problems require the
computation of all <em> N(N-1)</em>
pairwise interactions <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img121.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img121.gif">,
<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img122.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img122.gif">, between <em> N</em>
data, <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img123.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img123.gif">. Interactions
may be symmetric, in which case <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img124.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img124.gif"> and only
<em> N(N-1)/2</em>
interactions need be computed. For example, in
molecular dynamics we may require the total force vector <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img125.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img125.gif"> acting
on each atom <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img126.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img126.gif">, defined as follows:
<P><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img127.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img127.gif"><P>
Each atom is represented by its mass and Cartesian coordinates.
<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img128.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img128.gif"> denotes the mutual attraction or repulsion between atoms
<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img129.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img129.gif"> and <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img130.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img130.gif">; in this example, <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img131.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img131.gif">, so
interactions are symmetric.
<P>
A simple parallel algorithm for the general pairwise interactions
problem might create <em> N</em>
tasks. Task <em> i</em>
is given the datum
<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img132.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img132.gif"> and is responsible for computing the interactions <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img133.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img133.gif">. One might think that as each task needs a
datum from every other task, <em> N(N-1)</em>
channels would be needed to
perform the necessary communications. However, a more economical
structure is possible that uses only <em> N</em>
channels. These channels
are used to connect the <em> N</em>
tasks in a unidirectional ring
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -