Universidade Federal de Minas Gerais
Departamento de Ciência da Computação

CURSO DE PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO
PROJETO E ANÁLISE DE ALGORITMOS

Última alteração: 9 de Outubro de 2002

Professor: Nivio Ziviani
Monitora: Claudine Santos Badue
4$^{\underline{o}}$ Trabalho Prático - 20/08/02 - 10 pontos
Data de Entrega: 13/09/02
Penalização por Atraso: 1 ponto até 18/09/02 mais 1 ponto por dia a seguir
Observação: Toda a documentação deverá ser apresentada como uma página acessível via Web (apresente o link para acesso à documentação).

Computação Paralela

O objetivo deste trabalho é o de projetar um algoritmo paralelo para ser executado em uma máquina paralela. A implementação deve ser feita usando sockets e threads para comunicação entre o processo mestre e os processos escravos. Veja como criar um processo mestre , um processo escravo , e o arquivo makefile para compilá-los.

Problema: Multiplicação de Matrizes

Implemente um algoritmo paralelo para realizar multiplicação de matrizes usando uma máquina paralela MIMD. Você deverá discutir as diversas possibilidades de implementação descritas no capítulo 7 do livro do Quinn (1994) e escolher a mais adequada à arquitetura paralela MIMD. Alternativamente, além de discutir as possibilidades descritas na literatura, você poderá propor e implementar sua própria estratégia de paralelização do problema.

A máquina paralela MIMD deverá ser do tipo rede de estações de trabalho. (NOW - Network Of Workstations) (Anderson, Culler e Patterson, 1995).

O que deve ser apresentado:

• Listagem do programa.
• Listagem dos testes executados: execução passo-a-passo da massa de dados da figura 7-12 do livro do Quinn (1994).
• Complexidade e aspectos positivos e negativos das várias alternativas de implementação.
• Estudo comparativo entre o algoritmo sequencial e o algoritmo paralelo escolhido para implementação e o speedup obtido. Utilize 2, 4 e 8 máquinas. Gere massas de teste usando um gerador de números aleatórios para gerar matrizes randômicas. As matrizes devem ter um tamanho suficientemente grande para que o algoritmo paralelo apresente speedup. Discuta os resultados obtidos.
• Apresente a documentação das implementações realizadas (veja aqui maiores detalhes sobre instruções para a entrega de trabalhos praticos).
• Limite inferior para a implementação utilizando o modelo PRAM.
• Limite inferior para a implementação utilizando o modelo SIMD.

Critérios a serem utilizados na avaliação:

• Implementação:
  • Explicação dos algoritmos em alto nível. (10%)
  • Clareza, legibilidade, estruturação do código. (5%)
  • Indentaçao e comentários explicativos. (5%)
• Documentação:
  • Apresentação, descrição do problema a ser resolvido, motivação, dificuldades e possíveis aplicações práticas. (5%)
  • Descrição da arquitetura implementada e das técnicas utilizadas na solução, justificativa das principais decisões tomadas. (10%)
  • Complexidade e aspectos positivos e negativos da alternativa de implementação escolhida. (10%)
  • Limite inferior para a implementação utilizando o modelo PRAM e SIMD. (10%)
• Testes:
  • Estudo comparativo do speedup obtido para os algoritmos paralelos. (25%)
  • Apresentação (gráficos, tabelas, etc). (10%)
  • Análise dos resultados obtidos e conclusões. (10%)

Obs.: Toda a fase de depuração deverá ser executada em uma única estação de trabalho, até que seu programa esteja inteiramente depurado. Apenas a fase de estudos do speedup deverá ser realizada utilizando a rede do DCC.

Referências

[Q] M. J. Quinn, Parallel Computing Theory and Practice, McGraw-Hill, 1994, cap. 12.

T. Anderson and D. Culler and D. Patterson ``A Case for NOW (Network of Workstations)'', IEEE Micro, vol. 15, no. 1, 1995, pp. 54-64.