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 na internet (basta clicar no
link).
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 valor máximo da superfície ocupada até o momento.
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.
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.
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:
- não modifique o seu programa (que deve estar implementado com troca de
mensagens (MPI)) e submeta-o como um job mpich
- 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
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.
Cada experiência deve ser repetida pelo menos 10 vezes e a média de
tempo de execução deve ser reportada.
O que deve entregar:
Código da implementação
Relatório contendo as seguintes seções:
- Introdução (apresentação do problema)
- Solução paralela (explicação do seu código e justificativas)
- Resultados experimentais e comparação entre tempos sequenciais
e paralelos no grid. Incluir gráficos:
- 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)
- 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.
- Conclusões e comentários finais