"Office-hours"

Semestre: 1.o semestre de 2004

Horário da disciplina:

3.a feiras: 8 - 10 h

5.a feiras: 10 - 12 h

Sala: 259 Bloco A - 2.o andar

Data da primeira prova:
Dia 13 de maio de 2004 (quinta feira).

Matéria da primeira prova: até a aula 16 inclusive.

A prova será sem consulta, com duração de 2 horas.

Data da segunda prova:
Dia 24 de junho de 2004 (quinta feira).

Matéria da primeira prova: da aula 17 até a aula 25 inclusive.

A prova será sem consulta, com duração de 2 horas.

Data da terceira prova (opcional):
Dia 8 de julho de 2004 (quinta feira).

Matéria da primeira prova: toda a matéria.

A prova será sem consulta, com duração de 2 horas.

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 2004.

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 (.pdf 692K).
  É necessário também entregar um relatório descrevendo a implementação e os resultados, inclusive em gráficos.
• Programa 2:
  Implementar um dos algoritmos de list ranking probabilístico (.pdf) de Dehne e Song.
  É 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 A
• Exercício B
• Exercício C (.pdf 16K)
• Exercício 1 (.pdf 84K)
• Exercício 2 (.pdf 111K)
• Exercício 3 (.pdf 45K)
• Exercício 4 (.html)
• Exercício 5 (.html)
• Exercício 6 (.html)

Assuntos tratados em aulas:

Aula 1 (09/03/2004): Descrição do curso. Conteúdo e bibliografia. Introdução à computação paralela: slides usados (slide 1 a slide 40) (.pdf 86K).

Aula 2 (11/03/2004): 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 (16/03/2004): Continuação da aula 2 usando o restante dos slides da aula passada. Passar como lição de casa a leitura do Peter Pacheco - A User's Guide to MPI (.ps 152K).

Aula 4 (18/03/2004): 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). Ver também Instruções para testar programas em MPI (.html).

Aula 5 (23/03/2004): 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 e algoritmo CGM usando MPI). Os slides usados nesta aula (.pdf 117K).

Aula 6 (25/03/2004): Computações trivialmente paralelizáveis: operações básicas de processamentos de imagens (como deslocamento, escala), fractais Mandelbrot, cálculo de Pi pelo método de Monte Carlo. As transparências usadas nesta aula: slides 103 a 124. 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 para esta e as próximas aulas (.pdf 508K).

Aula 7 (30/03/2004): Ordenação por bucket, supondo distribuição uniforme da entrada num intervalo [0, a-1]. Sequência bitônica e propriedade do split bitônico. Como ordenar uma sequência bitônica; como tornar uma sequência qualquer (pode ser não bitônica) em bitônica.

Aula 8 (01/04/2004): Capa da CACM mostrando uma ilustração da ordenação bitônica. Split sort usando um conjunto de p-separadores (ou p-quartis ou p-splitters). Algoritmo Split Sort. Ideias do Algoritmo de Chan e Dehne unindo split sort com radix sort.

Aula 9 (13/04/2004): Implementação do Split Sort Paralelo em MPI. Os slides usados (.pdf 86K). Prova-se que o tamanho de cada bucket final é limitado por 2 n/p (conforme o artigo de Helman, JaJa and Bader, A New Deterministic Parallel Sorting Algorithm with an Experimental Evaluation. ACM Journal of Experimental Algorithmics, December 1998.

Aula 10 (15/04/2004): Algoritmo CGM/BSP para o problema de Máxima Subsequência: dada uma sequência de números reais, achar a subsequência (contígua) cuja soma é máxima. O artigo que descreve este algoritmo.

Aula 11 (20/04/2004): 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). Obs: esse algoritmo necessita de O(log p) rodadas de comunicação. Usando o que voce já conhece no estudo do split sort, projete um algoritmo de seleção que usa apenas O(1) rodadas de comunicação.

Aula 12 (22/04/2004): 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 158K). (Veremos apenas o caso uni-dimensional.)

