Referêencias bibliográficas:

• JáJá, Joseph. An Introduction to Parallel Algorithms. Addison-Wesley Publishing Company. 1992.
• Leighton, F. Thompson. Introduction to Parallel Algorithms and Architectures: arrays, trees, hypercubes. Morgan Kaufmann Publishers. 1992.
• Dehne, F., Fabri, A. and Rau-Chaplin, A. ``Scalable parallel computational geometry for coarse grained multicomputers''. Proc. ACM Symposium on Computational Geometry, 1993, pp. 298-307.
• Song, S. W. Parallel Graph Algorithms. (Postscript 419K) CIMPA International School of Parallel Computing. Natal, Brazil, 1999, 25 p.
• Artigos diversos.

Tipo de aulas: Aulas teóricas e práticas

Critérios de avaliação: Provas, exercícios, seminários.

Regime de oferecimento: esporádico

Duração: do início de março ao início de julho

Carga horária semanal: 4 horas

Data da primeira prova: Dia 7 de maio de 2001 (segunda feira). A prova será com consulta. Matéria: até a aula 11 inclusive.

Data da segunda prova: Dia 20 de junho de 2001 (quarta feira). A prova será com consulta. Matéria: desde a aula 12. (Obs: não entra a parte sobre CGM.)

Data da terceira prova (opcional): Dia de 2001 (quarta feira). A prova será com consulta. Matéria: toda matéria.

Avisos:

Exercícios:

• Exercício 1 (Não precisa entregar.)
• Exercício 2 (Entregar até 04/04/2001)
• Exercício 3 (Entregar até 04/04/2001)
• Exercício 4 (Entregar até 04/04/2001)
• Exercício 5 (Entregar até 02/05/2001.)

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

Aula 1 (12/março/01): 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. Comentar sobre importância da Complexidade de Algoritmos. Passar para casa o Exercício 1. (Não precisa entregar.)

Aula 2 (14/março/01): 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 3 (19/março/01): 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. Enunciar o problema que será resolvido na próxima aula.

Aula 4 (21/março/01): 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. Passar para casa o Exercício 2. (Ver prazo de entrega no item Exercícios acima.)

Aula 5 (26/março/01): 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: Exercício 3. Notação simplificada: não explitar os acessos à memória global compartilhada (omitindo globalread e globalwrite). Para casa: Exercício 4. Exemplo 1.6: Multiplicação de duas matrizes nxn - calcular C=AB.

Aula 6 (28/março/01): Continuação do 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 7 (4/abril/01): 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.

Aula 8 (16/abril/01): Passar para casa o Exercício 5. Definir o grafo de Bruijn. Comentar algumas propriedades (grau constante e diâmetro log n). Apresentar uma mágica baseada no grafo de Bruijn (ver http://www.ime.usp.br/~song/mac741/magica.html. 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).

Aula 9 (18/abril/01): Noções de algoritmos paralelos ótimos: dois conceitos - ótimo (no sentido fraco) e ótimo no sentido forte (trabalho-tempo ótimo). 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.

Aula 10 (23/abril/01): Algoritmo paralelo (Alg. 2.2) não recursivo para soma prefixa. 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 11 (25/abril/2001): 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 12 (02/maio/2001): 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 13 (07/maio/2001): Primeira Prova. Matéria: até a aula 11 inclusive.

Aula 14 (09/maio/2001): Problema de intercalação (merge) de duas sequências de números ordenados (continuação): discussão sobre a complexidade. 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 (21/maio/2001): Técnica de "accelerated cascading". 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 16 (23/maio/01): 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 17 (28/maio/01): Modelo de computação paralela CGM. (Aula dada pelo Prof. Edson Cáceres.)

Aula 18 (30/maio/01): Modelo de computação paralela CGM. (Aula dada pelo Prof. Edson Cáceres.)

Aula 19 (04/junho/01): Modelo de computação paralela CGM. (Aula dada pelo Prof. Edson Cáceres.)

Aula 20 (06/junho/01): Uso do circuito de Euler para vários problemas em árvores. Problema da determinação do pai de cada vértice de uma árvore, definido um vértice para raiz. Problema da determinação da pós-ordem numa árvore.

Aula 21 (18/junho/01): Uso do circuito de Euler para vários problemas em árvores (continuação): determinação da pós-ordem numa árvore; determinação do nível de cada vértice; determinação do número de descendentes de cada vértice. Uma rápida apresentação de problemas resolvidos no modelo CGM.

Aula 22 (20/junho/01): Segunda prova.

Aula 23 (02/julho/01): Terceira prova (substitutiva opcional).