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: 27 de Agosto 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. Você deve discutir as possibilidades de paralelização do problema proposto e implementar o paradigma de paralelismo (de dados ou de controle) mais adequado ao problema proposto. O trabalho deve ser implementado no ambiente Pthreads.

Problema: Caminho Mais Curto

Implemente o algoritmo Single-Source Shortest Path descrito na seção 12.4 do livro do Quinn (1994), utilizando uma máquina paralela MIMD. A máquina paralela MIMD deverá ser do tipo memória compartilhada, ou seja, todos os processos acessam um espaço de endereçamento único.

Para referência, estão disponíveis paralelizações usando Pthreads do QuickSort , filósofos jantando , produtor-consumidor , leitor-escritor , soma de vetor , e semáforos usando variável de condição , e duas versões do Crivo de Eratóstenes (dados e tarefas ).

O que deve ser apresentado:

• Listagem do programa.
• Listagem dos testes executados: execução passo-a-passo da massa de dados da figura 12-5 do livro do Quinn (1994).
• Complexidade e aspectos positivos e negativos da alternativa de implementação escolhida.
• Estudo comparativo entre o algoritmo sequencial e o algoritmo paralelo escolhido para implementação e o speedup obtido obtido pela sua implementação em termos da fração serial e fração paralela medida pelo programa. Utilize 2, 4 e 8 threads. Gere massas de teste usando um gerador de números aleatórios para gerar grafos randômicos. Discuta os resultados obtidos.
• Limite inferior para a implementação utilizando o modelo PRAM
• Apresente a documentação das implementações realizadas (veja aqui maiores detalhes sobre instruções para a entrega de trabalhos praticos).

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 (5%)
• Testes:
  • Estudo comparativo entre o algoritmo sequencial e o algoritmo paralelo escolhido para implementação e o speedup obtido obtido (25%)
  • Apresentação (gráficos, tabelas, etc) (10%)
  • Análise dos resultados obtidos e conclusões (10%)

Referências

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