Paralelismo

Usted está aquí

Créditos
6
Tipos
Obligatoria
Requisitos
  • Prerrequisito: AC
Departamento
AC
La asignatura Paralelismo cubre los aspectos fundamentales relacionados con la programación paralela, fundamental hoy en día para sacar provecho de las arquitecturas multi-núcleo que constituyen los computadores actuales. Se trabajan las principales estrategias de descomposición por tareas y de datos, así como los mecanismos necesarios para asegurar su ejecución correcta (sincronización, exclusión mutua, ...) y formas de mejorar su rendimiento.

Profesorado

Responsable

  • Daniel Jimenez Gonzalez ( )

Otros

  • Eduard Ayguadé Parra ( )
  • Gladys Miriam Utrera Iglesias ( )
  • Jesus Jose Labarta Mancho ( )
  • Jordi Tubella Murgadas ( )
  • Josep Ramon Herrero Zaragoza ( )
  • Mario Cesar Acosta Cobos ( )
  • Pedro José Martínez Ferrer ( )
  • Rosa Maria Badia Sala ( )

Horas semanales

Teoría
2
Problemas
0
Laboratorio
2
Aprendizaje dirigido
0.4
Aprendizaje autónomo
5.6

Competencias

Competencias Técnicas

Competencias técnicas comunes

  • CT1 - Demostrar conocimiento y comprensión de hechos esenciales, conceptos, principios y teorías relativas a la informática y a sus disciplinas de referencia.
    • CT1.1B - Interpretar, seleccionar y valorar conceptos, teorías, usos y desarrollos tecnológicos relacionados con la informática y su aplicación a partir de los fundamentos matemáticos, estadísticos y físicos necesarios. CEFB2. Capacidad para comprender y dominar los fundamentos físicos y tecnológicos de la informática: electromagnetismo, ondas, teoría de circuitos, electrónica y fotónica y su aplicación para la resolución de problemas propios de la ingeniería.
  • CT5 - Analizar, diseñar, construir y mantener aplicaciones de forma robusta, segura y eficiente, escogiendo el paradigma y los lenguajes de programación más adecuados.
    • CT5.1 - Escoger, combinar y explotar diferentes paradigmas de programación, en el momento de construir software, atendiendo a criterios como la facilidad de desarrollo, la eficiencia, la portabilidad y la mantenibilidad.
    • CT5.3 - Diseñar, escribir, probar, depurar, documentar y mantener código en un lenguaje de alto nivel para resolver problemas de programación aplicando esquemas algorítmicos y usando estructuras de datos.
    • CT5.6 - Demostrar conocimiento y capacidad de aplicación de los principios fundamentales y de las técnicas básicas de la programación paralela, concurrente, distribuida y de tiempo real.
  • CT6 - Demostrar conocimiento y comprensión del funcionamiento interno de un computador y del funcionamiento de las comunicaciones entre ordenadores.
    • CT6.2 - Demostrar conocimiento, comprensión y capacidad de evaluar la estructura y la arquitectura de los computadores, así como los componentes básicos que los conforman.
  • CT7 - Evaluar y seleccionar plataformas de producción hardware y software para la ejecución de aplicaciones y de servicios informáticos.
    • CT7.2 - Evaluar sistemas hardware/software en función de un criterio de calidad determinado.
  • CT8 - Planificar, concebir, desplegar y dirigir proyectos, servicios y sistemas informáticos en todos los ámbitos, liderando su puesta en marcha, su mejora continua y valorando su impacto económico y social
    • CT8.1 - Identificar tecnologías actuales y emergentes y evaluar si son aplicables, y en qué medida, para satisfacer las necesidades de los usuarios.

Competencias Transversales

Lengua extranjera

  • G3 [Avaluable] - Conocer el idioma inglés con un nivel adecuado de forma oral y por escrito, y con consonancia con las necesidades que tendrán los graduados y graduadas en ingeniería informática. Capacidad de trabajar en un grupo multidisciplinar y en un entorno multilingüe, y de comunicar, tanto por escrito como de forma oral, conocimientos, procedimientos, resultados e ideas relacionadas con la profesión de ingeniero técnico en informática.
    • G3.2 - Estudiar con materiales escritos en inglés. Redactar un informe o trabajo de tipo técnico en inglés. Participar en una reunión técnica llevada a cabo en inglés.

