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, 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, <B>"Designing and Building Parallel Programs"</B>, disponível <A
HREF="http://www-unix.mcs.anl.gov/dbpp/"> aqui. </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
Amin, que guarda o máximo valor de superfície ocupada até o momento.
<p>
Seu programa deve gerar aleatoriamente 10.000 peças de dimensões
diferentes (considere apenas retângulos) e com restrições baseadas
naquelas mencionadas na página 66.
<p>
Você deve rodar este programa em um processador e computar o tempo de
execução. Além disso, deve rodar o seu programa em grid usando
gLite. Deve primeiro escolher um nó do grid que atenda aos requisitos
do seu programa (escolha o resource broker adequado). Este seu
programa que roda 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>
O que você 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
   <LI> Conclusões e comentários finais
   </UL>