An important problem in the area of optimization is the 
so called "floorplan
design". Given some cells that can be floorspace specifications or
hardware components, the objective is to allocate these cells on a
surface minimizing the occupied area. 
<p>
An example and explanation of this problem can be found in page 64
(Section 2.7) of Ian Foster's book <A
HREF="http://www-unix.mcs.anl.gov/dbpp/">  <B>"Designing and Building
      Parallel Programs"</B> available in the internet (just click on
    the link). </A> 
<p>
For this assignment, you are going to implement a distributed solution
to this problem. For example, using the suggestion given in Foster's
book (page 69, Section 2.7.2), where he suggests to have a partitioned
search tree, each one having its own sub-manager of the <B>Amin</B>
variable (the variable that stores the current minimum area). 
<p>
Your program should randomly generate 200, 500 and 1.000 cells of
different dimensions (consider only rectangles or squares and randomly
pick the dimensions of each one) that obey the constraints mentioned
in page 66 (Section 2.7.1).
<p>
1) You should execute your program with 1, 2, 4 and 6 processors and
plot a curve with execution times for each set of cells.
In order to run your experiments, you may use the 6 nodes available in
our department (grid-node1 to grid-node8.alunos.dcc.fc.up.pt), whose
front-end is grid.alunos.dcc.fc.up.pt. These machines have OpenMPI installed.
<p>
2) You should also run your program in the grid (submission from the
machine glite-tutor.ct.infn.it), with
gLite, utilizing 2 approaches:
<ul>
<li> do not modify your program (it should be implemented using MPI)
  and submit it as an MPICH job. </li>
<li> modify your program such that the value of Amin is written in a
  disk file. You will need to reprogram in order to implement the
  interprocess communication via reads and writes to a file. (you may
  need to use the gLite gfal library to do that). Reprogram in order
  that you can vary the frequency of reads and writes to disk. </li>
</ul>

<!--Para submeter seus jobs devem primeiro escolher um nó do grid que
atenda aos requisitos do seu programa. -->
Your program that executes in the grid should compute the total
execution time (parallel time), submission time and queue waiting time.
<p>
<B>Each experience must be repeated at least 10 times. Times must be
  reported as the average of the 10 runs. </B>
<p>
What you should hand in:
<p>
<LI> Program code
<LI> Report with the following Sections:
   <UL> 
   <LI> Introduction (presentation of the problem)
   <LI> Parallel solution (explanation of your code and reasoning)
   <LI> Experimental Results and comparison of the sequential times
   with the parallel times. Include figures:
     <UL> 
     <LI> 1. first experiment: x axis: number of processors (1, 2, 4,
     6), y axis: average execution time, z axis: number of cells (200, 500 e 1.000)
     <LI> 2. second experiment: x axis: number of processors
     (variable), y axis: average execution time, z axis: number of cells (200, 500 e
     1.000). Besides this figure, you should also present a curve with
     maximum number of machines used containing: x axis: frequency of
     reads and writes to disk, y aixs: average execution time,
     z axis: number of cells.
     </UL>
   <LI> Conclusions and final comments
   </UL> 


<p>
<B><blink>Deadline: April 30th, 2012. </blink></B>