Paralelismo

Usted está aquí

Créditos
6
Tipos
Obligatoria
Requisitos
  • Prerrequisito: AC
  • Prerrequisito: EDA
  • Prerrequisito: SO
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, ...).

Profesores

Responsable

  • Eduard Ayguadé Parra ( )

Otros

  • Daniel Jimenez Gonzalez ( )
  • Gladys Miriam Utrera Iglesias ( )
  • Jordi Tubella Murgadas ( )
  • Josep Ramon Herrero Zaragoza ( )
  • Julian David Morillo Pozo ( )
  • Lluc álvarez Martí ( )
  • 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 - 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. El alumno debe ser capaz 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.
    Related competences: CT7.2,
  2. El alumno debe ser capaz 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.
    Related competences: CT7.2,
  3. El alumno debe ser capaz 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.
    Related competences: CT7.2, CT5.3,
  4. El alumno debe ser capaz de aplicar optimizaciones sencillas en fragmentos de código paralelo para mejorar su rendimiento en arquitecturas paralelas, atacando los factores que limitan su rendimiento
    Related competences: CT7.2, CT6.2,
  5. El alumno debe ser capaz de escoger la estrategia de descomposión más apropriada para expresar el paralelismo en una aplicación (tareas, datos).
    Related competences: CT5.1,
  6. El alumno debe ser capaz 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.
    Related competences: CT5.1,
  7. El alumno debe ser capaz de implementar en OpenMP la versión paralela de una aplicación secuencial
    Related competences: CT5.3, CT5.6,
  8. El alumno debe ser capaz 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.
    Related competences: CT8.1, CT6.2, CT1.1B,
  9. El alumno debe ser capaz 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.
    Related competences: CT8.1, CT6.2, CT1.1B,
  10. El alumno debe ser capaz 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.
    Related competences: G3.2,
  11. En caso de optar por la competencia transversal Tercera Lengua, el estudiante deberá ser capaz de elaborar los entregables de las práctica (parcial o totalmente) en inglés.
    Related competences: G3.2,

Contenidos

  1. Introducción y motivación
    Necessitat del paral.lelisme, paral.lelisme vs. concurrència, possibles problemes en l'us concurrència: deadlock, lifelock, starvation, fairness, data races
  2. Análisis de aplicaciones paralelas
    Mètriques bàsiques: paral·lelisme, temps d'execució, speedup i escalabilitat. Análisi de l'impacte dels overheads associats a la creació de tasques i la seva sincronització i la compartició de dades. Eines per la predicció i l'anàlisi de paral.lelisme i visualització de comportament: Paraver i Tareador
  3. Principios de programación paralela: descomposición en tareas
    Task decomposition vs. data decomposition. Descomposcio en tasques, granularitat i anàlisi de dependències. Identificació de patrons de paral.lelisme: iterative vs. divide and conquer task decompositions. Mecanismes per implementar la descomposició en tasques: creació de regions paral·leles i tasques; mecanismes per garantir task ordering i data sharing.
  4. Introducción a las arquitecturas paralelas
    Paral.lelisme dins d'un processador (ILP, DLP i TLP) i entre els processadors que formen els multiprocessadors de memòria compartida SMP i ccNUMA (coherència de cache, consistència de memòria, sincronització).
  5. Principios de programación paralela: descomposición de datos
    Descomposició de dades (descomposició geomètrica vs. estructures recursives) per arquitectures amb memoria compartida. Localitat en l'accés a les dades en arquitectures paral·leles de memòria compartida. Generació de codi en funció de la descomposició de dades. Breu introducció a les arquitectures de memòria distribuïda i la seva programació (cas concret: MPI).
  6. Programación con memoria compartida: OpenMP
    Regions paral.leles, threads i tasques. Task/thread barriers. Exclusió mútua i locks. Distribuïdors de feina: bucles.
  7. Revisión de problemas de controles
    En aquestes sessions es resoldran dubtes que els estudiants puguin tenir en els problemes dels controls

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 los ejercicios propuestos en las sesiones de laboratorio y extracción de conclusiones.
Objetivos: 1 3 2 10
Contenidos:
Teoría
6h
Problemas
0h
Laboratorio
8h
Aprendizaje dirigido
0h
Aprendizaje autónomo
6h

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

