Concorrência e Paralelismo

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.

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:

  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

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

Componente Teórico-Prática (CTP)

A componente teórico-prática (CTP) obtém-se através da realização de dois teses individuais durante o semestre, ou de um exame individual. Os testes e o exame decorrerão online e sem consulta (datas a anunciar pelos serviços da FCT-NOVA).

Tanto os testes como o exame conterão questões sobre os trabalhos práticos e o projeto realizado neste ano letivo. Os alunos com frequência estão dispensados apenas das questões sobre o projeto, tendo que responder às questões sobre os trabalhos práticos.

Unidades: a CTP será arredondada às centésimas.

Limite mínimo: é exigida uma classificação CTP ≥ 8,50 valores.

Componente Laboratorial (CL)

A componente laboratorial (CL) obtém-se através da aplicação da seguinte fórmula: 

CL = 0.6 * CG + 0.4 * CI

onde

CG = classificação grupo
CI = classificação individual

A classificação de grupo (CG) é definida pelo mérito do desenvolvimento de um projeto de programação e elaboração de um relatório que descreve, avalia e analisa a solução desenvolvida. O projeto é desenvolvido em grupos de dois alunos e a classificação CG é idêntica para ambos os elementos do grupo.

A classificação individual (CI) é definida pelo mérito individual no processo de desenvolvimento do projeto de programação referido em CG. Esta componente é aferida ponderando a distribuição de trabalho entre os elementos do grupo, tal como reportada pelos alunos no relatório do projeto, com a quantidade, dificuldade e relevância de trabalho individual percecionado através dos commits no repositório GIT do grupo.

Tanto o professor como os alunos podem requerer a realização de uma prova oral com todos ou parte dos elementos do grupo para apresentação e debate do trabalho realizado e reportado.

Unidades: a CG, CI e CL serão arredondadas às centésimas.

Limite mínimo: para ter frequência à unidade curricular é exigida uma classificação CL ≥ 8,50 valores.

Datas relevantes:

  • Apresentação do projeto: TBD
  • Submissão do código: TBD
  • Submissão do relatório: TBD
  • Formato de submissão: ID do commit a considerar (que tenha sido realizado dentro do prazo)

Componente Participação (CP)

A componente participação (CP) obtém-se através da participação nos vários canais de comunicação com o professor e com os colegas. Esta componente será definida pela ponderação da participação individual de cada aluno, considerando a quantidade e teor das participações nos fóruns Piazza e Slack. As participações com mais impacto no grupo/turma e/ou de apoio/esclarecimento aos colegas terão maior valoração.

Unidades: a CP será arredondada às centésimas.

Limite mínimo: não há limite mínimo para esta classificação.

Classificação Final (CF)

CF = 0.5 * CTP + 0.5 * CL + 0.05 * CP

Unidades: a CF será arredondada às unidades.

Conteúdo

  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.

Cursos

Cursos onde a unidade curricular é leccionada: