Electiva_V_Algoritmos_paralelos

Vista previa del material en texto

UNIVERSIDAD NACIONAL DE ASUNCIÓN 
FACULTAD POL ITÉCNICA 
PROGRAMA DE ESTUDIO 
INGENIERIA INFORMÁTICA 
 
 
I. - IDENTIFICACIÓN 
1. Materia : Electiva 5 - Diseño de algoritmos Paralelos 
2. Semestre : Noveno 
3. Horas semanales : 7 horas 
3.1. Clases teóricas : 3,5 horas 
3.2. Clases prácticas : 3,5 horas 
4. Total real de horas disponibles: 112horas 
4.1. Clases teóricas : 56 horas 
4.2. Clases prácticas : 56 horas 
II. - JUSTIFICACIÓN 
Esta asignatura es continuación de las anteriores sobre estructuras de datos y algoritmos, temas centrales de las ciencias de la 
computación y de cualquier carrera de informática. 
El curso presenta y analiza las estructuras de datos y los algoritmos fundamentales desarrollados en las últimas décadas, 
especialmente los relacionados a búsqueda y ordenación - interna y externa -, búsqueda de texto, algoritmos de grafos y técnicas de 
diseño de algoritmos, realizando en cada caso una evaluación del desempeño de estos algoritmos y estructuras de datos desde la 
perspectiva de su aplicación a problemas representativos. 
III. - OBJETIVOS 
1. Proveer al alumno los conocimientos básicos para el aprovechamiento de los computadores paralelos, multiprocesadores y 
multicomputadores. 
2. Presentar los distintos modelos de programación para máquinas paralelas. 
3. Proporcionar algoritmos paralelos para problemas fundamentales, e introducir el diseño y análisis de algoritmos paralelos para la 
resolución de problemas concretos en ciertos campos de aplicación. 
IV. - PRE-REQUISITO 
1. Algoritmos y Estructuras de Datos III, Redes de computadoras, Estructura de los lenguajes 
V. - CONTENIDO 
5.1. Unidades programáticas 
 
Unidad 1. Introducción al cómputo paralelo 
Unidad 2. Plataformas de programación paralela. 
Unidad 3. Principios de diseño de algoritmos paralelos 
Unidad 4. Operaciones de comunicación básicas 
Unidad 5. Modelos analíticos de programas paralelos 
Unidad 6. Programación utilizando el paradigma de pasos de mensajes 
Unidad 7. Programación de plataformas de memoria compartida 
Unidad 8. Algoritmos paralelos de matrices densas: 
Unidad 9. Ordenamiento 
Unidad 10. Algoritmos de grafos 
Unidad 11. Algoritmos de búsqueda para optimización discreta 
Unidad 12. Algoritmos iterativos paralelos 
 
Ingeniería en Informática Facultad Politécnica - 2005 
 
�
Página 2 de 3 
5.2. Desarrollo de las unidades programáticas 
Contenidos 
Unidad 1. Introducción al cómputo paralelo 
Introducción al cómputo paralelo. Motivación del paralelismo. 
 
Unidad 2. Plataformas de programación paralela. 
Paralelismo implícito. 
Limitaciones en el desempeño de los sistemas de memoria. 
Costos en la comunicación en máquinas paralelas. 
Organización física de plataformas paralelas. 
Mecanismos de enrutamientos para redes de interconexión 
Impacto del mapeo de procesos a procesadores y las técnicas de mapeo 
 
Unidad 3. Principios de diseño de algoritmos paralelos 
Técnicas de descomposición 
Características de tareas e interacciones 
Técnicas de mapeo para el balance de carga 
Métodos para contener sobrecargas de interacciones 
Modelos de algoritmos paralelos 
 
Unidad 4. Operaciones de comunicación básicas 
Broadcast uno a todos y reducción todos a uno 
Reducción y broadcast todos a todos 
Reducción a todos 
Scatter y Gather 
Comunicación personalizada todos a todos 
Corrimiento circular 
Mejora en la velocidad de algunas operaciones de comunicación 
 
Unidad 5. Modelos analíticos de programas paralelos 
Fuentes de sobrecostos en programas paralelos 
Métricas de desempeño de sistemas paralelos 
El efecto de la granularidad en el desempeño 
Escalabilidad de sistemas paralelos 
Tiempo mínimo de ejecución y tiempo de ejecución mínimo de costo optimo 
Análisis asintótico de programas paralelos 
Métricas de escalabilidad 
 
Unidad 6. Programación utilizando el paradigma de pasos de mensajes 
Principios de la programación de paso de mensajes 
Las primitivas Send y Receive 
PVM y MPI 
Solapamiento de comunicación con computación 
Operaciones de comunicación y computación colectiva 
Operaciones sobre grupos 
 
Unidad 7. Programación de plataformas de memoria compartida 
Hilos, pthreads. 
Creación y terminación de hilos 
Primitivas de sincronización de Pthreads 
Cancelación de un hilo 
OpenMP 
 
Unidad 8. Algoritmos paralelos de matrices densas 
Algoritmo de Cannon y DNS 
Multiplicación matriz-vector 
Multiplicación matriz-matriz 
Resolución de sistemas de ecuaciones lineales 
 
Unidad 9. Ordenamiento 
Ordenamiento en computadoras paralelas 
Redes de ordenamiento 
Ordenamiento en burbuja y variantes 
Quicksort 
 
Unidad 10. Algoritmos de grafos 
Definiciones y representación 
El algoritmo de Prim 
El algoritmo de Dijkstra 
Camino más corto a todos los pares 
Cerradura transitiva 
Algoritmos para grafos dispersos 
 
Ingeniería en Informática Facultad Politécnica - 2005 
 
�
Página 3 de 3 
Unidad 11. Algoritmos de búsqueda para optimización discreta 
Parallel Depth-First Search 
Parallel Depth-First Search 
Anomalías en el desempeño de algoritmos de búsqueda paralela 
 
Unidad 12. Algoritmos iterativos paralelos 
Algoritmo Iterativo de Jacobi, otros. 
 
VI. - ESTRATEGIAS METODOLÓGICAS 
1. Realización de prácticas en laboratorio. 
2. Trabajos prácticos. 
3. Actividades extra clases, a cargo de los alumnos (codificación de los alumnos). 
4. Exposición y discusión de los temas. 
VII. - MEDIOS AUXILIARES 
1. Proyector 
2. Laboratorios de informática con Linux 
3. PVM, MPI, Lenguaje C 
VIII. - EVALUACIÓN 
Los exámenes parciales requeridos por los reglamentos de la Facultad. Cada examen parcial constará de una parte teórica y otra 
práctica. 
Cinco trabajos prácticos. 
La calificación final será establecida de acuerdo a la escala vigente en la Facultad. 
IX. - BIBLIOGRAFÍA 
� Kumar, V; Grama, A.; Gupta, A.; Karypis, G.. Introduction to Parallel Computing, Second Edition. Addison Wesley, 2003 
� PVM Parallel Virtual Machine. A Users' Guide and Tutorial for Networked Parallel Computing. 
Geist, A.; Beguelin, A; Dongarra, J. et alt.. The MIT Press, 1994 
� P. S. Pacheco. Parallel Programming with MPI. Morgan Kaufmann Publishers, 1997