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 23, 2009</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 provides a simple implementation of a binary tree based on node zero
  16 as being the root. It generates the node numbers from which any node
  17 is to receive the information and to which to send this
  18 information.</p>
  19
  20 <h2>Part A</h2>
  21
  22 <p>Write a function <code>My_Bcast()</code> that performs a broadcast
  23 similar as the one provided by MPICH2. It should follow the same
  24 syntax as <code>MPI_Bcast()</code>, namely</p>
  25
  26 <pre>
  27 int My Bcast(void *buffer, int count, MPI Datatype datatype, int root,
  28              MPI Comm comm)
  29 </pre>
  30
  31 <p>This function should be based on the skeleton
  32 code <code>print_tree.c</code>. It should therefore assume that root
  33 is process zero (0). If not, it should print out an error message
  34 quoting this fact and return an exit code one (1).</p>
  35
  36 <p>Test your routine carefully for various process numbers and
  37 different count and datatype in the call.</p>
  38
  39 <h2>Part B</h2>
  40
  41 <p>Instrument your code for timing measurements. Modify your main code
  42 to broadcast the information three (3) different ways:</p>
  43
  44 <ol>
  45   <li>sequentially via a for loop,</li>
  46   <li>via your <code>My_Bcast()</code>, and</li>
  47   <li>via the MPICH2 <code>MPI_Bcast()</code>.</li>
  48 </ol>
  49
  50 <p>Broadcast 10,000 integers 100 times and take an average over the
  51 100 broadcasts to smooth out the time fluctuations. Repeat for 10,000
  52 double. Tabulate your timings and comment on the results.</p>
  53
  54 <h2>Part C</h2>
  55
  56 <p>Modify <code>My_Bcast()</code> to be able to broadcast from any
  57 process (the root process) within the virtual machine. Check your code
  58 carefully for different <em>root</em> processes and various number of
  59 processes.</p>
  60
  61 <!--#include virtual="$root_directory/shared/footer.shtml"-->