Concurrencia, Paralelismo y Sistemas Distribuidos

Créditos
6
Tipos
Obligatoria
Requisitos
Esta asignatura no tiene requisitos , pero tiene capacidades previas
Departamento
CS;DAC
Web
https://mwiki.fib.upc.edu/cpds-miri
Este curso tiene como objetivo proporcionar las bases sobre la computación como una colección de tareas que pueden estar ejecutando al mismo tiempo y que pueden interactuar entre ellas. Estas tareas se pueden ejecutar en uno o múltiples procesadores o distribuidas a través de una red. El curso presenta los modelos, problemas, algoritmos y sistemas y se centran en tres aspectos / módulos: concurrencia (múltiples procesos que interactúan entre sí), paralelismo (multiples núcleos o procesadores), y distribución (multiples ordenadores en una red).

Después de unas sesiones introductorias, el curso consta de 3 módulos: concurrencia, paralelismo y distribución. El estudiante debe seleccionar dos de los tres módulos. Las lecciones se complementan con prácticas de programación para ilustrar los problemas y evaluar las soluciones.

Profesorado

Responsable

Otros

Horas semanales

Teoría
2
Problemas
0
Laboratorio
2
Aprendizaje dirigido
0.5
Aprendizaje autónomo
8

Competencias

Competencias Técnicas de cada especialidad

