Computação Paralela Distribuída Mestrado Eng.ª Informática 2013/2014 Docente responsável: A. Proença

Direitos de Autor & Copyright
Avisos | Equipa docente | Objetivos | Resultados de Aprendizagem | Programa | Bibliografia | Sumários: SCD PAC PCP AMN PI | Avaliação

(Ano anterior: 2012/2013)

Ultima Modificação: 04 Dez 2013
 

departamento de informática

Avisos:

1. Ciclo de palestras temáticas: está já definido o calendário das palestras temáticas para o 1º semestre, findo as quais os grupos de Projeto Integrado passarão à escolha dos respetivos temas de trabalho (os links para osslides das apresentações estão incluídos à frente):
      05-nov-13, 11h30-13h00: Artur Cavaco-Paulo, Dep. Engª Biológica, Fine and coarse-grain simulations by molecular dynamics of protein and biological interfaces (slides) (vídeos, 159MB)
      05-nov-13, 14h00-15h00: José Luís Pinho, Dep. Engª Civil, Delft3D – Software for coastal processes modelling (slides)
      12-nov-13, 11h30-13h00: Miguel Nóbrega, Dep. Engª Polímeros, Computer aided design of extrusion forming tools (slides)
      12-nov-13, 14h00-15h00: Stéphane Clain, Dep. Mat & Aplicações, Modelling and numerical methods in Scientific Computing (slides)
      19-nov-13, 09h00-10h30: Luís Alves, Dep. Engª Mecânica, DD3IMP (Finite Element Solver): the challenge of computational performance improvement through HPC (slides)
      19-nov-13, 14h00-15h00: Manuel Melle-Franco, CCTC, Computer models for (carbon) nanotechnology (slides)
      26-nov-13, 11h30-13h00: Miguel Rocha, Dep. Informática, Graph-based algorithms for metabolic engineering applications (slides)
      03-dez-13, 12h00-13h00: Rui Silva, Dep. Informática, Experience with PAPI performance analysis tool  (slides)
      03-dez-13, 17h00-18h30: António Onofre / Nuno Castro, Dep. Física, Code optimization in High Energy Physics - challenges at the LHC   (slides)
   Após a última apresentação, os grupos de trabalho deverão enviar ao coordenados da UCE uma lista ordenada dos 3 temas que mais lhes interessam para o PI, até às 12h00 de sexta 06-dez-13, para que o processo final de alocação de temas seja concluído na terça 10-jan e os trabalhos definidos e atribuídos até 17-dez. (04-dez-13)
    

2. Atividades complementares: para além das atividades divulgadas no início do ano neste website, estão ainda previstas outras atividades especialmente organizadas em complemento e para apoio ao funcionamento desta UCE, incluindo a participação em palestras com investigadores convidados, em Seminários avançados e em Workshops internacionais e a realização de um estágio (internship) de 5 a 6 semanas na Universidade do Texas em Austin. Mais detalhes em Avisos separados. (27-set-13)
    

3. Funcionamento desta UCE: esta UCE vai funcionar com 4 módulos temáticos, 2 por semestre, e por uma componente de projeto integrado, ao longo dos 2 semestres. Os módulos previstos para o 1º semestre de 2013/14 serão essencialmente SCD (manhã) e PAC (tarde), embora alguns conteúdos dos outros módulos possam ser introduzidos quando necessário; haverá ainda um conjunto de palestras convidadas em temas relacionados com ciências computacionais, tendo em vista a preparação e funcionamento do Projeto Integrado; no 2º semestre funcionarão essencialmente os outros 2 módulos. A componente prática que integra os temas dos diversos módulos, terá uma parte de análise de casos de estudo para assimilação e treino de competências básicas, e posteriormente a realização de um ou mais mini-projetos.(27-set-13)
    

4. Funcionamento desta página: esta página contém informação que em princípio se manterá estável ao longo de todo o semestre, com exceção deste bloco de avisos; a fim de garantir a leitura atualizada deste bloco, sugere-se que se faça o refrescamento da página sempre que a ela aceder, para ter acesso aos conteúdos mais atualizados, nomeadamente, no que diz respeito aos sumários e notas complementares de estudo. (27-set-13)
    

5. Início das sessões letivas: terça, 01-out-13, pelas 9h00; este dia será dedicado à apresentação dos diversos temas que constituem esta UCE, por cada um dos docentes da equipa, bem como um debate para melhor contextualizar o ambiente de trabalho da UCE; antes desta sessão não serão disponibilizadas as restantes páginas deste website.  (27-set-13)

Topo...

Equipa docente

• Docentes responsáveis pela leccionação dos módulos

Sistemas de Computação e Desempenho (SCD)
Alberto José Proença
email: aproenca<at>di.uminho.pt

