Provas (de 1996):

• Primeira prova.

(Ver as aulas da mesma disciplina dada em 1996 em http://www.ime.usp.br/~song/mac741-96.html )

Aula 1 (13/março/00): Descrição do curso. Bibliografia. Computação paralela e disponibilidade de hardware (computadores paralelos no mercado hoje). Comentar sobre a lista TOP 500 - os 500 computadores mais potentes do mundo.

Aula 2 (15/março/00): Comentar sobre importância da Complexidade de Algoritmos. Passar para casa o Exercício 1.

Aula 3 (20/março/00): Motivação para o uso de computadores paralelos. Aplicações típicas que usam processamento paralelo. Conceitos de ganho ou aceleração (speedup) e eficiência.

Aula 4 (22/março/00): Modelo de grafo orientado acíclico: nós entrada, operação, saída. Exemplo 1.1 - calcular a soma de n números. Escalonamento: associação a cada nó i do grafo um processador e instante de execução. Modelo de memória compartilhada: PRAM (Parallel Random Access Machine). Exemplo 1.4 - multiplicação matriz vetor. Iniciar a discussão.

Aula 5 (27/março/00): Exemplo 1.4 - multiplicação matriz vetor - algoritmo para o processador i. Características do algoritmo: pode ser assíncrono, leitura concorrent, escrita não concorrente, todos os processadores executam o mesmo programa (SIMD). Exemplo 1.5 Somas de n números.

Aula 6 (29/março/00): Exemplo 1.5 Somas de n números. Passar para casa para pensar: ver Pensar 1, sobre uma forma alternativa de somar n numeros. Variações do modelo PRAM: PRAM EREW, CREW e CRCW. Este último tem três modalidades: CRCW comum, CRCW arbitrário, CRCW prioritário. Para casa: Pensar 2. Notação simplificada: não explitar os acessos à memória global compartilhada (omitindo globalread e globalwrite). Para casa: Pensar 3. Exemplo 1.6: Multiplicação de duas matrizes nxn - calcular C=AB.

Aula 7 (03/04/00): Exemplo 1.6: Multiplicação de duas matrizes nxn - calcular C=AB. Discutir necessidade de leitura concorrente mas não escrita concorrente (portanto PRAM CREW). Modelo de rede ou de memória distribuída ou de troca de mensagens: conceitos, grafo de nós (processadores) e arestas (canais de comunicação), diâmetro, grau, roteamento, comandos send e receive. Exemplo 1.7: multiplicação matriz (n x n) e vetor numa rede tipo anel de p processadores. Supor r = n/p inteiro. Algoritmo 1.4.

Aula 8 (05/04/00): Passar para casa o Exercício 2. Hipercubo: definição, propriedades. Exemplo de soma de n numeros num hipercubo de n processadores. Exemplo de broadcast de um dado localizado no processador P0 e difundir para todos os outros processadores. Introduzir o grafo de Bruijn.

Aula 9 (10/04/00): Definir o grafo de Bruijn. Comentar algumas propriedades (grau constante e diâmetro log n). Conceito de custo de um algoritmo. Paradigma trabalho-tempo para descrever algoritmos. Retomar o exemplo da soma de n numeros no PRAM e escrever o algoritmo na apresentacao trabalho-tempo (usando pardo). Noções de algoritmos paralelos ótimos: dois conceitos - ótimo (no sentido fraco) e ótimo no sentido forte (trabalho-tempo ótimo).

Aula 10 (12/04/00): Técnicas básicas ou paradigmas para projetar algoritmos paralelos. Árvore binária balanceada: exemplo de soma de n números. Outro exemplo é a soma prefixa. Algoritmo paralelo (Alg. 2.1) recursivo para soma prefixa. Algoritmo paralelo (Alg. 2.2) não recursivo para soma prefixa.

Aula 11 (24/04/00): Técnica de "pointer jumping". Árvore orientada com raiz. Problema de achar as raízes dos vértices de uma floresta. Algoritmo 2.4 determinar as raízes dos vértices de uma floresta, pelo método de pointer jumping. Problema da soma prefixa em paralelo. Algoritmo 2.5 soma prefixa por pointer jumping.

Aula 12 (26/04/00): Técnica da divisão e conquista. Problema da determinação do fecho convexo de n pontos no plano. Algoritmo 2.6 determinar o fecho superior de um conjunto de n pontos.

Aula 13 (03/05/00): Técnica do particionamento. Diferença com divisão-e-conquista é que na divisão-e-conquista o maior trabalho está na junção das soluções, no particionamento o maior trabalho é o particionamento. Problema de intercalação (merge) de duas sequências de números ordenados.

Aula 14 (08/05/00): Técnica do particionamento. Algoritmo de particionamento para o problema de merge. Técnica de pipelining. Idéias gerais e o exemplo de inserções de uma sequência de elementos em uma árvore 2-3.

Aula 15 (10/05/00): Primeira Prova.

Aula 16 (15/05/00): Algoritmo para inserir k elementos novos numa árvore 2-3, usando a técnica de pipelining. Técnica de "accelerated cascading". Exemplo: problema da determinação do máximo de n elementos.

Aula 17 (17/05/00): Exemplo: problema da determinação do máximo de n elementos. Dados um algoritmo otimo de tempo O(log n) e trabalho O(n) e outro algoritmo de tempo O(log log n) e trabalho O(n log log n). Usando a técnica de "accelerated cascading" obtido um novo algoritmo otimo de tempo O(log log n) e trabalho O(n).

Aula 18 (22/05/00): Técnica de quebra de simetria. Exemplo: 3-coloração num anel. Coloração inicial com n cores. Algoritmo básico para reduzir de n para O(log n) cores. Um algoritmo paralelo de tempo O(log* n) e trabalho O(n log* n).

Aula 19 (24/05/00): Não houve.

Aula 20 (29/05/00): Modelo de computação CGM (coarse grained multicomputer). Introdução. Exemplos de problemas que foram resolvidos com esse modelo considerado mais realístico.

Aula 21 (31/05/00): O problema de list ranking e um algoritmo CGM probabilistico, de O(log p + log log n) rodadas de comunicação. Ver vários detalhes desse algoritmo em Parallel Graph Algorithms (Postscript 419K). Passar o trabalho para casa.

Aula 22 (05/06/00): Problema de list ranking: Um algoritmo paralelo probabilístico que requer O( (log*n) (log p) ) rodadas de comunicação. Para o mesmo problema: Idéia de um algoritmo paralelo CGM determinístico que requer O(log p) rodadas de comunicação.

Aula 23 (07/06/00): Problema de seleção. Um algoritmo paralelo CGM (de Einar Saukas) que requer O(log p) rodadas de comunicação.