Concorrência e Paralelismo (2019/2020) - Departamento de Informática
Descrição

Esta UC visa expor os estudantes a um conjunto de conhecimentos e competências que lhes permite endereçar o problema cada vez mais relevante da programação de sistemas de software concorrentes e paralelos. Para atingir este objetivo, o curso endereça tanto o tema da programação paralela de larga-escala, orientada para as arquiteturas de “clustering” e de “cloud”, e o desenvolvimento de programas concorrentes, orientado para os sistemas de mulitprocessores.

O tópico da programação paralela endereça as metodologias aplicadas no desenho de programas e aplicações paralelas eficientes, incluindo o modelo map-reduce. O tópico da programação concorrente endereça as propriedades dos programas concorrentes, as técnicas e as gerramentas utilizadas no desenvolvimento de programas concorrentes.

Na componente laboratorial desta UC os estudantes aplicam os conceitos adquiridos nas aulas teóricas no desenvolvimento de programas concorrentes e paralelos, fazendo uso de bibliotecas paralelas pré-existentes (e.g., Hadoop para map-reduce) e de ferramentas para aferir a correção e prever e avaliar o desempenho dos programas.

A escolha da utilização da linguagem de programação Java disponibiliza acesso a uma conjunto considerável de ferramentas; adicionalmente, a natureza orientada ao objeto da linguagem permite o encapsulamento de detalhes qual tal se apresenta conveniente.

Objectivos

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:

  1. Compreender os conceitos de concorrência e paralelismo, e como estes são úteis no processo de desenvolvimento de software;
  2. Identificar os modelos utilizados para resolver recorrendo a sistemas multiprocessador e de elevado paralelismo;
  3. Conhecer os paradigmas utilizados no desenvolvimento de algoritmos em sistemas multiprocessador e de elevado paralelismo;
  4. Conhecer as linguagens, bibliotecas e ferramentas utilizadas no desenvolvimento de programas concorrentes e paralelos;
  5. Estar familiarizado com problemas de concorrência comuns e como os mitigar e evitar.

Saber Fazer:

  1. Ser capaz de identificar e explorar oportunidades para para concorrência e paralelização num sistema de software;
  2. Ser capaz de particionar um problema em múltiplas tarefas para serem executadas num sistema paralelo.
  3. Ser capaz de raciocinar sobre o comportamento de sistemas concorrentes e paralelos;
  4. Ser capaz de construir sistemas concorrentes e paralelos corretos e eficientes;
  5. Ser capaz de utilizar linguagens de programação como a Java e C e bibliotecas para desenvolver sistemas de software concorrentes e paralelos;
  6. 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.
  7. Ser capaz de prever e medir as características do desempenho de sistemas paralelos.
Programa
  1. 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.
  2. Arquiteturas paralelas
    Taxonomia de Flynn; teoria do desempenho (incluindo as leis de Amdhal e Gustafson).
  3. 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.
  4. “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”.
  5. O modelo transacional
    Operações compostas; transações (serialização), controlo de concorrência otimista (OCC) e memória transacioanl.
  6. Concorrência sem partilha de dados
    Objetos ativos; troca de mensagens; atores.
Bibliografia Principal

Bibliografia principal:

  1. McCool M., Arch M., Reinders J.; Structured Parallel Programming: Patterns for Efficient Computation; Morgan Kaufmann (2012);ISBN: 978-0-12-415993-8
  2. Raynal M.; Concurrent Programming: Algorithms, Principles, and Foundations; Springer-Verlag Berlin Heidelberg(2013); ISBN: 978-3-642-32026-2
Esforço do Aluno
  Horas por crédito 28
  Horas p/ semana Semanas Horas
Aulas práticas e laboratoriais   28.0
Aulas teóricas   28.0
Avaliação   8.0
Estudo   56.0
Projectos e trabalhos   48.0
Total de Horas 168
ECTS 6.0