Domingo Giménez Cánovas
DOCENCIA 2014/2015
Algoritmos y Programación Paralela
quinto curso de Ingeniería Informática
Metodología de la Programación Paralela
cuarto curso del Grado en Ingeniería Informática
3 créditos teóricos y 3 prácticos
Primer cuatrimestre
Las clases son en el aula B.03 del aulario Norte
Clases los jueves de 15:30 a 17:30, primer día el 18 de septiembre.
Tres de las sesiones que aparecen en la planificación no se impartirán (las de los viernes 26 de septiembre y 24 de octubre y la del 30 de octubre), por lo que las seis horas correspondientes a esas sesiones se impartirán en algunas de las otras sesiones teóricas, alargando estas entre media y una hora.
El horario de prácticas es los jueves de 17:50 a 19:30, en el laboratorio 2.1. Debido a que se usarán equipos del laboratorio de computación científica y posiblemente de centros externos, y a que algunas de las prácticas no serán guiadas, se realizarán prácticas presenciales sólo en algunas de las sesiones, que se anunciará en las clases de teoría y en esta página.
Tutorías lunes, miércoles y jueves de 12 a 14 (mejor quedar antes por correo, para esas horas u otras)
Sesiones y transparencias. Básicamente se seguirá el libro: Francisco Almeida, Domingo Giménez, José Miguel Mantas, Antonio M. Vidal: Introducción a la Programación Paralela, Paraninfo Cengage Learning, 2008 y los programas ejemplo que lo acompañan.
Planificación 2014-2015:
18 septiembre: Presentación, la realizará el profesor Joaquín Cervera, por encontrarse el profesor de la asignatura de viaje
25 septiembre: no hay clase por la inauguración del curso
26 septiembre (viernes, sería la recuperación del día 25, se cambiará a otro horario)
2 octubre: sistemas y programación paralela, códigos, prácticas, ficheros de la práctica 2
16 octubre: MPI, ejemplos MPI
23 octubre: programación híbrida, usaremos las transparencias del Curso de Programación en el Supercomputador Ben-Arabí. Manual de uso del laboratorio de computación científica (se dará una cuenta a cada alumno) en http://luna.inf.um.es/grupo_investigacion. Ejemplos de uso de colas.
24 octubre (viernes, recuperación, se cambiará a otro horario):
30 octubre (está sesión se cambiará a otro horario al estar el profesor de viaje):
6 noviembre: Análisis de algoritmos paralelos de 15:30 a 17:00, a partir de 17:00 presentaciones de temas alternativos de paralelismo
13 noviembre: Anulada por festividad de San Alberto
20 noviembre: Análisis de algoritmos. Clase de teoría de 15:50 a 18:30, para recuperar la del día 13. Puede haber presentaciones antes y después de esa hora para recuperar presentaciones del día 13.
27 noviembre: metodología de la programación paralela, transparencias, del curso de José Miguel Mantas de la Universidad de Granada, utilizados con su permiso.
4 diciembre: metodología de la programación paralela y Esquemas algorítmicos paralelos
11 diciembre: esquemas algorítmicos paralelos
18 diciembre (a partir de las 15:00): presentaciones de los alumnos sobre la paralelización de los métodos de resolución de las prácticas
Junto con el enunciado de los trabajos a realizar se incluirá la fecha de entrega, y en cualquier caso las fechas límite de entregas de los trabajos para cada convocatoria serán las que aparecen en el calendario de exámenes de la facultad (convocatoria de enero: 23 enero; convocatoria de junio: 8 de junio; convocatoria de julio: 14 de julio). De forma individual se puede acordar con el profesor otra fecha para alguna entrega particular, siempre que el alumno haya ido siguiendo los plazos de entrega establecidos de la mayoría de los trabajos. Los trabajos para las tres convocatorias del curso 2014-2015 serán los mismos.
Información diversa
Información sobre MPI: Message Passing Interface Forum y mpich.
Las 500 máquinas más rápidas: TOP500
1. Introducción a la programación paralela (4 horas): Necesidad de la programación paralela, ventajas e inconvenientes, Modelos de computadores paralelos
2. Modelos de programación paralela (8 horas): Modelos de programación; Programación en memoria compartida, OpenMP; Programación por paso de mensajes, MPI, programación de GPU
3. Análisis de algoritmos paralelos (4 horas): Tiempo de ejecución, speed-up, eficiencia y coste; Estudio de escalabilidad; Estudio experimental
4. Metodología de la programación paralela y diseño de algoritmos paralelos (12 horas): Descomposición, Asignación, Balanceo, Solapamiento, Diseño modular, Paralelismo / Particionado de Datos; Esquemas en árbol y grafo; Algoritmos relajados; Computación pipeline; Paralelismo síncrono; Maestro-esclavo, granja de procesos y trabajadores replicados
Trabajos y prácticas
Prácticas presenciales de trabajo con OpenMP y MPI.
Desarrollo de programas básicos de programación en OpenMP y MPI (opcionalmente GPU).
Exposiciones en clase sobre entornos paralelos y paralelización de algoritmos.
Implementación en OpenMP y MPI y estudio teórico y experimental de uno de los algoritmos paralelos estudiados.
Ian Foster: Designing and Building Parallel Programs. 1995
Kumar, Grama, Gupta, Karypis: Introduction to Parallel Computing. Design and Analysis of Algorithms. The Benjamin Cumming Publishing Company. 1994
Alexey L. Lastovetsky: Parallel Computing on Heterogeneous Networks. Wiley, 2003
Michael J. Quinn. Parallel Programming in C with MPI and OpenMP. McGrawHill, 2004
Andrews: Foundations of Multithreaded, Parallel, and Distributed Programming. Addison-Wesley, 2000
Rajkumar Buyya (Editor): High Performance Cluster Computing, Vol 2, Programming and Applications. Prentice Hall. 1999
Barry Wilkinson, Michael Allen: Parallel programming. Prentice-Hall. 1999
Rob H. Bisseling: Parallel Scientific Computation. Oxford University Press, 2004
Evaluación
La asignatura se evaluará sobre los trabajos y prácticas realizadas por los alumnos.
El peso de las distintas partes es:
Participación “activa” en clase: 10%
Prácticas presenciales con trabajo básico OpenMP y MPI (opcionalmente GPU): 10%
Exposición de entorno de programación paralela: 15%
Exposición de paralelismo en el problema, con análisis de diseño y costes y mejoras a conseguir con el paralelismo: 15%
Práctica de programación paralela (en OpenMP, MPI e híbrida, con estudio teórico y experimental y entrega de documentación): 50%