Algoritmos Paralelos

Código: PINF7043
Curso: Doutorado em Ciência da Computação
Créditos: 4
Carga horária: 60
Ementa: * Modelos de computação paralela:
* Memória compartilhada: PRAM síncrona e assíncrona, QSP, QWQR, BSP, LogP, SMP
* Memória distribuída: SMPD
* Paradigmas de programação: multi-threaded, BSP, passagem de mensagem, funcional, tuple space, CSP
* Desempenho: profundidade de computação, trabalho, custo, speed-up, eficiência
* Famílias fundamentais de algoritmos: árvore binária balanceada, divide-and-conquer, jumping pointer, compressão, randomização
* Exemplos de aplicações em áreas tais como:
* ordenação
* grafos
* processamento de strings
* métodos numéricos e operações com matrizes: multiplicação de matrizes, paralelização de método iterativo de Gaus-Seidel e Jacobi
* otimização
* Complexidade paralela: P-completeness
Bibliografia: * A. Gibbons, W. Rytter, "Efficient parallel algorithms", Cambridge University Press 1989.
* S. G. Akl, "Parallel Computation: Models and Methods", Prentice-Hall, Inc., 1997.
* E. Gropp, E. Lusk, A. Skjellum, "Using MPI: Portable Parallel Programming with the Message Passing Interface - 2nd Edition", MIT Press, 1999.
* P. Pacheco, "Parallel Programming with MPI", Morgan Kauffman -1st Edition, 1996
* Artigos selecionados de periódicos/conferências da área.