Computação Paralela Distribuída Mestrados em Informática e Eng.ª Informática 2010/2011 Docente responsável: A. Proença

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

(Ano anterior: 2009/2010)

Ultima Modificação: 12 Abr 2011
 

departamento de informática

Avisos:

1.  Guião com o Projecto Integrado: já se encontra disponível junto dos sumários de PI.  (12-Abr-11)
    

2. Estágios de investigação no Texas: à semelhança do sucedido em anos anteriores, os alunos desta UCE terão a oportunidade de realizar um estágio de 5 a 6 semanas na Univ. Texas em Austin, mais concretamente trabalhando integrado em equipas de investigação do ICES (Institut of Computational Engineering and Science) e com acesso a recursos únicos no mundo (abertos à comunidade científica) instalados no TACC (Texas Advanced Computing Center). Tal como anteriormente, a partida deverá ocorrer no 2º fim de semana de Julho e o regresso imediatamente a seguir a 15 de Agosto (os encargos com viagens e alojamento serão por conta da UM). Na imagem um relato da presença da equipa portuguesa em 2010 nestes internships em Austin, conforme apareceu na Newsletter do CoLab de Agosto 2010, enquanto aqui está idêntico relato referente ao ano anterior.  (12-Abr-11)

3. Workshop: GPU Programming for Scientific Applications: de 6 a 8 de Julho vai decorrer em Coimbra mais um evento internacional em Portugal ao abrigo do programa de colaboração entre Portugal e a Univ. Texas em Austin. Todos os alunos desta UCE deverão em princípio participar pelo menos num dia de sessões (as despesas serão por conta da UM). Informação em breve disponível no site oficial do evento.  (12-Abr-11)
    

4.   WACS: Winter Advanced Computing Seminars: de 10 a 12 de Janeiro decorreram as várias sessões com palestras de académicos convidados de 2 universidades do Texas, os Prof. Keshav Pingali, Prof. Calvin Lin e o Dr. Martin Burtscher, ao abrigo do programa de colaboração entre Portugal e a Univ. Texas em Austin. Todos os alunos desta UCE participaram neste evento. No website do evento estão os slides e as fotos mais relevantes.  (07-Fev-11)
    

5. Actividades complementares: para além das actividades divulgadas no início do ano neste website, estão ainda previstas outras actividades 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. (07-Fev-11)
    

6. Funcionamento desta UCE: esta UCE vai funcionar com 4 módulos temáticos, 2 por semestre, e por uma componente de projecto integrado, ao longo dos 2 semestres. Os módulos previstos para o 1º semestre de 2010/11 serão SCD (manhã) e PAC (tarde), embora alguns conteúdos dos outros módulos possam ser introduzidos quando necessário; no 2º semestre funcionarão 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 projectos. (01-Out-10)
    

7. 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 excepção deste bloco de avisos; a fim de garantir a leitura actualizada 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 actualizados, nomeadamente, no que diz respeito: aos sumários e notas complementares de estudo etc... (01-Out-10)

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 - substituindo os anteriores "supercomputadores" que foram, sucessivamente, computadores vectoriais e sistemas MPP - e em grelhas computacionais (Grid), 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 projectos; este é o principal objectivo do módulo de Projecto 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 activa 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 arquitectura 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 optimizar 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;
• projectar, desenvolver, implementar e optimizar 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, projectar, executar e divulgar os resultados de trabalhos em Engenharia da Computação.

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 arquitectura interna dos processadores e no seu acesso à memória, com destaque para os processadores multi-core e many-core
  • seleccionar as métricas, métodos e técnicas de avaliação de desempenho de programas em execução, para configurações da arquitectura 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 arquitectura 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 arquitecturas
  • implementar aplicações utilizando os tipos mais comuns de algoritmos paralelos
  • medir e optimizar 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 Projecto Integrado:
  • planear, executar e divulgar os resultados de projectos de avaliação e optimização de desempenho de sistemas de computação na execução de tarefas
  • desenvolver de forma integrada e em equipa, a função de concepção e projecto 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 arquitectura 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 arquitecturas: arquitecturas vectoriais, arquitecturas paralelas com memória partilhada e memória distribuída, arquitecturas distribuídas em rede; análise de desempenho em arquitecturas 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, arquitectura, 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: arquitectura, 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, objectos 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 optimizaçã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
• Projecto 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,  4th Ed., Morgan Kaufmann, 2009

  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
   

• 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 projectos 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 objectivo 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

• Sistemas de Computação e Desempenho (1/6 de peso):
  • análise, preparação, apresentação e discussão colectiva de temas (máx. 6): 40% a 50%
  • resolução individual em papel de problemas concretos em 1 ou 2 datas a indicar e com limite de tempo (testes): 30% a 40% *
  • 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%
• Projecto Integrado (1/3 de peso):
  • elaboração do(s) trabalho(s) indicado(s) e respectivo(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%