assignments/archive/mandelbrot/index.shtml

   1 <!--#set var="root_directory" value="../../.." --><!--#include virtual="$root_directory/shared/header.shtml"-->
   2
   3 <h1>Assignment #6</h1>
   4 <p><em>Due Friday, November 5, 2009</em></p>
   5
   6 <h2>Purpose</h2>
   7
   8 <p>Learn how to implement a hostless parallel algorithm.</p>
   9
  10 <p>Note: Please identify all your work.</p>
  11
  12 <p>This assignment consists in rewriting the code calculating the
  13 Mandelbrot Set in a static load balance approach using a hostless
  14 parallel algorithm.</p>
  15
  16 <p>In a hostless parallel algorithm, <em>all</em> nodes are treated on
  17 the same basis, except possibly for a brief dialogue with the user to
  18 start with and some post-processing of the data at the end of the
  19 calculation by node 0. In general, this paradigm is simpler to code
  20 than a master-slave approach. But it requires to ﬁnd a way to divide
  21 the problem in parcels of equal complexity, therefore taking
  22 equivalent time to compute.</p>
  23
  24 <p>In the Mandelbrot Set adjacent lines of pixels in the image ought
  25 to take comparable times to compute. Therefore a static load balance
  26 algorithm follows by requesting the nodes (including node 0 —
  27 therefore a hostless algorithm) to calculate the lines in the image on
  28 a cyclic basis. For instance, if three (3) nodes are used, each node
  29 should compute the lines of pixels according to the following
  30 table:</p>
  31
  32 <table>
  33   <tr><th>node</th><th>lines</th></tr>
  34   <tr><td>0</td>   <td>0, 3, 6, 9, ...</td></tr>
  35   <tr><td>1</td>   <td>1, 4, 7, 10, ...</td></tr>
  36   <tr><td>2</td>   <td>2, 5, 8, 11, ...</td></tr>
  37 </table>
  38
  39 <h2>Part A</h2>
  40
  41 <p>Write a code to</p>
  42
  43 <ul>
  44   <li>implement the hostless approach.</li>
  45   <li>produce the Mandelbrot Set image by piping the data in plot
  46     image.py.</li>
  47   <li>reproduce the same image as the serial and master-slave versions
  48     from the notes in the web pages.</li>
  49   <li>handle an arbitrary number of nodes.</li>
  50   <li>handle an arbitrary size for the image (default: 700x500).</li>
  51 </ul>
  52
  53 <h2>Part B</h2>
  54
  55 <p>Include timing calls in your code to prove (or disprove) the
  56 assumption that the approach described above really leads to a proper
  57 load balance. Quantify the time variations in the nodes when using
  58 from 2 to 16 nodes.</p>
  59
  60 <p>You could solve this assignment
  61 on <code>borg0.physics.drexel.edu</code>.</p>
  62
  63 <!--#include virtual="$root_directory/shared/footer.shtml"-->