Objetivos

  1. Capacidad de formular sencillos modelos de rendimiento dada una estrategia de paralelización para una aplicación, que permitan estimar la influencia de los principales aspectos arquitectónicos: numero de elementos de proceso, coste de acceso a los datos, coste de la interacción entre elementos de proceso, entre otros.
    Competencias relacionadas: CT7.2,
  2. Capacidad de medir, empleando herramientas de instrumentación, visualización y análisis, el rendimiento alcanzado con la ejecución paralela de una aplicación y detectar los factores que limitan dicho rendimiento: granularidad de tareas, distribución equitativa de carga de trabajo, interacción entre tareas, entre otros.
    Competencias relacionadas: CT7.2,
  3. Capacidad de compilar y ejecutar un programa paralelo, utilizando las herramientas básicas a nivel de línea de comandos para medir el tiempo de ejecucion.
    Competencias relacionadas: CT7.2, CT5.3,
  4. Capacidad de aplicar optimizaciones sencillas en fragmentos de código paralelo para mejorar su rendimiento en arquitecturas paralelas, atacando los factores que limitan su rendimiento.
    Competencias relacionadas: CT7.2, CT6.2,
  5. Capacidad de escoger la estrategia de descomposión más apropriada para expresar el paralelismo en una aplicación (tareas, datos).
    Competencias relacionadas: CT5.1,
  6. Capacidad de aplicar las técnicas básicas que permiten sincronizar la ejecución paralela, evitando las condiciones de carrera y abrazo mortal, y favoreciendo el solapamiento entre cálculo e interacción, entre otros.
    Competencias relacionadas: CT5.1,
  7. Capacidad de implementar en OpenMP la versión paralela de una aplicación secuencial.
    Competencias relacionadas: CT5.3, CT5.6,
  8. Capacidad de identificar los diferentes tipos de paralelismo que se pueden explotar en una arquitectura de computador (ILP, DLP y TLP dentro de un procesador, multiprocesador y multicomputador) y describir sus principios básicos de funcionamiento.
    Competencias relacionadas: CT8.1, CT6.2, CT1.1B,
  9. Capacidad de entender los mecanismos básicos que permiten la compartición coherente de datos en una arquitectura paralela de memoria compartida, con acceso uniforme o no uniforme a memoria.
    Competencias relacionadas: CT8.1, CT6.2, CT1.1B,
  10. Capacidad de seguir la asignatura utilizando los materiales proporcionados en ingles, así como realizar los actos de evaluación (controles y examen final) con el enunciado escrito en ingles.
    Competencias relacionadas: G3.2,
  11. En caso de optar por la competencia transversal Tercera Lengua, capacidad de elaborar los entregables de las práctica (parcial o totalmente) en inglés.
    Competencias relacionadas: G3.2,

Contenidos

  1. Introducción y motivación
    Necesidad del paralelismo, paralelismo vs. concurrencia, posibles problemas en el uso concurrencia: deadlock, lifelock, starvation, fairness, data races
  2. Análisis de aplicaciones paralelas
    Métricas básicas: paralelismo, tiempo de ejecución, speedup y escalabilidad. Análisis del impacto de los overheads asociados a la creación de tareas y su sincronización y compartición de datos. Herramientas para la predicción y el análisis de paralelismo y visualización de comportamiento: Paraver y Tareador
  3. Programación con memoria compartida: OpenMP
    Regiones paralelas, threads y tareas. Mecanismos de sincronización entre tareas y threads. Distribución de trabajo estático/dinámico, granularidad.
  4. Introducción a las arquitecturas paralelas
    Paralelismo dentro de un procesador (ILP, DLP y TLP) y entre los procesadores que forman los multiprocesadores de memoria compartida SMP y ccNUMA (coherencia de caché, consistencia de memoria, sincronización).
  5. Principios de programación paralela: descomposición en tareas
    Task decomposition vs. fecha decomposición. Descomposición en tareas, granularidad y análisis de dependencias. Identificación de patrones de paralelismo: iterative vs. divide y conquista task decompositions. Mecanismos para implementar la descomposición en tareas: creación de regiones paralelas y tareas; mecanismos para garantizar task ordering y data sharing.
  6. Principios de programación paralela: descomposición de datos
    Descomposición de datos (descomposición geométrica vs. estructuras recursivas) por arquitecturas con memoria compartida. Localidad en el acceso a los datos en arquitecturas paralelas de memoria compartida. Generación de código en función de la descomposición de datos. Breve introducción en las arquitecturas de memoria distribuida y su programación (caso concreto: MPI).

