Concorrência e Paralelismo
Objetivos
Esta UC pretende dar aos estudantes uma formação sólida sobre concorrência. No final da UC espera-se que estudantes compreendam os problemas relacionados com a concorrência e com a execução concorrente de programas, conheçam os mecanismos disponíveis nas linguagens de programação para especificação de programas concorrentes, saibam como desenvolver programas concorrentes corretos e eficientes fazendo uso de padrões e de técnicas de programação comuns.
Saber:
- Compreender os conceitos de concorrência e paralelismo, e como estes são úteis no processo de desenvolvimento de software;
- Identificar os modelos utilizados para resolver recorrendo a sistemas multiprocessador e de elevado paralelismo;
- Conhecer os paradigmas utilizados no desenvolvimento de algoritmos em sistemas multiprocessador e de elevado paralelismo;
- Conhecer as linguagens, bibliotecas e ferramentas utilizadas no desenvolvimento de programas concorrentes e paralelos;
- Estar familiarizado com problemas de concorrência comuns e como os mitigar e evitar.
Saber Fazer:
- Ser capaz de identificar e explorar oportunidades para para concorrência e paralelização num sistema de software;
- Ser capaz de particionar um problema em múltiplas tarefas para serem executadas num sistema paralelo.
- Ser capaz de raciocinar sobre o comportamento de sistemas concorrentes e paralelos;
- Ser capaz de construir sistemas concorrentes e paralelos corretos e eficientes;
- Ser capaz de utilizar linguagens de programação como a Java e C e bibliotecas para desenvolver sistemas de software concorrentes e paralelos;
- Ser capaz de utilizar ferramentas de programação no desenvolvimento de aplicações concorrentes e paralelas, incluindo as fases de desenho, implementação, depuração e instalação.
- Ser capaz de prever e medir as características do desempenho de sistemas paralelos.
Caracterização geral
Código
11158
Créditos
6.0
Professor responsável
João Manuel dos Santos Lourenço, Pedro Abílio Duarte de Medeiros
Horas
Semanais - 4
Totais - 56
Idioma de ensino
Inglês
Pré-requisitos
A disponibilizar brevemente
Bibliografia
Bibliografia principal:
- McCool M., Arch M., Reinders J.; Structured Parallel Programming: Patterns for Efficient Computation; Morgan Kaufmann (2012); ISBN: 978-0-12-415993-8
- Raynal M.; Concurrent Programming: Algorithms, Principles, and Foundations; Springer-Verlag Berlin Heidelberg (2013); ISBN: 978-3-642-32026-2
Método de ensino
O ensino consiste na exposição da matéria em aulas teóricas e na resolução de problemas em aulas práticas de laboratório. No laboratório, os alunos analisam, implementam e avaliam algoritmos concorrentes e paralelos. Algumas aulas práticas são dedicadas à realização dos projetos de programação.
Método de avaliação
A avaliação é contínua e composta por:
a) Média de três testes de escolha múltipla a realizar durante o semestre (em caso de ausência ou não aprovação por testes, os estudantes poderão realizar um exame no final do semestre). A média da clasificação dos testes (com arredondamentos às centésimas) ou do exame terá um peso de 65% na classificação final.
b) Cassificação individual no projeto (arredondada às centésimas), com peso de 30% na classificação final.
c) Participação ativa nas aulas teóricas e práticas, bem como no fórum Piazza e na interação com os colegas, terá um peso de 5% na classificação final (notar que "participação ativa nas aulas" não é "estar presente").
Nota: O exame final, quando realizado tanto para aprovação como para melhoria de nota, substitui a componente de avaliação a) no cálculo da classificação final.
Para obter frequência à UC é necessário:
— Obter uma classificação mínima de 9,50 valores na componente de avaliação b) (projecto).
Nota: Em caso de utilização da frquência do ano anterior, o peso das componentes a), b) e c) será, respetivamente, de 70%, 30% e 0%.
Para obter aprovação à disciplina é necessário:
i) Ter frequência à diciplina, obtida nesta edição ou na do ano anterior.
ii) Que a cassificação na componente de avaliação a) seja superior ou igual a 9,50 valores.
iii) Que a classificação final seja superior ou igual a 9,50 valores.
Conteúdo
- Programação paralela
O espectro dos problemas computacionais extremamente exigentes; problemas regulares e irregulares; estrateégias para a decomposição de problemas e o seu mapeamento em padrões de programação; os modelos transacional e map-reduce. - Arquiteturas paralelas
Taxonomia de Flynn; teoria do desempenho (incluindo as leis de Amdhal e Gustafson). - Controlo de concorrência e sincronização
Competição e colaboração; atomicidade; linearização; monitores, locks; semáforos; barreiras; produtor-consumidor; locks de leitura e escrita; futuros, concorrência na prática em Java e C. - “Safety” e “liveness”
“Savety” vs. “liveness”; progresso; “deadlock”; prevenção, deteção e recuperação de “deadlocks”; “livelocks”; prevenção de “livelocks”; inversão de prioridade; herança de prioridade. Algoritmos “lock-free”. - O modelo transacional
Operações compostas; transações (serialização), controlo de concorrência otimista (OCC) e memória transacioanl. - Concorrência sem partilha de dados
Objetos ativos; troca de mensagens; atores.