Planeamento e Administração de Clusters (PAC)
António Manuel Pina
email: pina<at>di.uminho.pt

Paradigmas de Computação Paralela (PCP)
João Luís Sobral
email: jls<at>di.uminho.pt

Algoritmos e Métodos Numéricos (AMN)
Rui Ralha
email: r_ralha<at>math.uminho.pt
 

Topo...

Objectivos

A computação paralela e distribuída (CPD) concentra-se actualmente, em ambiente de rede local, em clusters computacionais Beowulf e em grelhas computacionais (Grid ou Cloud), quando o ambiente de rede ultrapassa os limites institucionais.

A computação usando clusters interligados em grelha envolve várias áreas distintas mas interrelacionadas. A UCE CPD vai concentrar-se no desenvolvimento de competências (conhecimentos, e aptidões intelectuais e práticas) nas seguintes áreas, com indicação explícita dos módulos temáticos que constituem a UCE:

• a estrutura do sistema físico computacional, com a dupla finalidade de execução eficiente de aplicações e da gestão de recursos; este é o principal objectivo do módulo de Sistemas de Computação e Desempenho (SCD);
• o ambiente de administração e de gestão de recursos computacionais, quer em ambiente de cluster, quer em grelha; este é o principal objectivo do módulo de Planeamento e Administração de Clusters (PAC);
• a identificação e utilização de algoritmos, modelos, bibliotecas e ferramentas de apoio à programação paralela; este é o principal objectivo do módulo de Paradigmas de Computação Paralela (PCP);
• a análise dos algoritmos e métodos numéricos escaláveis mais comuns e respectiva complexidade; este é o principal objectivo do módulo de Algoritmos e Métodos Numéricos (AMN);
• integração de conceitos e práticas destes módulos temáticos em trabalhos e/ou projetos; este é o principal objectivo do módulo de Projeto Integrado (PI).

O reforço da profissionalização e integração em ambientes de I&D é também um objectivo a atingir, através (i) da realização de seminários temáticos por investigadores convidados, com ênfase em aspectos de Ciências e Engenharia Computacional, e (ii) da participação ativa em projectos internacionais de I&D em Computação Avançada num dos centros mais reputados nos USA.
Mais concretamente, este objectivo concretiza-se com a realização de um internship no Institute of Computational Engineering and Sciences (ICES) e/ou no Texas Advanced Computing Center (TACC), na Univ. Texas em Austin (custos de viagem e alojamento incluídos).

.

Topo...

Resultados de Aprendizagem

Um estudante que complete com sucesso a UCE em CPD deverá ser capaz de demonstrar que adquiriu as seguintes competências:

• caracterizar e avaliar qualitativa e quantitativamente a arquitetura de sistemas de computação paralelos/distribuídos e respectivo desempenho na execução de aplicações, bem como desenvolver e/ou modificar aplicações computacionais com vista a otimizar o seu desempenho e escalabilidade;
• planear e instalar clusters e grelhas computacionais, e avaliar a aplicar as técnicas mais adequadas de administração e gestão dos recursos;
• projetar, desenvolver, implementar e otimizar aplicações paralelas e distribuídas, utilizando paradigmas de computação paralela;
• caracterizar e desenvolver implementações sequenciais e paralelas de algoritmos e métodos numéricos;
• planear, projctar, executar e divulgar os resultados de trabalhos em Engenharia da Computação aplicada às Ciências Computacionais.

Algumas destas competências poderão ser mais detalhadas, de acordo com a ênfase dada em cada um dos módulos temáticos:

• em Sistemas de Computação e Desempenho:
  • identificar e caracterizar a introdução dos diversos tipos de paralelismo na arquitetura interna dos processadores e no seu acesso à memória, com destaque para os processadores multi-core e many-core
  • selecionar as métricas, métodos e técnicas de avaliação de desempenho de programas em execução, para configurações da arquitetura de um sistema computacional
  • avaliar quantitativamente o desempenho de um sistema de computação na execução de aplicações informáticas
  • descrever e caracterizar os principais componentes de um sistema de computação em cluster ou em grelha
  • avaliar criticamente a arquitetura dos sistemas de computação paralelos e distribuídos
• em Planeamento e Administração de Clusters:
  • identificar os diferentes tipos de arquitecturas de cluster e grids (incluindo a cloud) e discutir as respectivas vantagens e limitações
  • analisar e avaliar os requisitos de hardware e software com vista ao planeamento e instalação do equipamento, com referência à virtualização de máquinas
  • identificar os requisitos dos utilizadores necessários para seleccionar o software a instalar e a manter
  • identificar e caracterizar políticas de gestão e escalonamento de trabalhos e avaliar os resultados da sua aplicação
  • discutir e avaliar o desempenho efectivo de programas paralelos em clusters e grids
