Información Básica
-
Créditos: 3
-
Horas de trabajo acompañado: 5 / semana (3 horas clase, 2 horas taller)
-
Horas de trabajo independiente: 4 / semana
-
Pre-requisitos: Sistemas Operativos, Comunicación de Datos, Análisis y Diseño de Algoritmos
-
Tipo de curso: Núcleo de Formación Fundamental.
Descripción del Curso
Objetivos
Al finalizar el curso los participantes podrán, identificar diferentes aspectos de la programación paralela, analizár un problema y descomponerlo (de ser posible) para generar una solución paralela al problema planteado. Podrá comparar diferentes formas de programar en paralelo y podra determinar cuales soluciones paralelas ofrece las mejores ventajas en cuanto a desempeño. Podrá tomar como base alguno de los algoritmos paralelos existentes para desarrollar nuevos algoritmos paralelos.
Se desarrollan competencias en
Contenido
Primera parte: Programación paralela
| Sesión | Horas teóricas | Prácticas acompañadas | Temas | Profundidad | Bibliografía |
|---|---|---|---|---|---|
| 1 | 0.75 | Introducción a la programación paralela. | Familiaridad | [1,5] | |
| 1 | 0.75 | Necesidad por comunicación y coordinación/sincronización. | Familiaridad | [1,5] | |
| 2 | 0.75 | Independencia y Particionamiento. | Familiaridad | [1] | |
| 2 | 0.75 | Conocimientos básicos en los conceptos de descomposición paralela. | Familiaridad | [2,1] | |
| 3 | 1.0 | 0.5 | Descomposición basada en tareas | Uso | [2] |
| 3 | 0.5 | 1.5 | – Implementación usando hilos. | Uso | [2] |
| 4 | 1.5 | 0.5 | Descomposición basada en datos | Uso | [2] |
| 5 | 1.5 | 1.0 | – Implementación usando SIMD y MapReduce | Uso | [2,3] |
| 6 | 1.5 | 0.5 | Actores y procesos reactivos (ej. manejadores de solicitudes) | Evaluación | [1,5] |
| 7 | 1.5 | Memoria compartida y memoria distribuida | Evaluación | [1,4] | |
| 8 | 1.0 | 1.0 | Control de concurrencia. | Evaluación | [4] |
| 8 | 0.5 | 1.0 | Consistencia y su rol en las garantias en los lenguajes de programas para realizar programas libres de data-races. | Evaluación | [4,1] |
| 9 | 0.5 | 0.5 | – Mensajes punto-a-punto vs. multicast. | Uso | [2] |
| 9 | 0.5 | 1.0 | – Estilo de envio y recpción de mensajes bloqueantes y no-bloqueantes. | Uso | [2] |
| 9 | 0.5 | 0.5 | – Cola de mensajes. | Uso | [2] |
| 10 | 0.5 | Atomicidad | Evaluación | [4,2] | |
| 10 | 0.5 | – Especificación de requerimientos y pruebas de atomicidad y seguridad. | Evaluación | [5] | |
| 10 | 0.5 | – Granularidad de accesos y modificaciones atomicas, y el uso de secciones críticas o transacciones para modelarlos. | Evaluación | [1,4] | |
| 10,11 | 3.5 | 2.0 | – Exclusión mútua usando cerrojos, semaforos, monitores o construcciones relacionadas. | Uso | [2,5] |
| 12 | 0.75 | – Composición | Evaluación | [3,5] | |
| 12 | 0.75 | 1.0 | – Composición de acciones atómicas con granularidad gruesa usando sincronozación. | Evaluación | [2] |
| 13 | 1.0 | – Transacciones (aproximaciones optimisticas y conservativas). | Familiaridad | [5] | |
| 13 | 0.5 | 1.0 | Administración de las interacciones de transacciones con almacenamiento (especialmente bufering). | Familiaridad | [4] |
Total de Horas: 33.5.
Segunda parte: Algoritmos paralelos
| Sesión | Horas teóricas | Prácticas acompañadas | Temas | Profundidad | Bibliografía |
|---|---|---|---|---|---|
| 14 | 0.5 | Camino crítico, trabajo y expansión y su relación con la ley de Amdahl. | Familiaridad | [1,4] | |
| 14 | 1.0 | 0.5 | Speed-up y escalabilidad (Modelos de computación: PRAM, BSP, etc.). | Evaluación | [1,3] |
| 15 | 1.0 | 1.5 | Paralelismo natural (Algoritmos embarasosamente paralelos). | Evaluación | [1,3] |
| 15-16 | 2.0 | 2.0 | Patrones de algoritmos paralelos (dividir y conquistar, map y reduce, maestro-trabajador, otros). | Uso | [3] |
| 17-18 | 3.0 | 2.0 | – Algoritmos específicos (ej. Merge-Sort paralelo). | Uso | [3] |
| 19-20 | 3.0 | 2.0 | Algoritmos paralelos sobre grafos (ej. camino mas corto paralelo, spanning-tree paralelo). | Uso | [3] |
| 21-22 | 3.0 | 2.0 | Computación paralela de matrices. | Uso | [1,3] |
| 23 | 1.5 | 1.0 | Algoritmos productor-consumidor y pipelined. | Uso | [2,3] |
| 24 | 1.5 | Ejemplos de algoritmos no escalables. | Familiaridad | [3] | |
| 25 | 1.5 | 1.0 | Fallas y recuperación. | Evaluación | [1,5] |
Total de Horas: 30.
Uso de material en exámenes
Asistencia
Bibliografía
-
Introduction to Parallel Computing, Ananth Grama, George Karypis, Vipin Kumar and Anshul Gupta, Addison Wesley, 2 ed. 2003.
-
Parallel Programming in C with MPI and OpenMP, Michael Quinn, McGraw-Hill, 2003.
-
An Introduction to Parallel Algorithms, Joseph JaJa, Addison-Wesley Publishing Company, 1992.
-
Parallel Computer Architecture, David Culler, Jaswinder P. Singh, Anoop Gupta, Morgan Kaufmann Publishers, 1999.
-
Is Parallel Programming Hard, And, If So, What Can You Do About It?, Paul E. McKenney.
Instalaciones
Salón de clase con computador y proyector. Laboratorio de Ingeniería de Sistemas y Computación.