Computer networks and distributed systems

  • CEE2.1 - Capacidad para entender los modelos, problemas y algoritmos relacionados con los sistemas distribuidos, así como poder diseñar y evaluar algoritmos y sistemas que traten la problemática de la distribución y ofrezcan servicios distribuidos
  • CEE2.3 - Capacidad de entender los modelos, problemas y herramientas matemáticas que permiten analizar, diseñar y evaluar redes de computadores y sistemas distribuidos.

    • High performance computing

  • CEE4.2 - Capacidad de analizar, evaluar, diseñar y optimizar software considerando la arquitectura y de proponer nuevas técnicas de optimización.

    • Competencias Técnicas Genéricas

    Genéricas

  • CG1 - Capacidad para aplicar el método científico en el estudio y análisis de fenómenos y sistemas en cualquier ámbito de la Informática, así como en la concepción, diseño e implantación de soluciones informáticas innovadoras y originales.
  • CG5 - Capacidad para aplicar soluciones innovadoras y realizar avances en el conocimiento que exploten los nuevos paradigmas de la Informática, particularmente en entornos distribuidos.

    • Competencias Transversales

    Trabajo en equipo

  • CTR3 - Ser capaz de trabajar como miembro de un equipo, ya sea como un miembro más, o realizando tareas de dirección con la finalidad de contribuir a desarrollar proyectos con pragmatismo y sentido de la responsabilidad, asumiendo compromisos teniendo en cuenta los recursos disponibles.

    • Razonamiento

  • CTR6 - Capacidad de razonamiento crítico, lógico y matemático. Capacidad para resolver problemas dentro de su área de estudio. Capacidad de abstracción: capacidad de crear y utilizar modelos que reflejen situaciones reales. Capacidad de diseñar y realizar experimentos sencillos, y analizar e interpretar sus resultados. Capacidad de análisis, síntesis y evaluación.

    • Objetivos

    1. Entender la definición de sistema distribuido y sus posibles aplicaciones, además de los desafíos que se deben afrontar para su diseño e implementación.
      Competencias relacionadas: CEE2.1, CG5,
      Subcompetences
      • Conocer las posibles aplicaciones de un sistema distribuido
      • Entender los desafíos para diseñar e implementar un sistema distribuido: heterogeneidad, ausencia de visión global, concurrencia, ausencia de un único punto de control, seguridad, asincronía, apertura, transparencia, tolerancia a fallos, escalabilidad
      • Poner ejemplos de sistemas distribuidos
      • Entender la definición de sistema distribuido
    2. Entender la problemática del tiempo y la ordenación de eventos en un sistema distribuido y explicar e implementar los mecanismos de relojes lógicos para atacar esta problemática y los algoritmos para sincronizar relojes físicos en un sistema distribuido.
      Competencias relacionadas: CEE2.3, CEE2.1,
      Subcompetences
      • Entender la problemática del tiempo y la ordenación de eventos en un sistema distribuido
      • Explicar e implementar los mecanismos de relojes lógicos para atacar esta problemática: relación happened-before, relojes lógicos de Lamport (escalares, vectoriales)
      • Explicar e implementar los algoritmos para sincronizar relojes físicos en un sistema distribuido: Cristian (NTP), Berkeley
    3. Entender la problemática de obtener un estado global consistente en un sistema distribuido y explicar el mecanismo de snapshot distribuido para atacar esta problemática, además de definir predicados globales para la evaluación de propiedades en un sistema distribuido.
      Competencias relacionadas: CEE2.3, CEE2.1,
      Subcompetences
      • Entender la problemática de obtener un estado global consistente en un sistema distribuido
      • Definir predicados globales para la evaluación de propiedades en un sistema distribuido: propiedades de los predicados (estabilidad), ocurrencia de los predicados (possibly, definitely)
      • Explicar el mecanismo de snapshot distribuido de Chandy y Lamport para atacar esta problemática
    4. Describir, comparar e implementar los algoritmos para la coordinación de procesos en un sistema distribuido, incluyendo la coordinación necesaria para elección de líder, comunicación en grupo multicast, y consenso.
      Competencias relacionadas: CEE2.3, CEE2.1, CTR3,
      Subcompetences
      • Describir, comparar e implementar los algoritmos para la coordinación de procesos en un sistema distribuido para la comunicación en grupo multicast: multicast fiable básico, multicast fiable escalable, multicast ordenado (FIFO, causal, total), atomic multicast
      • Describir, comparar e implementar los algoritmos para la coordinación de procesos en un sistema distribuido para garantizar el consenso: problema de los dos ejércitos, algoritmo de Dolev & Strong, problema de los generales Byzantinos, Paxos
      • Describir, comparar e implementar los algoritmos para la coordinación de procesos en un sistema distribuido para la elección de líder: Bully, Chang & Roberts, Ring
    5. Comprender la problemática de la ejecución concurrente de transacciones y describir, comparar e implementar diferentes mecanismos de control de concurrencia.
      Competencias relacionadas: CEE2.3, CEE2.1, CTR6,
      Subcompetences
      • Describir, comparar e implementar diferentes mecanismos de control de concurrencia: two-phase locking (incluyendo detección y tratamiento de deadlock), optimistic concurrency control, timestamp ordering
      • Comprender la problemática de la ejecución concurrente de transacciones: lost update, inconsistent retrievals, equivalencia serie, recuperación de aborts (dirty read, premature write)
    6. Ampliar el concepto de transacción, el protocolo de commit y los mecanismos de control de concurrencia a un sistema distribuido.
      Competencias relacionadas: CEE2.3, CEE2.1,
      Subcompetences
      • Ampliar los mecanismos de control de concurrencia a un sistema distribuido: two-phase locking (incluyendo detección y tratamiento de deadlock distribuido), optimistic concurrency control, timestamp ordering
      • Ampliar el concepto de transacción a un sistema distribuido
      • Describir, comparar e implementar diferentes protocolos de commit distribuido: one-phase y two-phase
    7. Comprender la aplicación de la replicación en un sistema distribuido, además de la problemática que se introduce a nivel de consistencia, y describir los modelos de consistencia correspondientes y su implementación.
      Competencias relacionadas: CEE2.3, CEE2.1,
      Subcompetences
      • Describir implementaciones concretas de modelos de consistencia: protocolos basados ​​en primario (remote-write, local-write) y protocolos de escritura replicada (replicación activa, protocolos basados ​​en quórum)
      • Describir los modelos de consistencia fuerte centrados en los datos: estricta, linearizability, secuencial
      • Describir los modelos de consistencia relajada centrados en los datos: uso de variables de sincronización
      • Comprender la aplicación de la replicación en un sistema distribuido, además de la problemática que se introduce a nivel de consistencia
      • Describir los modelos de consistencia centrados en el cliente: eventual, monotonic-read, monotonic-write, read-your-writes, writes-follow-reads
    8. Comprender los problemas que puede causar el acceso concurrente de varios agentes (threads) a los recursos. Conocer las estrategias de diseño que aseguran una correcta coordinación de los agentes y evitan las inconveniencias del acceso concurrente
      Competencias relacionadas: CG1, CEE4.2,
      Subcompetences
      • Conocer el formalismo de los sistemas de transición para representar la semántica de un sistema concurrente. Saber usar herramientas de análisis para determiner las propiedades del sistema representado.
      • Comprender el beneficio de usar modelos para representar un sistema concurrente y poder analizar sus propiedades
      • Ser capaz de representar un sistema concurrente usando un modelo abstracto formal y de analizar sus propiedades
      • Conocer los conceptos característicos de un diseño concurrente: exclusión mutua, secciones críticas, interferencia, deadlocks y las instrucciones primitivas para el diseño de programas concurrentes.
    9. Adquirir destreza en el diseño de programas concurrentes en el paradigma de memoria compartida.
      Competencias relacionadas: CEE2.3, CEE4.2, CTR3,
      Subcompetences
      • Asimilar el concepto de thread y los fundamentos del diseño de programas concurrentes con threads. Conocer las construcciones básicas o primitivas disponibles en los lenguajes de programación modernos (como Java) para asegurar una coordinación correcta entre los diferentes threads.
      • Entender los problemas de interferencia y bloqueo (deadlock) de un sistema concurrente y saber diseñar sistemas concurrentes libres de estas inconveniencias.
      • Ser capaz de aplicar los recursos ofrecidos por los lenguajes de programación modernos para diseñar programas concurrentes: threads, semáforos, secciones críticas, monitores y condiciones de sincronización.
    10. Adquirir destreza en el diseño de programas concurrentes en el paradigma de paso de mensajes.
      Competencias relacionadas: CEE2.3, CEE2.1, CEE4.2, CTR3,
      Subcompetences
      • Reconocer y aplicar patrones de diseño concurrente que son frecuentes en la arquitectura de paso de mensajes: cliente/servidor, filter pipeline, supervisor/worker, announcer/listener
      • Comprender el paradigma de paso de mensajes que es característico de algunos lenguajes de programación concurrente (Erlang). Entender el concepto de proceso en Erlang. Ser capaz de diseñar programas de complejidad limitada en este lenguaje.
      • Saber trasladar algoritmos conocidos al paradigma de paso de mensajes, como por ejemplo el algoritmo de ordenación quicksort.
    11. Comprender y medir el paralelismo potencial disponible en una aplicación secuencial y el rendimiento logrado con su implementación paralela
      Competencias relacionadas: CG1, CEE4.2,
      Subcompetences
      • Comprender el rendimiento de una aplicación paralela y los factores generales que contribuyen a su degradación
      • Comprender el concepto de gráfico de tareas y cómo medir paralelismo potencial
      • Utilización de herramientas de instrumentación, visualización y análisis para entender el paralelismo y el rendimiento
    12. Decidir la estrategia de descomposición más adecuada para expresar el paralelismo en una aplicación
      Competencias relacionadas: CEE4.2, CTR3, CTR6, CG5,
      Subcompetences
      • Dada una descomposición de tareas, decidir el ordenamiento de las tareas y las restricciones de intercambio de datos que garantizan las dependencias
      • Dada la descomposición de datos, decidir los requerimientos de comunicación y el uso de operaciones punto a punto o colectivas para implementarlas
      • Uso de la descomposición de tareas y datos
    13. Especificar, utilizando el paradigma de programación apropiado, una versión paralela eficiente que corresponda a una determinada descomposición de tareas / datos
      Competencias relacionadas: CEE4.2, CTR3, CTR6, CG5,
      Subcompetences
      • Uso de la interfaz de paso de mensajes (MPI) para aplicaciones de computación / uso intensivo de datos en arquitecturas de memoria distribuida
      • Uso de CUDA para descargar datos de computación y transferencia para arquitecturas basadas en aceleradores

    Contenidos

    1. Sistemas de transición y algebra de procesos
      Procesos secuenciales y sistemas de transición. Construcciones prefix y choice. Concurrencia de procesos, concepto y construcción. Análisis de sistemas de transición. Implementaciones en Java y Erlang.
    2. Entender el paralelismo
      Introducción a las arquitecturas paralelas: arquitecturas de memoria compartida y distribuida y aceleradores. Gráfico de tareas: nodos y aristas. Métrica. Aceleración y eficiencia. Ley Amdahl.
    3. Conceptos de sistemas distribuidos
      Definición de sistema distribuido. Posibles aplicaciones de un sistema distribuido. Ejemplos de sistemas distribuidos. Desafíos para diseñar e implementar un sistema distribuido: heterogeneidad, seguridad, ausencia de visión global, concurrencia, ausencia de un único punto de control, asincronía, apertura , transparencia, tolerancia a fallos, escalabilidad.
    4. Propiedades de seguridad y vivacidad
      Descripción y ejemplos de propiedades de seguridad. Análisis propiedades de seguridad sobre sistemas de transición. Descripción de las propiedades de vivacidad y especialmente de las propiedades de progreso. Análisis de propiedades de progreso en sistemas de transición.
    5. Concurrencia, exclusion mutua y condiciones de sincronización. Deadlock.
      El problema de la interferencia destructiva. Locks y exclusión mutua. Semáforos, monitores y condiciones de sincronización. El problema del deadlock y su análisis sobre sistemas de transición. Estrategias de diseño para impedir deadlocks.
    6. Paso de mensajes. Arquitecturas
      Descripción del paradigma de paso de mensajes. La arquitectura cliente/servidor. Introducción a otras arquitecturas: Filter pipeline, supervisor/worker, announcer/listener. Paso de mensajes en Erlang. Diseños de arquitecturas en Erlang
    7. Predicción y análisis del rendimiento
      Uso de modelos y herramientas para entender el paralelismo y el rendimiento (Tareador, Extrae, Paraver y Dimemas).
    8. Programación de memoria distribuida usando MPI
      Visión general de la arquitectura del clúster. Creación, identificación y terminación de procesos. Operaciones punto a punto vs. operaciones colectivas. Comunicaciones síncronas vs asíncronas.
    9. Programación de dispositivos GPU para la aceleración computacional usando CUDA
      Descripción de la arquitectura de la GPU. Decomposiciones adecuadas para la aceleración de la GPU. Principios de programación de CUDA.
    10. Algoritmos distribuidos: Tiempo, estado global, coordinación y consenso
      Tiempo y la ordenación de eventos en un sistema distribuido. Relojes lógicos: relación happened-before, relojes lógicos de Lamport (escalares, vectoriales). Algoritmos para sincronizar relojes físicos en un sistema distribuido: Cristian (NTP), Berkeley. Estado global consistente en un sistema distribuido. Mecanismo de snapshot distribuido de Chandy y Lamport. Predicados globales para la evaluación de propiedades en un sistema distribuido: propiedades de los predicados (estabilidad), ocurrencia de los predicados (possibly, definitely). Coordinación de procesos en un sistema distribuido para la elección de líder: Bully, Ring. Coordinación de procesos en un sistema distribuido para la comunicación en grupo multicast: multicast fiable básico, multicast fiable escalable, multicast ordenado (FIFO, causal, total), atomic multicast. Coordinación de procesos en un sistema distribuido para garantizar el consenso: problema de los dos ejércitos, algoritmo de Dolev & Strong, problema de los generales Byzantinos, Paxos
    11. Datos compartidos distribuidos: Transacciones, consistencia y replicación
      Ejecución concurrente de transacciones: lost update, inconsistent retrievals, equivalencia serie, recuperación de aborts (dirty read, premature write). Mecanismos de control de concurrencia: two-phase locking (incluyendo detección y tratamiento de deadlock), optimistic concurrency control, timestamp ordering. Transacción distribuida. Protocolos de commit distribuido: one-phase y two-phase. Mecanismos de control de concurrencia en un sistema distribuido: two-phase locking (incluyendo detección y tratamiento de deadlock distribuido), optimistic concurrency control, timestamp ordering. Replicación y consistencia en un sistema distribuido. Modelos de consistencia fuerte centrados en los datos: estricta, linearizability, secuencial. Modelos de consistencia relajada centrados en los datos: uso de variables de sincronización. Modelos de consistencia centrados en el cliente: eventual, monotonic-read, monotonic-write, read-your-writes, writes-follow-reads. Implementaciones de modelos de consistencia: protocolos basados ​​en primario (remote-write, local-write) y protocolos de escritura replicada (replicación activa, protocolos basados ​​en quórum)

    Actividades

    Actividad Acto evaluativo


    Conceptos fundamentales de concurrencia, paralelismo y distribución

    Preparación de la clase con la ayuda del material de apoyo. Comprensión y asimilación de los contenidos del tema para su aplicación posterior
    Objetivos: 1 8 11
    Contenidos:
    Teoría
    6h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    12h

    Primer modulo elegido: Concurrencia o Paralelismo o Distribución

    Preparación de la clase con la ayuda del material de apoyo. Comprensión y asimilación de los contenidos asociados a los temas del modulo correspondiente para su aplicación posterior en las sesiones de laboratorio.

    Teoría
    10h
    Problemas
    0h
    Laboratorio
    10h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    30h

    Segundo modulo elegido: Concurrencia o Paralelismo o Distribución

    Preparación de la clase con la ayuda del material de apoyo. Comprensión y asimilación de los contenidos asociados a los temas del modulo correspondiente para su aplicación posterior en las sesiones de laboratorio.

    Teoría
    10h
    Problemas
    0h
    Laboratorio
    10h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    30h

    Módulo I: Concurrencia

    Preparación de la clase con la ayuda del material de apoyo. Comprensión y asimilación de los contenidos asociados a los temas del Módulo I (concurrencia) para su aplicación posterior en las sesiones de laboratorio.
    Objetivos: 8 9 10
    Contenidos:
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Módulo II: Paralelismo

    Preparación de la clase con la ayuda del material de apoyo. Comprensión y asimilación de los contenidos asociados a los temas del Módulo II (paralelismo) para su aplicación posterior en las sesiones de laboratorio.
    Objetivos: 11 12 13
    Contenidos:
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Módulo III: Distribución

    Preparación de la clase con la ayuda del material de apoyo. Comprensión y asimilación de los contenidos asociados a los temas del Módulo III (distribución) para su aplicación posterior en las sesiones de laboratorio.
    Objetivos: 1 2 3 4 5 6 7
    Contenidos:
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h



    Primer modulo elegido: Examen final

    Asimilación de los conceptos del curso y realización del examen
    Objetivos: 1 2 3 4 5 6 7 8 9 10 11 12 13
    Semana: 15 (Fuera de horario lectivo)
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Segundo modulo elegido: Examen final

    Asimilación de los conceptos del curso y realización del examen
    Objetivos: 1 2 3 4 5 6 7 8 9 10 11 12 13
    Semana: 15 (Fuera de horario lectivo)
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Metodología docente

    Durante el curso se realizarán dos tipos de actividades:

    a) Actividades centradas en la adquisición de conocimientos teóricos.
    b) Actividades centradas en la adquisición de conocimientos mediante experimentación con la implementación y evaluación empírica en el laboratorio de los mecanismos explicados a nivel teórico.

    Las actividades teóricas incluyen clases expositivas participativas donde se explican los contenidos básicos del curso. Las actividades prácticas incluyen seminarios de laboratorio donde los alumnos implementan los mecanismos descritos en las clases expositivas. Los seminarios requieren de una preparación previa mediante la lectura del enunciado y la documentación de apoyo, y una elaboración posterior de las conclusiones obtenidas en un informe.

    Método de evaluación

    Para cada modulo, habrá un examen (EF) y una nota de laboratorio (L). El examen será de problemas sobre la teoría explicada. La nota de laboratorio reflejará la calidad del trabajo realizado en las prácticas de laboratorio. La nota final del modulo será NF=0.6*EF+ 0.4*L.

    La nota final se calculará como la media aritmética de la nota de los dos modulos cursados por el estudiante: NF=0.5*M1+ 0.5*M2.

    Bibliografía

    Básico

    Complementario

    Capacidades previas

    Concurrencia: conocimientos de Java a nivel de clases y objetos.
    Paralelismo: conocimientos básicos sobre arquitecturas paralelas, incluyendo multiprocesadores con memoria compartida y distribuida.
    Distribución: conocimientos de la estructura interna y el funcionamiento de un sistema operativo y de una red de computadores.