assignments/archive/tree_broadcast/index.shtml

   1 <!--#set var="root_directory" value="../../.." --><!--#include virtual="$root_directory/shared/header.shtml"-->
   2
   3 <h1>Assignment #4</h1>
   4 <p><em>Due Friday, October 29, 2010</em></p>
   5
   6 <h2>Purpose</h2>
   7
   8 <p>Learn how to implement a truly parallel algorithm.</p>
   9
  10 <p>Note: Please identify all your work.</p>
  11
  12 <p>This assignment consists in building your own broadcast code based
  13 on a binary tree.  The code
  14 <a href="../../../content/global_operations/src/print_tree.c">print_tree.c</a>
  15 (see <a href="../../../content/global_operations/">Global
  16 Operations</a>) provides a simple implementation of a binary tree
  17 based on node zero as being the root.  It generates the node numbers
  18 from which any node is to receive the information and to which to send
  19 this information.</p>
  20
  21 <h2>Part A</h2>
  22
  23 <p>Write a function <code>My_Bcast()</code> that performs a broadcast
  24 similar as the one provided by MPICH2. It should follow the same
  25 syntax as <code>MPI_Bcast()</code>, namely</p>
  26
  27 <pre>
  28 int My_Bcast(void *buffer, int count, MPI_Datatype datatype, int root,
  29              MPI_Comm comm)
  30 </pre>
  31
  32 <p>This function should be based on the skeleton
  33 code <code>print_tree.c</code>. It should therefore assume that root
  34 is process zero (0). If not, it should print out an error message
  35 quoting this fact and return an exit code one (1).</p>
  36
  37 <p>Test your routine carefully for various process numbers and
  38 different <code>count</code> and <code>datatype</code> in the
  39 call.</p>
  40
  41 <h2>Part B</h2>
  42
  43 <p>Instrument your code for timing measurements. Modify your main code
  44 to broadcast the information three (3) different ways:</p>
  45
  46 <ol>
  47   <li>sequentially via a for loop,</li>
  48   <li>via your <code>My_Bcast()</code>, and</li>
  49   <li>via the MPICH2 <code>MPI_Bcast()</code>.</li>
  50 </ol>
  51
  52 <p>Broadcast 10,000 integers 100 times and take an average over the
  53 100 broadcasts to smooth out the time fluctuations. Repeat for 10,000
  54 <code>double</code>. Tabulate your timings and comment on the
  55 results.</p>
  56
  57 <h2>Part C</h2>
  58
  59 <p>Modify <code>My_Bcast()</code> to be able to broadcast from any
  60 process (the root process) within the virtual machine. Check your code
  61 carefully for different <code>root</code> processes and various numbers
  62 of processes.</p>
  63
  64 <!--#include virtual="$root_directory/shared/footer.shtml"-->