Actividades

Actividad Acto evaluativo


Asimilación de los conceptos fundamentales y herramientas para modelar y analizar el comportamiento de aplicaciones paralelas

Participar activamente en las sesiones de teoría / problemas. Estudiar los contenidos de los temas 1 y 2 y realizar los ejercicios propuestos. Resolución de las prácticas propuestas en las sesiones de laboratorio y extracción de conclusiones de los resultados obtenidos.
Objetivos: 1 3 2 10
Contenidos:
Teoría
6h
Problemas
0h
Laboratorio
6h
Aprendizaje dirigido
0h
Aprendizaje autónomo
10h

Uso de OpenMP para la expresión de paralelismo en memoria compartida

Participar activamente en las sesiones de laboratorio. Realizar los trabajos/lecturas previos, resolver los ejercicios durante en las sesiones de laboratorio, analizar resultados, extraer conclusiones de los experimentos y elaboración de las entregas correspondientes.
Objetivos: 4 7 10 11
Contenidos:
Teoría
1h
Problemas
0h
Laboratorio
4h
Aprendizaje dirigido
0h
Aprendizaje autónomo
4h

Asimilación de los aspectos fundamentales en las arquitecturas paralelas

Participar activamente en las sesiones de teoría/problemas. Estudiar los contenidos del tema 4 y realizar los ejercicios propuestos.
Objetivos: 8 10
Contenidos:
Teoría
6h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
6h

Asimilación de los principios de descomposición en tareas

Participar activamente en las sesiones de teoría/problemas. Estudiar los contenidos del tema 3 y realizar los ejercicios propuestos. Aplicar los nuevos conocimientos para la resolución de las prácticas de laboratorio asociadas.
Objetivos: 5 6 10
Contenidos:
Teoría
6h
Problemas
0h
Laboratorio
10h
Aprendizaje dirigido
0h
Aprendizaje autónomo
20h

Sesión extra de dudas por el examen parcial

El estudiante podrá realizar la petición de los problemas que quiera repasar por adelantado, pero también podrá realizar peticiones durante la sesión.
Objetivos: 8 9 1 3 2 4 10
Contenidos:
Teoría
0h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
2h
Aprendizaje autónomo
0h

Examen parcial


Objetivos: 9 1 5 6 7 10
Semana: 7
Teoría
2h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
10h

Sesión formativa: repaso de las soluciones a los problemas del examen parcial y retroacción general de los errores encontrados.

Con esta sesión formativa el estudiantado podrá terminar de asimilar conceptos de la primera mitad del cuatrimestre.
  • Aprendizaje dirigido: Realización de una sesión de repaso con las soluciones de las preguntas del control parcial. Esta sesión extra de resolución de problemas debe ayudar a dar una retroacción general del control parcial a todos los alumnos que deseen venir a la sesión.
Objetivos: 8 9 1 3 2 10
Contenidos:
Teoría
0h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
2h
Aprendizaje autónomo
0h

Asimilación de los principios de descomposición de datos

Participar activamente en las sesiones de teoría/problemas. Estudiar los contenidos del tema 6 y realizar los ejercicios propuestos. Aplicar los nuevos conocimientos para la resolución de las prácticas de laboratorio asociadas.
Objetivos: 5 6 10
Contenidos:
Teoría
6h
Problemas
0h
Laboratorio
10h
Aprendizaje dirigido
0h
Aprendizaje autónomo
14h

Sesión extra de dudas por el examen final

El estudiante podrá realizar la petición de los problemas que quiera repasar por adelantado, pero también podrá realizar peticiones durante la sesión.
Objetivos: 8 9 1 3 2 4 5 6 7 10
Contenidos:
Teoría
0h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
2h
Aprendizaje autónomo
0h

Examen final (Teoria y Laboratorio)

La parte de laboratorio estará diferenciada de la parte de teoría y será una prueba escrita sobre papel relacionada con lo que el estudiantado ha trabajado durante el curso.
Objetivos: 8 9 1 3 2 4 5 6 7 10
Semana: 15 (Fuera de horario lectivo)
Teoría
3h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
20h

Metodología docente

