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.

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, "Designing and Building Parallel Programs", disponível aqui.

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.

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.

Você deve rodar este programa em 1, 2, 4 e 8 processadores e "plotar" uma curva de tempo de execução. Para fazer esta parte do trabalho têm à disposição 8 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.

Além disso, deve rodar o seu programa em grid usando gLite utilizando 2 abordagens diferentes: