assignments/archive/tree_broadcast/index.shtml

   1 <!--#set var="root_directory" value="../../.." --><!--#include virtual="$root_directory/shared/header.shtml"-->
   2
   3 <h1>Assignment #3</h1>
   4 <p><em>Due Friday, October 26, 2007</em></p>
   5
   6 <h2>Purpose</h2>
   7
   8 <p>To learn how to implement truly parallel algorithms.</p>
   9
  10 <h2>Setup</h2>
  11
  12 <p>This assignment consists in building your own broadcast code based
  13 on a binary tree. The code <a href="src/print_tree.c">print_tree.c</a>
  14 provides a simple implementation of a binary tree based on node zero
  15 as being the root. It generates the node numbers from which any node
  16 is to receive the information and to which to send this
  17 information.</p>
  18
  19 <h2>To do</h2>
  20
  21 <h3>Part A</h3>
  22
  23 <ol>
  24   <li>Build a broadcast function based on the skeleton code
  25     <a href="src/print_tree.c">print_tree.c</a>.</li>
  26   <li>Call this function <code>my_broadcast()</code> with a calling
  27     sequence
  28     <pre>int my_broadcast( int my_rank, int size, int root, double *msg, int count )</pre>
  29     In other words, restrict it to only <code>double</code> data type for
  30     simplicity and to <code>root</code> pointing to node 0 only (via
  31     an <code>if ( )</code>).</li>
  32   <li>Move the inner parts of the loop
  33     in <a href="src/print_tree.c">print_tree.c</a> over to a function
  34     <code>my_broadcast</code> (still in a serial code).</li>
  35   <li>Use an integer array <code>target[]</code> created by
  36     <code>malloc()</code> to store the list of <code>to</code> target
  37     nodes.</li>
  38   <li>Include the MPI administrative calls
  39     (<code>MPI_Init()</code>,
  40      <code>MPI_Comm_size()</code>,
  41      <code>MPI_Comm_rank()</code>,
  42      <code>MPI_Finalize()</code>), and use the actual <code>size</code> and
  43     <code>rank</code> of the virtual machine instead for the loop
  44     over <code>rank</code>.</li>
  45   <li>Implement the send and receive routines (<code>MPI_Recv()</code> and
  46     <code>MPI_Ssend()</code>) to receive and transmit the message.</li>
  47   <li>Put <code>printf()</code> statements in the main program to
  48     check that the code is working correctly.</li>
  49 </ol>
  50
  51 <h3>Part B</h3>
  52
  53 <p>Use <code>MPI_Wtime()</code> to time three ways of "broadcasting" a
  54 message:</p>
  55 <ol>
  56   <li>Using a <code>for</code> loop over the nodes to send the message
  57   from the <code>root</code> node to the other nodes.</li>
  58   <li>Using <code>my_broadcast()</code>.</li>
  59   <li>Using <code>MPI_Bcast()</code>.</li>
  60 </ol>
  61
  62 <p>To do so, send a message of some length (at least 1000, 5000 and
  63 10000 double — filled with random numbers) over and over again
  64 100 times (using a <code>for</code> loop) to have good time
  65 statistics. Print the average of the times for each broadcast
  66 methods.</p>
  67
  68 <h3>Part C</h3>
  69
  70 <p>Modify your function <code>my_broadcast()</code> to broadcast from
  71 an arbitrary <code>root</code> node, namely</p>
  72 <ol>
  73   <li>Modify the algorithm (explain what you will implement).</li>
  74   <li>Modify <a href="print_tree.c">print_tree.c</a> accordingly.</li>
  75   <li>Modify <code>my_broadcast()</code> accordingly.</li>
  76   <li>Fully check that <code>my_broadcast()</code> works properly by
  77     inserting appropriate <code>printf()</code> in the main program and
  78     running the code for different number of processes and
  79     <code>root</code>.</li>
  80   <li>Repeat the timing study in part B for this new function.</li>
  81 </ol>
  82
  83 <!--#include virtual="$root_directory/shared/footer.shtml"-->