Aula 13 (27/04/2004): Continuação: busca de padrão unidimensional com escala.

Aula 14 (29/04/2004): O problema de list ranking e a sua importância pois aparece como subproblemas em vários outros problemas em árvores e grafos. Algoritmos CGB triviais pode levar O(n) rodadas de comunicação, ou O(log n) rodadas de comunicação com pointer jumping.

Aula 15 (04/05/2004): Discussão sobre listas de exercícios, dúvidas, etc. Propor o exercício da Lista C (.pdf 16K).

Aula 16 (06/05/2004): Resolver o exercício da Lista C (.pdf 16K). Discussão sobre listas de exercícios, dúvidas, etc.

Aula 17 (11/05/2004): Algoritmo probabilístico para o problema de list ranking. Idéia de usar uma amostra de O(n/p) que é armazenada em todos os processadores. Cada processador armazena portanto a sua parte de n/p dados de entrada mais a amostra. A amostra é a mesma em todos os processadores. Algoritmo 1 requer O(log p + log log n) rodadas de comunicação com alta probabilidade; Os slides usados (.pdf 1.29 Mbytes).

Aula 18 (13/05/2004): Primeira Prova.

Aula 19 (18/05/2004): List ranking probabilístico: Algoritmo 2 requer O((log* n)(log p)) rodadas de comunicação com alta probabilidade. Os detalhes dos 2 algoritmos probabísticos para list ranking estão no artigo IJPP 1997 (.ps 254K). 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 (20/05/2004): 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 slides usados (.pdf 103K). Grafo orientado em forma de grade (Grid DAG) [.jpg 102K] para o problema de alinhamento de duas cadeias (exemplo visto em classe). Para os detalhes, veja o artigo Alves et al. 2003 (.pdf 227K).

Aula 21 (25/05/2004): Comparação de genomas (Xanthomonas axonopodis pv. citri e Xanthomonas campestris pv. campestris) usando computação paralela. Os slides usados (.pdf 192K). Para os detalhes, veja o artigo Almeida et al. 2003 (.pdf 109K). Os slides sobre conceitos de DNA, gene, etc. podem ser obtidos no site http://www.genome.gov/glossary.cfm, procure pelos termos do glossário: chromosome, spectral karyotype, DNA, gene, gene expression, amino acid.

Aula 22 (27/05/2004): Um algoritmo CGM para o problema de alinhamento de duas cadeias usando O(log p) rodadas de comunicação. Os slides usados (apenas daremos uma idéia do algoritmo) (.pdf 103K). Esse é o principalmente resultado da tese de Carlos Eduardo Rodrigues Alves (.ps.gz 376K). Para um resumo, veja artigo CTD 2002 (.pdf 100K). Uma solução aproximada paralela para resolver o problema do hitting set, no contexto de expressão gênica. Os slides usados (.pdf 96K).

Aula 23 (01/06/2004): Uma solução aproximada paralela para resolver o problema do hitting set, no contexto de expressão gênica: continuação.

Aula 24 (03/06/2004): Um algoritmo CGM para achar o fecho transitivo de um grafo orientado. Os slides usados (.pdf 238K).

Aula 25 (17/06/2004): Um algoritmo CGM para o problema de k-cobertura mínima de um grafo, pelo método de FPT (Fixed Parameter Tractability). Os slides usados (.pdf 395K). O algoritmo ilustrado através de um exemplo. Gerando a árvore de busca ternária: Caso 1. (.pdf 18K). Gerando a árvore de busca ternária: Caso 2. (.pdf 10K). Gerando a árvore de busca ternária: Caso 3. (.pdf 8K). Gerando a árvore de busca ternária: Caso 4. (.pdf 6K). Gerando a árvore de busca ternária do exemplo. O slide ilustrando essa árvore. (.pdf 30K).

Aula 26 (22/06/2004): Discussão sobre exercícios.

Aula 27 (24/06/2004): Segunda Prova.

Aula 28 (8/7/2004): Terceira Prova.