Las clases de teoría introducen todos los conocimientos, las técnicas, los conceptos necesarios que se ponen en práctica en las horas dedicadas a problemas y de laboratorio, así como con trabajo personal utilizando una colección de problemas. Las dos horas de clases de teoría/problemas se hacen semanalmente. Las dos horas de clases de laboratorio también se hacen semanalmente, y se valorará la participación activa y rendimiento durante las mismas (trabajo en la práctica, avanzando en la medida de lo posible a fin de alcanzar los objetivos de cada sesión). El curso utiliza el lenguaje de programación C y el modelo de programación paralela OpenMP.

Método de evaluación

La nota de la asignatura (NF) se calcula en base a los siguientes componentes (todos evaluados sobre 10):
- P: la nota del examen parcial (incluye Temas 1 a 3)
- FT: la nota en la parte teórica del examen final (Temas 1 a 5)
- FL: la nota de laboratorio en la parte de laboratorio del examen final (25%)

Además, serán evaluados de forma continua:

- SL: informes de seguimiento del laboratorio (10%) que también servirá para evaluar la competencia transversal de la tercera lengua. IMPORTANTE: La realización y presentación de todos los informes de seguimiento del laboratorio será condición necesaria para superar la asignatura. Sólo se considera informe elaborado y presentado ese informe con un mínimo de contenido. Informes vacíos o con sólo las preguntas, por ejemplo, no se consideran realizados ni presentados.
- AA: la marca de las actividades online a través de Atenea realizadas en el plazo establecido


aplicando la ponderación que se indica a continuación:
N = 0,65*máx(FT, 0,35*P+0,65*FT) + 0,25*FL + 0,10*SL
Si N>=5.0 entonces NF = MIN(10, N * (1 + AA/100)); si no NF=N.

El examen final de laboratorio será un examen escrito (en papel) que se realizará el mismo día del examen final.


La competencia en lengua extranjera se evaluará a partir de los informes entregados para los trabajos de laboratorio. Estos informes deben estar escritos en inglés y requerirán la lectura de la descripción de la asignación del laboratorio (también en inglés), así como las especificaciones de OpenMP. Tanto la estructura del documento escrito como la capacidad de transmitir los resultados y conclusiones del trabajo se utilizarán para evaluar la competencia. La calificación de la competencia será A (excelente), B (bueno), C (satisfactorio), D (suspenso) o NA (No evaluado).

Bibliografía

Básica:

Complementaria:

  • Parallelism - Unit 1: Why Parallel Computing - Ayguade, E.; Ramon Herrero, J.R.; Jimenez, D.; Utrera, G, Departament d'Arquitectura de Computadors , 2022.
  • Parallelism - Unit 2: Understanding Parallelism - Ayguade, E.; Ramon Herrero, J.R.; Jimenez, D.; Utrera, G, Departament d'Arquitectura de Computadors , 2022.
  • Parallelism - Unit 3: Introduction to parallel architectures - Ayguade, E.; Ramon Herrero, J.R.; Jimenez, D.; Utrera, G, Departament d'Arquitectura de Computadors , 2022.
  • Parallelism - Unit 4: Mastering your task decomposition strategies: going some steps further - Ayguade, E.; Ramon Herrero, J.R.; Jimenez, D.; Utrera, G, Departament d'Arquitectura de Computadors , 2022.
  • Parallelism - Unit 5: Data-aware task decomposition strategies - Ayguade, E.; Ramon Herrero, J.R.; Jimenez, D.; Utrera, G, Departament d'Arquitectura de Computadors , 2022.
  • Parallelism: Collection of Exercises - Ayguade, E.; Ramon Herrero, J.R.; Jimenez, D.; Utrera, G, Departament d'Arquitectura de Computadors , 2022.
  • Parallelism: Selection of Exams (with Solutions) - Ayguade, E.; Ramon Herrero, J.R.; Jimenez, D.; Utrera, G, Departament d'Arquitectura de Computadors , 2022.
  • Parallelism Laboratory Assignments - Ayguadé, E... [et al.], Departament d'Arquitectura de Computadors , 2022.
  • Computer architecture: a quantitative approach - Hennessy, J.L.; Patterson, D.A, Elsevier, Morgan Kaufmann , 2019. ISBN: 9780128119051
    https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004117509706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
  • Parallel computer architecture: a hardware/software approach - Culler, D.E.; Singh, J.P.; Gupta, A, Morgan Kaufmann Publishers , 1999. ISBN: 9781558603431
    https://discovery.upc.edu/discovery/fulldisplay?docid=alma991001862689706711&context=L&vid=34CSUC_UPC:VU1&lang=ca

Capacidades previas

Las capacidades previas son las definidas por los pre-requisitos de la asignatura.