Algoritmos Paralelos (1/02, 1/07, 2/11, 2/2012)
Programa da Disciplina
Objetivos:
- Capacitar o aluno a resolver problemas algorítmicos em paralelo através do projeto e implementação de algoritmos com o auxílio de uma linguagem de programação e bibliotecas (MPI, OpenMP e CUDA).
Ementa:
1. Introdução a Computação Paralela. 2. Modelos de computação paralela. 3. Paradigma de troca de mensagens. 4. Introdução a MPI, OpenMP e CUDA e exemplos. 5. Operações básicas como soma e soma de prefixos. 6. Ordenação. 7. Algoritmos para problemas em grafos. 8. Estudos de Casos.
Programa:
1. Introdução a Computação Paralela. 2. Modelos de Computação Paralela. Modelo PRAM. Modelo de Rede. Modelos Realísticos. Modelo BSP/CGM. Modelo LogP. 3. Programação com Troca de Mensagens. 4. Programação usando as Bibliotecas MPI, OpenMP e CUDA. 5. Algoritmos Básicos. Soma, Soma de Prefixos, Integração e algoritmos com número de rodadas constantes de comunicação. 6. Busca e Ordenação Paralela. 7. Algoritmos para Problemas em Grafos. 8. Algoritmos para Problemas de Programação Dinâmica, Biologia Computacional, Algoritmos Numéricos e Utilização de Bibliotecas.
Bibliografia:
- E. N. Cáceres, H. Mongelli e S. W. Song, Algoritmos Paralelos usando CGM/PVM/MPI: Uma introdução, XXI Congresso da SBC, Jornada de Atualização em Informática, 2001, pp. 219-278.*
- P. Pacheco. An Introduction to Parallel Programming. Morgan Kaufmann, 2011.*
- D. B. Kirk and W. W. Hwu. Programming Massively Parallel Processors: A Hands-on Approach. Morgan Kaufamann, 2010.*
- A. Grama, A. Gupta, G. Karpys and V. Kumar. Introduction to Parallel Computing. 2nd Ed. Addison Wesley, 2006.*
- Barry Wilkinson and Michael Allen. Parallel Programming - Techniques and Applications Using Networked Workstations and Parallel Computers. 2nd Ed. Prentice Hall, 2005.*
- P. S. Pacheco. Parallel Programming with MPI. Morgan Kaufmann Publishers, 1997.*
- J. JáJá. Introduction to Parallel Algorithms. Addison Wesley, 1992.
- W. Gropp, E. Lusk and A. Skjellum. Using MPI Portable Parallel Programming with the Message-Passing Interface. 2nd Ed. MIT Press, 1999.
- W. Gropp, E. Lusk and R. Thakur. Using MPI-2 Advanced Features of the Message-Passing Interface. MIT Press, 1999.
- A. Gibbons and P. Spirakis. Lectures on Parallel Computation. Cambridge University Press, 1993.