CI-0117 Programación Paralela y Concurrente: 2021b

Presentación del curso y carta al estudiante

Proceso de resolución de problemas

Paradigmas de programación

Paradigmas de programación (cont.)

Serial vs concurrente vs paralelo

Concurrencia basada en eventos

Concurrencia multihilo

Distribución simétrica. Clústers

Distribución asimétrica. Mallas. Comparación con simétrica.

Concurrencia heterogénea. Aceleración por hardware

Incremento del desempeño (paralelismo de datos). Separación de asuntos (concurrencia de tareas)

Crear repositorio personal. IDE. Plugin para pseudocódigo

Ejemplo Hello: Diseño en pseudocódigo

Anuncio: Tarea01

Notación de pseudocódigo (ocho tipos de instrucciones)

Creación de threads en pseudocódigo

Ptheads = POSIX threads

Convertir pseudocódigo en comentarios usando expresiones regulares

Implementación del hola Pthread. pthread_create(). Error estándar

Compilar el código. Compilador, preprocesador, enlazador

Tool1: El compilador. Habilitar warnings

Tool2: Linter (cpplint). Análisis estático de código.

Tool3: Memcheck de Valgrind: errores de memoria (fugas, accesos inválidos…​)

Makefiles

Tool4: Helgrind de Valgrind: errores de concurrencia (condiciones de carrera…​)

Tool5: Address Sanitizer (ASan) de Google para fugas y accesos inválidos

Tool6: Memory Sanitizer (MSan) de Google para memoria no inicializada

Tool7: Thread Sanitizer (TSan) de Google para errores de concurrencia

Tool8: Undefined Behavior Sanitizer (UBSan) de Google para comportamientos inesperados

Corregir el thread leak. pthread_join()

Indeterminismo. sleep()

Rastreo de memoria. Cargado del proceso. Segmento de código. Segmento de datos

Creación del hilo principal. El ambiente de ejecución del lenguaje (crt0)

Invocación de main(). Stack frame

Crear un nuevo hilo. Start routine. Stack pointer

Estado ready y estado running de un hilo de ejecución

Colas de espera. Reanudar la ejecución

Estado terminated. pthread_join(). Diagrama de tiempo

Definición de hilo de ejecución. Metáfora de hilo

Actividad hello_w. Copiar hello/ a hello_w/. Archivo .gitignore.

Variables y funciones en Makefile

Solución en pseudocódigo de hello_w. create_thread(func, params)

Argumentos en línea de comandos. Espacios e interpolación en argumentos.

Implementación de pseudocódigo. Conversión texto a número con sscanf(). Conversión entre números y punteros

Corregir vulnerabilidad índice fuera de rango. Programación defensiva. assert. Validar la entrada.

Desborde de pila por arreglo variable automático (vulnerabilidad). Memoria dinámica. malloc()

Corregir fuga de memoria. free()

Serialización por join

Concepto de indeterminismo

Correr herramientas de validación. Falsos positivos de helgrind

Linter. Enteros de tamaño fijo. Filtrar reglas del linter

Obtener la cantidad de CPUs disponibles con sysconf()

Modularización del ejemplo hello_w. Códigos de error en la línea de comandos

Makefile para uso de los ejemplos, tareas, y proyectos del curso

Diferencia entre la concurrencia de tareas y el paralelismo de datos en pseudocódigo

Implementación de memoria privada (parte 1): Thread team. Registros de memoria.

Implementación de memoria privada (parte 2): calloc()

Validar código. Ejercicio para la casa: hello_count

Ejemplo hello_iw_shr: memoria compartida

Memoria compartida en pseudocódigo. La declaración shared

Implementación de la memoria compartida en Pthreads

Medir tiempo de pared. CPU time. SO de tiempo real. División entera

Espera activa (busy waiting). Pseudocódigo de hello_order_busywait

Implementación y ejecución de espera activa con Pthreads

Explicación del efecto en tiempo de ejecución de la espera activa

Ejemplo position_race: pseudocódigo con condición de carrera

Ejemplo position_race: implementación y ejecución

Definición de condición de carrera (data race o race condition)

Exclusión mutua (mutex o candado). Región crítica. Metáfora del puente angosto

Repaso de la lección previa: exclusión mutua

Implementación de mutex en Pthreads. Imprimir en la región crítica

Liberar el mutex (pthread_mutex_destroy)

Mutex debe proteger todos los accesos a la variable, no sólo escritura

Múltiples regiones críticas

Olvidar liberar un mutex ("el proceso bello durmiente")

Definición original de semáforo (Dijkstra)

Metáfora de semáforo

Usar un arreglo de semáforos para imponer orden

Repaso: mutex, semáforo. Futex (fast userspace mutex)

Ejemplo hello_order_semaphor: solucion en pseudocódigo

Semáforos en POSIX. Semáforos de memoria. Semáforos nombrados

hello_order_semaphor: implementación de la solución

Corrección de errores en hello_order_semaphor y position_race [27-set]

Seguridad condicional (conditionally safe)

hello_order_cond_safe: solución en pseudocódigo

hello_order_cond_safe: implementación en C

Análisis del problema del productor-consumidor de buffer acotado

Ejecutar el código dado

Comprensión del pseudcódigo dado

Idear una solución con dos semáforos

Solución en pseudocódigo

Comprensión del código en C dado

Implementación y ejecución de la solución con Pthreads

Poblema del Productor-consumidor de buffer acotado. Archivos dados. Makefile v2.2.2

Comprender el pseudocódigo dado

Rastreo de procesamiento. Encontrar las condiciones de carrera

Hacer la cola thread-safe usando exclusión mutua

Corregir productores usando variables contadoras (variante 0)

Corregir productores usando ciclo infinito (variante 1)

Corregir consumidores usando variables contadoras y ciclo infinito (variante 1)

Evitar que los consumidores extraigan de la cola si está vacía

Rastreo rápido de procesamiento de los consumidores con variables contadoras (variante 1)

Consumidores con variables contadoras y espera activa (variante -2)

Detener consumidores cuando la cola está vacía y los productores terminaron (variante 2)

Repaso. Numerar las variantes de productor y consumidor

Detener consumidores usando un valor centinela (variante 3)

Comprender el código C dado

Implementación de la cola thread-safe: init(), is_empty()

Cola thread-safe: enqueue()

Cola thread-safe: dequeue(), is_empty_unsafe()

Cola thread-safe: remove_first_unsafe()

Cola thread-safe: clear()

Cola thread-safe: ¿Debería init y destroy ser thread-safe?

Corrección de errores en hello_order_semaphor y position_race

Implementación de la variante 1 de los productores en Pthreads

Implementación de la variante 1 de los consumidores en Pthreads

Patrón productor-consumidor. Ejecución de la simulación de red

Principio del patrón productor-consumidor. Flow-based programming paradigm

Repaso del patrón modelo-vista-controlador (MVC)

Controlador de la simulación de red

Controlador de la simulación de red (repaso)

Clase abstracta genérica Producer

Clase abstracta Thread. Registro NetworkMessage

Plantilla Queue. Clase envoltura Semaphore

Clase abstracta genérica Consumer. Condición de parada

Clase abstracta genérica Dispatcher (repartidor)

Clase abstracta genérica Assembler. Problema del diamante

Motivación al paralelismo de datos

Optimización. Método sugerido para optimizar

Repaso de optimización

Descomposición: concepto y técnicas: recursiva, de datos, exploratoria, especulativa

Mapeo: concepto. Mapeo estático. Mapeo dinámico

Actividad de mapeo manual en una hoja de cálculo

Mapeo estático por bloque no balanceado

Modelo matemático del mapeo estático por bloque balanceado

Mapeo dinámico en la actividad de la hoja de cálculo

Mapeo estático cíclico. Metáfora de la baraja de naipes

Mapeo estático cíclico con bloques

Mapeo dinámico

Métrica del incremento de velocidad (speedup)

Métrica de eficiencia (efficiency). Gráficos combinados

Mapeos estáticos para los casos 2 y 3 en la hoja de cálculo

Mapeo dinámico para los casos 2 y 3 en la hoja de cálculo

Comparación de los tipos de mapeo

Ejercicio de la simulación de mapeo. Algoritmos de posibles implementaciones de los mapeos

Mapeo dinámico aleatorio

Eficiencia ideal (1.0)

Ley de Amdahl. Máximo speedup teórico. Usarla para estimar recursos

Análisis estático y dinámico de código

Problema de ejemplo: marcar la cerca

Callgrind: herramienta de profiling para invocaciones y procesamiento

Concepto de visualización. Procesos en segundo plano en el shell

Kcachegrind: herramienta de visualización. Encontrar regiones de código que más consumen CPU

Clúster de Arenal. Nodo máster y esclavos

Determinar cantidad de CPUs (lscpu). Núcleos físicos y virtuales. Hyperthreading

Correr procesos en el clúster. Monitorear procesos (top). Terminar procesos (kill)

Objetivo del proyecto. Estructura del código dado. Correr el servidor web

Servidor web vs aplicación web. Interfaz de un servidor

El servidor web (clase HttpServer). Puertos de red

Iniciar el servidor (método start). Bitácoras. Aceptar todas las conexiones

Establecimiento de la conexión

Mensaje de solicitud y de respuesta. Ciclo de atención de solicitudes. Lista de to-do

Metáfora del food court. Tomador de órdenes (HttpConnectionHandler). Socket de red

Avances del proyecto 1 explicados en la cadena de producción

Enrutamiento web. HTML. Solicitud HTTP. Respuesta HTTP

La aplicación web de factorización de números

Concurrencia de tareas. El pequeño libro de los semáforos

Notaciones de pseudocódigo concurrente

Rutas de ejecución concurrente

Redes de Petri. Modelado de sistemas concurrentes y distribuidos.

Ejemplo de las rutas de ejecución en red de Petri. Lugares, transiciones y arcos

Ejemplo for_count: encontrar rutas de ejecución que cumplen una condición

Ejemplo signaling (avisar/notificar) en pseudocódigo

Ejemplo signaling (avisar/notificar) en red de Petri

Encuentro (rendezvous): solución 1 en pseudocódigo [err]

Encuentro (rendezvous): solución 2 en pseudocódigo [err]

Encuentro (rendezvous): Bloqueo mutuo (deadlock)

Encuentro (rendezvous): red de Petri

Exclusión mutua con semáforos (sem_mutex): pseudocódigo

Exclusión mutua con semáforos (sem_mutex): red de Petri

Exclusión mutua simétrica (sem_mutex_sym): pseudocódigo

Concurrencia acotada (multiplex): pseudocódigo

Repaso de patrones básicos en redes de Petri

Exclusión mutua simétrica (sem_mutex_sym): red de Petri

Concurrencia acotada (multiplex): red de Petri

Barrera con semáforos (sem_barrier): pseudocódigo

Barrera con semáforos (sem_barrier): red de Petri 1 con join/fork

Barrera con semáforos (sem_barrier): red de Petri 2 con arcos ponderados

Metáfora de barrera: aguja de paso vehicular

Problema de la barrera reusable (sem_barrier_reusable). Patrón torniquete o trompo (turnstile)

Barrera diseñada con un torniquete (turnstile)

Barrera reusable en un ciclo con dos torniquetes (turnstiles)

Interfaz en pseudocódigo concurrente para crear barreras

Carrera de relevos (relay_race): análisis del problema

Carrera de relevos (relay_race): solución gráfica con metáforas

Carrera de relevos (relay_race): solución en pseudocódigo

Barreras en Pthreads

Carrera de relevos (relay_race): implementación en Pthreads. _DEFAULT_SOURCE, Git Stash

Concurrencia de tareas declarativa: OpenMP

Hola mundo en OpenMP. Directivas del preprocesador. Instrumentalización de código con OpenMP

Región paralela. Bloque estructurado

Invocación de subrutinas en la región paralela

Indeterminismo en la salida por los operadores de flujo de C++. Región crítica (mutex)

OpenMP con Google Sanitizers y Valgrind

Ejemplo hello_w. Mutex nombrados. Cláusula num_threads. Biblioteca de subrutinas de OpenMP

Ejemplo de un bloque no estructurado

Repaso. Potencial concurrencia de tareas en OpenMP

Ejemplo parallel_for: repartir iteraciones

Restricciones: ciclo por contador y bloque estructurado

Pasar valores a los hilos: default(none), datos privados, datos compartidos

Enunciado de reutilizar hilos (several_for)

Reutilizar hilos. Diferencia entre omp parallel for y omp for

Barreras (omp barrier) y ejecución por un hilo al azar (omp single)

Anuncio: Ejercicio de ordenamiento par-impar. Comandos gprof y perf

Descomposición (iteraciones) y mapeo (scheduling) en OpenMP. Mapeo estático por bloque

Mapeo dinámico y mapeo guiado en OpenMP

Mapeo guiado (guided scheduling). Diferencias entre GCC y Clang

Parámetro tamaño de bloque en los mapeos de OpenMP. Mapeo cíclico

Mapeo en tiempo de ejecución (runtime). Variables de ambiente (entorno)

Ejemplo de calcular el promedio (average_atomic): versión serial

average_atomic: solución con mutex: serialización innecesaria

average_atomic: seguridad condicional con variables privadas

average_atomic: operaciones atómicas

average_reduction: Reducciones en OpenMP

Paradigma de programación distribuida

Pregunta: Cómo se detiene el ciclo de lectura con el operador de flujo >>

Modelo de ejecución de MPI (ssh, nfs)

Rastreo de procesos e hilos. Mecanismos de intercomunicación de procesos (IPC)

hello_hybrid: diseño en pseudocódigo para Pthreads y OpenMP

hybrid_distr_arg: problema y pseudocódigo inicial

hybrid_distr_arg: calcular el inicio y fin en mapeo estático por bloque

hybrid_distr_arg: Distribuir y llevar el rastro de las iteraciones en pseudocódigo

hybrid_distr_arg: Implementación con MPI y OpenMP. Ejemplo de ejecución

Comunicación punto a punto. Primitivas send y receive. Entrada y salida blocking o sincrónica

send_recv_ord_sem: Solución en pseudocódigo. Negativos en módulo y residuo

send_recv_ord_sem: Implementación con MPI. MPI_Send(). MPI_Recv(). Operaciones orientadas a vectores

Repaso ejemplo send_recv_ord_sem

send_recv_ord_sem: Visualización manual de una ejecución en el clúster

send_recv_ord_sem: Manejo de errores y modularización del código fuente

send_recv_ord_itm: Programación orientada a arreglos. Simular seguridad condicional con un intermediario. Solución en pseudocódigo 1.

send_recv_ord_itm: Implementación 1. Buffers en C++: stringstream, string, y vector

send_recv_ord_itm: Los procesos no pueden enviarse mensajes a sí mismos. Solución 2

send_recv_ord_itm: Visualización de ejecución. Message match: type, source, tag

send_recv_urd: Relajar el message match con MPI_ANY_SOURCE y MPI_ANY_TAG

Tipos de send y receive en MPI: blocking, non-blocking (I), buffered (B) y ready (R)

stdin_sendrecv: Solución ingenua: todos los procesos leen de la entrada estándar, pero mpiexec sólo la envía a proceso 0

stdin_sendrecv: Solución en pseudocódigo: proceso 0 envía el arreglo a los demás. Orden de paso de mensajes

stdin_sendrecv: Implementación de la solución. static_assert en C++

stdin_sendrecv: Medición de tiempo de pared con MPI_Wtime. Problema del tiempo distribuido

relay_race_dist: Enunciado del problema

Solución con metáforas visuales. Modelos centralizados y descentralizados

Solución en pseudocódigo: subrutina main()

Pseudocódigo de los corredores de las etapas 1 y 2. Barreras en MPI (MPI_Barrier())

Pseudocódigo del árbitro

Implementación con MPI. Tiempo transcurrido desde el punto de vista del árbitro

stdin_bcast: Enunciado y diseño en pseudocódigo. Concepto de comunicación colectiva. Difusión (broadcast)

stdin_bcast: Implementación. Difusión de mensajes en MPI (MPI_Bcast())

lucky_number_reduce: enunciado. Reusar código en carpeta common en Makefile o con enlaces simbólicos

lucky_number_reduce: diseño en pseudocódigo. Reducciones distribuidas. Programación funcional: map y reduce.

lucky_number_reduce: código fuente inicial. Generación de números pseudoaleatorios

lucky_number_reduce: implementación. MPI_Reduce()

Cómo funciona la reducción en MPI. Árbol binario de reducción. Usar número de proceso en la semilla de números aleatorios.

lucky_number_who: enunciado del problema. Solución en pseudocódigo. Operación all_reduce()

lucky_number_who: implementación. MPI_Allreduce()

Otros temas de MPI: scatter, gather, soporte multi-hilos, paralelización de archivos.

mist_cond_var: enunciado. Rastreo de procesamiento. Supuestos

mist_cond_var: rastreo de procesamiento parte 1

Concepto de variable de condición. Metáfora del oficial de tránsito y el intercomunicador. Variables de condición en Pthreads

mist_cond_var: rastreo de procesamiento parte 2

Filósofos comensales: Enunciado del problema (dining_philosophers)

Filósofos comensales: análisis del psedocódigo inicial

Filósofos comensales: solución 1: lateralidad (zurdos y diestros)

Filósofos comensales: solución 2: cuota (capacidad de comensales concrrentes en la mesa)

Filósofos comensales: Otras soluciones: con contadores, distribuida centralizada (mesero), y distribuida descentralizada.

Filósofos comensales: solución en red de Petri (con inanición)

Lectores y escritores: Enunciado del problema

Lectores y escritores: Solución en pseudocódigo

readers_writers_rwlock: Código inicial

Candado de lectura y escritura. Metáfora del puente levadizo. rwlock de Pthreads

Ejercicios de candados de lectura y escritura. Comparación de rendimiento entre rwlock vs mutex.

build_h2o: Enunciado. Solución con metáforas visuales

build_h2o: Solución en pseudocódigo

false_sharing_array: Análisis del problema

false_sharing_array: Código inicial. Tiempo de ejecución de los 4 modos

Arquitectura de la jerarquía de caché

Rastreo de caché. Fallo de caché. Principio de localidad. Dirty bit. Coherencia de caché

Falso compartido (false sharing). Modificación de memoria cercana y distante

Análisis dinámico de fallos de caché (profiling). perf stat

Relación entre los tipos de mapeo y el falso compartido

false_sharing_record: Evitar el falso compartido con memoria privadas

Subrutinas reentrantes vs thread-safe