• em Paradigmas de Computação Paralela:
  • desenvolver aplicações paralelas capazes de executar numa gama alargada de arquiteturas
  • implementar aplicações utilizando os tipos mais comuns de algoritmos paralelos
  • medir e otimizar o desempenho de aplicações em sistemas de memória distribuída
  • implementar técnicas de gestão de recursos ao nível da aplicação
• em Algoritmos e Métodos Numéricos:
  • apreender os fundamentos teóricos matemáticos e numéricos para suporte aos métodos estudados
  • identificar, a diferentes níveis (complexidade, robustez numérica, etc.) pontos fortes e fracos dos métodos
  • desenvolver implementações sequenciais e paralelas e discutir os resultados numéricos obtidos
  • identificar, nos algoritmos paralelos, eventuais problemas de balanceamento de carga e/ou elevados custos de comunicação entre os processadores
  • usar bibliotecas numéricas (BLAS, Lapack, Scalapack).
• em Projeto Integrado:
  • planear, executar e divulgar os resultados de projetos de avaliação e otimização de desempenho de sistemas de computação na execução de tarefas em contexto de aplicações reais de ciência Computacional
  • desenvolver de forma integrada e em equipa, a função de conceção e projeto em Engenharia da Computação, e respectiva comunicação escrita e discussão oral dos resultados.

Topo...

Programa

Conteúdos para cada um dos módulos temáticos e para o projecto integrado:

• Sistemas de Computação e Desempenho:
  • evolução recente da arquitetura de processadores: pipeline, superescalaridade, multi-threading, multi-core, many-core; hierarquia de memória em ambiente partilhado
  • avaliação de desempenho na execução de aplicações: métricas, profiling, análise e afinação de código (destaque para ciclos iterativos, manuseamento de matrizes e chamada de funções, localidade dos dados), benchmarking
  • evolução do paralelismo nas arquiteturas: arquiteturas vetoriais, arquiteturas paralelas com memória partilhada e memória distribuída, arquiteturas distribuídas em rede; análise de desempenho em arquitcturas massivamente paralelas, com destaque para as plataformas heterogéneas com as novas gerações de GPU's
• Planeamento e Administração de Clusters:
  • introdução aos clusters: arquitectura (terminologia, tecnologias, limitações); equipamentos (componentes individuais e de rede, coordenação de recursos descentralizados)
  • Linux para clusters Beowulf: características; instalação e configuração de serviços; segurança
  • planeamento e construção de clusters: missão, arquitetura, suporte lógico e virtualização; sistemas de ficheiros paralelo; tecnologias de interligação; clonagem e automatização de instalações
  • gestão de clusters: modelos de execução de trabalhos, monitorização e administração de utilizadores e recursos, políticas de escalonamento e contabilização, segurança de dados, análise de desempenho e afinação
  • construção de grids: arquitetura, protocolo e serviços; modelos de utilização e segurança; interfaces de programação; evolução nos desktop grids e no cloud computing.
  • estudo de caso: o cluster SEARCH na Universidade do Minho, com Rocks, Ganglia, OpenPBS, Maui, GPFS
• Paradigmas de Computação Paralela:
  • modelos de programação: fios de execução, passagem de mensagens, objetos distribuídos, workflows
  • metodologias de desenvolvimento de aplicações paralelas: partição, comunicação, agregação e mapeamento de tarefas
  • análise de algoritmos paralelos típicos: pipelining, farming, heartbeat e divide & conquer
  • medição e otimização do desempenho de aplicações em sistemas de memória distribuída
  • escalonamento de recursos ao nível da aplicação
• Algoritmos e Métodos Numéricos:
  • métodos de Monte Carlo: geradores sequenciais e paralelos de números aleatórios, aplicações do método de Monte Carlo (case studies)
  • multiplicação de matrizes: implementações sequenciais, implementações paralelas no modelo message-passing
  • sistemas de equações lineares: método de eliminação de Gauss, métodos iterativos, análise da convergência, implementações sequenciais e paralelas
  • método das diferenças finitas: resolução numérica das equações diferenciais que ocorrem em certos problemas "clássicos" (vibração de uma corda, difusão de calor)
  • transformada rápida de Fourier: análise de Fourier (introdução), as transformadas DDT (discreta) e FFT, algoritmos sequenciais e paralelos
• Projeto Integrado:
  • iniciação ao ambiente de trabalho em cluster computacional e respectivas ferramentas de desenvolvimento de software e de apoio à execução
  • iniciação ao método científico em práticas laboratoriais experimentais e em trabalho de grupo
  • análise experimental de execução de código e consequente avaliação e optimização do desempenho da execução, em ambiente concorrente/paralelo/distribuído (por partilha de memória, por passagem de mensagens e híbrido), em plataformas homogéneas e heterogéneas (multicore CPU e GPU)
  • resolução de problemas computacionais de média complexidade, com requisitos de métodos numéricos.

