node97.html

Design and building parallel program

<A NAME=12708>&#160;</A>
root</tt> process sends data to all processes, sending the <em> i</em>
th
portion of its <tt> inbuf</tt> to process <em> i</em>
; each process receives
data from <tt> root</tt> in <tt> outbuf</tt>.  Hence, the <tt> inbuf</tt> in the
root process must be <em> P</em>
 times larger than <tt> outbuf</tt>.  Notice
the subtle difference between this function and <tt> MPI_BCAST</tt>:
while in <tt> MPI_BCAST</tt> every process receives the <em> same
 </em>
value from the root process, in <tt> MPI_SCATTER</tt> every process
receives a <em> different
 </em> value.
<P>
<H2><A NAME=SECTION03533000000000000000>8.3.3 Reduction Operations</A></H2>
<P>
<A NAME=secmpred>&#160;</A>
<P>
<A NAME=12724>&#160;</A>
The functions <tt> MPI_REDUCE</tt> and <tt> MPI_ALLREDUCE</tt> implement
reduction operations.  They combine the values provided in the input
buffer of each process, using a specified operation <tt> op</tt>, and
<A NAME=12728>&#160;</A>
return the combined value either to the output buffer of the single
<A NAME=12729>&#160;</A>
<tt> root</tt> process (in the case of <tt> MPI_REDUCE</tt>) or to the output
<A NAME=12732>&#160;</A>
buffer of all processes (<tt> MPI_ALLREDUCE</tt>).  The operation is
applied pointwise to each of the <tt> count</tt> values provided by each
process.  All operations return <tt> count</tt> values with the same
datatype as the operands.  Valid operations include maximum and
minimum (<tt> MPI_MAX</tt> and <tt> MPI_MIN</tt>); sum and product (<tt>
MPI_SUM</tt> and <tt> MPI_PROD</tt>); logical and, or, and exclusive or
(<tt> MPI_LAND</tt>, <tt> MPI_LOR</tt>, and <tt> MPI_LXOR</tt>); and bitwise
and, or, and exclusive or (<tt> MPI_BAND</tt>, <tt> MPI_BOR</tt>, and <tt>
MPI_BXOR</tt>).
<P>
<P><A NAME=13984>&#160;</A><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1018.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1018.gif">
<BR><STRONG>Figure:</STRONG> <em> Applications of <tt> MPI_REDUCE</tt> and <tt> MPI_ALLREDUCE</tt>.
The first line shows the send buffers (of size 2) in each of four
processes; subsequent lines show the output buffers in each process
following four different global communication
calls.</em><A NAME=figmpreduce>&#160;</A><BR>
<P>
<P>
As an example, the following call would be used to compute the minimum
of two sets of <em> P</em>
 values, where <em> P</em>
 is the number of
processes involved in the reduction.
<P>
<tt> MPI_REDUCE(inbuf, outbuf, 2, MPI_INT, MPI_MIN, 0, MPI_COMM_WORLD)</tt>
<P>
After the reduction, <tt> outbuf[0]</tt> in process 0 contains the minimum
of the first element in each input buffer (<tt> min(inbuf[0])</tt>);
similarly, <tt> outbuf[1]</tt> contains <tt> min(inbuf[1])</tt>.  The
operation of this and other calls to MPI reduction functions are
illustrated in Figure <A HREF="node97.html#figmpreduce" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node97.html#figmpreduce">8.4</A>.
<P>
<P><A NAME=progmp4>&#160;</A><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1019.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1019.gif"><P>
<P>
<BR><HR>
<b> Example <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1022.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1022.gif">.<IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1020.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1020.gif">    Finite Difference</b>:<A NAME=exmpfd>&#160;</A>
<P>
Once again we consider a finite difference problem, this time to
<A NAME=12802>&#160;</A>
illustrate the use of global operations.  The algorithm
<A NAME=12803>&#160;</A>
considered requires both nearest-neighbor communication (to exchange
boundary values) and global communication (to detect termination).
Similar problems have previously been discussed in
Chapter <A HREF="node14.html#chap2" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node14.html#chap2">2</A>.  The MPI implementation given in
Program <A HREF="node97.html#progmp4" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node97.html#progmp4">8.5</A> is for a one-dimensional decomposition of a
one-dimensional problem in which each process has two neighbors.  It
uses <tt> MPI_SEND</tt> and <tt> MPI_RECV</tt> for nearest-neighbor
communication and four MPI global communication routines, for a total
of five distinct communication operations.  These are summarized 
as follows and are illustrated in Figure <A HREF="node97.html#figmpfdcomm" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node97.html#figmpfdcomm">8.5</A>:
<P>
<P><A NAME=14026>&#160;</A><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1021.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1021.gif">
<BR><STRONG>Figure 8.5:</STRONG> <em> Communication performed in the finite difference program,
assuming three processes.  Each column represents a processor; each
subfigure shows data movement in a single phase.  The five phases
illustrated are (1) broadcast, (2) scatter, (3) nearest-neighbor
exchange, (4) reduction, and (5) gather.</em><A NAME=figmpfdcomm>&#160;</A><BR>
<P>
<P>
<OL><LI>
<tt> MPI_BCAST</tt> to broadcast the problem size parameter (<tt> size</tt>)
from process 0 to all <tt> np</tt> processes;
<P>
<LI>
<tt> MPI_SCATTER</tt> to distribute an input array (<tt> work</tt>) from
process 0 to other processes, so that each process receives <tt>
size/np</tt> elements;
<P>
<LI>
<tt> MPI_SEND</tt> and <tt> MPI_RECV</tt> for exchange of data (a single
floating-point number) with neighbors;
<P>
<LI>
<tt> MPI_ALLREDUCE</tt> to determine the maximum of a set of <tt>
localerr</tt> values computed at the different processes and to
distribute this maximum value to each process; and
<P>
<LI>
<tt> MPI_GATHER</tt> to accumulate an output array at process 0.
</OL>
<P>
The use of scatter and gather operations to transfer input and
output data is particularly simple and convenient.  Note, however, that
their use in this example is inherently nonscalable.  As we solve
larger problems, storage limitations will eventually prevent us from
accumulating all input and output data in a single process.  In
addition, the associated communication costs may be prohibitive.
<P>
<BR><HR>
<P>
<A NAME=12826>&#160;</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=tex2html3129 HREF="node96.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node96.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=tex2html3137 HREF="node98.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node98.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=tex2html3135 HREF="node94.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node94.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=tex2html3139 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=tex2html3140 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=tex2html3138 HREF="node98.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node98.html">8.4 Asynchronous Communication</A>
<B>Up:</B> <A NAME=tex2html3136 HREF="node94.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node94.html">8 Message Passing Interface</A>
<B> Previous:</B> <A NAME=tex2html3130 HREF="node96.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node96.html">8.2 MPI Basics</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>