MAC 5705 - Tópicos de Algoritmos Paralelos usando MPI e BSP/CGM - 2005 |
Semestre: 1.o semestre de 2005
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 12 de maio de 2005 (quinta feira).
(Prova com consulta. Matéria até a aula 10 inclusive.)
Data da segunda prova:
Dia 23 de junho de 2005 (quinta feira).
(Prova com consulta. Matéria da aula 11 até a aula 22 inclusive.)
Data da terceira prova (opcional):
Dia 30 de junho de 2005 (quinta feira).
(Prova com consulta. Matéria: toda a matéria desde a aula 1 até a aula 22 inclusive.)
Requisitos:
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 2005.
Referências bibliográficas:
Dois programas: média aritmética Pg
Nota de aproveitamento final A = (Pg + 2 P) / 3.
Aula 1 (15/03/2005): Descrição do curso. Conteúdo e bibliografia. Introdução à computação paralela: slides usados (slide 1 a slide 40) (.pdf 86K).
Aula 2 (17/03/2005): Modelos de computação paralela: PRAM, rede com conexões fixas (como anel, grade, hipercubo). Exemplos de algoritmos (soma) nestes modelos. Os slides usados nesta aula (.pdf 544K).
Aula 3 (29/03/2005): Continuação da aula 2 usando o restante dos slides da aula passada: modelos BSP e CGM, exemplo da soma no modelo CGM. Passar como lição de casa a leitura do Peter Pacheco - A User's Guide to MPI (.ps 727K). ou em pdf (.pdf 362K).
Aula 4 (31/03/2005): 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 5 (7/4/2005): Continuação da aula passada sobre paradigma de troca de mensagens. Instruções para testar programas em MPI (.html). 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). Os slides usados nesta aula e nas seguintes (.pdf 117K).
Aula 6 (12/4/2005): Continuação da aula passada sobre paradigma de troca de mensagens. Soma de prefixos de n números (algoritmo PRAM e algoritmo CGM usando MPI). 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 (14/04/2005): 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. Capa da CACM mostrando uma ilustração da ordenação bitônica.
Aula 8 (19/04/2005): 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. 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. Passar o Programa 1 (ver acima).
Aula 9 (26/04/2005):
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 foi proposto em 1998,
e necessita de O(log p) rodadas de comunicação.
Hoje nós já aprendemos várias outras técnicas, entre elas,
o uso de separadores no chamado split sort. Projete um
algoritmo de seleção que usa apenas O(1) rodadas de comunicação.
Aula 10 (28/04/2005): 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 11 (03/05/2005): Resolver dúvidas e discutir exercícios de listas de exercícios.
Aula 12 (05/05/2005): Aula prática sobre o uso da máquina Beowulf (conhecida no IME como Biowulf) do grupo de Bioinformática do IME (tiramisu).
Aula 13 (10/05/2005): Resolver dúvidas e discutir exercícios de listas de exercícios.
Aula 14 (12/05/2005): Primeira Prova.
Aula 15 (17/05/2005): 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. 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. Explicar a importância da distância máxima que separa dois elementos consecutivos (na lista) da amostra. Os slides ref. apresentação dissertação Guilherme (.ppt 875K). Outros slides: Ver também (.pdf 1.29 Mbytes).
Aula 16 (19/05/2005): Analisar essa distância máxima. Apresenta o Algoritmo 1 que requer O(log p + log log n) rodadas de comunicação com alta probabilidade; List ranking probabilístico: Passar o Programa 2 (ver acima).
Aula 17 (31/05/2005): 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). Iniciar a apresentação de um algoritmo determinístico que usa O(log p) rodadas de comunicação.
Aula 18 (02/06/2005): 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 19 (07/06/2005): 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). e o slide mostrando um grafo orientado em forma de grade (Grid DAG) [.jpg 102K] para o problema de alinhamento de duas cadeias (exemplo visto em classe).
Aula 20 (09/06/2005): Continuação da aula anterior. Para os detalhes, veja o artigo Alves et al. 2003 apresentado no evento ICCSA 2003 (.pdf 227K). 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 21 (14/06/05): Uma solução aproximada paralela para resolver o problema do hitting set, no contexto de expressão gênica. Os slides usados.
Aula 22 (16/06/05): 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. Um algoritmo CGM para achar o fecho transitivo de um grafo orientado. Os slides usados (.pdf 238K).
Aula 23 (21/06/05): Aula para tirar dúvidas.
Aula 24 (23/06/05): Segunda Prova.
Aula 25 (30/06/05): Terceira Prova (opcional).