Topo...

Bibliografia

Cada um dos módulos temáticos terá um conjunto de referências bibliográficas de base e complementares, baseadas em livros, e aqui referidos:

• Sistemas de Computação e Desempenho:

  Computer Organization and Design: The Hardware/Software Interface, David Patterson and John Hennessy,  5th Ed., Morgan Kaufmann, 2011

  Programming Massively Parallel Processors, A Hands-on Approach, David Kirk and Wen-mei Hwu, Morgan Kaufmann, 2010

• Planeamento e Administração de Clusters:

  Beowulf Cluster Computing with Linux, William Gropp, Ewing Lusk, Thomas Sterling, 2nd Ed., The MIT Press, 2003

  High Performance Linux Clusters with Oscar, Rocks, OpenMosix and MPI, Joseph Sloan, O'Reilly Media, Inc., 2004
   

• Paradigmas de Computação Paralela:

  Parallel Programming in C with MPI and OpenMP, Michael J. Quinn, McGraw-Hill Education, 2003

  Designing and Programming Parallel Programs: Concepts and Tools for Parallel Software Engineering, Ian Foster, Addison-Wesley, 1995
  (free online at http://www.mcs.anl.gov/~itf/dbpp/text/book.html, or here)
   

• Algoritmos e Métodos Numéricos:

  Parallel Programming in C with MPI and OpenMP, Michael J. Quinn, McGraw-Hill Education, 2003

  Matrix Computations, G. Golub, C. F. Van Loan, 3rd. Ed., John Wiley & Sons 1996

Adicionalmente cada um dos módulos temáticos indicará pontualmente fontes complementares de informação, sendo na maioria dos casos artigos de conferências e/ou revistas científicas, para além de sítios na Web com informação de produtos, utilitários ou projetos de I&D.
Esta informação complementar será incluída junto dos sumários de cada módulo temático.

Topo... 

Avaliação

Global

A UCE CPD com 30 ECTS está estruturada em 4 módulos temáticos com níveis de exigência semelhantes e num módulo laboratorial integrador (PI) que funcionará ao longo dos 2 semestres. O PI exige dos estudantes, em cada semestre, um nível de participação equivalente a cada módulo temático. Nestas circunstâncias a avaliação irá reflectir esta distribuição dos níveis de dedicação, na distribuição dos pesos de cada módulo: 5/30 para cada módulo temático, 10/30 para o PI.
O processo de avaliação é essencialmente constituído por componentes que têm como objetivo avaliar a capacidade de assimilação e aplicação dos conceitos adquiridos (as competências intelectuais), e ajuizar e quantificar as competências práticas e as genéricas resultantes da integração e aplicação laboratorial dos conhecimentos na resolução concreta de problemas.

Nota:
A avaliação da UCE é marcadamente realizada durante todo o período lectivo e contém vários elementos que requerem obrigatoriamente que sejam bem sucedidos para se obter aprovação à UCE. Haverá recurso apenas para as provas que forem realizadas de modo presencial e em papel (testes). Este "recurso" será realizado na época de exames e terá peso idêntico às suas provas equivalentes realizadas durante o semestre (assinaladas com * em baixo).

Por módulo (proposta provisória)

• Sistemas de Computação e Desempenho (1/6 de peso):
  • análise, preparação, apresentação e discussão coletiva de temas (máx. 3): 30% a 40%
  • resolução individual em papel de problemas concretos em 1 ou 2 datas a indicar e com limite de tempo (testes): 40% a 50% *
  • preparação e participação em sessões laboratoriais/experimentais e em Seminários Avançados com convidados externos: 20%
• Planeamento e Administração de Clusters (1/6 de peso):
  • trabalhos individuais/grupo, com elaboração de relatório, apresentação e defesa: 40% a 60%
  • uma prova escrita individual de avaliação de conhecimentos gerais: 40% a 60% *
• Paradigmas de Computação Paralela (1/6 de peso):
  • um trabalho laboratorial (versão paralela de um algoritmo usando um padrão de exploração de paralelismo): 70%
  • trabalhos sucintos de análise/síntese de artigos científicos (máx. 3): 30%
• Algoritmos e Métodos Numéricos (1/6 de peso):
  • trabalhos individuais, com elaboração de relatório, apresentação e defesa: 100%
• Projeto Integrado (1/3 de peso):
  • elaboração do(s) trabalho(s) indicado(s) e respetivo(s) relatório(s): 50% a 60%
  • apresentação e defesa individual do(s) trabalho(s): 20% a 30%
  • avaliação feita pela equipa que orientar o internship na Univ. Texas em Austin: 10% a 30%