Um problema importante na área de otimização é o chamado "floorplan
design", onde, dadas algumas peças (que podem ser especificações de
planta baixa de uma casa ou mesmo componentes de hardware), o objetivo
é alocar estas peças sobre uma superfície, de forma que estas ocupem a
menor área possível.
<p>
Um exemplo e explicação mais detalhada deste problema, com sugestões
de paralelização, podem ser encontrados na página 64 do livro do Ian
Foster, <A
HREF="http://www-unix.mcs.anl.gov/dbpp/">  <B>"Designing and Building
      Parallel Programs"</B> disponível na internet (basta clicar no
    link). </A> 
<p>
Neste trabalho, vocês terão que implementar uma solução distribuída
para este problema, por exemplo, utilizando a sugestão do livro do
Foster (página 69), onde este sugere que a árvore de busca seja
particionada em sub-árvores, cada uma com seu sub-gerente da variável
<B>Amin</B>, que guarda o valor máximo da superfície ocupada até o momento.
<p>
Seu programa deve gerar aleatoriamente 200, 500 e 1.000 peças de dimensões
diferentes (considere apenas retângulos e selecione as dimensões de cada
peça de forma aleatória) e com restrições baseadas
naquelas mencionadas na página 66.
<p>
1) Vocês devem correr este programa em 1, 2, 4 e 6 processadores e "plotar"
uma curva de tempo de execução para cada conjunto de peças. Para fazer
esta parte do trabalho têm 
à disposição 6 nós (grid-node1 a grid-node8.alunos.dcc.fc.up.pt), cuja
máquina de entrada principal é grid.alunos.dcc.fc.up.pt. Estas
máquinas têm OpenMPI instalado.
<p>
2) Além disso, devem correr o seu programa em grid (submissão a partir
da máquina glite-tutor.ct.infn.it), com
gLite, utilizando 2 abordagens diferentes:
<ul>
<li> não modifique o seu programa (que deve estar implementado com troca de
  mensagens (MPI)) e submeta-o como um job mpich  </li>
<li> modifique seu programa de forma que o valor corrente da
  área calculada seja guardado num ficheiro, ou seja, reprograme para
  que a comunicação entre processos possa ser feita através de
  leituras e escritas a um ficheiro (para isto pode precisar utilizar
  a biblioteca gfal do gLite). Reprograme de forma que possa variar a
  frequência de escritas e leituras ao disco</li>
</ul>

<!--Para submeter seus jobs devem primeiro escolher um nó do grid que
atenda aos requisitos do seu programa. -->
Este seu programa que executa em
grid deve computar o tempo total de execução útil (tempo paralelo de
execução), e os tempos de submissão e de espera em fila.
<p>
<B>Cada experiência deve ser repetida pelo menos 10 vezes e a média de
tempo de execução deve ser reportada.</B>
<p>
O que deve entregar:
<p>
<LI> Código da implementação
<LI> Relatório contendo as seguintes seções:
   <UL> 
   <LI> Introdução (apresentação do problema)
   <LI> Solução paralela (explicação do seu código e justificativas)
   <LI> Resultados experimentais e comparação entre tempos sequenciais
   e paralelos no grid. Incluir gráficos:
     <UL> 
     <LI> 1. para a primeira experiência: eixo do x: número de
     processadores (1, 2, 4, 6), eixo do y: média de tempo 
     das 10 execuções, eixo do z: número de 
     peças (200, 500 e 1.000)
     <LI> 2. para a segunda experiência: eixo do x: número de
     processadores (variável), eixo do y: média de tempo 
     das 10 execuções, eixo do z: número de peças (200, 500 e
     1.000). Além deste gráfico apresentar também um gráfico com o
     número máximo de máquinas utilizadas com eixo x: frequência de
     escritas e leituras ao disco, eixo y: tempo médio de execução,
     eixo z: número de peças.
     </UL>
   <LI> Conclusões e comentários finais
   </UL> 


<p>
<B><blink>Data de entrega: 30 de Abril de 2012. </blink></B>