"Office-hours"

Semestre: 1.o semestre de 2003

Horário:

3.a feiras: 10 - 12 h

5.a feiras: 8 - 10 h

Sala: 268 Bloco A - 2.o andar

Data da primeira prova:
8 de maio de 2003. Prova sem consulta com duração exata de duas horas. Favor comparecer pontualmente às 8h.

Data da segunda prova:
17 de junho de 2003
Prova sem consulta com duração exata de duas horas. Matéria da prova: da aula 17 até a aula 25.

Data da terceira prova (opcional): 8 de julho de 2003 (3.a feira) às 10h. Matéria da prova: toda.

Requisitos:

Boa experiência em programação, em Pascal ou C.

Outros avisos:

Para informações sobre prazos de matrículas, trancamento, dias sem aula, etc. veja o

Calendário da Pós-Graduação para 2003.

Conteúdo da disciplina:

• Introdução a computação paralela.
• Paradigma de troca de mensagens.
• Introdução a MPI e exemplos.
• Operações básicas como soma e soma de prefixos, etc.
• Ordenação.
• Algoritmos para problemas em grafos.
• Multiplicação de matrizes.
• Programação dinâmica.
• Problemas de busca.

Referências bibliográficas:

• E. N. Cáceres, H. Mongelli e S. W. Song. Algoritmos Paralelos usando CGM/PVM: Uma introdução (.pdf 985K). XXI Congresso da Sociedade Brasileira da Computação, Jornada de Atualização em Informática, 2001, pp. 219-278.
• F. Dehne (Editor) Coarse Grained Parallel Algorithms. Algorithmica, Vol. 24, No. 3/4, 1999, pp. 173-176
• Peter Pacheco. A User's Guide to MPI (.ps 152K). 1998.
• P. S. Pacheco. Parallel Programming with MPI. Morgan Kaufmann Publishers, 1997
• Marc Snir, Steve Otto, Steven Huss-Lederman, David Walker, and Jack Dongarra. MPI: the Complete Reference (html).
• Barry Wilkinson and Michael Allen. Parallel Programming - Techniques and Applications Using Networked Workstations and Parallel Computers. 1st Ed. Prentice Hall, 1999.
  ( As transparências de 11 capítulos deste livro estão disponíveis. )
• Artigos diversos.

Avaliação:

Dois programas: média aritmética Pg

Nota de aproveitamento final A = (Pg + 2 P) / 3.

Programas:

• Programa 1:
  Implementar o algoritmo de ordenação de inteiros (algoritmo 1 ou algoritmo 2 do artigo) de Chan and Dehne.
  É necessário também entregar um relatório descrevendo a implementação e os resultados, inclusive em gráficos.
• Programa 2:
  Implementar o algoritmo de list ranking (.pdf) de Dehne et al.
  É necessário também entregar um relatório descrevendo a implementação e os resultados, inclusive em gráficos.
• Dicas:
  Compilando e executando MPI (incluindo dois exemplos simples).
  

Exercícios:

• Exercício 1 (.pdf 84K)
• Exercício 2 (.pdf 111K)
• Exercício 3 (.pdf 45K)

Assuntos tratados em aulas:

Aula 2 (27/2/2003): Modelos de computação paralela: PRAM, rede (anel, grade, hipercubo), BSP, CGM. Exemplos de algoritmos (soma) nestes modelos. Os slides usados nesta aula (.pdf 544K).

Aula 3 (06/03/2003): Paradigma de troca de mensagens: comunicação síncrona, assíncrona, operação bloqueante ou não-bloquante, operações de comunicação coletiva. Introdução a MPI. As transparências usadas nesta aula: slides 41 a 58, slides 70 a 95, slides 98 a 102. (.pdf 123K).

Aula 4 (11/03/2003): Computações trivialmente paralelizáveis: operações básicas de processamentos de imagens (como deslocamento, escala), fractais Mandelbrot, cálculos Monte Carlo. As transparências usadas nesta aula: slides 103 a 124. Para pensar em casa: Dados n pontos no plano (pelas suas coordenadas x e y), desenvolva um algoritmo paralelo CGM de p processadores para determinar se todos os pontos são colineares ou estão situados numa circunferência.

Aula 5 (18/03/2003): Técnicas básicas usando paradigmas de particionamento de dados ou divisão e conquista: soma de n números (algoritmo PRAM e algoritmo CGM em MPI), cálculo da integral definida (usando o método dos trapézios, apenas a idéia), soma de prefixos de n números (algoritmo PRAM). Os slides usados nesta aula (.pdf 117K).

Aula 6 (20/03/2003): Continuação soma de prefixos de n números (algoritmo CGM usando MPI). Ordenação por inserção: idéia do algoritmo, considerando um número entrando por vez. Algoritmo de ordenação por inserção CGM: ao invés de considerar um número, consideramos um bloco de n/p números cada vez. Complexidade em número de comunicação é O(p) e computação local em cada rodada O(n log n/p). Os slides usados sobre ordenação nesta e proximas aulas - este arquivo ainda está sendo completado - por enquanto tem 35 páginas das quais algumas iniciais estão em branco (.pdf 360K).

Aula 7 (25/03/2003): Ordenação por bucket. Sequência bitônica e propriedade do split bitônico. Os slides usados estão no mesmo arquivo da aula passada (.pdf 360K).

