A disciplina MAC5741 no catálogo de disciplinas

Todo o catálogo de disciplinas

Calendário da Pós-Graduação para 2002.

Referêencias bibliográficas:

• JáJá, Joseph. An Introduction to Parallel Algorithms. Addison-Wesley Publishing Company. 1992.

  (O livro está esgotado e sem previsão de novas edições. Há uma cópia na Sala Xerox do Bloco B do IME: pasta número 32 - Prof. Siang)

• 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 15 de abril de 2002 (segunda feira): prova com consulta.

Data da segunda prova: Dia 24 de junho de 2002 (segunda feira): prova com consulta. Matéria: aula 9 até a aula 18 inclusive.

Data da terceira prova (opcional): Prova opcional. Dia 1 de julho de 2002 (segunda feira): prova com consulta. Matéria: toda a matéria.

Avisos:

Exercícios:

• Exercício 1 (Entregar até 25/março/2002.)
• Exercício 2 (Entregar até 3/abril/2002.)
• Exercício 3 (Data entrega: até dia 30/junho/2002)
• Exercício 4 (Data entrega: até dia 30/junho/2002)
• Exercício 5 (Data entrega: até dia 30/junho/2002)

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

Aula 1 (6/março/02): Descrição do curso. Bibliografia. Tabelas mostrando a evolução da capacidade de memória, do processador e a velocidade de processamento. 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 (11/março/02): Comentar sobre importância da Complexidade de Algoritmos. Passar para casa o Exercício 1. (Entregar até 25/março/2002.)

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

Aula 4 (18/março/2002): 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. Exemplo 1.3 - multiplicar duas matrizes n x n. Modelo de memória compartilhada: PRAM (Parallel Random Access Machine).

Aula 5 (20/março/02): 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 6 (1/abril/02): 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 n x n - 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.

Aula 7 (3/abril/02): 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. Hipercubo: definição, propriedades. Exemplo de soma de n numeros num hipercubo de n processadores.

Aula 8 (15/abril/02): Primeira Prova.

Aula 9 (17/abril/02): Exemplo de broadcast de um dado localizado no processador P0 e difundir para todos os outros processadores. Passar para casa o Exercício 5. Definir o grafo de Bruijn. Comentar algumas propriedades (grau constante e diâmetro log n). Comentar sobre 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 10 (22/abril/02): 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 11 (24/abril/02): 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.

Aulas 12 e 13 Semana do Break.

Aulas 14 (13/maio/02 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. 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 15 (15/maio/02): 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 16 (20/maio/2002): 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 17 (03/junho/02): 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 18 (05/junho/02): List ranking: apenas o algoritmo básico baseado em pointer jumping simples. (Este problema será revisto para o modelo de computador paralelo de memória distribuída.) 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 19 (19/junho/02): Modelo CGM (Coarse-Grained Multicomputer): um modelo mais realístico para computadores paralelos de memória distribuída. O Problema de list ranking : técnicas de uso de amostras, quebra de simetria, pointer jumping.

Aula 20 (24/junho/02): Segunda Prova.

Aula 21 (01/julho/02): Terceira Prova (opcional).