Computação Paralela Distribuída Mestrado em Informática 2007/2008 Docente responsável: A.J.Proença

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

Ultima Modificação: 21 Nov 2007
 

departamento de informática

Avisos:

1. Página quase completa finalmente! Os sumários de SCD estão actualizados, bem como o material de estudo; em breve ficarão os de PAC e PI. (31-Out-07)

2. Funcionamento das sessões em SCD: em princípio, cada sessão começa com um debate/diálogo entre todos os presentes sobre um tema que foi proposto na sessão anterior, seguindo-se uma intervenção do docente (com uma síntese do assunto e/ou apresentação de um novo tema) e terminando com uma análise/resolução de problemas concretos. O tema proposto para a 2ª sessão foi a revisão dos conceitos de paralelismo de instruções e hierarquia de memória, com destaque para os processadores x86, e o proposto para a 3ª sessão foi uma pesquisa dos utilitários existentes para avaliação do impacto dos modelos de organização de um CPU e respectiva hierarquia de memória, na execução de programas. Para as sessões seguintes esta indicação ficará incluída nos sumários. (22-Out-07)

3. 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 2007/08 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. (09-Out-07)

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 excepção deste bloco de avisos; a fim de garantir a leitura actualizada deste bloco, sugere-se que se faça o "refresh" da página sempre que a ela aceder. A informação que irá sendo actualizada ao longo do semestre, com periodicidade semanal, será a referente aos sumários e respectiva divulgação de notas complementares de estudo (junto com os sumários) (09-Out-07)

Topo...

Equipa docente

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

Módulo de Sistemas de Computação e Desempenho (SCD)
Alberto José Proença
email: aproenca@di.uminho.pt

Módulo de Planeamento e Administração de Clusters (PAC)
António Manuel Pina
email: pina@di.uminho.pt

Módulo de Paradigmas de Computação Paralela (PCP)
João Luís Sobral
email: jls@di.uminho.pt

Módulo de Algoritmos e Métodos Numéricos (AMN)
Rui Ralha
email: r_ralha@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).

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
  • 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 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
  • 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 (proposto no início do semestre)

Proposta de 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; 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), 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 paralelas
• 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 e suporte lógico; 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
  • 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 paralelo (multi-threading, por passagem de mensagens e híbrido)
  • 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 Systems: A Programmer's Perspective (CS:APP), Randal Bryant and David O'Hallaron,  Prentice Hall, 2002

  Measuring Computer Performance: A Practitioner's Guide, David J. Lilja, Cambridge University Press, 2000
   

• 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
   

• Algoritmos e Métodos Numéricos:

  **** a completar em breve *******

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

Objectivos

O processo de avaliação é essencialmente constituído por 2 componentes: uma que tem como objectivo avaliar a capacidade de assimilação e compreensão dos conceitos adquiridos (as competências intelectuais), e outro para ajuizar e quantificar as competências práticas resultantes da integração e aplicação
laboratorial dos conhecimentos na resolução concreta de problemas.
A primeira componente é avaliada em 2 testes sumativos, enquanto a segunda é avaliada por apresentação escrita e consequente defesa oral dos resultados dos trabalhos realizados.

Método