Aula 8 (27/03/2003): Ordenação bitônica e Split Sort. Capa da CACM mostrando uma ilustração da ordenação bitônica.

Aula 9 (01/04/2003): Algoritmo CGM Split Sort usando MPI. Algoritmo de Chan e Dehne. Os slides ref. algoritmo CGM SplitSort em MPI (.pdf 86K).

Aula 10 (03/04/2003): Algoritmo CGM para o problema de edição de cadeias (string editing) de O(p) rodadas de comunicação e computação local O(m n / p), para duas cadeias de comprimentos m e n. Os detalhes estão no artigo WOB 2002 (.ps 180K).

Aula 11 (10/04/2003): Algoritmo CGM para o problema de seleção: dados n números e um inteiro k entre 1 a n, achar o k-ésimo menor número. Técnica de reduzir a entrada de tamanho n para n/p para depois resolver o problema sequencialmente num processador. Os slides usados nesta aula (.pdf 108K). Mais detalhes no artigo Saukas e Song 1998 (html).

Aula 12 (22/04/2003): Algoritmo CGM para o problema de seleção simultânea de até p números. Algoritmo de ordenação baseado na seleção simultânea. Dados experimentais. Seleção simultânea e Ordenação no artigo Saukas e Song 1998 (html). Algoritmo CGM para solução de sistemas tridiagonais (Einar Saukas): algoritmo e dados experimentais. Os slides usados nesta aula sobre sistemas tridiagonais (.pdf 111K). Mais detalhes no artigo Saukas e Song 1997 (.pdf 193K).

Aula 13 (24/04/2003): Algoritmo CGM, com número constante de rodadas de comunicação, ara o problema de mínimo intervalar (range minima). O assunto está detalhado no artigo de Mongelli e Song 1999 (.ps 276K).

Aula 14 (29/04/2003): Busca de padrão de uma e duas dimensões, sem e com escala. Um algoritmo CGM com número constante de rodadas de comunicação, baseado nos conceitos de range minima, LCA, árvore de sufixos, algoritmo de KMP e algortimo de Amir, Landau e Vishkin 1992. Os slides usados estão em Os slides usados nesta aula (.pdf 402K).

Aula 15 (06/05/2003): Tirar dúvidas e discussão das listas de exercícios.

Aula 16 (08/05/2003): Primeira prova. Prova sem consulta com duração exata de duas horas. Favor comparecer pontualmente às 8h.

Aula 17 (13/05/2003): Busca Padrão 2-D sem escala e com escala: apenas algumas idéias. Importância do problema de list ranking que aparece como subproblemas em vários outros problemas de grafos.

Aula 18 (20/05/2003): Algoritmo probabilístico para o problema de list ranking: Algoritmo 1 requer O(log p + log log n) rodadas de comunicação com alta probabilidade; Algoritmo 2 requer O((log* n)(log p)) rodadas de comunicação com alta probabilidade. Técnica do uso de uma amostra que é armazenada em todos os processadores. Os detalhes dos 2 algoritmos probabísticos para list ranking estão no artigo IJPP 1997 (.ps 254K).

Aula 19 (22/05/2003): Algoritmo determinístico para o problema de list ranking: requer O(log p) rodadas de comunicação. Os detalhes do algoritmo para list ranking estão no artigo de Dehne et al. 2002 .

Aula 20 (27/05/2003): Discussão geral sobre algoritmos PRAM e BSP/CGM. Muitos algoritmos BSP/CGM (soma, soma de prefixos, ordenação) podem ser resolvidos com um número constante de rodadas de comunicação. Em problemas de grafos, muitos algoritmos PRAM se baseiam no subproblema list ranking, que pode ser resolvido no BSP/CGM com O(log p) rodadas de comunicação. Introduzir o algoritmo PRAM para determinação de componentes conexos.

Aula 21 (29/05/2003): Apresentar o algoritmo BSP/CGM para determinação de componentes conexos. Sobre esse algoritmo, ver o trabalho de Dehne et al. 2002. Apresentar as idéias da obtenção do Euler tour de um digrafo Euleriano: algoritmo sequencial e paralelo.

Aula 22 (03/06/2003): Algoritmo BSP/CGM para o problema do fecho transitivo de um digrafo acíclico (ver o trabalho de Cáceres et al.) e as aplicações deste algoritmo para vários outros problemas como todos os caminhos mais curtos, componentes conexos, árvore geradora mínima, etc.

Aula 23 (05/06/2003): Algoritmos BSP/CGM para multiplicação de matrizes A (n x m) por B (m x s) - dois algoritmos triviais: um algoritmo BSP (sem limitação de memória, guardando toda a matriz B em todos os processadores) que usa número constante de rodadas de comunicação; um algoritmo CGM (guardando faixas de A e B e mudando as faixas em cada rodada) que usa $O(p)$ rodadas de comunicação. Apresentar vários outros algoritmos que usam estratégias mistas, entre os dois extremos acima.

Aula 24 (10/06/2003): Processamento paralelo de imagens. As transparências usadas nesta aula são slides números 517 a 561 (.pdf 268K).

Aula 25 (12/06/2003): Uma solução aproximada paralela para resolver o problema do hitting set. Ver o artigo A Parallel Approximation Hitting Set Algorithm for Gene Expression Analysis. (.ps 137K.)

Aula 26 (17/06/2003): Segunda prova.