Participar activamente en las sesiones de teoría/problemas. Estudiar los contenidos del tema 6 y preparar la realización de los ejercicios propuestos para las sesiones de laboratorio. Resolución de los ejercicios propuestos en las sesiones de laboratorio y extracción de conclusiones.
Objetivos: 4 7 10 11
Contenidos:
Teoría
0h
Problemas
0h
Laboratorio
22h
Aprendizaje dirigido
0h
Aprendizaje autónomo
22h

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

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

Control temas 1, 2 y 3


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

Asimilación de los aspectos fundamentales en las arquitecturas paralelas

Participar activamente en las sesiones de teoría/problemas. Estudiar los contenidos del tema 5 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 de datos

Participar activamente en las sesiones de teoría/problemas. Estudiar los contenidos del tema 5 y realizar los ejercicios propuestos. Usar OpenMP para expresar descomposiciones de datos para arquitecturas con memoria compartida.
Objetivos: 5 6 10
Contenidos:
Teoría
6h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
8h

Control temas 4 y 5


Objetivos: 8 4 5 6 7 10
Semana: 14
Tipo: examen de teoría
Teoría
2h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
8h

Revisión de problemas de los controles

Participar activamente en las sesiones de problemas.
  • Aprendizaje dirigido: Realización de actividades prácticas dirigidas, en grupos pequeños, sobre otros modelos de programación
Objetivos: 9 10
Contenidos:
Teoría
0h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
3h
Aprendizaje autónomo
4h

Examen final


Objetivos: 8 9 4 5 6 7 10
Semana: 15 (Fuera de horario lectivo)
Tipo: examen final
Teoría
0h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
3h
Aprendizaje autónomo
12h

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 clase de laboratorio también se hacen semanalmente.

El curso utiliza el lenguaje de programación C y principalmente el modelo de programación paralela OpenMP.

Método de evaluación

La nota de la asignatura se calcula a partir de 2 notas:
- Nota de contenidos teóricos (peso 70%)
- Nota de laboratorio (peso 30%)

La nota de laboratorio (Lab) se obtiene principalmente a partir de las notas de los entregables, modulada por el rendimiento durante las sesiones de prácticas y una posible entrevista a final de curso por parte del profesor de laboratorio.

Durante el curso se realizan 2 controles C1 i C2. La nota de evaluación continua (AC) se calcula como la media de la nota obtenida en los 2 controles:

AC = 0.5*C1 + 0.5*C2

Si AC>=5 entonces la nota final (NF) del alumno será:

NF = 0.3*Lab + 0.7*AC

El alumno que no supere la evaluación continua (AC<5) tendrá que hacer el examen final (EF). En este caso, la nota final será:

NF = 0.3*Lab + 0.7*max(EF, 0.25*AC + 0.75*EF)

Si algún alumno que haya aprobado la asignatura por evaluación continua (AC>=5) quiere hacer el examen final con el objetivo de mejorar nota, tendrá que avisar al coordinador de la asignatura por e-mail al menos con una semana de antelación a la fecha del examen. En este caso, la nueva nota final se calculará utilizando la expresión siguiente:

NF = 0.3*Lab + 0.7*max(EF, AC)

La competencia transversal de tercera lengua se evaluará a partir de los informes asociados a las prácticas de laboratorio. Estos informes deberán escribirse en inglés y requerirán la lectura del enunciado de la práctica (también en inglés) asi como el manual de OpenMP. Se evaluará tanto la estructura del documento escrito como la capacidad de transmitir los resultados y las conclusiones de la práctica (siguiendo un documento de rúbricas disponible). La nota de la competencia podrá ser A, B, C, D o NA donde:
- A indica que la competencia se ha superado con un nivel de excelencia
- B indica que la competencia se ha superado con el nivel deseado
- C indica que la competencia se ha superado con un nivel suficiente
- D indica que la competencia no se ha superado
- NA indica que la competencia no se ha evaluado

Bibliografía

Básica:

Complementaria:

Capacidades previas

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