Este trabalho é baseado na Maratona de Programação Paralela, um torneio de programação que ocorre há vários anos junto com os eventos SBAC-PAD (International Symposium on Computer Architecture and High Performance Computing) / WSCAD-SCC (Simpósio em Sistemas Computacionais de Alto Desempenho).
O objetivo geral do torneio é reduzir o tempo de processamento de um conjunto de problemas fornecido, utilizando técnicas de programação paralela.
Regras
Para cada problema, é fornecida uma descrição e uma implementação sequencial.
A descrição de cada problema ilustra o formato de entrada e saída do programa, que deve ser observado cuidadosamente, pois será usado como critério para julgar se a solução está correta.
Cada programa pode ser modificado utilizando ferramentas/técnicas vistas na disciplina (MPI, OpenMP) ou facilmente instaláveis nas máquinas linux01/02 (nesse caso, é necessário consultar a professora antes). Os Makefile's fornecidos podem ser alterados, mas devem conter regras all e run, respectivamente para compilação e execução.
Os programas serão executados em 2 servidores com a mesma capacidade de processamento paralelo das máquinas linux01 e linux02. Outras entradas no mesmo formato poderão ser usadas para executar os programas.
O tempo de execução de cada programa será obtido com o programa 'time', usando o 'user time' como métrica. Cada programa será executado no mínimo 2 vezes com a mesma entrada e será levado em conta o menor tempo obtido. O tempo de cada programa sequencial será medido da mesma forma.
Será calculada a aceleração para cada programa, dividindo-se o tempo sequencial pelo tempo da solução paralela. Cada equipe ganhará pontos em função da aceleração obtida em cada problema. Soluções não entregues, ou com erro de compilação/execução terão pontuação zerada. A equipe com maior número de pontos será vencedora.
Conjunto de Problemas
Para este torneio, foi escolhido um conjunto de problemas utilizado na Maratona de Programação Paralela de 2009, cujos programas são de áreas bem variadas (otimização, matemática, ordenação, biologia computacional, etc.).
A descrição original dos problemas está disponível aqui.
O trabalho pode ser feito em equipes de até 2 alunos. Cada equipe deve ser identificada por um "nome de guerra" :-)
A entrega deve ser por mail à professora e deve conter identificação da equipe e dos alunos componentes. O trabalho deve ser entregue em um único arquivo compactado, contendo uma subpasta para cada problema resolvido (A, B, ..) . Em cada pasta, deve ser entregue o código-fonte e um Makefile, contendo duas regras: all (para compilação) e run (para execução).
Prazo: 09/06, 23:59 (Obs.: a maratona original dura no máximo 8h ;-) )
Premiação
A equipe vencedora poderá terminar o semestre mais cedo, sendo dispensada do último trabalho.
Possíveis empates ou outros casos omissos serão resolvidos pela comissão julgadora, isto é, pela professora ;-)