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
Hervé Miguel Cordeiro Paulino
Horas
Semanais - 4
Totais - 52
Idioma de ensino
Portuguê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
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 serão presenciais e sem consulta (datas a anunciar pelos serviços da FCT-NOVA).
Tanto os testes como o exame poderão questões sobre os trabalhos práticos e sobre o projeto realizado neste ano letivo. Nenhum aluno (repetente/não-repetente) está isento de responder às questões sobre os trabalhos práticos e o projeto.
Nos testes e no exame pode-se utilizar uma calculadora simples (não-alfanumérica e não-programável).
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 apenas 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.
Datas relevantes:
- Apresentação do projeto: TBD (ver os slides)
- Submissão do código: TBD (ver os slides)
- Submissão do relatório: TBD (ver os slides)
- Formato de submissão: ID do commit a considerar (que tenha sido realizado no prazo)
Frequência
O critério para a obtênção de frequencia é: CL >= 8.5
A frequência dos 2 anos anteriores é válida para o presente ano. No entanto, tal não impede que o aluno possa inscrever-se num truno prático e frequentar as aulas práticas. O aluno pode ainda tentar melhorar a nota obtida anteriormente. Nesse caso, a nota CL final será a melhor nota de entre a nota CL obtida este ano e a obtida anteriormente.
Classificação Final (CF)
CF = 0.6 * CTP + 0.4 * CL
Unidades: a CF será arredondada às unidades.
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”
“Safety” 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.