Créditos ECTS Créditos ECTS: 4.5
Horas ECTS Criterios/Memorias Trabajo del Alumno/a ECTS: 74.2 Horas de Tutorías: 2.25 Clase Expositiva: 18 Clase Interactiva: 18 Total: 112.45
Lenguas de uso Inglés
Tipo: Materia Ordinaria Grado RD 1393/2007 - 822/2021
Centro Escuela Técnica Superior de Ingeniería
Convocatoria: Segundo semestre
Docencia: Sin docencia (En extinción)
Matrícula: No matriculable (Sólo alumnado repetidor)
Esta materia tiene como objetivo introducir a los estudiantes en el tópico de la programación paralela de sistemas múltinúcleo con memoria compartida y de sistemas multiprocesador. Se hará un énfasis especial en desarrollar abstracciones de alto nivel para facilitar la detección de concurrencia en las aplicaciones que les permitan optimizar el rendimiento. Asimismo los alumnos aprenderán los mecanismos que les permiten programar la concurrencia en los sistemas de computación y caracterizar su rendimiento.
PROGRAMA
El programa teórico se desarrollará en un total de 12 clases magistrales. Se dedican un total de 27 horas de clase a resolución y discusión de casos y realización de prácticas.
TEORÍA
Tema 1: Mecanismos de Implementación para Programación Paralela (6 horas)
- Programación paralela para sistemas de memoria compartida: OpenMP.
- Programación paralela para sistemas basados en paso de mensajes: MPI.
- Programación paralela para sistemas manycore: MPI
- Escalamiento y ley de Amdahl: caracterización de rendimiento (ganancia en velocidad, isoeficiencia).
Objetivo: dar a conocer las interfaces para programar la concurrencia en los programas con dos paradigmas ampliamente aceptados: paso de mensajes y memoria compartida. Introducir el concepto de escalamiento y sus límites y las diferentes técnicas de caracterización del rendimiento.
Tema 2: Introducción teórica a la Programación Paralela (2 horas)
- Anális del problema.
- Descomposición del problema.
- Descomposición guiada por tareas.
- Descomposición guiada por datos.
- Comunicaciones.
- Sincronización.
- Dependencia de Datos.
- Balanceo da carga.
- Granularidad.
- Entrada/salida en paralelismo.
- Depuración de programas paralelos.
- Análisis de prestaciones y sintonización (tuning) de programas paralelos.
Objetivo: dar una introducción de alto nivel a los principales conceptos teóricos de la programación paralela. Pretendemos dar una base teórica mínima para abordar la parte práctica de programación paralela.
Tema 3: Ejemplos de Paralelización (4 horas)
Objetivo: en este tema presentamos varios ejemplos de paralelización de programas, partiendo de una versión puramente serie, pasando por versiones paralelas poco eficientes, hasta llegar a versiones paralela mas eficientes.
PRÁCTICAS
Las prácticas se llevarán a cabo en los multprocesadores del CESGA y en sistemas multinúcleo disponibles en la ETSE o estructuras asociadas.
BLOQUE 1: Programación básica con OpenMP, MPI (6 horas)
Objetivo: familiarizarse con la programación con paso de mensajes (MPI), la programación con memoria compartida (OpenMP).
BLOQUE 2: Programación paralela de algoritmos básicos. (6 horas)
Objetivo: aplicar a ejemplos básicos la metodología de programación paralela descrita en las clases teóricas, utilizando OpenMP y MPI. Optimizar y caracterizar el rendimiento.
BLOQUE3: Proyecto de programación paralela. (12 horas)
Objetivo: paralelizar una aplicación de cierta complejidad aplicando la metodología descrita en las clases de teoría para optimizar el rendimiento. Optimizar la implementación para obtener un escalamiento idóneo. Hacer un estudio de escalamiento dependiente del número de procesadores y tamaño del problema (caracterización de rendimiento). El proyecto puede llevarse a cabo en grupos de dos alumnos.
Básica:
T.G. Mattson, B.A. Sanders and B.L. Massingill, Patterns for Parallel Programming, Addison-Wesley, 2005.
Esta é a referencia fundamental para as clases de teoría. Expón unha medoloxía baseada en patróns para programación paralela, que sirve de soporte para os contidos da materia. Esta é metodoloxía que Intel, intenta que asimilen os programadores ante o reto da programación paralela. Polos contidos do libro, podemos dicir que a maior parte do mesmo é atemporal, e podemos dicir que as metodoloxías de programación paralela non progresan co tempo dunha forma clara.
P. Pacheco, "An Introduction to Parallel Programming", Morgan Kaufmann Publishers, 2011.
Libro de introducción a la programación paralela que complementa el anterior, que explica las metodologías y ejemplos para programar con OpenMP e MPI.
https://computing.llnl.gov/tutorials/parallel_comp/. Blaise Barney, Lawrence Livermore National Laboratory
Web del Lawrence Livermore National Laboratory que sirve como introducción a la programación paralela.
Complementaria:
S. Akhter and J. Roberts, Multi-core Programming. Increasing Performance through Software Multi-threading, Intel Press, 2006.
Este es un libro editado por Intel, que sirve de complemento al anterior, donde se explican detalles de más bajo nivel para la implementación de programas paralelos.
M.J. Quinn, Parallel Programming in C with MPI and OpenMP, McGraw-Hill, 2004.
Libro de referencia para programación con MPI y OpenMP, y descripción de ejemplos sencillos de programación paralela utilizando estas herramientas.
B. Chapman, G. Jost and . van der Pas, "Using OpenMP: Portable Shared Memory Parallel Programming", The MIT Press, 2007
Libro de referencia para programación con OpenMP, centrado en la obtención de elevadas prestaciones con numerosos ejemplos y explicación en profundidad de la funcionalidad de OpenMP.
J. Levesque, Aaron Vose, "Programming for Hybrid Multi/ManyCore Mpp Systems", CRC, 2018.
Libro reciente que aborda ejemplos complejos de paralelización con OpenMP e MPI.
Contribuír a alcanzar las competencias recogidas en la memoria del título de Grado en Ingeniería Informática en la USC (CG4, CG9, TR1, TR2, TR3, RI1, RI6, RI7, RI8, RI14).
Específicamente:
CG4. Capacidad para definir, evaluar y seleccionar plataformas hardware y software para el desarrollo y ejecución de sistemas, servicios y aplicaciones informáticas, de acuerdo con los conocimientos adquiridos según lo establecido en el "Acuerdo del Consejo de Universidades del 03/03/2009 para los títulos oficiales en el ámbito de la Ingeniería Técnica Informática".
CG9. Capacidad para resolver problemas con iniciativa, toma de decisiones, autonomía y creatividad. Capacidad para saber comunicar y transmitir los conocimientos, habilidades y destrezas de la profesión de Ingeniero en Informática.
TR1. Instrumentales: capacidad de análisis y síntesis. Capacidad de organización y planificación. Comunicación oral y escrita en gallego, castellano e inglés. Capacidad de gestión de la información. Resolución de problemas. Toma de decisiones.
TR2. Personales: Trabajo en equipo. Trabajo en un equipo multidisciplinar y multilingüe. Habilidades en las relaciones interpersonales. Razoamiento crítico. Compromiso ético.
TR3. Sistémicas: Aprendizaje autónomo. Adaptación a nuevas situaciones. Creatividad. Iniciativa y espíritu emprendedor. Motivación por la calidad. Sensibilidad por temas medioambientales.
RI1. Capacidade para deseñar, desenvolver, seleccionar e avaliar aplicacións e sistemas informáticos, asegurando a súa fiabilidade, seguridade e calidade, conforme aos principios éticos e a lexislación e normativa vixente.
RI6. Coñecemento e aplicación dos procedimentos algorítmicos básicos das tecnoloxías informáticas para deseñar solucións a problemas, analizando a idoneidade e complexidade dos algoritmos propostos.
RI7. Coñecemento, deseño e utilización de forma eficiente dos tipos e estructuras de datos más axeitadas á resolución dun problema.
RI8. Capacidade para analizar, deseñar, construir e manter aplicacións de forma robusta, segura e eficiente, elixindo o paradigma e as linguaxes de programación máis axeitados.
RI14. Coñecemento e aplicación dos principios fundamentais e técnicas básicas da programación paralela, concorrente, distribuída e de tiempo real.
Competencias asociadas al módulo de programación dentro del Grado:
- Saber calcular la complejidad computacional de un algoritmo y evaluar la implementación más adecuada de un algoritmo determinado de acuerdo con los recursos disponibles (memoria y tiempo de ejecución).
- Conocer diferentes paradigmas de programación y saber escoger el más apropiado en cada situación.
- Conocimiento de los diferentes paradigmas de programación.
Esta materia tiene un enfoque eminentemente práctico, donde el aprendizaje es a través de ejercicios y un proyecto de programación. Planteamos los siguientes tipos de clases:
Clases magistrales (12 horas): En estas clases el profesor desarrollará de una manera resumida los contenidos del programa teórico, que sirve de base para la posterior aplicación en las clases prácticas de programación. Los alumnos podrán acceder al material que se expondrá en clase con antelación, por lo que se espera que el alumno participe en la discusión de los conceptos que se traten. El profesor promoverá un ambiente participativo y le asignará a algunos alumnos ciertas partes del programa para que las expliquen.
Clases prácticas (24 horas): estas clases estarán dedicadas a desarrollar el programa de prácticas de la materia. Básicamente consistirán en la realización de programas paralelos de complejidad creciente hasta asignarle un proyecto completo de programación paralalela a grupos de dos alumnos. Los alumnos serán el elemento activo en estas clases, y el profesor guiará el aprendizaje ante las cuestiones y dudas planteadas. Los enunciados de las prácticas, así como el material de ayuda (tutoriales, etc) estarán disponibles en el campus virtual de la USC.
Clases de discusión (3 horas): En estas clases los alumnos expondrán los proyectos realizados, discutiendo su implementación a diferentes niveles y el grado de escalamento de la aplicación.
Las tutorías podrán ser presenciales (horario de acuerdo con los alumnos o fijado por el centro), a través de correo electrónico, o a través del campus virtual.
Desarrollo de competencias:
CG4: con la era multinúcleo, la commputación en la nube y "big data", la programación paralela resulta fundamental. Esta competencia se desarrolla en las clases teóricas en el aspecto concreto del contexto de herramientas para la programación paralela.
CG9: el proyecto constituye la mayor oportunidad para desarrollar esta competencia, ya que el planteamiento es bastante abierto, y permite al alumno mostrar y desarrollar sus capacidades en terminos de creatividad, toma de decisiones, autonomía e iniciativa. El alumno tiene el incentivo de desarrollar estas capacidades debido a los criterios de evaluación. En la interacción durante la realización del proyecto, el profesor intercambiará ideas al respecto y guiará a los estudiantes en el desarrollo de estas competencias.
TR1:
- Capacidad de análisis y síntesis: las prácticas de programación paralela que se llevan a cabo obligan a ejercitar estas capacidades, ya que los alumnos tienen que diseñar la estrategia de paralelización (síntesis) y realizar un análisis de las ganancias de velocidad que se obtienen (normalmente requiere analizar la limitación de las ganancias en velocidad obtenidas).
- Capacidad de organización y planificación: todos los ejercicios y prácticas a entregar tienen plazos estrictos de entrega, por lo que los alumnos tienen un claro incentivo a mejorar sus capacidades de organización y planificación. Para ayudar a los alumnos, en el caso de las prácticas, además del plazo de entrega, se indica el número de sesiones de prácticas recomendado para cada una de ellas.
- Comunicación oral y escrita en lengua nativa y extranjera: la calidad de la presentación y redacción de las memorias de prácticas aparecen en los criterios de valoración de las mismas. Los alumnos tienen que hacer una presentación oral de los resultados de la última práctica (proyecto), lo cual también se tiene en cuenta en la nota de la misma.
En la interacción con los alumnos en las clases prácticas, ante las dudas de los alumnos, el profesos tiene por norma no mirar a la pantalla del ordenador, y por lo tanto el alumno tiene que explicarle verbalmente al profesor el problema que surgió de forma concisa y clara.
En cuanto a la lengua extrajera, la materia se imparte completamente en inglés, y los alumnos tienen el incentivo de expresarse también en esta lengua en todos os aspectos docentes. Los alumnos tienen que consultar manuales y documentos en inglés para llevar a cabo algunos ejercicios y prácticas.
- Resolución de problemas: el proceso de paralelización de programas ayuda a desarrollar esta competencia.
- Toma de decisiones: la práctica 2 (proyecto) se especifica de una forma bastante abierta, de tal forma que el alumno tiene que tomar decisiones para su diseño. Por supuesto, estas decisiones tienen consecuencias en la evaluación de la práctica.
TR2:
- Trabajo en equipo: parte de las prácticas se lleva a cabo en grupos de dos personas, lo que exige cierta coordinación.
- Razonamiento crítico: la idea de la presentación de los resultados de la práctica 2 (proyecto) es que el resto de alumnos opine y critiquen dicha presentación.
- Compromiso ético: Se hace mucha incidencia en evitar el plagio, por lo injusto que resulta, y por los riesgos que implica: se hace saber que existe una normativa antiplagio en la Escuela que puede tener serias consecuencias, que el profesor no vacilará en aplicarla si detecta casos claros.
TR3:
- Aprendizaje autónomo: algunas partes de la materia no se explican en detalle en clase y simplemente se les proporciona el material para su estudio autónomo. En las prácticas tienen que elaborarse algunos conceptos que no fueron explicados en detalle, por lo que el propio alumno tiene que profundizar de forma autónoma.
- Creatividad: este es un criterio que se valorar en las notas de prácticas. Creatividad y elegancia en las soluciones aportadas. En la interacción con los alumnos, el profesor ilustrará con ejemplos este aspecto, e intentará transmitir a los alumnos la importancia del proceso creativo.
- Motivación por la calidad: este es un criterio que se valora en la nota de prácticas y ejercicios, haciendo énfasis explícito este aspecto cuando se proponen los enunciados.
- Sensibilidad hacia los temas medioambientales: por los temas tratados en la materia, se hará énfasis en el problema del consumo de potencia/energía de los procesadores, y la necesidad de reducirlo para contribuir a una sociedad sostenible. Específicamente, el profesor le hará ver a los alumnos que la programación paralela puede ser fundamental para ahorrar en consumos de potencia/energía. Por otra parte, cuando es necesario entregar ejercicios o memorias de prácticas, se indica que se utilice el mínimo papel posible, y con materiales austeros (por ejemplo encuadernación con grapas, etc).
RI1: esta capacidad se desarrolla en las clases teóricas a lo largo del proyecto, ya que hace énfasis en que muchas aplicaciones informáticas necesitan programación paralela, y en estas es necesario garantizar su fiabilidad, seguridad y calidad. Transmitirle al alumno la dificultad de la programación paralela en estos aspectos por la falta de determinismo durante la ejecución. El proyecto sirve para desarrollar esta capacidad, ya que los alumno comprueban lo complejo que resulta depurar programas paralelos y lo difícil que puede resultar garantizar una aplicación fiable y segura.
RI6: esta competencia se trabaja en el contexto de la programación paralela mediante numerosos ejemplos de algoritmos paralelos básicos en diferentes campos, que son revisados y analizados en las clases teóricas. En los ejercicios de programación básicos de las clases interactivas los alumnos tienen la posibilidad de implementar algunos de estos algoritmos básicos.
RI7: esta competencia se trabaja también en el contexto de la programación paralela, analizando las estructuras de datos más adecuadas según el paradigma de programación de memoria compartida o paso de mensajes. Se analizará en las clases teóricas el efecto de las diferentes estructuras de datos según el tipo de problema, en términos d e ganancia de velocidad, posibilidad de errores, etc. El proyecto sirve para poner en práctica todas estas habilidades.
RI8: en las clases teóricas se analizarán los diferentes paradigmas de programación paralela y las lenguajes e interfaces más utilizadas para expresar el paralelismo. Durante las clases interactivas, los alumnos se familiarizan con estos paradigmas y herramientas de programación, en principio resolviendo ejercicios básicos de programación paralela. En el proyecto se afianza esta competencia, realizando ya una aplicación más compleja.
RI14: esta competencia es el núcleo central de esta materia y se trabaja en todas las actividades docentes que realizamos en la materia.
Con respecto a:
"Competencias asociadas ao módulo de programación dentro do grao:
PROG1- Saber calcular la complejidad computacional de un algoritmo y evaluar la implementación más adecuada de un algoritmo determinado de acuerdo con los recursos disponibles (memoria e tiempo de ejecución).
PROG2- Conocer diferentes paradigmas de programación y saber escoger el más apropiado en cada situación.
PROG3- Conocimiento de los diferentes paradigmas de programación."
En las clases teóricas explicamos a ley de Amdahl, y las causas de las limitaciones da ganancia en velocidad de las aplicaciones paralelas. También se enseña a hacer estimaciones de complejidad de los algoritmos paralelos, teniendo en cuenta también los tiempos de comunicación y sincronización según el tipo de paradigma de computación paralela que se utilice. Resulta de relevancia también la explicación del fenómeno de la compartición falsa en el paradigma de memoria compartida. Todos estos conceptos se ilustran con ejemplos, que posteriormente son analizados por estudiantes en las clases prácticas con ejercicios similares. El proyecto resulta ser el mejor medio para afianzar esas competencias, ya que es una aplicación paralela con cierto grado de complejidad, en la que los alumnos tienen que aplicar todos estos conocimientos/habilidades para obtener resultados aceptables. Los criterios de evaluación del proyecto tienen en cuenta explícitamente estos aspectos.
Oportunidad ordinaria:
Contribución a la nota final y criterios de evaluación (sobre 10 puntos):
- Participación en el desarrollo de las clases teóricas (1.5p): el alumno recibirá una nota de hasta 1.5 puntos en función de su participación en las clases teóricas. Puede participar presentado algunos conceptos o discutiendo y planteando dudas o resolviendo dudas planteadas por otros compañeros. En este apartado se evalúan de forma implícita o explícita las siguientes competencias: CG4, TR1, RI1, RI6, RI7, RI8 e RI14, PROG1, PROG2, PROG3.
- Adquisición de conocimientos con OpenMP, MPI y CUDA (1.5p): se valorará el grado de conocimiento adquirido con la realización de algunos ejercicios propuestos y la calidad de los mismos. En este apartado se evalúan de forma implícita o explícita las siguientes competencias: TR1, TR3, RI6, RI8, RI14, PROG3.
- Realización de programas paralelos sencillos (2p): se valorará la aplicación de las metodologías descritas en las clases teóricas, el uso de estructuras eficientes de programación con OpenMP y MPI aplicadas a cada problema concreto. En este apartado se evalúan de forma implícita o explícita las siguientes competencias: TR1, TR3, RI6, RI14.
- Proyecto de programación paralela (5p): se valorará la aplicación de la metodología para programación paralela descrita en las clases teóricas, el grado de dificultad elegido por los alumnos para el proyecto propuesto (la propuesta por parte del profesor será relativamente abierta, y serán los alumnos los que decidan el grado de dificultad que quieran conseguir), calidad del estudio de escalamiento y caracterización del programa, presentación de resultados (oral y escrita). En este apartado se evalúan de forma implícita o explícita las siguientes competencias: CG9, TR1, TR2, TR3, RI1, RI7, RI14, PROG1, PROG2, PROG3.
No existe un mínimo a conseguir en ninguna de las partes. Para superar la materia, debe conseguirse una puntuación de 5 o superior.
Los alumnos que non sean de nueva matrícula non conservan notas de cursos anteriores.
Oportunidad de recuperación y convocatoria extraordinaria:
Los mismos criterios de evaluación que en la oportunidad ordinaria. El límite para la entrega del proyecto y prácticas es el día del examen oficial. Los alumnos harán una presentación del proyecto el día del examen.
Condición para calificación de no presentado: no presentar ninguna práctica o proyecto.
Las tutorías, las discusiones en clase, y la interacción en las clases prácticas le permitirán al profesor conocer de manera informal el grado de asimilación de la materia que van consiguiendo los alumnos al largo del cuatrimestre.
Con 4.5 créditos ECTS, el trabajo personal del alumno debe ser de unas 67.5 horas, distribuidas de la siguiente manera:
- Estudio autónomo: 20 horas, dedicadas a la asimilacíon de los contenidos teóricos para aplicación a las prácticas y al proyecto, y preparación de asignaciones por parte del profesor para desarrollar en clase alguna de las partes del programa teórico.
- Escritura de ejercicios, conclusiones y otros trabajos: 5 horas, fundamentalmente dedicadas a la preparación de la presentación de resultados del proyecto (oral y escrita).
- Programación/experimentación: 35 horas, dedicadas a la resolución de las prácticas y proyecto propuestos.
- Actividades de evaluación: 7.5 horas, dedicadas a la propia presentación de resultados del proyecto, y modificaciones requeridas del proyecto posterior a la corrección y exposición, incorporarndo las propuestas del profesor y del resto de compañeros.
La programación de la materia será de tal forma que la distribución del número de horas de trabajo personal a lo largo del cuatrimestre sea el más uniforme posible. La distribución de este esfuerzo puede variar a lo largo del cuatrimestre, en especial en la etapa de preparación del proyecto, y en la elaboración y presentación de resultados de prácticas.
Resulta recomendable tener conocimientos de programación en C. También resulta interesante tener cursada la materia del grado Sistemas Paralelos, o la de ETIS Sistemas Distribuidos y Paralelos.
La materia está diseñada para que el alumno participe activamente y de manera regular durante su desarrollo.
La entrega de materiales del curso y las comunicaciones electrónicas con los alumnos se llevarán a cabo con la herramienta del campus virtual de la USC.
Algunos temas y notas de clase están disponibles en Inglés.