Curricula CS-UNI

5.45. CS3P1. Computación Paralela y Distribuída (Obligatorio)

Semestre: 8vo Sem. Créditos: 4
Horas del curso: Teoría: 2 horas; Práctica: 2 horas; Laboratorio: 2 horas;
Prerrequisitos:
- CS212. Análisis y Diseño de Algoritmos (5to Sem)
- CS231. Redes y Comunicación (6to Sem)

Figura 5.45: Mapa de Conexión. CS3P1 Computación Paralela y Distribuída

5.45.1. Justificación

Con el fin del escalado de frecuencia en procesadores de un solo núcleo, la computación paralela y distribuida se ha vuelto esencial para el desarrollo de software de alto rendimiento. Este curso introduce a los estudiantes a los modelos de programación, patrones de comunicación y mecanismos de coordinación necesarios para explotar sistemas de múltiples núcleos y clústeres distribuidos. Los estudiantes aprenderán a diseñar algoritmos escalables y evaluar su rendimiento bajo diferentes restricciones computacionales.

5.45.2. Objetivos Generales

1.: Diseñar e implementar programas paralelos utilizando memoria compartida y distribuida.
2.: Dominar protocolos de comunicación y sincronización en sistemas distribuidos.
3.: Evaluar el rendimiento y la escalabilidad mediante métricas formales.
4.: Aplicar algoritmos paralelos para resolver problemas computacionales complejos.

5.45.3. Contribución a los resultados (Outcomes)

: AG-C11) Uso de Herramientas: Aplica herramientas modernas de computación en la resolución de problemas. (Usage)
: AG-C09) Diseño y Desarrollo de Soluciones: Diseña, implementa y evalúa soluciones para problemas complejos de computación. (Usage)

5.45.4. Contenido

5.45.4.1. Programas: Paralelismo Declarativo (4 horas) [Habilidades AG-C09,AG-C11]

Referencias Bibliográficas: [Pacheco and Malensek, 2021]

Temas

1.

Paralelismo

a): Paralelismo declarativo: Determinar qué acciones pueden, o no deben, realizarse en paralelo, a nivel de instrucciones, funciones, clausuras, acciones compuestas, sesiones, tareas y servicios es la idea principal que subyace a los algoritmos PDC; no hacerlo es la principal fuente de errores. Ver también: Computación Paralela y Distribuida (PDC) -Algorithms
b): Definir orden: por ejemplo, usando relaciones de "sucede antesº grafos acíclicos dirigidos serie/paralelo que representan programas.
c): Independencia: determinar cuándo el orden no importa, en términos de conmutatividad, dependencias, precondiciones.
d): Garantizar el orden entre acciones que de otro modo serían paralelas cuando sea necesario, incluyendo bloqueos, publicación segura; e imponer comunicación - enviar un mensaje sucede antes de recibirlo; y relajarlo cuando no sea necesario.

Aprendizaje esperado (Learning Outcomes)

1.: Mostrar gráficamente (como un Grafo Acíclico Dirigido - Directed Acyclic Graph (DAG)) cómo paralelizar una expresión numérica compuesta; por ejemplo, a = (b + c) ∗ (d + e) [Diseñar]
2.: Explicar por qué los conceptos de consistencia y tolerancia a fallos no surgen en programas puramente secuenciales [Explicar]

5.45.4.2. Programas: Inicio de Actividades (3 horas) [Habilidades AG-C09,AG-C11]

Referencias Bibliográficas: [Pacheco and Malensek, 2021]

Temas

1.

Iniciar actividades

a): Las opciones que permiten que las acciones se realicen (eventualmente) en lugares van desde el cableado directo hasta scripts de configuración; también establecer comunicación y gestión de recursos; estos se expresan de manera diferente en los lenguajes y contextos, generalmente confiando en el aprovisionamiento y gestión automatizados por las plataformas. Ver también: Fundamentos de Sistemas (SF) -Resource
b): Procedimental: Permitir que múltiples acciones comiencen en un punto de programa dado; por ejemplo, iniciar nuevos hilos, posiblemente delimitando su alcance u organizándolos en grupos jerárquicos.
c): Reactiva: Habilitar al ocurrir un evento instalando un manejador de eventos, con menos control de cuándo comienzan o terminan las acciones, y puede aplicarse incluso en monoprocesadores.
d): Dependiente: Habilitar al completarse otras; por ejemplo, secuenciando conjuntos de acciones paralelas. Ver también: Computación Paralela y Distribuida (PDC) -Coordination.
e): Granularidad: El costo de ejecución de los cuerpos de las acciones debe superar la sobrecarga de organizarlos.

Aprendizaje esperado (Learning Outcomes)

1.: Escribir un servicio que cree un hilo (u otra forma de activación procedimental) para devolver una página web solicitada a cada nuevo cliente [Escribir]

5.45.4.3. Programas: Propiedades de Ejecución (3 horas) [Habilidades AG-C09,AG-C11]

Referencias Bibliográficas: [van Steen and Tanenbaum, 2023]

Temas

1.

Propiedades de Ejecución

a): Ejecución no determinista de acciones sin orden.
b): Consistencia: Garantizar el acuerdo entre partes sobre valores y predicados cuando sea necesario para evitar carreras, mantener seguridad y atomicidad, o llegar a consenso.
c): Tolerancia a fallos: Manejar fallos en las partes o la comunicación, incluyendo (Bizantino) mal comportamiento debido a partes y protocolos no confiables, cuando sea necesario para mantener el progreso o la disponibilidad. Ver también: Fundamentos de Sistemas (SF) -Reliability.
d): Los compromisos son un foco de evaluación. Ver también: Computación Paralela y Distribuida (PDC) -Evaluation.

Aprendizaje esperado (Learning Outcomes)

1.: Escribir una función que cuente eventos, como recepciones de paquetes de red, de manera eficiente [Escribir]

5.45.4.4. Programas: Distribución (2 horas) [Habilidades AG-C09,AG-C11]

Referencias Bibliográficas: [van Steen and Tanenbaum, 2023]

Temas

1.

Distribución

a): Definir lugares, como dispositivos que ejecutan acciones, incluyendo componentes de hardware, hosts remotos; también pueden incluir dispositivos, hosts y usuarios externos no controlados. Ver también: Arquitectura y Organización (AR) -InterfacingCommunication
b): Un dispositivo puede dividir el tiempo o emular múltiples acciones paralelas mediante menos procesadores mediante planificación y virtualización. Ver también: Sistemas Operativos (OS) -Scheduling
c): Nombrar o identificar lugares (por ejemplo, IDs de dispositivo) y acciones como partes (por ejemplo, IDs de hilo).
d): Las actividades a través de lugares pueden comunicarse a través de medios. Ver también: Computación Paralela y Distribuida (PDC) -Communication

Aprendizaje esperado (Learning Outcomes)

1.: Escribir un programa de filtro/mapeo/reducción en múltiples estilos [Escribir]

5.45.4.5. Programas: Mapeos de Implementación (2 horas) [Habilidades AG-C09,AG-C11]

Referencias Bibliográficas: [Pacheco and Malensek, 2021, mei W. Hwu et al., 2022]

Temas

1.

Una o más de las siguientes asignaciones y mecanismos a través de sistemas en capas:

a): Paralelismo a nivel de instrucción y datos en la CPU. Ver también: Arquitectura y Organización (AR) -FunctionalOrganization.
b): SIMD y paralelismo de datos heterogéneo. Ver también: Arquitectura y Organización (AR) -HeterogeneousArchitectures.
c): Concurrencia planificada en multinúcleo, tareas, actores. Ver también: Sistemas Operativos (OS) -Scheduling.
d): Clústeres, nubes; aprovisionamiento elástico. Ver también: Desarrollo de Plataformas Especializadas (SPD) -CommonAspectsSharedConcerns.
e): Sistemas distribuidos en red. Ver también: Redes y Comunicaciones (NC) -Applications.
f ): Tecnologías emergentes como la computación cuántica y la computación molecular.

Aprendizaje esperado (Learning Outcomes)

1.: Explicar las compensaciones entre diferentes estrategias de mapeo en términos de rendimiento, costo y complejidad de implementación [Explicar]

5.45.4.6. Programación GPU (4 horas) [Habilidades AG-C09]

Referencias Bibliográficas: [Kirk and mei W. Hwu, 2016, Corporation, 2024]

Temas

1.

Computación de Propósito General en GPU (GPGPU)

a): Arquitectura de GPU: multiprocesadores de flujo (SMs), núcleos CUDA y modelo de ejecución por warp.
b): Modelo de ejecución SIMT (Single Instruction, Multiple Threads) y sus diferencias respecto al SIMD de CPU.
c): Interacción host-dispositivo: transferencia de datos entre memoria de CPU (host) y GPU (dispositivo) vía PCIe.
d): Casos de uso: computación científica, aprendizaje automático, procesamiento de imágenes y simulación a gran escala.

2.

Modelo de Programación CUDA

a): Jerarquía de ejecución CUDA: grids, bloques de hilos e hilos individuales; mapeo al hardware GPU.
b): Definición y lanzamiento de kernels; parámetros de configuración (dimensiones de grid y bloque).
c): Indexación de hilos: threadIdx, blockIdx, blockDim, gridDim; cálculo de índices globales en 1D, 2D y 3D.
d): Divergencia de warp: implicaciones de las bifurcaciones dentro de un warp en el rendimiento.
e): Primitiva de sincronización intra-bloque: __syncthreads.

3.

Jerarquía de Memoria CUDA

a): Memoria global: grande, alta latencia, accesible por todos los hilos; patrones de acceso coalescente para el rendimiento.
b): Memoria compartida: memoria en chip de baja latencia compartida dentro de un bloque de hilos; conflictos de banco.
c): Registros y memoria local: almacenamiento privado por hilo.
d): Memoria constante y de textura: cachés de solo lectura optimizadas para patrones de acceso específicos.
e): Memoria unificada: modelo de programación simplificado con migración automática de datos entre host y dispositivo.

Aprendizaje esperado (Learning Outcomes)

1.: Escribir un kernel CUDA que realice una operación data-paralela (p. ej., suma de vectores, multiplicación de matrices) y configurar correctamente las dimensiones de grid y bloque [Escribir]
2.: Analizar el impacto de los patrones de acceso a memoria global (acceso coalescente vs. acceso entrelazado) y el uso de memoria compartida en el rendimiento de un kernel GPU [Analizar]
3.: Diseñar un algoritmo paralelo usando el modelo de programación CUDA, incluyendo la jerarquía de hilos, estrategia de asignación de memoria y transferencias de datos entre host y dispositivo [Diseñar]

5.45.4.7. Comunicación (8 horas) [Habilidades AG-C09,AG-C11]

Referencias Bibliográficas: [van Steen and Tanenbaum, 2023, Kleppmann, 2017b]

Temas

1.

Medios

a): Variedades: canales (paso de mensajes o E/S), memoria compartida, heterogéneos, almacenes de datos.
b): Dependencia de la disponibilidad y naturaleza del hardware subyacente, conectividad y protocolos; soporte del lenguaje, emulación. Ver también: Arquitectura y Organización (AR) -InterfacingCommunication.

2.

Canales

a): Medios de comunicación de parte a parte explícitos (generalmente nombrados).
b): APIs: Sockets, constructos arquitectónicos, basados en lenguaje y de kits de herramientas, como Message Passing Interface (MPI), y constructos en capas como Llamada a Procedimiento Remoto (RPC). Ver también: Redes y Comunicaciones (NC) -Fundamentals.
c): APIs de canales de E/S.

3.

Memoria

a): Arquitecturas de memoria compartida en las que las partes se comunican directamente solo con la memoria en direcciones dadas, con extensiones a memoria heterogénea que admite múltiples almacenes de memoria con transferencia de datos explícita entre ellos; por ejemplo, memoria local y compartida de GPU, Acceso Directo a Memoria (DMA).
b): Jerarquías de memoria: Múltiples capas de dominios, alcances y cachés compartidos; localidad: latencia, falso uso compartido.
c): Propiedades de consistencia: Límites de atomicidad a nivel de bits, coherencia, orden local.

4.

Almacenes de Datos

a): Estructuras de datos mantenidas cooperativamente que implementan mapas y TADs relacionados.
b): Variedades: Propiedad exclusiva, compartida, fragmentada, replicada, inmutable, versionada.

Aprendizaje esperado (Learning Outcomes)

1.: Explicar las similitudes y diferencias entre: (1) La parte A envía un mensaje en el canal X con contenido 1 recibido por la parte B (2) A establece la variable compartida X a 1, leída por B (3) A establece "X=1en un mapa compartido distribuido al que accede B [Explicar]
2.: Escribir un programa que distribuya diferentes segmentos de un conjunto de datos a múltiples trabajadores y recoja los resultados (por ejemplo, sumar segmentos de un arreglo) [Escribir]
3.: Escribir un programa paralelo que solicite datos de múltiples sitios y los resuma usando alguna forma de reducción [Escribir]
4.: Comparar el rendimiento de versiones con y sin búfer de un programa productor-consumidor [Comparar]

5.45.4.8. Comunicación: Propiedades y Extensiones (3 horas) [Habilidades AG-C09,AG-C11]

Referencias Bibliográficas: [van Steen and Tanenbaum, 2023, Kleppmann, 2017b]

Temas

1.

Una o más de las siguientes propiedades y extensiones:

a): Topologías: Unicast, Multicast, Buzones, Conmutadores; Enrutamiento a través de redes de interconexión de hardware y software.
b): Propiedades de concurrencia de medios: Orden, consistencia, idempotencia, superposición de comunicación con computación.
c): Rendimiento del medio: Latencia, ancho de banda (rendimiento), contención (congestión), capacidad de respuesta (vivacidad), confiabilidad (tasas de error y pérdida), progreso basado en protocolo (acks, tiempos de espera, mediación).
d): Propiedades de seguridad del medio: integridad, privacidad, autenticación, autorización. Ver también: Seguridad (SEC) -Coding.
e): Formatos de datos: Serialización, validación, cifrado, compresión.
f ): Políticas de canal: Puntos finales, sesiones, almacenamiento en búfer, respuesta a saturación (esperar vs. descartar), control de velocidad.
g): Multiplexación y demultiplexación de muchos dispositivos o partes de E/S relativamente lentos; técnicas basadas en finalización y basadas en planificador; APIs async-await, select y polling.
h): Formalización y análisis de comunicación por canales; por ejemplo, CSP.
i): Aplicaciones de la teoría de colas para modelar y predecir el rendimiento.

Aprendizaje esperado (Learning Outcomes)

1.: Determinar si un esquema de comunicación dado proporciona propiedades de seguridad suficientes para un uso dado [Determinar]
2.: Dar un ejemplo de un escenario en el que los envíos de mensajes bloqueantes pueden causar un punto muerto (deadlock) [Crear]
3.: Describir al menos una técnica de diseño para evitar fallos de vivacidad en programas que usan múltiples bloqueos [Describir]

5.45.4.9. Memoria y Consistencia (3 horas) [Habilidades AG-C09,AG-C11]

Referencias Bibliográficas: [van Steen and Tanenbaum, 2023, Kleppmann, 2017b]

Temas

1.

Modelos de memoria, consistencia de datos y tolerancia a fallos:

a): Modelos de memoria: consistencia secuencial y de liberación/adquisición.
b): Gestión de memoria; incluyendo la reclamación de datos compartidos; conteo de referencias y alternativas.
c): Colocación y transferencia masiva de datos; reducción del tráfico de mensajes y mejora de la localidad; superposición de transferencia de datos y computación; impacto del diseño de datos como array de estructuras vs. estructura de arrays.
d): Emular memoria compartida: memoria compartida distribuida, Acceso Directo a Memoria Remota (RDMA).
e): Consistencia de almacenes de datos: Atomicidad, linealizabilidad, transaccionalidad, coherencia, orden causal, resolución de conflictos, consistencia eventual, cadenas de bloques.
f ): Fallos, particionamiento y fallos parciales; votación; protocolos como Paxos y Raft.
g): Compromisos de diseño entre consistencia, disponibilidad, tolerancia a partición (fallos); imposibilidad de cumplir con todos a la vez.
h): Seguridad y confianza: Fallos bizantinos, prueba de trabajo y alternativas.

Aprendizaje esperado (Learning Outcomes)

1.: Dar un ejemplo de un orden de accesos entre actividades concurrentes (por ejemplo, un programa con una carrera de datos) que no sea secuencialmente consistente [Crear]
2.: Escribir un programa que ilustre el reordenamiento de acceso a memoria o de mensajes [Escribir]
3.: Describir los méritos relativos del control de concurrencia optimista versus conservador bajo diferentes tasas de contención entre actualizaciones [Describir]
4.: Dar un ejemplo de un escenario en el que un intento de actualización optimista podría nunca completarse [Crear]
5.: Modificar un sistema concurrente para usar un almacén de datos más escalable, confiable o disponible [Crear]
6.: Usando una plataforma existente que admita almacenes de datos replicados, escribir un programa que mantenga un mapeo clave-valor incluso cuando uno o más hosts fallen [Escribir]

5.45.4.10. Coordinación (7 horas) [Habilidades AG-C09,AG-C11]

Referencias Bibliográficas: [Herlihy et al., 2020, van Steen and Tanenbaum, 2023]

Temas

1.

Dependencias

a): La iniciación o progreso de una actividad puede depender de otras actividades, para evitar condiciones de carrera, garantizar la terminación o cumplir otros requisitos.
b): Garantizar el progreso evitando ciclos de dependencia, usando condiciones monótonas, eliminando dependencias no esenciales.

2.

Constructos de control y patrones de diseño:

a): Basados en finalización: Barreras, reuniones (joins), incluido el control de terminación.
b): Habilitados por datos: Colas, diseños productor-consumidor.
c): Basados en condición: Polling, reintentos, retrocesos, ayuda, suspensión, señalización, tiempos de espera.
d): Reactivos: Habilitar y activar continuaciones.

Aprendizaje esperado (Learning Outcomes)

1.: Mostrar cómo garantizar que un programa termine correctamente cuando todas las tareas concurrentes de un conjunto hayan finalizado [Diseñar]
2.: Escribir una función que cuente eventos, como entradas de sensores o recepciones de paquetes de red, de manera eficiente [Escribir]
3.: Escribir un programa de filtro/mapeo/reducción en múltiples estilos [Escribir]
4.: Escribir un programa en el que la terminación de un conjunto de acciones paralelas sea seguida por otra [Escribir]
5.: Escribir un servicio que cree un hilo (u otra forma de activación procedimental) para devolver una página web solicitada a cada nuevo cliente [Escribir]

5.45.4.11. Coordinación: Sincronización y Atomicidad (3 horas) [Habilidades AG-C09,AG-C11]

Referencias Bibliográficas: [Herlihy et al., 2020]

Temas

1.

Atomicidad

a): Instrucciones atómicas, ordenamientos de acceso local impuestos.
b): Bloqueos y exclusión mutua; granularidad de bloqueo.
c): Uso de bloqueos en un lenguaje específico; mantener la vivacidad sin introducir carreras.
d): Evitar punto muerto (deadlock): Ordenamiento, mayor granularidad, reintentos aleatorios; retrocesos, encapsulación mediante administradores de bloqueos.
e): Errores comunes: No bloquear o desbloquear cuando es necesario, mantener bloqueos mientras se invocan operaciones desconocidas.
f ): Evitar bloqueos: replicación, solo lectura, propiedad, y construcciones no bloqueantes.

Aprendizaje esperado (Learning Outcomes)

1.: Mostrar cómo evitar o reparar un error de carrera en un programa dado [Analizar]

5.45.4.12. Coordinación: Propiedades Avanzadas (4 horas) [Habilidades AG-C09,AG-C11]

Referencias Bibliográficas: [Herlihy et al., 2020]

Temas

1.

Una o más de las siguientes propiedades y extensiones:

a): Propiedades de progreso incluyendo libre de bloqueo (lock-free), libre de espera (wait-free), equidad (fairness), planificación por prioridad, interacciones con consistencia, confiabilidad.
b): Rendimiento con respecto a contención, granularidad, convoy, escalabilidad.
c): Estructuras de datos y algoritmos no bloqueantes.
d): Propiedad y control de recursos.
e): Variantes y alternativas de bloqueos: bloqueos de secuencia, bloqueos de lectura-escritura; Actualizar-Copiando-Lectura (RCU), reentrada; tickets; control del ciclo activo (spinning) versus bloqueo.
f ): Control basado en transacciones: Optimista y conservador.
g): Bloqueo distribuido: confiabilidad.
h): Alternativas a barreras: Relojes; contadores, relojes virtuales; flujo de datos y continuaciones; futuros y RPC; basadas en consenso, recolección de resultados con reductores y colectores.
i): Especulación, selección, cancelación; consecuencias en observabilidad y seguridad.
j): Control de recursos usando semáforos y variables de condición.
k): Flujo de control: Planificación de computaciones, bucles serie-paralelo con líderes (posiblemente elegidos), tuberías y flujos, paralelismo anidado.
l): Excepciones y fallos. Manejadores, detección, tiempos de espera, tolerancia a fallos, votación.

Aprendizaje esperado (Learning Outcomes)

1.: Escribir un programa que busque especulativamente una solución mediante múltiples actividades, terminando las demás cuando se encuentre una [Escribir]
2.: Escribir un programa en el que una excepción numérica (como división por cero) en una actividad cause la terminación de las demás [Escribir]
3.: Escribir un programa para que múltiples partes acuerden la hora actual del día; discutir sus limitaciones en comparación con protocolos como el protocolo de transferencia de red (NTP) [Escribir]

5.45.4.13. Evaluación (7 horas) [Habilidades AG-C09,AG-C11]

Referencias Bibliográficas: [Sterling et al., 2024, Pacheco and Malensek, 2021]

Temas

1.: Requisitos de seguridad (safety) y vivacidad (liveness) en términos de constructos de lógica temporal para expresar "siempre 2 e ventualmente"Ver también: Fundamentos de los Lenguajes de Programación (FPL) -ParallelDistributedComputing.
2.: Identificar, probar y reparar violaciones, incluyendo formas comunes de errores como no garantizar el orden necesario (errores de carrera), atomicidad (incluyendo errores de "verificar luego actuar") y terminación (bloqueo activo).
3.: Métricas de requisitos de rendimiento para rendimiento (throughput), capacidad de respuesta, latencia, disponibilidad, consumo de energía, escalabilidad, uso de recursos, costos de comunicación, espera y control de velocidad, equidad; acuerdos de nivel de servicio. Ver también: Fundamentos de Sistemas (SF) -Performance.
4.: Impacto en el rendimiento de las opciones de diseño e implementación, incluyendo granularidad, sobrecarga, costos de consenso y consumo de energía. Ver también: Sociedad, ética y la Profesión (SEP) -Sustainability.
5.: Estimar limitaciones de escalabilidad, por ejemplo usando la Ley de Amdahl o la Ley de Escalabilidad Universal. Ver también: Fundamentos de Sistemas (SF) -Evaluation.

Aprendizaje esperado (Learning Outcomes)

1.: Revisar una especificación para habilitar el paralelismo y la distribución sin violar otras propiedades o características esenciales [Rediseñar]
2.: Explicar cómo las nociones concurrentes de seguridad (safety) y vivacidad (liveness) extienden sus contrapartes secuenciales [Explicar]
3.: Especificar un conjunto de invariantes que deben mantenerse en cada paso de cómputo de paralelismo masivo [Analizar]
4.: Escribir un programa de prueba que pueda revelar un error de carrera de datos; por ejemplo, perder una actualización cuando dos actividades intentan incrementar una variable [Escribir]
5.: En un contexto dado, explicar hasta qué punto se esperaría que introducir paralelismo en un programa por lo demás secuencial mejoraría el rendimiento (throughput) y/o reduciría la latencia, y cómo podría afectar la eficiencia energética [Explicar]
6.: Mostrar cómo cambian la escalabilidad y la eficiencia para problemas de muestra con y sin el supuesto de que el tamaño del problema cambia con el número de procesadores; además, explicar si y cómo cambiaría la escalabilidad bajo relajaciones de dependencias secuenciales [Diseñar]

5.45.4.14. Evaluación: Métodos Formales (3 horas) [Habilidades AG-C09,AG-C11]

Referencias Bibliográficas: [Sterling et al., 2024, Pacheco and Malensek, 2021]

Temas

1.

Métodos formales de verificación y análisis:

a): Extensiones a requisitos formales secuenciales como la linealizabilidad.
b): Especificaciones de protocolo, sesión y transacciones.
c): Uso de herramientas como Lenguaje Unificado de Modelado (UML), Lógica Temporal de Acciones (TLA), lógicas de programa.
d): Análisis de seguridad: seguridad y vivacidad en presencia de comportamientos hostiles o con errores de otras partes; propiedades requeridas de mecanismos de comunicación (por ejemplo, ausencia de fugas entre capas), filtrado de entrada, limitación de velocidad. Ver también: Seguridad (SEC) -Foundations.
e): Análisis estático aplicado a corrección, rendimiento (throughput), latencia, recursos, energía. Ver también: Sociedad, ética y la Profesión (SEP) -Sustainability.
f ): Análisis del modelo de Grafo Acíclico Dirigido (DAG) de eficiencia algorítmica (trabajo, span, caminos críticos).

Aprendizaje esperado (Learning Outcomes)

1.: Especificar y medir el comportamiento cuando un servicio es solicitado por un número inesperadamente grande de clientes [Analizar]
2.: Identificar y reparar un problema de rendimiento debido a cuellos de botella secuenciales [Analizar]
3.: Comparar empíricamente el rendimiento (throughput) de dos implementaciones de un diseño común (quizás usando un marco de pruebas existente) [Comparar]

5.45.4.15. Evaluación: Pruebas y Medición (2 horas) [Habilidades AG-C09,AG-C11]

Referencias Bibliográficas: [Sterling et al., 2024, Pacheco and Malensek, 2021]

Temas

1.

Herramientas de prueba y técnicas de medición:

a): Pruebas y depuración; herramientas como detectores de carreras, fuzzers, verificadores de dependencia de bloqueos, pruebas de unidad/esfuerzo/tortura, visualizaciones, integración continua (CI), despliegue continuo (CD), y generadores de pruebas.
b): Medir y comparar rendimiento (throughput), sobrecarga, espera, contención, comunicación, movimiento de datos, localidad, uso de recursos, comportamiento en presencia de números excesivos de eventos, clientes o hilos. Ver también: Fundamentos de Sistemas (SF) -Evaluation.
c): Análisis específicos del dominio de aplicación y técnicas de evaluación.

Aprendizaje esperado (Learning Outcomes)

1.: Identificar y reparar un problema de rendimiento debido a latencia de comunicación o datos [Analizar]
2.: Identificar y reparar un problema de rendimiento debido a sobrecarga en la gestión de recursos [Analizar]
3.: Identificar y reparar un problema de confiabilidad o disponibilidad [Analizar]

5.45.4.16. Algoritmos (4 horas) [Habilidades AG-C09,AG-C11]

Referencias Bibliográficas: [Pacheco and Malensek, 2021, Herlihy et al., 2020]

Temas

1.

Expresar e implementar algoritmos en lenguajes y marcos de trabajo dados, para iniciar actividades (por ejemplo hilos), usar constructos de memoria compartida, y APIs de canales, sockets y/o llamada a procedimiento remoto (RPC). Ver también: Fundamentos de los Lenguajes de Programación (FPL) -ParallelDistributedComputing.

a): Ejemplos de datos paralelos incluyendo mapeo/reducción.
b): Uso de APIs de canal, socket y/o RPC en un lenguaje dado, con control del programa para enviar (generalmente procedimental) vs recibir (generalmente reactivo o basado en RPC).
c): Uso de bloqueos, barreras y/o sincronizadores para mantener la vivacidad sin introducir carreras.

Aprendizaje esperado (Learning Outcomes)

1.: Implementar un componente paralelo/distribuido basado en un algoritmo conocido [Implementar]
2.: Escribir un programa de datos paralelos que, por ejemplo, calcule el promedio de un arreglo de números [Escribir]
3.: Escribir un programa productor-consumidor en el que un componente genere números y otro calcule su promedio. Medir las aceleraciones cuando los números son escalares pequeños versus valores de multiprecisión grandes [Escribir]

5.45.4.17. Algoritmos: Dominios de Aplicación (4 horas) [Habilidades AG-C09,AG-C11]

Referencias Bibliográficas: [Pacheco and Malensek, 2021, Herlihy et al., 2020]

Temas

1.

Panorama de dominios de aplicación comunes en multinúcleo, reactivo, datos paralelos, clúster, nube, sistemas distribuidos abiertos y marcos de trabajo (con referencia a la siguiente tabla).

a): Multinúcleo: Agentes de ejecución típicos: Hilos. Mecanismos de comunicación típicos: Memoria compartida, Atómicos, bloqueos. Dominios algorítmicos típicos: Gestión de recursos, procesamiento de datos. Objetivos de ingeniería típicos: Rendimiento (throughput), latencia, energía.
b): Reactivo: Agentes de ejecución típicos: Manejadores, hilos. Mecanismos de comunicación típicos: Canales de E/S. Dominios algorítmicos típicos: Servicios, tiempo real. Objetivos de ingeniería típicos: Latencia.
c): Datos paralelos: Agentes de ejecución típicos: GPU, SIMD, aceleradores, híbridos. Mecanismos de comunicación típicos: Memoria heterogénea. Dominios algorítmicos típicos: álgebra lineal, gráficos, análisis de datos. Objetivos de ingeniería típicos: Rendimiento (throughput), energía.
d): Clúster: Agentes de ejecución típicos: Hosts gestionados. Mecanismos de comunicación típicos: Sockets, canales. Dominios algorítmicos típicos: Simulación, análisis de datos. Objetivos de ingeniería típicos: Rendimiento (throughput).
e): Nube: Agentes de ejecución típicos: Hosts aprovisionados. Mecanismos de comunicación típicos: APIs de servicio. Dominios algorítmicos típicos: Aplicaciones web. Objetivos de ingeniería típicos: Escalabilidad.
f ): Distribuido abierto: Agentes de ejecución típicos: Hosts autónomos. Mecanismos de comunicación típicos: Sockets, Almacenes de datos. Dominios algorítmicos típicos: Almacenes de datos y servicios tolerantes a fallos. Objetivos de ingeniería típicos: Confiabilidad.

Aprendizaje esperado (Learning Outcomes)

1.: Extender un programa secuencial dirigido por eventos estableciendo una nueva actividad en un manejador de eventos (por ejemplo, un nuevo hilo en un manejador de acciones de GUI) [Diseñar]
2.: Mejorar el rendimiento de un componente secuencial introduciendo paralelismo y/o distribución [Crear]
3.: Elegir entre diferentes diseños paralelos/distribuidos para componentes de un sistema dado [Evaluar (valorar)]

5.45.4.18. Algoritmos: Dominios Algorítmicos (4 horas) [Habilidades AG-C09,AG-C11]

Referencias Bibliográficas: [Pacheco and Malensek, 2021, Herlihy et al., 2020]

Temas

1.

Uno o más de los siguientes dominios algorítmicos. Ver también: Fundamentos Algorítmicos (AL) -AlgorithmicStrategies:

a): álgebra lineal: Operaciones con vectores y matrices, precisión/estabilidad numérica, aplicaciones en análisis de datos y aprendizaje automático.
b): Procesamiento de datos: ordenación, búsqueda y recuperación, estructuras de datos concurrentes.
c): Grafos, búsqueda y combinatoria: Marcado, paralelización de aristas, acotamiento, especulación, análisis basado en redes.
d): Modelado y simulación: ecuaciones diferenciales; aleatorización, problemas de N-cuerpos, algoritmos genéticos.
e): Lógica computacional: satisfactibilidad (SAT), programación lógica concurrente.
f ): Gráficos y geometría computacional: Transformaciones, renderizado, trazado de rayos.
g): Gestión de recursos: Asignar, colocar, reciclar y planificar procesadores, memoria, canales y hosts; recursos exclusivos vs compartidos; algoritmos estáticos, dinámicos y elásticos; Restricciones de tiempo real; Lotes, priorización, partición; descentralización mediante robo de trabajo y técnicas relacionadas.
h): Servicios: Implementar APIs web, moneda electrónica, sistemas de transacción, juegos multijugador.

Aprendizaje esperado (Learning Outcomes)

1.: Diseñar, implementar, analizar y evaluar un componente o aplicación para X que opere en un contexto dado, donde X esté en uno de los dominios listados, por ejemplo, un algoritmo genético para el diseño de una planta de fábrica [Diseñar]
2.: Criticar el diseño e implementación de un componente o aplicación existente, o uno desarrollado por compañeros de clase [Críticar (análisis crítico)]
3.: Comparar el rendimiento y la eficiencia energética de múltiples implementaciones de un diseño similar, por ejemplo, multinúcleo versus clúster versus GPU [Comparar]

5.45.5. Referencias Bibliográficas

: [Pacheco and Malensek, 2021]
: [van Steen and Tanenbaum, 2023]
: [mei W. Hwu et al., 2022]
: [Kirk and mei W. Hwu, 2016]
: [Corporation, 2024]
: [Kleppmann, 2017b]
: [Herlihy et al., 2020]
: [Sterling et al., 2024]