Departamento de Informática (UM)

Algoritmos Paralelos

16920 [ME97ME9700005441]

Mestrado em Computação Avançada [MCA]

S2

João Luís Ferreira Sobral

Objetivos

Os conteúdos programáticos abordam os aspetos mais relevantes da análise e desenho de algoritmos paralelos, incluindo os modelos para análise da complexidade dos algoritmos, padrões básicos/típicos de paralelismo e a apresentação dos algoritmos paralelos mais comuns em aplicações científicas. Deste modo, os conteúdos programáticos permitem aos estudantes obterem as competências pretendidas.

Programa

1. Análise de complexidade algoritmos paralelos
2. Padrões básicos de paralelismo (map, reduce e scan) e sua implementação eficiente nas várias plataformas de elevado desempenho (Clusters, GPUs)
3. Padrões típicos de paralelismo: pipeline, farm, hearbeat e divide&conquer.
4. Análise de algoritmos paralelos existentes: ordenação, operações sobre matrizes densas e esparsas, soluções iterativas de sistemas de equações lineares, N-body e algoritmos sobre grafos (MST).
5. Geração de números aleatórios e alocação de memória.
6. Algoritmos paralelos lock-free.

Bibliografia

Parallel Scientific Computation: A Structured Approach Using BSP, Rob H. Bisseling, Oxford University Press, 2020.

Structured Parallel Programming, Michael McCool, Arch Robison & James Reinders, 2012.

Parallel Computing Architectures and APIs, Vivek Kale, Chapman and Hall/CRC, 2019.

Programming Massively Parallel Processors, A Hands-on Approach, 3rd Ed., David Kirk & Wen-mei Hwu, Morgan Kaufmann, 2016.

Resultados da aprendizagem

- Caracterizar os padrões base de paralelismo.
- Analisar a complexidade dos algoritmos paralelos nos vários tipos de sistemas de computação.
- Conceber algoritmos paralelos eficientes para computação científica adequados a cada arquitetura.
- Identificar nas aplicações científicas os algoritmos paralelos subjacentes.

Método de avaliação

A avaliação é realizada através de um teste (peso de 30 a 50%) e de um trabalho prático (peso 50 a 70%).

Funcionamento

Turno: T 1; Docente: João Luís Ferreira Sobral; Dep.: DI; Horas: 15.
Turno: PL 1; Docente: João Luís Ferreira Sobral; Dep.: DI; Horas: 30.