MAC 5741 - Introdução a Algoritmos e Arquiteturas Paralelas - 1996 |
Semestre: 1.o semestre de 1996
Horário: 4.a feiras 8 - 10h, 6.a feiras 8 - 10h
Sala: 4.a feira sala 259 - 6.a feira sala 267
Data da primeira prova: 9 de outubro de 1996 (4.a feira) 8-10 h
Data da segunda prova: 22 de novembro de 1996 (6.a feira) 8-10 h
Requisitos:
Aula 1 (14/8/96): Descrição do curso; Complexidade de algoritmos.
Aula 2 (16/8/96): Motivação da computação paralela; algumas máquinas massivamente paralelas (MPP) existentes no mercado.
Aula 3 (21/8/96): Conceitos de speed-up, eficiência; modelo paralelo Grafo Orientado Acíclico, escalonamento do GOA; Exemplo 1.1 soma de n números no modelo GOA.
Aula 4 (23/8/96): Exemplo 1.3 multiplicação de matrizes no modelo GOA; modelo de memória compartilhada; Exemplo 1.4 multiplicação de matriz vetor; Algoritmo 1.1 multiplicação matrizes.
Aula 5 (28/8/96): Exemplo 1.5 Soma de n números no PRAM: duas soluções ( a do livro e a do Mauro di Giorgi); variações do PRAM quanto a acessos simultâneos: EREW, CREW, CRCW; notação simplificada (sem usar globalread e globalwrite).
Aula 6 (30/8/96): Exemplo 1.6 Multiplicação de matrizes no PRAM, algoritmo 1.3; modelo de memória distribuída (modelo de rede), array linear, anel; exemplo 1.7 multiplicação matriz vetor no anel e algoritmo 1.4.
Aula 7 (11/9/96): Hipercubo; exemplo 1.8 soma no hipercubo; exemplo 1.10 difusão (broadcast) no hipercubo.
Aula 8 (13/9/96): Exemplo 1.11 multiplicação de matrizes no hipercubo; Passar lista de exercício no. 2 (comentar imersão de grafos).
Aula 9 (18/9/96): Redes shuffle-exchange; Butterfly; cube connected cycles; relações entre as várias estruturas.
Aula 10 (20/9/96): Grafo de Bruijn; Modelo PRAM; desempenho de algoritmos paralelos; paradigma trabalho-tempo; comando pardo; exemplo 1.12 soma de n números no paradigma trabalho-tempo.
Aula 11 (25/9/96): Mágica baseada no Grafo de Bruijn; Princípio de escalonamento trabalho-tempo; conceito de optimalidade: algoritmos ótimos (no sentido fraco) e ótimos no sentido forte; técnicas básicas - árvore balanceada, algoritmo (alg. 2.1) para soma prefixa.
Aula 12 (27/9/96): Técnica de ``pointer jumping''; algoritmo (alg. 2.4) para determinação de raízes de árvores; algoritmo (alg. 2.5) para calcular soma prefixa em árvores.
Aula 13 (2/10/96): Técnica de divisão-e-conquista; algoritmo (alg. 2.6) para o problema de casco convexo.
Aula 14 (9/10/96): Primeira prova.
Aula 15 (11/10/96): Técnica de particionamento; um algoritmo ótimo de intercalação (alg. 2.7).
Aula 16 (16/10/96): Técnica de pipelining; exemplo árvore 2-3. Técnica de aceleração em cascata ("accelerated cascading"); exemplo de achar o máximo.
Aula 17 (18/10/96): Técnica de quebra de simetria; algoritmo para 3-coloração em tempo O(log* n).
Aula 18 (23/10/96): Problema de "list ranking" usando pointer jumping (alg. 3.1); contração de lista (alg. 3.2); um algoritmo ótimo para "list ranking" (alg. 3.3).
Aula não dada (25/10/96): a ser reposta na semana seguinte.
Aula 19 (30/10/96): Problemas em árvores usando circuito de Euler; atribuição de raiz e obtenção de pai de cada vértice; percurso em pós-ordem; determinação de núumero de descendentes; determinaçãoo do nível de cada vértice.
Aula 20 (1/11/96 - aula normal): Contração de árvore; avaliação de expressões aritméticas.
Aula 21 (1/11/96 - aula reposição):
Uso da máquina paralela Parsytec PowerXplorer: aula prática.
Exemplos de programas em Parix.
Transparências usadas num seminário sobre Parix dado por Gubi.
Aula 22 (6/11/96): Algoritmo paralelo de busca usando p processadores(alg. 4.1); intercalação (alg. 4.2).
Aula 23 (8/11/96): Rede de interconexão; algoritmo paralelo de ordenação bitônica.
Aula 24 (13/11/96): Modelo de granularidade grossa em computador paralelo de memória distribuída: exemplo: algoritmo paralelo para list ranking
Aula 25 (20/11/96): Algoritmos paralelos para list ranking de O(log p + log log n) e O(log* n log p) rodadas de comunicação. Ver artigo de Dehne e Song.
Aula 26 (22/11/96): Segunda prova (com consulta; matéria a partir da técnica de pointer jumping).