content/global_operations/index.shtml

   1 <!--#set var="root_directory" value="../.." --><!--#include virtual="$root_directory/shared/header.shtml"-->
   2
   3 <h1>Global Operations</h1>
   4
   5 <!--TableOfContents:Begin-->
   6 <!--TableOfContents:End-->
   7
   8 <p>Global operations are those that affect all processes at once.
   9 This section deals with some of these operations provided by MPI.
  10 These routines are highly optimized for the hardware in use, and
  11 are likely to be more efficient than any equivalent "hand-coded"
  12 similar operations.</p>
  13
  14 <h2 id="sync">Synchronization</h2>
  15
  16 <pre>int MPI_Barrier ( MPI_Comm comm )</pre>
  17
  18 <p>A call that causes each process in the
  19 communicator <code>comm</code> to block until all the process have
  20 called it. Useful for timing codes. Also used in preparation for
  21 transmission operations. The use of this routine is time consuming and
  22 should be avoided under most conditions. Recall that synchronous
  23 message sending routines provide synchronization implicitly.</p>
  24
  25 <h2 id="Bcast">Broadcast</h2>
  26
  27 <pre>
  28 int MPI_Bcast ( void *buffer, int count, MPI_Datatype datatype,
  29                 int root, MPI_Comm comm )
  30 </pre>
  31
  32 <p>The process specified by <code>root</code> sends the content of
  33 <code>buffer</code>, <code>count</code> elements of
  34 type <code>datatype</code>, to all processes in the
  35 communicator <code>comm</code>.  This is a very efficient way to send
  36 information from any process to all other processes in a
  37 communicator. The time used by this routine is much shorter than the
  38 time needed for sequential calls
  39 to <code>MPI_Ssend</code>/<code>MPI_Recv</code>, especially for large
  40 number of processors.</p>
  41
  42 <h2 id="Reduce">Reduce</h2>
  43
  44 <p>The necessity to find global maximum, minimum, sum, product, or
  45 other "global" operations on a set of process distributed numbers
  46 often occurs. MPI provides general purpose reduce commands to perform
  47 these tasks.</p>
  48
  49 <pre>
  50 int MPI_Reduce ( void *local_value, void *results, int count,
  51                  MPI_Datatype datatype, MPI_Op operator,
  52                  int target_process, MPI_Comm comm )
  53 int MPI_Allreduce ( void *local_value, void *results, int count,
  54                     MPI_Datatype datatype, MPI_Op operator,
  55                     MPI_Comm comm )
  56 </pre>
  57
  58 <p>The commands perform a specific operation specified
  59 <code>operator</code> on <code>count</code> elements of the local
  60 array <code>local_value</code> and stores the results in the array
  61 <code>results</code>.</p>
  62
  63 <p>The difference between the <code>MPI_Allreduce()</code>
  64 and <code>MPI_Reduce()</code> routines is the disposition of the
  65 latest result; <code>MPI_Reduce()</code> leaves the final result on
  66 the <code>target_process</code>, while <code>MPI_Allreduce()</code>
  67 broadcast the results to all the nodes in the communicator.</p>
  68
  69 <p>The pre-defined operations are</p>
  70
  71 <dl>
  72   <dt><code>MPI_MAX</code></dt>
  73   <dd>Maximum</dd>
  74   <dt><code>MPI_MIN</code></dt>
  75   <dd>Minimum</dd>
  76   <dt><code>MPI_SUM</code></dt>
  77   <dd>Sum</dd>
  78   <dt><code>MPI_PROD</code></dt>
  79   <dd>Product</dd>
  80   <dt><code>MPI_LAND</code></dt>
  81   <dd>Logical and</dd>
  82   <dt><code>MPI_BAND</code></dt>
  83   <dd>Bitwise and</dd>
  84   <dt><code>MPI_LOR</code></dt>
  85   <dd>Logical or</dd>
  86   <dt><code>MPI_BOR</code></dt>
  87   <dd>Bitwise or</dd>
  88   <dt><code>MPI_LXOR</code></dt>
  89   <dd>Logical exclusive or</dd>
  90   <dt><code>MPI_BXOR</code></dt>
  91   <dd>Bitwise exclusive or</dd>
  92   <dt><code>MPI_MAXLOC</code></dt>
  93   <dd>Maximum and location</dd>
  94   <dt><code>MPI_MINLOC</code></dt>
  95   <dd>Minimum and location</dd>
  96 </dl>
  97
  98 <h2 id="sample">Sample Code</h2>
  99
 100 <p>The code
 101 <a href="../../src/global_operations/global_mpi_operations.c">global_mpi_operations.c</a>
 102 illustrates the use of the MPI global operation routines. Note the
 103 syntax of the calls.</p>
 104
 105 <h2 id="MyBcast">Binary Tree Algorithm — Broadcast</h2>
 106
 107 <p>The MPI global operations routines are based on clever algorithms
 108 for efficiency.  As a learning tool, we look here at a possible
 109 implementation of a broadcast algorithm. It is based on the fact that
 110 a binary tree nomenclature leads to an efficient broadcasting
 111 strategies which can seriously reduce the time to send the messages to
 112 all the nodes in a parallel system.  Such a tree, based on node 0 and
 113 written for a total of 8 nodes is illustrated as follows</p>
 114
 115 <img border="0" src="img/binary_tree.png" width="702" height="220" />
 116
 117 <p>The node zero sends the info to node 1. Then nodes 0 and 1 send the
 118 info to nodes 2 and 3 respectively. Then nodes 0, 1, 2, and 3 all send
 119 the info to nodes 4, 5, 6, and 7 respectively. It is seen that this
 120 strategy saves a large factor in time compared to a sequential series
 121 of sends. This is illustrated as follows:</p>
 122
 123 <img border="0" src="img/transmit_time.png" width="437" height="351" />
 124
 125 <p>Each time unit in this diagram includes the overhead time
 126 (handshaking protocol) as well as the time necessary to send the
 127 info. The larger the number of processors is, more significant the
 128 saving factor is.</p>
 129
 130 <p>A skeleton implementation of this algorithm is given in the
 131 code <a href="../../src/global_operations/print_tree.c">print_tree.c</a>.</p>
 132
 133 <p>The transmission tree translates in the following rules (generation
 134 refers to the time sequence of receive/send in the tree —
 135 generation ranges over 1 to 3 for a tree with up to 8 nodes, nodes 0
 136 to 7).</p>
 137
 138 <table>
 139   <tr>
 140     <th><code>if</code></th>
 141     <th>direction</th>
 142     <th>partner</th>
 143   </tr>
 144   <tr>
 145     <td>2<sup>generation</sup> &lt;= my_rank &lt;
 146       2<sup>(generation-1)</sup></td>
 147     <td>receive from</td>
 148     <td>my_rank - 2<sup>generation</sup></td>
 149   </tr>
 150   <tr>
 151     <td>my_rank &lt; 2<sup>generation</sup></td>
 152     <td>send to</td>
 153     <td>my_rank + 2<sup>generation</sup></td>
 154   </tr>
 155 </table>
 156
 157 <p>The
 158 code <a href="../../src/global_operations/print_tree.c">print_tree.c</a>
 159 implements these rules.</p>
 160
 161 <p>The example code from this section is bundled in
 162 <a href="../../src/global_operations/global_operations.tar.gz">global_operations.tar.gz</a>.</p>
 163
 164 <!--#include virtual="$root_directory/shared/footer.shtml"-->