📄 node17.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>2.3 Communication</TITLE>
</HEAD>
<BODY>
<meta name="description" value="2.3 Communication">
<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=tex2html2047 HREF="node16.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node16.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=tex2html2055 HREF="node18.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node18.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=tex2html2053 HREF="node14.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node14.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=tex2html2057 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=tex2html2058 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=tex2html2056 HREF="node18.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node18.html">2.4 Agglomeration</A>
<B>Up:</B> <A NAME=tex2html2054 HREF="node14.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node14.html">2 Designing Parallel Algorithms</A>
<B> Previous:</B> <A NAME=tex2html2048 HREF="node16.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node16.html">2.2 Partitioning</A>
<BR><HR><P>
<H1><A NAME=SECTION02330000000000000000>2.3 Communication</A></H1>
<P>
<A NAME=seccomm> </A>
<P>
<A NAME=1158> </A>
The tasks generated by a partition are intended to execute
concurrently but cannot, in general, execute independently. The
computation to be performed in one task will typically require data
associated with another task. Data must then be transferred between
tasks so as to allow computation to proceed. This information flow is
specified in the <em> communication
</em> phase of a design.
<P>
Recall from Chapter <A HREF="node6.html#chap1" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node6.html#chap1">1</A> that in our programming model, we
conceptualize a need for communication between two tasks as a
<A NAME=1161> </A>
channel linking the tasks, on which one task can send messages
<A NAME=1162> </A>
and from which the other can receive. Hence, the communication
associated with an algorithm can be specified in two phases. First,
we define a channel structure that links, either directly or
indirectly, tasks that require data (consumers) with tasks that
possess those data (producers). Second, we specify the messages that
are to be sent and received on these channels. Depending on our
eventual implementation technology, we may not actually create these
channels when coding the algorithm. For example, in a data-parallel
language, we simply specify data-parallel operations and data
distributions. Nevertheless, thinking in terms of tasks and channels
helps us to think quantitatively about locality issues and
communication costs.
<P>
The definition of a channel involves an intellectual cost and the
sending of a message involves a physical cost. Hence, we avoid
introducing unnecessary channels and communication operations. In
addition, we seek to optimize performance by distributing
communication operations over many tasks and by organizing
communication operations in a way that permits concurrent execution.
<P>
<A NAME=1163> </A>
In domain decomposition problems, communication requirements can be
difficult to determine. Recall that this strategy produces tasks by
first partitioning data structures into disjoint subsets and then
associating with each datum those operations that operate solely on
that datum. This part of the design is usually simple. However, some
operations that require data from several tasks usually remain.
Communication is then required to manage the data transfer necessary
for these tasks to proceed. Organizing this communication in an
efficient manner can be challenging. Even simple decompositions can
have complex communication structures.
<P>
<A NAME=1164> </A>
In contrast, communication requirements in parallel algorithms
obtained by functional decomposition are often straightforward: they
correspond to the data flow between tasks. For example, in a climate
model broken down by functional decomposition into atmosphere model,
ocean model, and so on, the communication requirements will correspond to
the interfaces between the component submodels: the atmosphere model
will produce values that are used by the ocean model, and so on
(Figure <A HREF="node16.html#figenv" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node16.html#figenv">2.3</A>).
<P>
In the following discussion, we use a variety of examples to show how
communication requirements are identified and how channel structures
and communication operations are introduced to satisfy these
requirements. For clarity in exposition, we categorize communication
<A NAME=1166> </A>
patterns along four loosely orthogonal axes: local/global,
structured/unstructured, static/dynamic, and synchronous/asynchronous.
<UL><LI>
<A NAME=1168> </A>
In <em> local
</em> communication, each task communicates with a small
set of other tasks (its ``neighbors''); in contrast, <em> global
</em>
communication requires each task to communicate with many tasks.
<LI>
<A NAME=1171> </A>
In <em> structured
</em> communication, a task and its neighbors form
a regular structure, such as a tree or grid; in contrast, <em>
unstructured
</em> communication networks may be arbitrary graphs.
<LI>
<A NAME=1174> </A>
In <em> static
</em> communication, the identity of communication partners
does not change over time; in contrast, the identity of communication
<A NAME=1176> </A>
partners in <em> dynamic
</em> communication structures may be determined
by data computed at runtime and may be highly variable.
<LI>
<A NAME=1178> </A>
In <em> synchronous
</em> communication, producers and consumers execute in
a coordinated fashion, with producer/consumer pairs cooperating in
<A NAME=1180> </A>
data transfer operations; in contrast, <em> asynchronous
</em>
communication may require that a consumer obtain data without the
cooperation of the producer.
</UL>
<A NAME=1183> </A>
<P>
<P>
<H2><A NAME=SECTION02331000000000000000>2.3.1 Local Communication</A></H2>
<P>
<A NAME=seclocal> </A>
<P>
<A NAME=1186> </A>
A local communication structure is obtained when an operation requires
data from a small number of other tasks. It is then straightforward
to define channels that link the task responsible for performing the
operation (the consumer) with the tasks holding the required data (the
producers) and to introduce appropriate send and receive operations
in the producer and consumer tasks, respectively.
<P>
<A NAME=1187> </A>
For illustrative purposes, we consider the communication requirements
associated with a simple numerical computation, namely a Jacobi finite
difference method. In this class of numerical method, a
multidimensional grid is repeatedly updated by replacing the value at
each point with some function of the values at a small, fixed number
of neighboring points. The set of values required to update a single
<A NAME=1188> </A>
grid point is called that grid point's <em> stencil</em>. For example,
the following expression uses a five-point stencil to update each
element <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img163.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img163.gif"> of a two-dimensional grid <em> X</em>
:
<P><A NAME=eq5pt> </A><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img164.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img164.gif"><P>
This update is applied repeatedly to compute a sequence of values
<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img165.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img165.gif">, <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img166.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img166.gif">, and so on. The notation <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img167.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img167.gif">
denotes the value of grid point <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img168.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img168.gif"> at step <em> t</em>
.
<P>
<P><A NAME=2406> </A><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img169.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img169.gif">
<BR><STRONG>Figure 2.4:</STRONG> <em> Task and channel structure for a two-dimensional finite
difference computation with five-point update stencil. In this simple
fine-grained formulation, each task encapsulates a single element of a
two-dimensional grid and must both send its value to four neighbors
and receive values from four neighbors. Only the channels used by the
shaded task are shown.</em><A NAME=figsten4> </A><BR>
<P>
<P>
Let us assume that a partition has used domain decomposition
techniques to create a distinct task for each point in the
two-dimensional grid. Hence, a task allocated the grid point
<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img170.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img170.gif"> must compute the sequence
<PRE><TT>
<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img171.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img171.gif">
</TT></PRE>
This computation requires in turn the four corresponding sequences
<PRE><TT>
<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img172.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img172.gif">
</TT></PRE>
<PRE><TT>
<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img173.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img173.gif">
</TT></PRE>
<PRE><TT>
<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img174.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img174.gif">
</TT></PRE>
<PRE><TT>
<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img175.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img175.gif">
</TT></PRE>
which are produced by the four tasks handling grid points <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img176.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img176.gif">,
<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img177.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img177.gif">, <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img178.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img178.gif">, and <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img179.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img179.gif">, that is, by its four
neighbors in the grid. For these values to be communicated, we define
channels linking each task that requires a value with the task that
generates that value. This yields the channel structure illustrated
in Figure <A HREF="node17.html#figsten4" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node17.html#figsten4">2.4</A>. Each task then executes the following
logic:
<P>
<P>
<PRE><TT>
<tt> for</tt> <em> t=0</em>
<tt> to</tt> <em> T-1</em>
<P>
<tt> send</tt> <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img180.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img180.gif"> <tt> to each neighbor</tt>
<P>
<tt> receive</tt> <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img181.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img181.gif">, <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img182.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img182.gif">,
<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img183.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img183.gif">, <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img184.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img184.gif"> <tt> from neighbors</tt>
<P>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -