3.13.4 PD/Análisis y programación de algoritmos paralelos (3 horas Core-Tier1)

Temas:
Core Tier2

• Caminos críticos, el trabajo y la duración y la relación con la ley de Amdahl.
• Aceleración y escalabilidad.
• Naturalmente (vergonzosamente) algoritmos paralelos.
• Patrones Algoritmicos paralelos (divide-y-conquista, map/reduce, amos-trabajadores, otros)
  1. Algortimos específicos (p.e., MergeSort paralelo)

Electivo

• Algoritmos de grafos paralelo (por ejemplo, la ruta más corta en paralelo, árbol de expansión paralela)
• Cálculos de matriz paralelas.
• Productor-consumidor y algoritmos paralelos segmentados.
• Ejemplos de algoritmos paralelos no-escalables.

Objetivos de Aprendizaje (Learning Outcomes):
Core-Tier2:

1. Definir: camino crítico, trabajo y span [Familiarizarse (Familiarity)]
2. Calcular el trabajo y el span y determinar el camino crítico con respecto a un diagrama de ejecución paralela. [Usar (Usage)]
3. Definir speed-up y explicar la noción de escalabilidad de un algoritmo en este sentido [Familiarizarse (Familiarity)]
4. Identificar tareas independientes en un programa que debe ser paralelizado [Usar (Usage)]
5. Representar características de una carga de trabajo que permita o evite que sea naturalmente paralelizable [Familiarizarse (Familiarity)]
6. Implementar un algoritmo dividir y conquistar paralelo (y/o algoritmo de un grafo) y medir empiricamente su desempeño relativo a su analogo secuencial [Usar (Usage)]
7. Descomponer un problema (por ejemplo, contar el número de ocurrencias de una palabra en un documento) via operaciones map y reduce [Usar (Usage)]

Elective:

1. Proporcionar un ejemplo de un problema que se corresponda con el paradigma productor-consumidor [Familiarizarse (Familiarity)]
2. Dar ejemplos de problemas donde el uso de pipelining sería un medio eficaz para la paralelización [Familiarizarse (Familiarity)]
3. Implementar un algoritmo de matriz paralela [Usar (Usage)]
4. Identificar los problemas que surgen en los algoritmos del tipo productor-consumidor y los mecanismos que pueden utilizarse para superar dichos problemas [Familiarizarse (Familiarity)]