Programación concurrente: ejemplos de clase

Figura 1. Paradigmas de programación concurrente y distribuido

1. Concurrencia compartida imperativa (Phtreads)

La concurrencia de estado compartido, concurrencia de recursos compartidos, o simplemente concurrencia compartida ocurre cuando varios trabajadores (hilos de ejecución) realizan una tarea concurrentemente y pueden acceder a regiones compartidas de memoria porque están dentro del mismo espacio de direcciones de memoria del proceso.

Los hilos de ejecución siguen este esquema, dado que comparten todos los segmentos del proceso (código, datos, y memoria dinámica), excepto el segmento de pila. Por ejemplo, un dato que un hilo escriba en la memoria compartida, otro hilo puede leerlo inmediatamente, sin tener que depender de la intervención del sistema operativo. De esta forma, la memoria compartida se convierte en un mecanismo directo de comunicación entre los hilos de ejecución.

Se estudiarán en el curso dos tecnologías para implementar concurrencia compartida: Pthreads y OpenMP. Los POSIX Threads es un estándar que permite a los desarrolladores crear y controlar hilos de ejecución en los sistemas operativos basados en Unix. Cree en una carpeta ejemplos/pthreads para los siguientes ejemplos en su repositorio personal de control de versiones para el curso. Para cada ejemplo cree una subcarpeta que utilice el nombre dado entre corchetes.

1.1. Hola mundo (thread)

Actividad 1. Hola mundo en Pthreads [hello]

Escriba un programa que al correr cree dos hilos, el principal y uno secundario. Ambos hilos deben saludar en la salida estándar con el mensaje "Hello from main thread" y "Hello from secondary thread" respectivamente. Utilice un analizador dinámico de código como las herramientas memcheck y helgrind de Valgrind, o los Google Sanitizers, para asegurarse de que su programa no provoca condiciones de carrera.

En la siguiente solución se incluye además un archivo de reglas Makefile que permite a un desarrollador compilar el código fuente sin tener que recordar los argumentos con los que se debe invocar al compilador. Bastará que el programador emita el comando make en la carpeta, y éste invocará al compilador siguiendo la primera regla estipulada en el Makefile.

Tabla 1. Hola mundo en Pthreads [hello]
Archivo	Descripción	Cambios
hello.pseudo	Diseño en pseudocódigo de la solución.
hello.c	Implementación en Pthreads. Dice "hola mundo" desde el hilo principal y desde un hilo secundario.
Makefile	Un archivo para compilar el código fuente sin tener que recordar los argumentos de invocación al compilador. También permite correr pruebas durante el desarrollo como quitar pelusas (linting), revisar accesos inválidos y fugas de memoria (`memcheck`, `asan`, `msan`, `ubsan`), y revisar condiciones de carrera (`helgrind`, `tsan`).

Para instalar el compilador (GCC), el analizador estático de código (cpplint), el analizador dinámico de código (valgrind), y el compilador Clang que instrumenta código con sanitizers, puede instalar los siguientes paquetes en un Linux basado en Debian:

sudo apt update
sudo apt install build-essential python3-pip valgrind clang
sudo pip3 install cpplint

Para compilar con GCC –o un compilador compatible– código fuente que use Pthreads, se necesita el parámetro -pthread:

cc -g -Wall -Wextra hello.c -o hello -pthread

echo hello > .gitignore
git add hello.c .gitignore

Recuerde siempre ignorar los ejecutables en su repositorio de control de versiones. Para ello, cree o agregue a su archivo .gitignore el nombre del ejecutable. Luego agregue el código fuente y el .gitignore a control de versiones. Los dos últimos comandos de arriba hacen este trabajo. La Figura 2 muestra el resultado final de rastrear la memoria durante la ejecución del código.

Figura 2. Resultado de rastrear la memoria del programa hello

1.2. Hola mundo múltiple (indeterminismo)

Actividad 2. Hola mundo múltiple en Pthreads [hello_w]

Modifique el programa de "hola mundo" para crear una cantidad arbitraria de hilos de ejecución. Cada uno de los cuales imprime "Hello from secondary thread i" en la salida estándar y termina su ejecución. Permita al usuario indicar la cantidad de hilos de ejecución como argumento de la línea de comandos. Si este argumento se omite, suponga la cantidad de CPUs disponibles en el sistema.

Tabla 2. Hola mundo múltiple en Pthreads [hello_w]
Archivo	Descripción	Cambios
hello_w.pseudo	Diseño en pseudocódigo de la solución.
hello_w.c	Varios threads dicen "hola mundo" junto con el hilo principal.
Makefile	El Makefile usa unas pocas variables nombradas, variables automáticas, y funciones. Por ejemplo para especificar banderas del compilador, el nombre del ejecutable, y archivos de compilación.

1.3. Hola mundo numerado (memoria privada)

Actividad 3. Hola mundo numerado con memoria privada [hello_iw_pri]

Cree una nueva versión de su programa "hola mundo" donde cada thread imprime "Hello from secondary thread i of w", donde i es el número de thread y w la cantidad total de hilos creada. Está prohibido usar variables en el segmento de datos (globales, estáticas, externas). Cree un registro de memoria (estructura) privado para cada thread.

Tabla 3. Hola mundo numerado [hello_iw_pri]
Archivo	Descripción	Cambios
hello_iw_pri.pseudo	Diseño en pseudocódigo de la solución.
hello_iw_pri.c	Varios threads saludan indicando su identificador y tamaño del equipo en la salida estándar.
Makefile	A partir de este ejemplo se usa un `Makefile` genérico con funciones para compilar, probar, y otras tareas comunes. El código fuente se recomienda esté en una subcarpeta `src/`.

Ejercicio 1 [hello_count]

Utilizando los argumentos en línea de comandos, ubique la cantidad máxima de threads que su sistema operativo le permite crear. Escriba el número obtenido en un archivo count.md en su carpeta ejemplos/pthreads/hello_iw_pri, junto con el nombre de su sistema operativo (por ejemplo, Debian 10 64bits o Fedora 30 64bits).

1.4. Hola mundo numerado (memoria compartida)

Actividad 4. Hola mundo numerado con memoria compartida [hello_iw_shr]

Cree una nueva versión de su programa "hola mundo numerado" donde cada hilo de ejecución imprime "Hello from secondary thread i of w\n", donde i es el número de hilo y w la cantidad total de hilos que componen el equipo, pero con los siguientes cambios:

Haga que los datos comunes para todos los hilos de ejecución (el número w) estén en un registro (estructura) compartido para cada hilo. Mantenga los datos exclusivos para cada hilo (i) se mantengan en el registro privado.
Reporte la duración en segundos que los hilos toman en saludar. Puede usar la función POSIX clock_gettime() de <time.h>.

Tabla 4. Hola mundo numerado [hello_iw_shr]
Archivo	Descripción	Cambios
hello_iw_shr.pseudo	Diseño en pseudocódigo de la solución.
hello_iw_shr.c	Varios threads saludan indicando su identificador en la salida estándar.
Makefile	Facilita la construcción y prueba de la la solución.

El código en este ejemplo es de suma importancia, porque es el código base para crear programas concurrentes con Pthreads. Este código permite a los hilos tanto compartir memoria como tener su propia memoria privada de trabajo sin incurrir en malas prácticas como el uso de variables globales.

1.5. Hola mundo ordenado (espera activa)

Actividad 5. Hola mundo ordenado con espera activa [hello_order_busywait]

Haga que los threads saluden siempre en orden. Es decir, si se crean w threads, la salida sea siempre en orden

Hello from thread 0 of w
Hello from thread 1 of w
Hello from thread 2 of w
...
Hello from thread w of w

Utilice espera activa como mecanismo de sincronización (control de concurrencia).

La espera activa (busy waiting) es un ciclo que hace a un hilo de ejecución esperar repetitivamente hasta que una condición se haga falsa. Por ejemplo, si la variable next_thread indica el número del próximo thread que puede realizar una tarea que debe ser serializada en orden, el código

// Wait until it is my turn
while (next_thread < my_thread_id) {
	// busy-wait
}

// Do the ordered-task here
task();

// Allow subsequent thread to do the task
++next_thread;

Tabla 5. Hola mundo ordenado con espera activa [hello_order_busywait]
Archivo	Descripción	Cambios
hello_order_busywait.pseudo	Diseño en pseudocódigo de la solución.
hello_order_busywait.c	Varios threads saludan en orden gracias a la espera activa, pero a costa de un consumo injustificado de recursos.
Makefile	Facilita la construcción y prueba de la la solución.

Actividad 6. Impacto de la espera activa [busywait_rationale]

Ejecute varias veces su solución de hello_order_busywait con la cantidad máxima de threads que el su sistema operativo le permite. ¿Es consistente la duración de su solución con espera activa?

Describa el comportamiento del programa y explique la razón de este comportamiento en un archivo rationale.md dentro de su carpeta hello_order_busywait. Indique en qué condiciones sería apremiante utilizar espera activa, o en caso de no haberlas, sugiera soluciones alternativas.

1.6. Posición en la carrera (mutex)

Actividad 7. Posición en la carrera (mutex) [position_race]

Modifique su solución a Actividad 5 para implementar una carrera de hilos de ejecución. Cada vez que un hilo llega a la meta, lo avisa en la salida estándar, como ocurre en la siguiente corrida hipotética:

Thread 0/4: I arrived at position 1
Thread 2/4: I arrived at position 2
Thread 1/4: I arrived at position 3
Thread 3/4: I arrived at position 4

Note que las posiciones tienen que aparecer en orden, no el número de cada hilo. Utilice algún mecanismo de control de concurrencia para que el reporte sea correcto.

Tabla 6. Posición en la carrera [position_race]
Archivo	Descripción	Cambios
position_race.pseudo	Diseño en pseudocódigo de la solución.
position_race.c	Varios threads compiten en una carrera, y reportan el orden en que llegan a la meta. Utilizan exclusión mutua cuando llegan a la meta para incrementar la variable contadora correctamente y para evitar la condición de carrera en la impresión en la salida estándar.
Makefile	Facilita la construcción y prueba de la la solución.

1.7. Hola mundo ordenado (semáforos)

Actividad 8. Hola mundo ordenado con semáforos [hello_order_semaphor]

Al igual que Actividad 5, haga que los threads saluden siempre en orden. Es decir, si se crean w threads, la salida sea siempre en orden

Hello from thread 0 of w
Hello from thread 1 of w
Hello from thread 2 of w
...
Hello from thread w of w

Utilice una colección de semáforos como mecanismo de sincronización (control de concurrencia).

Tabla 7. Hola mundo ordenado (semáforos) [hello_order_semaphor]
Archivo	Descripción	Cambios
hello_order_semaphor.pseudo	Diseño en pseudocódigo de la solución.
hello_order_semaphor.c	Utiliza una colección de semáforos, uno para cada hilo de ejecución. Sólo el semáforo para el hilo 0 está inicialmente en verde. Cuando un hilo pasa su semáforo, saluda en la salida estándar, y luego enciende el semáforo del siguiente. De esta forma, las impresiones se hacen en orden. Esta solución tiene una limitación de la cantidad de hilos que se pueden crear.
Makefile	Facilita la construcción y prueba de la la solución.

1.8. Concepto de semáforo

La definición original de semáforo por Dijkstra puede variar ligeramente de algunas implementaciones. Para Dijkstra un semáforo es un entero con signo, con tres características:

Cuando se crea un semáforo, éste se inicializa con un entero cualquiera (negativo, cero, o positivo). Pero después de inicializado las únicas dos operaciones que están permitidas es incrementar en uno (signal) y decrementar en uno (wait) al semáforo. No se puede leer el valor actual del semáforo.
Cuando un hilo decrementa un semáforo, si el resultado es negativo, el hilo es bloqueado y no puede continuar hasta que otro hilo incremente el semáforo.
Cuando un hilo incrementa un semáforo, si hay otros threads esperando, uno de ellos será desbloqueado. Tanto el hilo que incrementa el semáforo como el que fue desbloqueado siguen ejecutándose concurrentemente. Si hay varios hilos esperando, no hay forma de saber cuál de ellos será el desbloqueado por el scheduler del sistema operativo. El programador no tiene forma de saber si al incrementar un semáforo, se desbloqueará o no un hilo en espera, dado que no se puede leer el valor actual del semáforo por la regla 1.

El valor actual de un semáforo indica lo siguiente. Si el valor es positivo indica la cantidad de hilos que pueden decrementar el semáforo sin bloquearse. Si es negativo indica la cantidad de hilos que están bloqueados esperando actualmente por el semáforo. Si el valor es cero, indica que no hay hilos esperando por el semáforo, pero si un thread trata de decrementarlo, será bloqueado.

Algunas implementaciones, por ejemplo POSIX, permiten probar la espera (sem_trywait). Esta función nunca bloquea al hilo que la invoca. Si se trata de esperar un semáforo que tiene un valor positivo, se decrementará el semáforo y el hilo continuará ejecutándose como una invocación normal a wait(). Pero si se trata de esperar por un semáforo que quedaría en un valor negativo, la función sem_trywait() no decrementa al semáforo ni bloquea al hilo, sino que retorna de inmediato indicando un código de error (por ejemplo, -1). Dado que el hilo mantiene su ejecución, el programador puede decidir, condicionando (if) el valor de retorno del sem_trywait() y tomar distintas acciones que realice el hilo cuando se pudo o no esperar por el semáforo.

En los siguientes ejemplos se seguirá la definición original de Dijkstra, que no permite probar la espera. Se usará pseudocódigo con la siguiente sintaxis para los hilos y semáforos, con el fin de centrar la atención en estos temas y no en detalles de implementación de una tecnología particular (ej.: Pthreads):

sem := create_semaphore(3) // Create a semaphore with initial value 3
signal(sem)                // Increment and wake a waiting thread if any
wait(sem)                  // Decrement and block if the result is negative

Ejercicio 2 [hello_order_semaphor2]

Modifique su solución de Actividad 8 para inicializar todos los semáforos en 0. Luego haga que el hilo principal incremente el semáforo del hilo 0. ¿Produce el mismo resultado que su solución anterior?

¿Qué pasa si el hilo principal incrementa el semáforo del hilo 0 después de hacer su saludo Hello from main thread?

Ejercicio 3 [hello_order_semaphor_named]

La solución a Actividad 8 utiliza semáforos no nombrados o también llamados semáforos de memoria. Son regiones de la memoria alojadas con sem_init() y liberadas con sem_destroy(). En macOS, estos semáforos están desaprobados (deprecated).

Modifique su solución para usar semáforos nombrados que tienen la ventaja de ser más universales entre sistemas operativos. Son archivos, abiertos con sem_open(), cerrados con sem_close() y eliminados del sistema de archivos con sem_unlink(). Si no se eliminan, quedan en el sistema de archivos y próximas ejecuciones del programa podrían continuar usándolos o dependiendo del modo de apertura, fallarán.

¿Puede su programa con semáforos nombrados crear más hilos que con semáforos de memoria?

1.9. Hola mundo ordenado (seguridad condicional)

Actividad 9. Hola mundo ordenado con seguridad condicional [hello_order_cond_safe]

Al igual que Actividad 8, haga que los threads saluden siempre en orden. Es decir, si se crean w threads, la salida sea siempre en orden

Hello from thread 0 of w
Hello from thread 1 of w
Hello from thread 2 of w
...
Hello from thread w of w

Evite (si es posible) el control de concurrencia, es decir, trate de usar seguridad condicional (conditionally safe).

Tabla 8. Hola mundo ordenado (seguridad condicional) [hello_order_cond_safe]
Archivo	Descripción	Cambios
hello_order_cond_safe.pseudo	Diseño en pseudocódigo de la solución.
hello_order_cond_safe.c	Imprime en orden sin usar mecanismos de control de concurrencia. Usa una estructura de datos (un arreglo) donde cada hilo de ejecución escribe sus resultados sin afectar a los demás. El hilo principal se encarga de la tarea secuencial de imprimir.
Makefile	Facilita la construcción y prueba de la la solución.

1.10. Productor-consumidor

El problema del productor-consumidor en computación es un problema clásico de control de concurrencia, propuesto por Edsger Dijkstra. Se suele presentar de forma semi-concreta, lo que ayudar a identificar otros contextos donde su solución se puede aplicar. Hay dos variantes, una de buffer acotado y otra de buffer no acotado. De ambas se puede generalizar un patrón de software que puede enriquecerse con otros paradigmas de programación como el genérico y orientado a objetos.

1.10.1. Problema de buffer acotado

El problema del productor-consumidor lo tienen dos entes concurrentes, uno que produce algo que el segundo consume. Ambos tienen acceso a un espacio finito (acotado) donde se alojan los productos, comúnmente llamado buffer y de naturaleza circular. Dado que los entes son concurrentes, uno está agregando productos al buffer mientras el otro está al mismo tiempo consumiéndolos (o quitándolos) del buffer.

El problema surge cuando ambos entes actúan a diferente velocidad. Si el consumidor es más rápido que el productor, podría consumir productos que aún no se han colocado en el buffer. Si el productor es más rápido que el consumidor, lo alcanza y sobrescribe productos que el consumidor aún no ha procesado.

El problema se resuelve cuando el consumidor procesa todos los productos y en el mismo orden en que el productor los genera. Al igual que ocurre con seres humanos, la solución implica imponer espera. Si el consumidor es más veloz, vaciará el buffer y deberá esperar a que el productor genere el próximo producto. Si el productor es más veloz y satura el buffer, deberá esperar a que el consumidor libere al menos un espacio para poder continuar produciendo.

Actividad 10. Productor-consumidor de buffer acotado [prod_cons_bound]

Cree una simulación del productor-consumidor. Su programa recibirá seis argumentos en la línea de comandos:

El tamaño del buffer.
La cantidad de rondas, vueltas, o veces que se debe llenar y vaciar el buffer.
La duración mínima en milisegundos que el productor tarda en generar un producto.
La duración máxima en milisegundos que el productor tarda en generar un producto.
La duración mínima en milisegundos que el consumidor tarda en consumir un producto.
La duración máxima en milisegundos que el consumidor tarda en consumir un producto.

El programa debe crear un buffer para almacenar productos identificados por números secuenciales iniciando en 1. Por ejemplo, si se piden 2 rondas con un buffer de tamaño 3, el 4 identificará el primer producto de la segunda ronda.

Generar un producto no es inmediato. El tiempo que el productor tarda depende de la naturaleza del contexto en que se aplique el problema del consumidor-productor. Para efectos de la simulación, los argumentos 3 y 4 sirven de rango para generar números pseudoaleatorios. Cada vez que el productor tiene que construir un producto, se generará una duración pseudoaletoria y el proceso esperará esta cantidad de milisegundos, simulando hasta que el producto esté acabado. Luego el productor agrega el producto al buffer e imprime en la salida estándar el texto i generated, donde i es el número de producto.

Una vez que el consumidor extrae un producto del buffer imprime en la salida estándar el texto Consuming i y se dispone a consumir. Consumir un producto no es inmediato. El tiempo que el consumidor tarda se genera también en forma pseudoaletoria con los argumentos 5 y 6. Sugerencia: indente la salida del consumidor para distinguirla de la salida del productor.

En el siguiente ejemplo de ejecución, los entes hacen dos rondas llenando y consumiendo un buffer de 3 elementos. El productor es rápido y tarda máximo 100ms creando un producto. El consumidor es más lento y podría tardar máximo 750ms consumiendo un producto. Como se puede ver en la salida, el productor rápidamente llena el buffer y debe esperar a que el consumidor libere espacio en el buffer para continuar produciendo. En la salida se comprueba que el consumidor procesa todos los datos generados por el productor y en el mismo orden.

$ ./producer_consumer 3 2 0 100 0 750
Produced 1
Produced 2
Produced 3
		Consuming 1
Produced 4
		Consuming 2
Produced 5
		Consuming 3
		Consuming 4
		Consuming 5
Produced 6
		Consuming 6

Puede usar el siguiente código no modularizado como punto de partida para su solución:

Archivo	Descripción
prod_cons_bound.pseudo	Diseño inicial en pseudocódigo
prod_cons_bound.c	Implementación inicial en C sin modularización

Archivo

Descripción

prod_cons_bound.pseudo

Diseño inicial en pseudocódigo

prod_cons_bound.c

Implementación inicial en C sin modularización

Tabla 9. Productor-consumidor de buffer acotado [prod_cons_bound]
Archivo	Descripción	Cambios
prod_cons_bound.pseudo	Diseño en pseudocódigo de la solución.
prod_cons_bound.c	Simula el problema con un productor y un consumidor que comparten un buffer acotado.
Makefile	Facilita la construcción y prueba de la la solución. Usa la variable `APPARGS` para

Ejercicio 4 [prod_cons_bound_mod]

Modularice su solución de Actividad 10. Sugerencia: puede implementar archivos para:

La función principal
La simulación
El productor
El consumidor

1.10.2. Problema de buffer no acotado

Dijkstra publicó una segunda versión del problema del productor-consumidor que elimina las limitaciones del buffer acotado. En esta versión, el buffer tiene memoria infinita, hay una cantidad arbitraria de productores, y una cantidad arbitraria de consumidores. Al igual que el anterior, el problema se resuelve si todos los consumidores procesan todos los productos en el mismo orden en que los productores los generan.

Actividad 11. Productor-consumidor de buffer no acotado [prod_cons_unbound]

Modifique la simulación del problema productor-consumidor generalizando las siguientes restricciones.

El buffer no es acotado, sino de tamaño arbitrario o dinámico, definido por los límites de memoria del sistema.
No existe el concepto de ronda. El primer argumento de línea de comandos indica la cantidad de productos a simular. Identifique los productos en orden secuencial.
Varios productores, indicados por el usuario en el segundo argumento de línea de comandos.
Varios consumidores, indicados por el usuario en el tercer argumento de línea de comandos.
Cada productor y consumidor indica su número en la salida estándar.

El siguiente ejemplo de ejecución simula la construcción de 5 unidades de trabajo por 2 productores que tardan entre 0 y 100 milisegundos en producir, y 3 consumidores que tardan entre 0 y 750 milisegundos en consumir.

$ ./producer_consumer 5 2 3 0 100 0 750
0 produced 1
1 produced 3
		1 consuming 1
0 produced 2
		2 consuming 3
0 produced 5
		0 consuming 5
		1 consuming 2
1 produced 4
		2 consuming 4

Note que no necesariamente los productos se generan en orden secuencial, debido al indeterminismo de los productores. Recuerde, el problema está resuelto si todos los consumidores procesan todos los productos en el mismo orden en que los productores los generan. Puede usar el siguiente código modularizado como punto de partida para su solución:

Tabla 10. Código inicial para el productor-consumidor de buffer no acotado [prod_cons_unbound]
Archivos	Descripción
prod_cons_unbound.7z	Contiene a todos los demás
prod_cons_unbound.pseudo	Diseño preliminar en pseudocódigo de la solución.
main.c	Instancia e inicia la simulación
simulation.h / simulation.c	Implementa el controlador de la simulación
common.h / common.c	Código común usado entre todos los componentes de la simulación
queue.h / queue.c	Implementa una cola de enteros
producer.h / producer.c	Rutina de inicio de un hilo productor
consumer.h / consumer.c	Rutina de inicio de un hilo consumidor

Tabla 11. Productor-consumidor de buffer no acotado [prod_cons_unbound]
Archivo	Descripción	Cambios
prod_cons_unbound0.pseudo	Variante 0: Detiene a los productores con variables contadoras y redundancia de código. Incluye también una variante de consumidor con espera activa a modo de ejemplo de una solución que no es aceptable.
prod_cons_unbound1.pseudo	Variante 1: Detiene a los productores y consumidores con variables contadoras
prod_cons_unbound2.pseudo	Variante 2: Detiene a los consumidores con cuando la cola está vacía y los productores han terminado de producir.
prod_cons_unbound3.pseudo	Variante 3: Detiene a los consumidores con un valor especial en la cola que indica la condición de parada
main.c	Inicia la ejecución de la simulación.
simulation.h, simulation.c	Realiza la simulación del productor-consumidor de buffer no acotado
common.h, common.c	Código común usado entre todos los componentes de la simulación
queue.h, queue.c	Implementa una cola thread-safe de productos (números enteros)
producer.h, producer.c	Realiza la simulación del productor-consumidor de buffer no acotado
consumer.h, consumer.c	Realiza la simulación del productor-consumidor de buffer no acotado
Makefile	Facilita la construcción y prueba de la la solución. Actualizado a la versión 2.2.2

Ejercicio 5 [prod_cons_unbound_trace]

Rastree el procesamiento concurrente completo del diseño realizado en Actividad 11 con produce1() y consume3() al ser invocado con los argumentos de línea de comandos 2 2 0 0 0 0. Utilice una hoja de cálculo o una hoja de papel.

Ejercicio 6 [prod_cons_unbound_produce0]

En los diseños de Actividad 11 se proveyó una versión produce0() que sufre de redundancia de código. Modifique el diseño para eliminar dicha redundancia. Implemente esta mejora en el código C y compruebe que resuelve el problema correctamente.

Ejercicio 7 [prod_cons_unbound_consume0]

En los diseños de Actividad 11 se proveyeron las versiones consume1(), consume2(), y consume3(). Provea la versión consume0() análoga al produce0() que realizó en Ejercicio 6 [prod_cons_unbound_produce0]. Su diseño no debe tener redundancia de código. Implemente esta versión en C y compruebe que resuelve el problema correctamente.

Ejercicio 8 [prod_cons_unbound_produce2]

En los diseños de Actividad 11 se proveyó una versión produce1() que usa variables contadoras y exclusión mutua. Cree la versión produce2() que utilice control de concurrencia en lugar de variables contadoras con exclusión mutua. Sugerencia: puede apoyarse en la solución concurrente de Actividad 10 y la función try_wait(semaphore) que retorna false si el semáforo está en 0 o negativo en lugar de bloquear al hilo. Implemente esta variante en Pthreads y compruebe que resuelve el problema correctamente.

Ejercicio 9 [create_threads_pri]

En el enunciado de Actividad 11 se solicita que cada productor y cada consumidor reporte su número de hilo en la salida estándar. Modifique la subrutina create_threads() para que cree el arreglo de registros de datos privados, los cuales tienen dos valores: el número de cada hilo, y el puntero a los datos compartidos, los cuales se reciben por parámetro. Haga que retorne un puntero al arreglo de registros privados. Modifique a join_threads() para que reciba ese puntero a arreglo de registros privados, espere por los hilos, y libere el arreglo.

Ejercicio 10 [prod_cons_unbound_cpp]

Traslade su solución de Actividad 11 del lenguaje de programación C a C++ para que aproveche los paradigmas de programación genérica y orientada a objetos. Tome en consideración las siguientes sugerencias:

Cambie la tecnología procedimental Pthreads, por los hilos provistos en la biblioteca estándar de C++.
Cree una cola genérica que sea thread-safe, y por lo tanto, protegida por mecanismos de control de concurrencia. Use contenedores de la biblioteca estándar de plantillas.
Cree una clase base abstracta para los hilos de ejecución.
Cree una plantilla base abstracta para los productores. Haga que herede de la clase abstracta de hilo de ejecución.
Cree una plantilla base abstracta para los consumidores, de forma similar a los productores.
Herede de las abstracciones anteriores, su productor y consumidor para la simulación.
Cambie el registro y funciones de la simulación por una clase. Use el productor y consumidor que adaptó en el punto anterior en la implementación de su simulación.

1.10.3. Patrón productor-consumidor

La solución al problema del productor-consumidor es aplicable a una cantidad significativa de contextos. El código siguiente trata de generalizar la solución para que pueda ser reutilizada. Para esto se aprovechan mecanismos de reutilización de código provistos por paradigmas de programación como el orientado objetos (herencia y polimórfismo) y programación genérica (plantillas en C++). Se aplican otros patrones como el modelo-vista-controlador y singleton.

Tabla 12. Patrón productor-consumidor [prod_cons_pattern]
Archivo	Descripción	Cambios
prod_cons_pattern/	Carpeta con los archivos fuente que simulan una red de un productor, un repartidor, y una cantidad de consumidores dada por argumentos de línea de comandos. Incluye el código para crear un servidor web, base para el proyecto01.

La subcarpeta prodcons/ contiene las clases base genéricas reutilizables en otros contextos en particular:

Thread: Clase abstracta que facilita crear hilos de ejecución. Se debe crear una clase hija que sobrescriba el método run(), el cual se invocará en un hilo aparte cuando se le invoque startThread().
Semaphore: Encapsula un semáforo POSIX, dado que std::counting_semaphore requiere compiladores modernos con C++20.
Producer: Clase base abstracta genérica para crear hilos productores. Se debe heredar y sobrescribir el método run() heredado de Thread.
Consumer: Clase base abstracta genérica para crear hilos consumidores. Se debe heredar y sobrescribir el método run() heredado de Thread y el método consume() que se invoca cada vez que el consumidor logra extraer un dato de la cola de consumo.
Assembler: Es un hilo que consume de una cola que produce en otra cola.
Dispatcher: Es un hilo que consume de una cola y reparte a varias colas usando valores llave.

El código provisto ofrece un ejemplo en el que se usa las clases genéricas anteriores. Se trata de una simulación de una red, donde un productor genera paquetes dirigidos a una cantidad arbitraria de consumidores. Un repartidor intermediario se encarga de redirigir los paquetes de red a su correspondiente destinatario.

Figura 3. Diseño de la simulación de red

El código provisto contiene un servidor web serial que puede ser paralelizado mediante una cadena de producción, y por lo tanto, la intervención de varios hilos productores y consumidores. Este es el objetivo del proyecto01 del curso.

Ejercicio 11 [network_simul_packet_loss]

Modifique el código de la simulación de red para introducir pérdida de paquetes. Reciba un parámetro más en línea de comandos que corresponde a la probabilidad de perder paquetes, como un porcentaje en precisión flotante. Implemente un hilo ensamblador que es uno de los destinos del repartidor, como se ve en el siguiente diseño.

Por cada paquete que este hilo ensamblador recibe, se genera un número flotante pseudoaleatorio entre 0 y 100. Si este número generado es menor que la probabilidad de pérdida de paquetes, el hilo descarta el paquete, de lo contrario, modifica al azar el destino del paquete, y lo pone de regreso en la cola entre el productor y el repartidor.

Ejercicio 12 [network_simul_packet_loss2]

Modifique su solución al Ejercicio 11 [network_simul_packet_loss] para que el hilo que pierde paquetes esté ubicado entre el productor y el repartidor, de tal forma, que el porcentaje de pérdida de paquetes afecte a todos los paquetes y no una fracción de los mensajes de red.

¿Cuántas líneas de código debió modificar para reflejar este cambio? ¿Cuántas de esas líneas fueron en la implementación de su (a) productor, (b) repartidor, (c) consumidor, (d) ensamblador, y (e) controlador de la simulación?

Ejercicio 13 [network_simul_producers]

Modifique la simulación de red para recibir la cantidad de productores en el segundo argumento de línea de comandos. Cree tantos productores como indica el usuario y todos producen en la misma cola. Utilice mecanismos de control de concurrencia para que los productores se repartan la carga de creación de mensajes de red.

Ejercicio 14 [network_simul_bounded]

Modifique la simulación de red para recibir en un argumento de línea de comandos la capacidad máxima de paquetes que cabe en cada cola de la simulación. Modifique la plantilla Queue para que represente un buffer acotado. Sugerencia, agregue un semárofo canProduce que se inicialice en esta capacidad indicada por el usuario en el constructor de la cola. Si este número no se provee, suponga el número más grande que cabe en una variable unsigned.

Corra su simulación de red con dieferentes límites en las colas ¿Se afecta el tiempo de ejecución?

Ejercicio 15 [network_simul_demux]

Provea un componente genérico que realice el trabajo opuesto al repartidor (dispatcher). Es decir, reciba paquetes de una cantidad arbitraria de colas y redirija todos ellos hacia una única cola. Considere que este componente no puede determinar de antemano por cuáles colas de entrada recibirá o no paquetes de red ni en qué orden.

2. Concurrencia de tareas

Los dos tipos de problemas que resuelve el paradigma de programación concurrente son los que requieren incremento de desempeño y separación de asuntos.

El incremento del desempeño se busca principalmente al optimizar algorimos que requieren mucho poder de cómputo o procesar grandes volúmenes de datos. Son de especial interés para otras disciplinas que requieren apoyo de la computación. Se busca principalmente maximizar el paralelismo de datos a través de entes de ejecución (hilos o procesos) y disminuir la cantidad de comunicación entre los entes.
La separación de asuntos o concurrencia de tareas no busca tanto la optimización, sino que los entes realicen tareas distintas de forma correcta. Los problemas en esta categoría son de especial interés para la computación misma, dado que son aplicables a variedad de herramientas como sistemas operativos, motores de bases de datos, servidores web, entre otros. Típicamente los problemas en esta categoría buscan que la concurrencia de tareas genere resultados correctos a través de la aplicación de mecanismos de sincronización, por lo que se les suele también llamar problemas de sincronización.

Esta sección se concentra en problemas del segundo tipo de la lista anterior, muchos de los cuales tienen aspecto de acertijos y resultan muy interesantes para la persona profesional de la computación. Están basados en el libro libre The Little Book of Semaphores escrito por Allen B. Downey.

2.1. Primitivas

En la solución de problemas de sincronización se suele trabajar a nivel de diseño, lo que permite concentrarse en el problema de sincronización y abstraer los detalles del contexto en el que se aplica (ej.: persistencia en una base de datos) y los detalles de implementación (como lenguajes de programación y ambientes de concurrencia).

Existen varias notaciones empleadas para el diseño concurrente, como diagramas de flujo, UML, TLA+, cálculo-π, pseudocódigo, redes de Petri, entre otros. En el curso se usarán los últimos dos.

2.1.1. Algoritmos (pseudocódigo)

No existe una convención estándar para especificar algoritmos en pseudocódigo. Por el contrario, es común que los autores escojan sus propias convenciones. Existen estilos similares a un lenguaje de programación, a la notación matemática, o al idioma natural. En el curso se ha usado una notación que ha surgido de la creación de los docentes y estudiantes del mismo. En el siguiente listado se resume esta notación.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69 // Declares a constant shared by all threads, operator := is for variables
const CONST_NAME = const_value

// Declares a new data type as an enumeration of constants
define Month as enumeration of
	jan = 1, feb, mar, apr, may, jun, jul, aug, sep, oct, nov, dec
end enumeration

// Declares a new type of record, note the use of Uppercase
define Date as record of
	day as integer,
	month as Month,
	year as integer
end record

// Use {} for records. Use [] for arrays and associative-arrays
const CHRISTMAS = Date{25, dec, 0000}

// Main subroutine that will be executed by the main thread
procedure main:
	// Declares a local, private variable, data type is optional if it can be
	// inferred from initial_value
	declare local_var as data_type := initial_value
	// Declares a variable shared by all threads, stored in shared_data record
	// Its initial value is read as an integer from standard input
	shared thread_count := read_integer()
	// Create an array of boolean, char, integer, float, text, semaphore, record
	shared values as array of thread_count of integer initialized in 0
	// Concurrency control mechanisms are always shared
	shared a_mutex := create_mutex()
	// Semaphores receive an initial integer value
	shared a_semaphore := create_semaphore(5)
	// Create a secondary thread, returns a thread identifier
	// args is a list of comma-separated values passed as private variables
	declare thread1 := create_thread(routine1, args)
	// Create a team of threads, all of them will execute the same routine
	// concurrently. The routine will be called with the thread_number as first
	// parameter starting at 0. Extra arguments can be provided.
	// Returns an array of thread identifiers
	declare team := create_threads(thread_count, routine2, 5)
	// Secondary threads are implicitly joined before main() finishes, however
	// they can be joined/waited manually using the thread identifiers
	join_thread(thread1)
	join_threads(team)
end procedure

// Functions always return a value and has no side effects in process state
function routine1(params):
	// Arithmetic operators are similar to mathematics: div for integer division,
	// mod for integer modulus, and / for floating point division
	return 3 * mod(10, 4)
end function

// Procedure may not return a value and has side effects in process state
procedure routine2(my_rank, increment):
	// Note the flow control structures
	if condition then
		// Condition-loop
		while condition do
			statements
		end while
	else
		// Counter-loops, "for" implies declaration of new variables
		// "in steps of 1" is by default
		for index := 0 to thread_count in steps of 1 do
			values[my_rank] := index * my_rank + increment
		end for
	end if
end procedure

Cuando la notación de pseudocódigo no define un constructo específico, se toman características del lenguaje de programación usado en el curso, en este caso, C/C++.

Actividad 12. Rutas de ejecución [execution_paths]

Dos threads ejecutan las siguientes tareas. Liste todas las rutas de ejecución indicando el valor final de la variable x y la salida estándar. Una ruta de ejecución (execution path) es una combinación de instrucciones que depende del orden en que sean ejecutadas.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14 procedure main:
  shared x := 0
  create_thread(thread_a)
  create_thread(thread_b)
end procedure

procedure thread_a:
  x := 5
  print(x)
end procedure

procedure thread_b:
  x := 7
end procedure

Tabla 13. Rutas de ejecución [execution_paths]
Archivo	Descripción	Cambios
execution_paths.md	Lista todas las posibles rutas de ejecución.

2.1.2. Redes de Petri

Las redes de Petri (Petri net) fueron ideadas por el alemán Carl Adam Petri (1926-2010) a sus 13 años para describir procesos químicos, aunque su formalización ocurriría 23 años después, en su tesis doctoral de matemática en 1962. La aplicación de este concepto beneficia la representación de fenómenos que tienen componentes que actúan de forma concurrente o distribuida.

Una red de Petri es una representación matemática (un modelo) de la estructura y comportamiento dinámico de un sistema distribuido. Un sistema es un conjunto de componentes que interactúan de forma coordinada para realizar una actividad. El sistema es un concepto recursivo porque un sistema, con todos sus componentes, forma una unidad que puede ser parte de un sistema más grande, lo que crea una jerarquía o red de sistemas y subsistemas. Un sistema tiene estado (memoria), realiza actividades (procesamiento), e interacciona con otros sistemas (comunicación).

Cada componente en sí es un sistema que tiene un estado independiente al de otros componentes, lo que crea distribución del estado. El comportamiento futuro de un componente depende de este estado, y puede o no depender del pasado gracias a que el estado puede guardar historia. La actividad que un componente realiza podría ser simultánea a las actividades que realizan los otros componentes del sistema, lo que crea concurrencia o paralelismo de las actividades.

Es común que los componentes tengan que interactuar para lograr la actividad global del sistema, y esto requiere sincronización entre ellos para que los resultados sean correctos. Esta sincronización es normalmente una forma de espera (waiting), donde un componente detiene su actividad hasta la ocurrencia de un evento que asegure el orden correcto de actividades o la transferencia correcta de estado entre los componentes.

Figura 4. Red de Petri que representa las rutas de ejecución

Actividad 13. Agregar declaración de variable [execution_paths]

Al modelo de Petri de las rutas de ejecución le hizo falta la declaración de la variable commpartida shared x := 0. Modifique la red de Petri para agregar esta instrucción. Use la herramienta Workflow Petrinet Designer (WoPeD) que requiere del ambiente de ejecución de Java.

Tabla 14. Agregar declaración de variable [execution_paths]
Archivo	Descripción	Cambios
execution_paths.pnml	Red de petri que representa el mismo programa que el pseudocódigo dado.

Actividad 14. Rutas de ejecución extremas [for_count]

Suponga que el hilo de ejecución principal crea w=100 hilos secundarios con los siguientes códigos.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12 shared count := 0

procedure main:
  create_threads(100, secondary)
end procedure

procedure secondary:
  for i := 1 to 100 do
    declare temp := count
    count := temp + 1
  end for
end procedure

¿Cuál es el valor más grande que la variable compartida count podría llegar a obtener? ¿En qué rutas de ejecución se alcanza este valor?
¿Cuál es el menor valor que la variable compartida count podría llegar a obtener? ¿En qué rutas de ejecución se alcanza este valor?

Tabla 15. Rutas de ejecución extremas [for_count]
Archivo	Descripción	Cambios
for_count.md	Conjetura los potenciales resultados.

2.2. Patrones básicos

2.2.1. Avisar/notificar (signaling)

Actividad 15. Avisar/notificar [signaling]

Modifique los códigos de los hilos para que la instrucción a1 se ejecute siempre antes que la instrucción b1. Esto es, que un hilo envíe una señal (aviso) a otro (signaling).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12 procedure main:
  create_thread(thread_a)
  create_thread(thread_b)
end procedure

procedure thread_a:
  statement a1
end procedure

procedure thread_b:
  statement b1
end procedure

Modifique la red de Petri para que el hilo a haga el aviso al hilo b:

Tabla 16. Avisar/notificar [signaling]
Archivo	Descripción	Cambios
signaling.pseudo	Usa un semáforo que indica cuando la instrucción `a1` ha sido ejecutada.
signaling.pnml	Red de petri que usa una un estado intermedio para representar el aviso.

Ejercicio 16 [signaling_3]

Modifique los códigos de los hilos para que la instrucción a1 se ejecute siempre antes que la instrucción b1 y ésta siempre se ejecute antes que la instrucción c1. Este orden de ejecución puede abreviarse como a1 < b1 < c1.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17 procedure main:
  create_thread(thread_a)
  create_thread(thread_b)
  create_thread(thread_c)
end procedure

procedure thread_a:
  statement a1
end procedure

procedure thread_b:
  statement b1
end procedure

procedure thread_c:
  statement c1
end procedure

Actualice la red de Petri para que el aviso se dé entre los tres hilos.

Ejercicio 17 [signaling_w]

Generalice el patrón de aviso (signaling) para dada una cantidad arbitraria w de hilos que ejecutan la instrucción a, lo hagan en el orden del número de hilo. Por ejemplo, si ai es la ejecución de la instrucción statement a por parte del hilo con número i, entonces se asegure que siempre se ejecute la secuencia a0 < a1 < a2 < a3 < … < aw.

1
2
3
4
5
6
7
8 procedure main:
  declare thread_count := read_integer()
  create_threads(thread_count, secondary)
end procedure

procedure secondary:
  statement a
end procedure

Nota: una solución a este problema se había hecho antes en el curso ¿recuerda en cuál ejemplo?

2.2.2. Encuentro (rendezvous)

Actividad 16. Encuentro [rendezvous]

Modifique los códigos de los hilos para que la instrucción a1 y b1 se ejecuten siempre antes que las instrucciones a2 y b2. Este problema tiene el nombre francés rendezvous que significa encuentro en un punto de ejecución, y ninguno de los dos hilos pueden continuar su ejecución hasta que el otro haya llegado.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14 procedure main:
  create_thread(thread_a)
  create_thread(thread_b)
end procedure

procedure thread_a:
  statement a1
  statement a2
end procedure

procedure thread_b:
  statement b1
  statement b2
end procedure

Modifique la red de Petri para que ocurra el encuentro entre los hilos de ejecución:

Tabla 17. Encuentro [rendezvous]
Archivo	Descripción	Cambios
rendezvous1.pseudo	Usa dos semáforos para asegurar que dos threads han llegado a cierto punto. En esta solución, los dos threads avisan apenas hayan terminado de ejecutar las instrucciones `a1` o `b1`. En esta solución el nombre del semáforo indica el evento ocurrido, como `a1_ready`, y es lo que se prefiere. Otro nombre válido es indicar el manejador del evento o acción que debe realizarse cuando la señal ocurre, como `can_run_b2`.
rendezvous2a.pseudo rendezvous2b.pseudo	En esta versión un thread primero espera y el otro avisa. Es una solución correcta aunque ligeramente menos eficiente que la versión 1. Hay dos variantes equivalentes: a) El hilo `a` primero avisa y luego espera y el hilo `b` primero espera y luego avisa. b) El hilo `a` primero espera y luego avisa y el hilo `b` primero avisa y luego espera.
rendezvous3.pseudo	En esta versión ambos threads esperan a que el otro haya terminado de ejecutar su instrucción. No es una solución al problema porque genera un bloqueo mutuo (deadlock).
rendezvous1.pnml	Un encuentro es una doble señal cruzada entre los hilos

2.2.3. Exclusión mutua con semáforos (mutex)

Actividad 17. Exclusión mutua con semáforos [sem_mutex]

Agregue semáforos al pseudocódigo siguiente para forzar a que los incrementos en los hilos se hagan con exclusión mutua.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13 procedure main:
  shared count := 0
  create_thread(thread_a)
  create_thread(thread_b)
end procedure

procedure thread_a:
  count := count + 1
end procedure

procedure thread_b:
  count := count + 1
end procedure

Corrija la red de Petri para que los incrementos se realicen con exclusión mutua.

Tabla 18. Exclusión mutua [sem_mutex]
Archivo	Descripción	Cambios
sem_mutex.pseudo	Un semáforo inicializado en 1 y que nunca supera este valor, es un semáforo binario. Es equivalente a un mutex excepto que no tiene dueño (ownership). Cuando el semáforo tiene el valor 1 indica que el mutex está disponible, y el valor 0 que está bloqueado. Se diferencia en que un mutex nunca supera el valor 1, mientras que un semáforo técnicamente puede hacerlo, y de que un mutex sólo puede ser incrementado por el mismo thread que lo decrementó.
sem_mutex.pnml	Un lugar (place) con un token del cual salen dos arcos sirve para crear exclusión mutua en una red de Petri, lo que corresponde a "bloquear" el mutex. Luego el token debe regresar a este lugar, lo que semánticamente equivale a "desbloquear" (unlock) el mutex.

Actividad 18. Exclusión mutua simétrica [sem_mutex_sym]

Note que en la actividad anterior ambos threads ejecutaban el código en subrutinas distintas, a lo que se le llama una solución asimétrica (separación de asuntos o concurrencia de tareas). Sin embargo, el código de las subrutinas era el mismo y por tanto podría convertirse en una solución simétrica. En una solución simétrica los hilos ejecutan el mismo código, es decir, la misma subrutina.

Las soluciones simétricas son a menudo más fáciles de generalizar. Agregue semáforos al pseudocódigo siguiente para forzar a que los incrementos hechos por una cantidad arbitraria de hilos sean con exclusión mutua.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10 procedure main:
  shared count := 0
  shared constant thread_count = read_integer()
  create_threads(thread_count, secondary)
end procedure

procedure secondary:
  // Critical section
  count := count + 1
end procedure

Corrija la red de Petri para que una cantidad arbitraria de hilos (cinco en la red dada) hagan el incremento con exclusión mutua.

Tabla 19. Exclusión mutua simétrica [sem_mutex_sym]
Archivo	Descripción	Cambios
sem_mutex_sym.pseudo	El semáforo usado adecuadamente obliga a una serialización de los hilos.
sem_mutex_sym.pnml	Se usa un place con un token que permite avanzar sólo a un hilo a la vez

2.2.4. Exclusión mutua acotada (multiplex)

Actividad 19. Exclusión mutua acotada [multiplex]

Modifique el pseudocódigo dado para que imponga una cota o límite superior de n hilos ejecutando una sección de concurrencia acotada. A este patrón se le llama multiplex y es útil para problemas donde se tienen distintos entes trabajando al mismo tiempo pero con máximo de capacidad.

Por ejemplo, la cantidad de cajeros atendiendo en las ventanillas de un banco o de clientes patinando en la pista del salón de patines. En este último caso, si la capacidad de la pista se agota, algunos clientes tendrán que esperar afuera, y apenas un cliente sale de la pista, otro podrá ingresar de inmediato. Use el código siguiente para reflejar este comportamiento.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10 procedure main:
  shared constant skater_count = read_integer()
  shared constant room_capacity = read_integer()
  create_threads(skater_count, skater)
end procedure

procedure skater:
  // Concurrency-bounded region
  skate()
end procedure

Modifique la red de Petri para reflejar la llegada de 10 patinadores a un salón de patines que tiene una capacidad para 3 patinadores concurrentes.

Tabla 20. Exclusión mutua acotada [multiplex]
Archivo	Descripción	Cambios
multiplex.pseudo	Simplemente se inicializa el semáforo con el límite superior de threads permitidos concurrentemente. Si el semáforo llega a alcanzar el valor 0, indica que se agotó la capacidad concurrente y los hilos subsecuentes tendrán que esperar. Cuando un hilo incrementa el semáforo es porque "sale del salón" y deja espacio para que otro ingrese. ¿Cuál será el valor final del semáforo cuando todos los hilos hayan pasado por la sección crítica?
multiplex.pnml	Es la misma solución a sem_mutex_sym (Actividad 18) con la diferencia de que el semáforo en lugar de inicializarse en 1, lo hace en la capacidad de la región de concurrencia acotada.

2.2.5. Barrera (barrier)

Actividad 20. Barrera de una pasada con semáforos [sem_barrier]

Generalice su solución a la actividad rendezvous (Actividad 16) para asegurar que una cantidad arbitraria de hilos no continúen su ejecución hasta que todos hayan alcanzado (ejecutado) el punto de encuentro. Es decir, si se crean w hilos, los primeros w - 1 hilos que lleguen al punto de encuentro deberían esperar hasta que el hilo en la posición w llegue al punto de encuentro. En tal momento todos los w threads podrán continuar ejecutándose concurrentemente. A este patrón se le conoce como barrera (barrier). Implemente una barrera con semáforos en el siguiente pseudocódigo para que la instrucción Statement B se ejecute sólo hasta que todos los hilos hayan ejecutado la instrucción Statement A.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19 procedure main:
  // How many threads have arrived to the barrier
  shared count := 0
  // Protects the increment of the count
  shared can_access_count := create_semaphore(1)
  // Locked (0) until all threads arrive, then it is unlocked (1)
  shared barrier := create_semaphore(0)
  // Read thread count from standard input
  shared constant thread_count = read_integer()
  // Create a thread team running secondary
  create_threads(thread_count, secondary)
end procedure

procedure secondary:
  Statement A
  // Adapt rendezvous solution here
  // Statement B can be only executed until all threads have run Statement A
  Statement B
end procedure

Agregue una barrera a la red de Petri para que los tres hilos ejecuten las instrucciones Statement B sólo hasta que los tres hayan ejecutado las instrucciones Statement A.
Generalice la red de Petri para que w hilos ejecuten las instrucciones Statement B sólo hasta que todos hayan ejecutado las instrucciones Statement A.

Tabla 21. Barrera de una pasada con semáforos [sem_barrier]
Archivo	Descripción	Cambios
sem_barrier.pseudo	Implementa una barrera de una pasada. Es decir, después de usada, la barrera no se debe reutilizar.
sem_barrier_3.pnml	Implementa una barrera para 3 hilos usando un esquema de fork/join
sem_barrier_w.pnml	Implementa una barrera para una cantidad arbitraria de hilos usando arcos ponderados (weighted arcs)

Actividad 21. Barrera reusable con semáforos [sem_barrier_reusable]

Haga que su solución a la actividad Actividad 20 sea reusable. Es decir, que la barrera quede lista para volver a usarse, por ejemplo, dentro de un ciclo. Debe asegurarse de que el contador quede en 0, y los threads que salen de la barrera no se combinen con otros que aún están en ella.

Sugerencia: Puede reemplazar la barrera por dos torniquetes. Un torniquete (turnstile) o "trompo" es un dispositivo de control de acceso que impide o da paso a una secuencia de personas de acuerdo a ciertas condiciones. Se usa típicamente en instalaciones deportivas, transporte público, acceso a edificios, parques de diversiones, y otros.

Un torniquete es un semáforo que detiene a todos los hilos que lleguen a él. Pero apenas un hilo logre pasarlo, inmediatamente habilita el paso al siguiente. Puede pensarse como una manera más elegante de que el último hilo que llega a la barrera haga un ciclo de incrementos por todos los demás.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19 procedure main:
  ...
  // Stops all threads, but the first one that passess it passess the rest
  shared turnstile := create_semaphore(0)
  ...
end procedure

procedure secondary:
  while true do
    Statement A
    ...
    // Use turnstile
    wait(turnstile)
    signal(turnstile)
    ...
    // Statement B can be only executed until all threads have run Statement A
    Statement B
  end while
end procedure

Tabla 22. Barrera reusable con semáforos [sem_barrier_reusable]
Archivo	Descripción	Cambios
sem_barrier_reusable.pseudo	Usa dos torniquetes (trompos) para evitar que hilos de ejecución ávidos salgan de la barrera y vuelvan a ingresar a ella antes que otros hayan salido.

La solución a este problema permite reutilizar barreras. Por ejemplo, se puede crear una interfaz como la siguiente:

Tabla 23. Interfaz barrera reusable con semáforos [sem_barrier_reusable]
Archivo	Descripción
sem_barrier_include.pseudo	Pseudocódigo que convierte la barrera en código reusable.

Para la solución de nuevos problemas se puede suponer que se tiene disponible barreras con la siguiente interfaz:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10 procedure main:
	shared my_barrier := create_barrier(3)
	...
end procedure

procedure secondary:
	...
	wait(my_barrier)
	...
end procedure

2.2.6. Carrera de relevos (barrera)

Actividad 22. Carrera con relevos [relay_race]

Simule una carrera de relevos, donde los competidores son equipos de threads. Cada equipo consta de dos corredores. Un corredor tomará la estafeta (en inglés, baton) y se posicionará en la línea de salida. El otro corredor esperará en la mitad de la pista a que el primer corredor llegue y le transfiera la estafeta. En tal momento, el segundo corredor seguirá a toda velocidad hasta alcanzar la meta. Ganan únicamente los tres primeros equipos en llegar con la estafeta a la meta, quienes son premiados con oro, plata, y bronce.

Su simulación recibirá tres parámetros: la cantidad de equipos, la duración en milisegundos que tarda el primer corredor atravesando la etapa 1 de la carrera (entre la salida y la mitdad de la pista), y la duración en milisegundos del segundo corredor atravesando la etapa 2 de la carrera (de la mitad de la pista hasta la meta). Suponga que los corredores de una etapa tardan exactamente esta duración y no un valor generado al azar. Ejemplo de ejecución:

./relay_race 10 300 700
Place 1: team 2
Place 2: team 4
Place 3: team 1
Simulation time: 1.006079000s

En la salida anterior se reportan sólo los tres primeros equipos en llegar. Recuerde verificar la corrección de su solución (ej.: fugas de memoria, condiciones de carrera). Puede usar el siguiente código como punto de partida.

Archivo	Descripción
relay_race.pseudo	Pseudocódigo inicial para la carrera de relevos.
relay_race.c	Código en C con Pthreads inicial para la carrera de relevos.

Archivo

Descripción

relay_race.pseudo

Pseudocódigo inicial para la carrera de relevos.

relay_race.c

Código en C con Pthreads inicial para la carrera de relevos.

Tabla 24. Carrera con relevos [relay_race]
Archivo	Descripción	Cambios
relay_race.svg	Diseño de la simulación de carrera de relevos usando metáforas visuales.
relay_race.pseudo	Diseño en pseudocódigo de la simulación de carrera de relevos con equipos de hilos de ejecución.
relay_race.c	Implementación con Pthreads de la simulación de la carrera de relevos.
Makefile	Facilita la construcción y prueba de la la solución.

Ejercicio 18 [relay_race_order_effect]

¿Afecta el orden de creación de los equipos el resultado de la carrera de relevos? Modifique su solución de la Actividad 22 para crear los equipos en orden inverso y compare los resultados de las ejecuciones. Sugerencia: no duplique el código, sino que utilice metaprogramación (#ifdef…) para escoger en tiempo de compilación el orden de creación de los equipos.

2.2.7. Misterio (variable de condición)

Actividad 23. Misterio (variable de condición) [mist_cond_var]

Rastree la memoria y el procesamiento del siguiente programa en una copia de esta hoja de cálculo, la cual tiene precargado el programa. Exporte el rastreo a un PDF y agréguelo a su repositorio de ejemplos. ¿Qué trabajo realiza la función mistery()?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63 #include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

typedef struct {
  unsigned int counter;
  unsigned int max;
  pthread_mutex_t mutex;
  pthread_cond_t cond_var;
} mist_t;

void mist_init(mist_t* mist, unsigned max) {
  mist->counter = 0;
  mist->max = max;
  pthread_mutex_init(&mist->mutex, NULL);
  pthread_cond_init(&mist->cond_var, NULL);
}

void mist_destroy(mist_t* mist) {
  mist->counter = 0;
  pthread_mutex_destroy(&mist->mutex);
  pthread_cond_destroy(&mist->cond_var);
}

void mistery(mist_t* mist) {
  pthread_mutex_lock(&mist->mutex);
  ++mist->counter;
  if (mist->counter < mist->max) {
    // Preferred: while ( pthread_cond_wait(...) != 0 ) /* empty */;
    pthread_cond_wait(&mist->cond_var, &mist->mutex);
  } else {
    mist->counter = 0;
    pthread_cond_broadcast(&mist->cond_var);
  }
  pthread_mutex_unlock(&mist->mutex);
}

static mist_t mist;

void* run(void* data) {
  fprintf(stderr, "%zu: before mist()\n", (size_t)data);
  sleep((unsigned)(size_t)data);
  mistery(&mist);
  fprintf(stderr, "%zu: after mist()\n", (size_t)data);
  return NULL;
}

int main() {
  mist_init(&mist, 3);

  pthread_t* workers = malloc(3 * sizeof(pthread_t));
  for (size_t index = 0; index < 3; ++index) {
    pthread_create(&workers[index], NULL, run, (void*)index);
  }

  for (size_t index = 0; index < 3; ++index) {
    pthread_join(workers[index], NULL);
  }

  mist_destroy(&mist);
  return 0;
}

Tabla 25. Misterio (variable de condición) [mist_cond_var]
Archivo	Descripción	Cambios
mist_cond_var.pdf	Rastreo de procesamiento en una hoja de cálculo del código misterio.

2.3. Filósofos comensales

En 1965 Edsger Dijkstra planteó el problema de los filósofos comensales como un ejercicio de un examen para estudiantes. Posteriormente Tony Hoare lo reformuló y se convirtió en un problema clásico de sincronización de procesos en los cursos de sistemas operativos. Existen varias adaptaciones como la que se muestra a continuación considerando algunos aspectos de higiene.

Cinco filósofos, que representan procesos o hilos de ejecución, están sentados a una mesa circular (Figura 5). Los filósofos en silencio piensan y luego comen, y repiten esta rutina eternamente. Ante cada filósofo se encuentra un plato, y al centro de la mesa un tazón con infinito abastecimiento de espagueti. Este abastecimiento representa un recurso compartido, como una cinta magnética en el problema original.

Figura 5. Filósofos comensales

Para poder comer espagueti, en la mesa están dispuestos cinco tenedores (forks) o palillos chinos en el problema original (chopstiks). Tanto los filósofos como los palillos están enumerados de 0 a 4 como se ve en la figura Figura 5. Para poder comer, un filósofo i necesita los dos palillos (get chopstick), uno a su mano izquierda (i + 1) y el otro a su mano derecha (i), y no los comparte mientras está comiendo. Una vez que haya terminado de comer, el filósofo lava los tenedores y los coloca de regreso en sus posiciones en la mesa (put chopstick). Un filósofo nunca sabe cuándo otro va a comer o pensar.

El reto es construir un algoritmo que permita a los filósofos eternamente pensar y comer que cumpla los siguientes tres requerimientos:

Los filósofos no se detengan de pensar y comer (bloqueo mutuo o deadlock).
Ningún filósofo muera de hambre esperando por un palillo (inanición o starvation).
Dos o más filósofos puedan comer al mismo tiempo (concurrency).

Los filósofos ya saben cómo realizar las operaciones de pensar think() y comer eat(), ninguna de las dos dura eternamente, y se debe detener a un filósofo mientras las realiza.

Actividad 24. Filósofos comensales [dining_philosophers]

Corrija el siguiente pseudocódigo de concurrencia de recursos compartidos para que resuelva el problema de los filósofos comensales, y por lo tanto, logre cumplir con los tres requerimientos.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34 procedure main(argc, argv[]):
  shared chopsticks[] := create_semaphores(5, 1)

  for id := 0 to 5 do
    create_thread(philosopher, id)
  end for
end procedure

procedure philosopher(id):
  while true do
    think()
    get_left_chopstick(id)
    get_right_chopstick(id)
    eat()
    put_left_chopstick(id)
    put_right_chopstick(id)
  end while
end procedure

procedure get_left_chopstick(id):
  wait(chopsticks[(id + 1) mod 5])
end procedure

procedure get_right_chopstick(id):
  wait(chopsticks[id])
end procedure

procedure put_left_chopstick(id):
  signal(chopsticks[(id + 1) mod 5])
end procedure

procedure put_right_chopstick(id):
  signal(chopsticks[id])
end procedure

Considere las condiciones que son necesarias para que el bloqueo mutuo o la inanición ocurran, y cambie una de ellas a la vez para generar distintas soluciones:

Considere la lateralidad de los filósofos.
Considere la cantidad de filósofos que pueden comer concurrentemente.
Haga que los filósofos decidan con variables protegidas con exclusión mutua.

Tabla 26. Filósofos comensales [dining_philosophers]
Archivo	Descripción	Cambios
dining_philosophers_laterality.pseudo	Solución 1: No todos los filósofos tienen la misma lateralidad
dining_philosophers_quota.pseudo	Solución 2: Hay una cuota o límite (de 4) en la cantidad de filósofos que pueden intentar comer al mismo tiempo, implementada por un multiplex
dining_philosophers.pnml	Red de petri que impide el bloqueo mutuo de los filósofos comensales, pero no la inanición.

Ejercicio 19 [dining_philosophers_dist]

Idee una solución distribuida, y por lo tanto, mediante paso de mensajes, al problema de los filósofos comensales. Su solución puede ser:

Centralizada, por ejemplo, con un proceso que toma el rol de mesero (árbitro).
Descentralizada, donde los filósofos se ponen de acuerdo entre ellos para determinar quién come y quien espera en caso de conflicto por los palillos.

Ejercicio 20 [dining_philosophers_n]

El problema de los filósofos comensales original considera 5 filósofos. Generalice su solución para que permita que una cantidad arbitraria de n ≥ 1 filósofos pensar y comer con max(n, 2) palillos. Su solución debe cumplir los requerimientos del problema.

Ejercicio 21 [dining_philosophers_impl]

Implemente las soluciones que haya diseñado al problema de los filósofos comensales en alguna tecnología concurrente. Permita que el usuario especifique el rango mínimo y máximo de tiempo en milisegundos para pensar y comer. Haga impresiones cuando los filósofos piensan y comen tras una espera de duración aleatoria en el rango dado. Ejecute su solución para determinar que resuelve el problema.

2.4. Lectores y escritores (candado de lectura-escritura)

El problema de los lectores y escritores es de mucha importancia en la disciplina de la computación porque ocurre en varios escenarios, como sistemas operativos y bases de datos.

Actividad 25. Lectores y escritores [readers_writers]

Permita que varios lectores puedan leer de un medio común, pero sólo un escritor puede modificarlo a la vez. Por cada letra R que se lea de la entrada estándar se crea un hilo lector (reader), y por cada W que se lea de la entrada estándar se crea un hilo escritor (writer). Varios hilos pueden invocar la función read() al mismo tiempo, pero sólo un único hilo puede invocar write() a la vez. Esta puede considerarse una exlusión mutua categórica (categorical mutual exclusion) porque permite paralelismo de una categoría de hilos, pero excluye los de otra.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17 procedure main:
  while true:
    case read_char() of:
      'R': create_thread(reader)
      'W': create_thread(writer)
      EOF: return
    end case
  end while
end procedure

procedure reader:
  read()
end procedure

procedure writer:
  write()
end procedure

Tabla 27. Lectores y escritores [readers_writers]
Archivo	Descripción	Cambios
readers_writers.pseudo	Diseño en pseudocódigo de la solución.

Ejercicio 22 [readers_writers]

Implemente su diseño al problema Actividad 25 usando semáforos en Pthreads u otra tecnología. Asegúrese de que su implementación genera los resultados deseados y no provoca anomalías de memoria ni de concurrencia.

Actividad 26. Candados de lectura y escritura [readers_writers_rwlock]

Implemente una solución al problema de los lectores y escritores usando candados de lectura y escritura de Pthreads. Los escritores escriben en un contador compartido, y los lectores reportan el valor leído. Recuerde que varios lectores pueden trabajar al mismo tiempo mientras que en escritor necesita acceso exclusivo al recurso compartido. Su código no debe producir anomalías de memoria ni concurrencia. Puede usar el siguiente código como punto de partida.

Archivos	Descripción
readers_writers_rwlock.7z	Contiene a los demás archivos
readers_writers_rwlock.c	Código inicial para la solución a los lectores y escritores con candados de lectura y escritura
Makefile	Makefile para facilitar la construcción de la solución con Pthreads
input001.txt input002.txt	Casos de prueba de ejemplo

Archivos

Descripción

readers_writers_rwlock.7z

Contiene a los demás archivos

readers_writers_rwlock.c

Código inicial para la solución a los lectores y escritores con candados de lectura y escritura

Makefile

Makefile para facilitar la construcción de la solución con Pthreads

input001.txt
input002.txt

Casos de prueba de ejemplo

Tabla 28. Candados de lectura y escritura [readers_writers_rwlock]
Archivo	Descripción	Cambios
readers_writers_rwlock.c	Los candados de lectura y escritura de Pthreads (`pthread_rwlock_t`) tienen una interfaz similiar a un mutex con la diferencia de que tienen dos operaciones de decremento: `pthread_rwlock_rdlock()` para los hilos que pretenden leer del medio y `pthread_rwlock_wrlock()` para quienes pretenden modificarlo.
Makefile	Facilita la construcción y prueba de la la solución.
input001.txt input002.txt	Casos de prueba de ejemplo. Son parte del código inicial dado.

2.5. Reentrante vs thread-safe

Actividad 27. Azar reentrante [reentrant_rand]

Modifique la siguiente implementación del generador lineal congruencial de números pseudoaleatorios para que sea:

Thread-safe
Reentrante y thread-safe

Archivos	Descripción
reentrant_rand.c	Generación de números aleatorios que no es ni reentrante ni thread-safe
Makefile	Makefile para facilitar la construcción de la solución con Pthreads

Archivos

Descripción

reentrant_rand.c

Generación de números aleatorios que no es ni reentrante ni thread-safe

Makefile

Makefile para facilitar la construcción de la solución con Pthreads

Ejercicio 23 [array_reentrant]

Haga que la siguiente implementación de un arreglo dinámico en C sea reentrante. Asegúrese de que produzca la salida esperada y no genere fugas de memoria ni accesos inválidos (con valgrind o sanitizers):

Descargar Arreglo dinámico versión 1

Ejercicio 24 [array_thrsafe_mutex]

Modifique su arreglo dinámico en C para que sea thread-safe. Proteja la implementación de cada subrutina pública con un mutex. Note que las subrutinas para incrementar y reducir la capacidad son privadas (no están declaradas en el encabezado .h). El mutex debe ser único para cada instancia de un arreglo, es decir, dos instancias del arreglo no comparten el mismo mutex.

Su implementación debe permitir al siguiente código de prueba correr correctamente sin generar fugas de memoria, accesos inválidos ni condiciones de carrera:

array_thrsafe_mutex/main.c

Ejercicio 25 [array_thrsafe_rwlock]

Provea una segunda implementación thread-safe de su arreglo dinámico en C. Provea un candado de lectura y escritura (pthread_rwlock_t) para cada instancia del arreglo dinámico. Proteja el código de cada subrutina que no modifica el arreglo bloqueando el candado para lectura. De la misma forma proteja el código de cada subrutina que modifica bloqueando el candado para escritura.

Su implementación debe permitir al código de prueba del ejercicio anterior correr correctamente sin generar fugas de memoria, accesos inválidos ni condiciones de carrera:

Ejercicio 26 [array_thrsafe_perf]

Copie sus dos implementaciones del arreglo dinámico thread-safe de los dos ejercicios anteriores a la carpeta array_thrsafe_perf. Renombre los símbolos y archivos de la implementación con mutex del prefijo array_ por array_mutex_ y la implementación con candados de lectura y escritura para iniciar con el prefijo array_rwlock_. De esta forma, las dos implementaciones pueden coexistir en un mismo ejecutable. Para probarlas puede usar el siguiente programa:

array_thrsafe_perf/main.c

El programa de pruebas anterior recibe siete argumentos en la línea de comandos:

La cantidad inicial de elementos en el arreglo (size_t).
La cantidad de operaciones a realizar en el arreglo (size_t).
El porcentaje de operaciones que son inserciones en el arreglo (double).
El porcentaje de operaciones que son eliminaciones en el arreglo (double).
El porcentaje de operaciones que son búsquedas en el arreglo (double).
La cantidad de trabajadores (threads) a probar (size_t).
El arreglo a probar ("mutex" o "rwlock").

De acuerdo al último argumento, el hilo principal crea un arreglo thread-safe protegido por un mutex o por un candado de lectura-escritura (rwlock). Luego el hilo principal inserta la cantidad inicial (primer argumento) de elementos aleatorios en el arreglo.

Luego el programa lanza la cantidad de hilos indicada en el sexto argumento. Los hilos se reparten la cantidad de operaciones indicada en el segundo argumento. Cada hilo procura distribuir sus operaciones sobre el arreglo de acuerdo a los porcentajes dados en los argumentos tres a seis. Los hilos escogen estas operaciones al azar, sin ningún orden definido.

Verifique que el programarealice las operaciones sin fugas de memoria o accesos inválidos. Haga varias corridas para replicar los experimentos de (Pacheco 2011 pp.188-9). Con la herramienta gprof (si lo prefiere puede usar perf) mida la duración de cada corrida.

Para ambos experimentos cree arreglos con 1000 elementos iniciales y realice un millón de operaciones con 1 hilo, 1xCPU, 2xCPU, y 4xCPU, donde CPU es la cantidad de CPU disponibles en la máquina donde realiza las pruebas. En el primer experimento realice 10% de inserciones, 10% de eliminaciones, y 80% de búsquedas en el arreglo. Para el segundo experimento realice 0.1% de inserciones, 0.1% de eliminaciones, y 99.8% de búsquedas. Anote las duraciones de cada corrida en una hoja de cálculo con la siguiente estructura:

Tabla 29. Duraciones
		threads
distribution	array	1 thread	1xCPU	2xCPU	4xCPU
10-10-80	mutex
10-10-80	rwlock
.1-.1-99.8	mutex
.1-.1-99.8	rwlock

Elabore en su hoja de cálculo un gráfico con cuatro series (una por cada fila) que permita comparar el rendimiento de los mutex contra los candados de lectura-escritura (rwlock). ¿En qué circustancia recomendaría usted usar candados de lectura y escritura? Responda con un comentario en la celda "rwlock" correspondiente.

2.6. Otros problemas de sincronización

2.6.1. Formar agua

Este problema aparentemente está basado en un ejercicio de libro de programación concurrente de Gregory Andrews, y popularizado en el curso de sistemas operativos de la Universidad de California en Berkeley.

Actividad 28. Formar agua [build_h2o]

Hay dos tipos de hilos: los de hidrógeno y los de oxígeno. Su objetivo es formar agua con ellos. Usted dispone de un dispositivo, que cuando se coloca en él dos átomos de hidrógeno y uno de oxígeno, y se invoca bond() en cada uno de ellos, se forma agua. El dispositivo no funciona en cualquier otra combinación de átomos.

El dispositivo sólo puede trabajar en una molécula a la vez. Es decir, usted debe garantizar que los tres átomos de una molécula invoquen bond() antes de los hilos de la siguiente molécula. Escriba el código para cada átomo que garantice este comportamiento. Puede tomar el siguiente pseudocódigo como punto de partida.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17 procedure main:
  while true do
    case read_char() of
      'H': create_thread(hydrogen)
      'O': create_thread(oxygen)
      EOF: return
    end case
  end while
end procedure

procedure hydrogen:
  bond()
end procedure

procedure oxygen:
  bond()
end procedure

Tabla 30. Formar agua [build_h2o]
Archivo	Descripción	Cambios
build_h2o.pseudo 🖼	Solución propuesta por Jeisson Hidalgo. Utiliza multiplex y una barrera.

2.6.2. Parejas de baile (colas con semáforos)

Actividad 29. Parejas de baile (parte 1) [dancing_pairs_1]

En una academia de artes los aprendices están entrenando bailes criollos, los cuales se bailan en parejas de un hombre con una mujer. Como es natural, los bailarines no llegan todos al mismo tiempo al salón, sino que cuando se aproximan hacen dos grupos o filas, una de hombres y otra de mujeres. Cuando en ambas filas hay personas, un hombre y una mujer se toman de la mano e ingresan al salón de baile.

Naturalmente si una o varias mujeres llegan a la fila y la fila de hombres está vacía, tendrán que esperar. Lo mismo ocurre si los hombres llegan y encuentran la fila de mujeres vacía. Simule con threads a los bailarines, su espera en las colas, y el ingreso al salón de baile (subrutina dance()). Suponga que los bailarines se leen de la entrada estándar donde W indica una mujer y M un hombre como muestra el siguiente código. Suponga además que el salón tiene capacidad ilimitada para el número de parejas.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12 main:
	while true:
		case read_char() of:
			'M': create_thread(male)
			'W': create_thread(female)
			EOF: return

male:
	dance()

female:
	dance()

Sugerencia. Un semáforo puede representar una cola de espera. Un valor inicial de 0 indica que la cola está vacía. Un valor negativo indica la cantidad de threads esperando en ella.

Actividad 30. Parejas de baile (parte 2) [dancing_pairs_2]

Si es necesario, modifique su solución al problema Actividad 29 para asegurarse de que realmente los bailarines entren en pareja al salón de baile. Es decir, que un hombre invoque dance() concurrentemente con una única mujer y viceversa. Suponga que se trata de un examen o audición, y por tanto, sólo una pareja puede estar en el salón de baile a la vez con el fin de que el jurado pueda calificarlos.

Ejercicio 27 [dancing_pairs_3]

Modifique su solución al problema Actividad 30 para asegurarse que los bailarines entren en pareja al salón de baile, el cual tiene capacidad ilimitada para la cantidad de parejas.

Ejercicio 28 [dancing_pairs_4]

Modifique su solución al problema Ejercicio 27 [dancing_pairs_3] para asegurarse que los bailarines entren en pareja al salón de baile, el cual tiene una capacidad limitada para la cantidad de parejas dada en la entrada estándar.

Si el salón está lleno, las nuevas parejas deberán esperar a que se libere espacio. Las parejas en el salón bailan hasta cansarse. Para cada bailarín genere un número pseudoaleatorio que indica la cantidad de minutos que baila. Cuando se conforma una pareja, bailarán por el mínimo de minutos de sus integrantes.

Ejercicio 29 [dancing_pairs_5]

Modifique su solución al problema Ejercicio 28 [dancing_pairs_4] para que las parejas, después de bailar en el salón, retornen a la sala de espera. Una vez en la sala de espera, la pareja se disuelve y los integrantes pueden hacer pareja con otros, como si llegaran al salón por primera vez.

Reciba en la entrada estándar la cantidad mínima de minutos que un bailarín deberá estar en la pista de baile. En el momento en que todos los bailarines hayan cumplido este tiempo, la simulación termina.

Ejercicio 30 [dancing_pairs_6]

Modifique su solución al problema Ejercicio 29 [dancing_pairs_5] para un baile criollo donde se forman, no parejas, sino equipos de 4 bailarines compuestos de dos hombres y dos mujeres.

2.6.3. Fumadores de cigarrillos

Originalmente presentado por Suhas Patil. Participan cuatro hilos:

Un agente que representa un sistema operativo que asigna recursos.
Tres fumadores que representan aplicaciones que necesitan los recursos para realizar su labor.

Los cuatro hilos están en un ciclo infinito. Los fumadores esperan por tres ingredientes que representan los recursos: papel, tabaco, y fósforos. Una vez que obtienen los tres ingredientes pueden fabricar un cigarrillo y fumarlo.

El agente tiene un suminitro infinito de todos los tres ingredientes, y cada fumador tiene un suministro infinito de uno de los tres ingredientes. Es decir, un fumador tiene sólo papel, otro tiene sólo tabaco, y el tercero tiene sólo fósforos. Sin embargo, los fumadores no se comunican entre ellos.

El agente repetidamente escoge dos ingredientes al azar y los hace disponible a los fumadores. El fumador con el tercer ingrediente debería recoger los dos disponibles y fabricar su cigarrillo. Por ejemplo, si el agente provee papel y tabaco, el fumador que tiene fósforos debería recogerlos y avisarle al agente que ya puede sacar otros dos ingredientes.

El reto de la solución es permitir a las aplicaciones, que cuentan con los recursos que necesitan, correr concurrentemente, y evitar despertar una aplicación que no puede proceder. Usted tiene el rol de un desarrollador de aplicaciones, quien no puede modificar el código del agente (sistema operativo). Esta es una restricción realista, dado que no se modifica el sistema operativo cada vez que alguien desarrolla una aplicación para el usuario.

El siguiente pseudocódigo provee la implementación del agente, el cual delega trabajo en sub-agentes que proveen los materiales. Se provee una implementación intuitiva para cada fumador. ¿Qué problema presenta esta solución?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59 main:
	shared agent_sem := semaphore(1)
	shared match := semaphore(0)
	shared paper := semaphore(0)
	shared tobacco := semaphore(0)

	create_thread(agent)
	create_thread(smoker_with_matches)
	create_thread(smoker_with_paper)
	create_thread(smoker_with_tobacco)


agent:
	create_thread(agent_without_matches)
	create_thread(agent_without_paper)
	create_thread(agent_without_tobacco)

agent_without_matches:
	while true do
		wait(agent_sem)
		signal(paper)
		signal(tobacco)

agent_without_paper:
	while true do
		wait(agent_sem)
		signal(match)
		signal(tobacco)

agent_without_tobacco:
	while true do
		wait(agent_sem)
		signal(match)
		signal(paper)


smoker_with_matches:
	while true do
		wait(paper)
		wait(tobacco)
		make_cigarette()
		signal(agent_sem)
		smoke()

smoker_with_paper:
	while true do
		wait(match)
		wait(tobacco)
		make_cigarette()
		signal(agent_sem)
		smoke()

smoker_with_tobacco:
	while true do
		wait(match)
		wait(paper)
		make_cigarette()
		signal(agent_sem)
		smoke()

Actividad 31. Fumadores de cigarrillos [cigarette_smokers]

Corrija el pseudocódigo dado para que los agentes y fumadores logren su objetivo.

Sugerencia. La solución propuesta por Parnas usa tres hilos asistentes llamados pushers que responden a los avisos (signal) del agente, llevan cuenta de los ingredientes disponibles, y avisaan al fumador apropiado. Esta solución agrega las siguientes variables al código provisto:

1
2
3
4
5
6
7
8
9 main:
	shared mutex := semaphore(1)
	shared is_match := false
	shared is_paper := false
	shared is_tobacco := false

	shared match_sem := semaphore(0)
	shared paper_sem := semaphore(0)
	shared tobacco_sem := semaphore(0)

Las variables booleanas indican si un ingrediente está o no disponible en la mesa. Los pushers usan los semáforos con nombre de ingrediente para avisar al fumador con tal ingrediente que los ingredientes complementarios están disponibles.

3. Paralelismo de datos

3.1. Optimización

La optimización es una etapa normalmente opcional del proceso de resolución de problemas (Figura 6), que surge cuando las implementaciones no logran satisfacer los requerimientos de eficiencia de los usuarios. Consiste regresar a la fase de diseño, y encontrar un modelo solución más eficiente. Este modelo típicamente es más elaborado, complejo, con un efecto de hacer más difícil de comprender al código o hacerlo más dependiente de un contexto, por lo que debe tenerse el cuidado de que exista un retorno de la inversión. Resulta muy apremiante realizar esta fase del proceso de resolución de problemas de forma sistemática, por lo que se propone un método para optimizar del Método sugerido para optimizar.

Figura 6. Fase de optimización en el proceso de resolución de problemas

Método sugerido para optimizar

Medir el rendimiento del código antes de realizar las modificaciones.
Analizar el código para detectar las regiones críticas a optimizar (profiling).
Hacer las modificaciones que se cree incrementarán el rendimiento en las regiones críticas.
Asegurarse de que las modificaciones sean correctas (correr el programa de pruebas).
Medir el rendimiento del código después de realizar las modificaciones y comparar para determinar si hubo una ganancia.
Indiferentemente de si se incrementó o no el rendimiento, documentar las lecciones aprendidas, ya que servirán para otros desarrolladores que intenten optimizar la misma sección de código.
Si es realmente requerido incrementar aún más el rendimiento, repetir desde el paso 2.

3.2. Profiling

Para encontrar regiones de código que podrían ser optimizadas por su alto consumo de recursos se puede usar una herramienta de profiling. Estas herramientas proveen análisis dinámico de código ejecutable con fines de optimización. Algunos ejemplos son Callgrind y perf.

3.2.1. Callgrind

Callgrind es una herramienta que forma parte de Valgrind. Conviene incrustar el código fuente al compilar el ejecutable para obtener información más contextualiazada, como muestran los siguientes comandos.

# Install tools
sudo apt install build-essential valgrind kcachegrind

# Compile executable including its source code
cc -g -Wall -Wextra source.c -o executable -pthread

# Run the program under callgrind
valgrind --tool=callgrind --separate-threads=yes ./executable args_for_executable

# Visualize the data collected by callgrind in the current directory
kcachegrind &

Callgrind realiza contabilidad de invocaciones de subrutinas y cantidad de instrucciones ejecutadas. Se requiere incluir el código fuente dentro del ejecutable al compilar el programa. Luego se corre el programa con callgrind, el cual crea archivos en la carpeta donde se invoca con nombres como callgrind.PID-TH donde PID es el número de proceso y TH el número de hilo, si se pide separar las estadísticas de cada hilo ejecutado por el programa. Finalmente se requiere un programa de visualización que tome las estadísticas almacenadas en los archivos y los presente de forma que ayude a las personas a comprender el comportamiento del programa, como KCachegrind (en algunas distribuciones de Linux podría llamarse qcachegrind).

Figura 7. Visualización de KCachegrind de las líneas que consumen más procesamiento

KCachegrind permite encontrar rápida y visualmente las líneas de código fuente que consumen más instrucciones de procesador, y por tanto, las líneas críticas que convienen optimizar, incluso en una base de código extensa. En la esquina superior izquierda de la Figura 7 muestra un gráfico de consumo por cada hilo de ejecución. En la esquina inferior izquierda muestra las subrutinas que han ejecutado más instrucciones de procesador en porcentajes, isPrime() está seleccionada. En la esquina superior derecha se muestra las líneas de código fuente de isPrime() que consumieron más instrucciones. Se puede ver la invocación a qSqrt() y el operador módulo (%) son los que causan casi la totalidad del procesamiento. Estos son los puntos críticos a optimizar para esta aplicación.

Actividad 32. Marcar la cerca [fence_profiling]

Suponga que se le contrata para optimizar una solución a un problema que debe encontrar el perímetro mayor para marcar una cerca en mapas. Ya existe una solución serial disponible en la carpeta fence/.

Encuentre las regiones de código que consumen mayor procesamiento y podrían ser las prioritarias de paralelizar. Use una herramienta de profiling para este fin.

Ejercicio 31 [fence_parallelization]

Diseñe una solución paralela al problema de marcar la cerca de la Actividad 32. Implemente una solución en C o C++ paralelizada. Compruebe que realmente obtuvo un incremento del desempeño.

3.2.2. Gprof

Gprof es una herramienta que reporta el tiempo de pared que toma cada invocación de subrutina. Los siguientes comandos resumen el uso de gprof:

# Compile a modified executable that measures function call durations
gcc -g -Wall -Wextra -pg -no-pie source.c -o executable

# Run the executable as usual, it will generate binary file gmon.out
./executable args

# Generate a report from the gmon.out binary log
gprof ./executable gmon.out > report.txt

3.2.3. Perf

La herramienta perf permite realizar variedad de análisis de rendimiento de los programas, sin afectar su tiempo de ejecución. Tampoco requiere modificar o recompilar el ejecutable en estudio. Es capaz de reportar las funciones que consumen más CPU, generar gráficos de uso de CPU, entre otras operaciones. Para obtener la duración total que tarda un programa se usa la acción stat de la forma:

perf stat ./executable args

Para que perf pueda monitorear otros programas, puede requerir darle permisos o configurar el sistema operativo para disminuir el nivel de seguridad del sistema. Este paso varía mucho de un sistema operativo a otro. En Debian algunos o todos los siguientes comandos -que requieren permisos de administración- podrían ser suficientes.

# Install linux-perf:
apt install linux-perf

echo kernel.perf_event_paranoid=1 > /etc/sysctl.d/local.conf

echo 1 >/proc/sys/kernel/perf_event_paranoid

3.3. Descomposición

En un problema, la descomposición es identificar las tareas o unidades de trabajo que se pueden realizar de forma independiente, y por lo tanto, de forma paralela. Una vez definidas, las tareas se consideran unidades indivisibles de computación. Es seguido por el mapeo, que consiste en asignar esas unidades de trabajo a los ejecutantes (procesos o hilos de ejecución). Esta sección resume conceptos teóricos de la descomposición de acuerdo a (Grama, Gupta, Karypis, y Kumar. Introduction to Parallel Computing 2ed, 2003) y el mapeo se estudia en la sección siguiente.

La granularidad (granularity) de la descomposición es la cantidad y tamaño de las tareas en la que un problema es descompuesto, y puede ser:

Granularidad fina (fine-grained) cuando se definen muchas tareas pequeñas. Tiende a incrementar el grado de concurrencia, pero también, la interacción entre tareas (ejecutantes), es decir, compoartir datos, trabajo, o información de sincronización.
Granularidad gruesa (coarse-grained) cuando se definen pocas tareas grandes. Disminuye la interacción entre ejecutantes, pero reduce el grado de concurrencia.

Existen algunas técnicas que pueden emplearse para definir las unidades de descomposición, entre las que se pueden citar:

Descomposición recursiva (recursive decomposition) es una forma de divide y vencerás. Un problema o tarea se divide en subproblemas o subtareas que se pueden realizar de forma concurrente. Cada una de estas se subdividen en otros subproblemas o subtareas y así sucesivamente. Por ejemplo, quicksort es un algoritmo que se puede paralelizar de esta manera. Cada vez que se subdivide el vector en dos, el ejecutante se encarga de un trozo y crea otro ejecutante que se encarga del otro trozo del arreglo.
Descomposición de datos (data-decomposition) se usa con grandes estructuras de datos. Se particiona el conjunto de datos en trozos de aproximadamente igual carga de trabajo. Todos los ejecutantes contribuyen al progreso de la solución, y típicamente obtiene un incremento del desempeño sistemático.
Descomposición exploratoria (exploratory decomposition) se usa con problemas de búsqueda en un espacio de soluciones, el cual se puede particionar para buscar concurrentemente hasta encontrar las soluciones esperadas. Apenas un ejecutante encuentra una o la última solución, avisa a los demás para que todos se detengan. Son ejemplos, el ajedrez o buscar el camino en un laberinto. A diferencia de la descomposición de datos, los ejecutantes podrían no contribuir al progreso de la solución (su partición no contiene solución alguna) y un incremento de desempeño no se comporta de forma sistemática, pues depende de dónde se encuentre la solución en el espacio de búsqueda y cómo se particione éste.
Descomposición especulativa (speculative decomposition) se usa cuando se puede predecir con alguna probabilidad que un evento futuro ocurrirá, y la tarea asociada puede ser ejecutada en forma anticipada y concurrente a la actual. De esta forma si el evento ocurre, su tiempo de ejecución será menor. Por ejemplo, tras una consulta en un buscador web, mientras el navegador carga los resultados, concurrentemene carga la página del primer resultado retornado por el buscador. Si el usuario hace click en el primer resultado, verá casi de forma instantánea la página cargada en el navegador.

Las técnicas anteriores no son las únicas ni son excluyentes. Varias pueden emplearse para resolver problemas complejos, a lo que corresponde una descomposición híbrida (hybrid decomposition).

3.4. Mapeo

La Figura 8 muestra el resultado de la actividad de mapear tres conjuntos de datos de distinta naturaleza, representados como arreglos en fondo celeste. El valor en cada celda celeste significa una unidad de trabajo medida como una potencial duración. Los números sobre el arreglo de fondo celeste indican el índice basado en cero.

Figura 8. Actividad de mapear tres conjuntos de datos a cuatro trabajadores

Debajo de los arreglos celestes en la Figura 8 se anota el número de trabajador que realiza esa unidad de trabajo. El número varía de acuerdo al mapeo. Los mapeos pueden clasificarse en estáticos o dinámicos. En el mapeo estático la asignación de las unidades de trabajo se conoce de antemano, es decir, antes de iniciar el trabajo, sólo depende de conocer el número total de unidades de trabajo y trabajadores. El mapeo por bloque y cíclico son dos formas de mapeo estático. En el mapeo dinámico la asignación ocurre durante la realización del trabajo, es decir, los trabajadores se asignan las unidades de trabajo conforme ellos terminan las previas. Aunque normalmente consigue mejores distribuciones, es más costoso en recursos que los mapeos estáticos, dado que requiere control de concurrencia y manipulación de estructuras de datos dinámicas.

3.4.1. Mapeo por bloque

El mapeo estático por bloque asigna rangos continuos de trabajo a cada trabajador. Es el mapeo que potencialmente puede disminuir más fallos de caché o false sharing si se trabaja con memoria continua. El bloque de un trabajador \$i\$ está dado por el rango de índices enteros \$[\text{start}, \text{finish}[\$, donde \$\text{start}\$ y \$\text{finish}\$ son funciones dadas por

\$\text{start(i,D,w)} = i\lfloor \frac{D}{w} \rfloor + \min(i, \mod(D, w))\$

\$\text{finish(i,D,w)} = \text{start(i + 1,D,w)\$

donde \$i\$ es el número del trabajador (iniciando en 0), \$D\$ es la cantidad de datos, y \$w\$ es la cantidad total de trabajadores.

3.4.2. Mapeo cíclico

El mapeo estático cíclico asigna al trabajador \$i\$ todas las unidades de trabajo con índice \${i,i+w, i+2w, ...}\$. Puede tener ventajas cuando las unidades de datos presentan algún patrón predecible y que no es apto para el mapeo por bloque. Se puede hacer un híbrido del mapeo cíclico por bloque que reparte no una unidad, sino bloques de unidades de trabajo de igual tamaño de forma cíclica a cada trabajador.

3.4.3. Mapeo dinámico

Los algoritmos de mapeo dinámico reparten las unidades de descomposición entre los ejecutantes en tiempo de ejecución. Un principio de diseño que puede seguirse es "cuando un ejecutante se desocupa toma la siguiente unidad de trabajo disponible". Este principio puede implementarse de formas como las siguientes:

Variable de control. Una variable compartida y protegida por exclusión mutua que indica cuál es la próxima unidad de trabajo disponible. Cuando un ejecutante se desocupa, compite por el mutex y cuando lo adquiere, toma la siguiente unidad de trabajo disponible y deja en la variable compartida la unidad que le sigue. Esto se repite hasta que los ejecutantes hayan completado todo el trabajo.
Productor-consumidor. El trabajo se agrega, normalmente por el hilo principal a un buffer (por ejemplo, una cola thread-safe) llamado work pool. Los ejecutantes consumen del buffer y procesan cada unidad de trabajo que extraen. Se debe decidir la forma de detener los consumidores, como usar variables contadoras, cuando el buffer está vacío, o cuando se extrae un valor centinela.
Mapeo dinámico aleatorio. En caso de paso de mensajes o de uso del patrón productor-consumidor, el productor de trabajo lo reparte de forma aleatoria entre los ejecutantes (consumidores).

Ejercicio 32 [mapping_simulation]

Escriba un programa que recibe de la entrada estándar un conjunto de duraciones de trabajo, y como argumento de línea de comandos la cantidad de trabajadores. El programa debe crear tantos hilos como trabajadores se indicaron en los argumentos (o la cantidad de CPUs disponibles si se omite), y repartir el trabajo de la entrada estándar siguiendo los tres tipos principales de mapeo vistos en clase: estático por bloque, estático cíclico, y dinámico.

Los hilos de ejecución reciben el trabajo asignado por el mapeo y simulan que lo realizan mediante una espera (sleep). Suponga que las duraciones están dadas en milisegundos. Cada hilo debe llevar la estadística de la cantidad de trabajo asignado.

Tras realizar las tres simulaciones (una por cada tipo de mapeo), el programa reporta estadísticas en la salida estándar que le ayudarían a un desarrollador a escoger el tipo mapeo más adecuado a un conjunto de datos de interés. La salida del programa puede tener formato de tabla como el sugerido a continuación, el cual sigue la estructura del ejemplo de la sección Section 3.4.

$ echo 1 2 1 3 2 1 1 2 1 3 1 2 2 3 2 2 1 1 2 2 2 2 | ./mapping_simulation 4
39         0    1    2    3 Duration Speedup Efficiency
Block     10   10   10    9    10.00    3.90      0.975
Cyclic     9   12    7   11    12.00    3.25      0.813
Dynamic   10   10   10    9    10.00    3.90      0.975

En la línea de encabezado de la salida 39 es la duración serial (suma de todas las duraciones en la entrada estándar), y 0 a 3 son los números de thread. Los números bajo ellos son las duraciones asignadas (trabajo) de cada hilo. La columna duración indica el tiempo tomado por cada tipo de mapeo (tiempo de pared del mapeo y no el mayor de los hilos). Con esta duración de tiempo de pared se calcula el incremento de velocidad y la eficiencia, respecto a la hipotética versión serial.

Puede aprovechar el siguiente código inicial para implementar su simulación. Primero idee una solución que complete el pseudocódigo provisto. Se requiere implementar los tres tipos de mapeos cuyos procedimientos se encuentran vacíos. Puede agregar código en la subrutina main que puede utilizar en la implementación de los mapeos. Si lo desea puede implementar más de una versión del mapeo dinámico, como: repartir con una variable contadora, usar un buffer thread-safe (cola), y un mapeo dinámico aleatorio.

3.5. Métricas

3.5.1. Incremento de velocidad (speedup)

Para determinar en cada iteración de optimización si hubo realmente una ganancia de rendimiento (pasos 1 y 5 del método sugerido), se puede utilizar varias métricas. La medida relativa speedup \$S\$ (incremento de velocidad), se calcula como la relación entre el tiempo que tarda una computación previa a la optimización (\$T_\text{before}\$), contra el tiempo que tarda la misma computación posterior la optimización (\$T_\text{after}\$):

\$S = \frac{T_\text{before}}{T_\text{after}} = \frac{T_\text{serial}}{T_\text{parallel}}\$

La paralización de código serial es una forma de optimización. Una comparación de incremento de velocidad común es el tiempo de ejecución serial (antes) respecto al tiempo de ejecución posterior a la paralización (después). En este caso, el speedup indica la cantidad de veces que la computación paralela es más rápida que la computación serial. Un valor mayor a 1 indica un incremento de velocidad, 1 que la velocidad se mantiene igual, y un valor menor a 1 un decremento en la velocidad.

3.5.2. Eficiencia

El speedup sólo considera los tiempos de ejecución pero no los recursos que se invirtieron en conseguir el incremento de desempeño. La métrica de eficiencia (\$E\$, efficiency) es una relación entre el incremento de velocidad y la cantidad de trabajadores (\$w\$) que tuvieron que involucrarse para conseguirlo:

\$E = \frac{\text{speedup}}{\text{workers}} = \frac{T_\text{serial}}{T_\text{parallel} \cdot \text{w}}\$

La eficiencia es un valor entre 0 y 1, donde 0 indica un sistema no eficiente, y 1.0 es la eficiencia ideal donde todo el trabajo es realizado en paralelo por los trabajadores, en forma equitativa y sin necesidad de control de concurrencia. Sin embargo, es poco probable que un programa logre una eficiencia de 1.0. Normalmente los programas tienen porciones de código secuencial (por ejemplo, antes de crear los hilos de ejecución, o al usar control de concurrencia como exclusión mutua) y porciones de código paralelo, como ocurre en la línea de tiempo de la Figura 9.

Figura 9. Gráfico de tiempo de un programa con tres fases: serial inicial, paralela, y serial final

3.5.3. Ley de Amdahl

La Ley de Amdahl establece que el máximo speedup que un programa puede alcanzar por paralelización está acotado por la porción del programa que se mantiene o sólo puede ser serial. Por ejemplo, para la Figura 9 la duración total del trabajo si se realizara en forma serial sería \$T_s = 1 + 24 + 1 = 26\$ horas. Si se tuviera una paralelización ideal, la fase paralelizable de 24h se podría repartir entre \$w\$ trabajadores y reducir a \$\frac{24}{w}\$ horas, por ejemplo en la Figura 9 se ilustran \$w = 3\$ trabajadores que reducirían la fase central a \$\frac{24}{3} = 8\$ horas. Por consiguiente la duración total de la versión paralela del programa sería \$2 + \frac{24}{w}\$ horas, y por lo tanto, el incremento de velocidad se obtendría por la relación:

\$S = \frac{T_s}{T_p} = \frac{26}{2 + \frac{24}{w}}\$

Por ejemplo, con \$w = 3\$ trabajadores, el speedup sería \$S = \frac{26}{2 + \frac{24}{3}} = 2.6\$. Con ocho trabajadores se tendría el doble del speedup anterior \$S = 5.2\$. Para maximizar el speedup es natural pensar en incrementar la cantidad de trabajadores \$w\$, procurando que el denominador se acerque a cero. Sin embargo, en caso extremo, cuando \$w\$ tiende a infinito número de trabajadores se obtiene que

\$\lim_{w \to \infty} S = \lim_{w \to \infty} \frac{26}{2 + \frac{24}{w}} = \frac{26}{2 + 0} = 13\$

Es decir, para la situación del programa de la Figura 9, el speedup está acotado a 13. Aunque la Ley de Amdahl puede verse como una limitación negativa al paralelismo, también puede usarse a favor. Si se sabe que para un programa concurrente el speedup máximo es 13, con unos pocos hilos o alquilar unas pocas máquinas en la nube, se podría alcanzar un speedup satisfactorio, en lugar de invertir en recursos costosos que poco incrementarían la velocidad, dado a que está acotada como muestra la Figura 10 para 100 trabajadores.

Figura 10. El incremento de velocidad está acotado por la porción serial de un programa

3.6. Falso compartido (false sharing)

Actividad 33. Arreglo falso compartido [false_sharing_array]

Estudie y ejecute el programa dado en sus cuatro modos, usando los argumentos de línea de comandos 0 a 3. Todos los modos realizan la misma tarea de actualizar dos elementos de un arreglo cien millones de veces. En los modos 0 y 1 los dos elementos se actualizan de forma serial. En los modos 2 y 3 dos hilos concurrentemente actualizan los elementos, como se muestra en la siguiente tabla.

Modo

Tipo

Elemento 1

Elemento 2

Sequencial

El primero del arreglo

El segundo del arreglo

Sequencial

El primero del arreglo

El último del arreglo

Concurrente

El primero del arreglo

El segundo del arreglo

Concurrente

El primero del arreglo

El último del arreglo

Se espera que las versiones seriales tarden aproximadamente lo mismo y que las versiones concurrentes tarden aproximadamente la mitad de las versiones seriales. Sin embargo, esto no ocurre. Trate de explicar por qué.

Archivo Descripción

false_sharing_array.c

Actualiza cien millones de veces dos elementos de un arreglo.

Makefile

Permite compilar y ejecutar la solución. Puede usar make perf para estudiar el comportamiento del programa.

Actividad 34. Registro falso compartido [false_sharing_record]

Estudie y ejecute el programa dado en sus cuatro modos, usando los argumentos de línea de comandos 0 a 3. Todos los modos realizan las mismas tareas: sumar usando un incremento en una variable compartida, e incrementar un contador compartido. En los modos 0 y 1 las dos tareas se realizan de forma serial. En los modos 2 y 3 la suma y el incremento se realizan de forma concurrente, como se muestra en la siguiente tabla.

Modo

Tipo

Tarea 1

Tarea 2

Sequencial

Suma leyendo el incremento compartido

Incrementa el contador compartido

Sequencial

Suma con una copia privada del incremento

Incrementa el contador compartido

Concurrente

Suma leyendo el incremento compartido

Incrementa el contador compartido

Concurrente

Suma con una copia privada del incremento

Incrementa el contador compartido

Se espera que las versiones seriales tarden aproximadamente lo mismo, y que las versiones concurrentes tarden aproximadamente la mitad de las versiones seriales. Sin embargo, esto no ocurre. Trate de explicar por qué.

Archivo Descripción

false_sharing_record.c

Suma leyendo e incrementa escribiendo cien millones de veces los campos de un registro compartido.

Makefile

Permite compilar y ejecutar la solución. Puede usar make perf para estudiar el comportamiento del programa.

3.7. Concurrencia compartida declarativa (OpenMP)

OpenMP (Open Multi-Processing) es una tecnología desarrollada por varias empresas para implementar paralelismo de datos de manera más declarativa, o menos imperativa que Pthreads. No está diseñada para concurrencia de tareas, por ejemplo, no dispone de semáforos. Es una especificación para C/C++ y Fortran que varios compiladores implementan. Conviene tener a mano la guía de referencia al iniciar con esta tecnología. Para los ejemplos de esta sección cree una carpeta openmp/ en su repositorio personal de control de versiones para el curso.

3.7.1. Hola mundo (región paralela, directivas)

El siguiente es un "Hola mundo" en OpenMP. En adelante se usará C++, aunque OpenMP puede usarse perfectamente con C. Considera conceptos como los siguientes:

Instrumentalización de código.
Directivas del preprocesador (pragma): son ignoradas por compiladores en los que no se ha habilitado la instrumentalización.
Región paralela (omp parallel): siempre implica la creación de un equipo de hilos
Barrera o join tras el bloque de instrucciones que conforman la región paralela.
En los Linux OpenMP usa Pthreads internamente. La instrumentalización traslada el código de la región paralela a una rutina, crea hilos con pthread_create(), y espera por ellos con pthread_join().
El hilo principal no puede ejecutar trabajo durante la región paralela, a diferencia de Pthreads.

Tabla 31. Hola mundo en OpenMP [hello]
Archivo	Descripción	Cambios
hello.cpp	Dice "hola mundo" desde hilos secundarios con OpenMP. En esta tecnología el hilo principal sólo crea y espera por los hilos secundarios por lo tanto, no puede realizar otra acción mientras los hilos secundarios están en ejecución.
Makefile	Agrega la bandera `-fopenmp` para habilitar la tecnología OpenMP. Se compara contra el ejemplo de Actividad 22.

Para compilar con GCC o un compilador compatible debe habilitarse instrumentalización de OpenMP con la opción -fopenmp. El Makefile del ejemplo incluye esta bandera:

gcc -g -Wall -Wextra -fopenmp source.c   -o executable
g++ -g -Wall -Wextra -fopenmp source.cpp -o executable

Para poder usar OpenMP con Valgrind (y en algunas circuntancias con Google Sanitizers) es necesario recompilar la biblioteca de OpenMP que viene con el compilador. Es decir, descargar el código fuente del compilador, compilarlo con banderas que indiquen que se quiere habilitar el soporte para Valgrind (o Sanitizers), y posiblemente instalar el compilador en el sistema o hacerlo funcionar en como una alternativa al oficial de la distribución de Linux.

3.7.2. Hola mundo múltiple (funciones de biblioteca)

Actividad 35. Hola mundo múltiple en OpenMP [hello_w]

Modifique el programa de "hola mundo" para que cada hilo de ejecución salude indicando su número y la cantidad de hilos en el equipo al que pertenece. Permita al usuario indicar la cantidad de hilos como argumento de la línea de comandos. Si el usuario omite este argumento, suponga la cantidad de CPUs disponibles en el sistema. La siguiente podría ser una salida hipotética.

Hello from secondary thread 1 of 4
Hello from secondary thread 2 of 4
Hello from secondary thread 0 of 4
Hello from secondary thread 3 of 4

Indague en la especificación cómo obtener el número de CPUs disponibles con OpenMP o bien, la cantidad sugerida de hilos a crear en una región paralela.

Tabla 32. Hola mundo múltiple en OpenMP
Archivo	Descripción	Cambios
hello_w.cpp	Cada hilo secundario saluda diciendo su número en el equipo (team) y la cantidad de miembros en el equipo.
Makefile	Facilita la construcción y prueba de la la solución.

Aunque OpenMP no está diseñado para la concurrencia de tareas, se puede conseguir separación de asuntos asignando a los hilos secundarios tareas distintas de acuerdo a su número de hilo (rank), por ejemplo:

1
2
3
4
5
6
7 #pragma omp parallel num_threads(2)
{
  switch (omp_get_thread_num()) {
    case 0: produce(); break;
    case 1: consume(); break;
  }
}

3.7.3. Repartir las iteraciones (`omp parallel for`)

La directiva omp parallel crea siempre una región paralela, que implica la creación y destrucción (join) de hilos de ejecución (a menos de que esté anidada). La instrucción o bloque paralelizado es ejecutado por todos los hilos del equipo. La directiva omp parallel for siempre debe estar seguida por un ciclo por contador (for) estructurado (sin terminaciones abruptas como break, continue, y return). Por ser una región paralela (por la palabra parallel) también crea y destruye hilos, pero a diferencia de omp parallel, omp parallel for reparte las iteraciones del ciclo entre los hilos creados.

Actividad 36. Repartir las iteraciones [parallel_for]

Modifique el programa de Actividad 35 para repartir iteraciones entre hilos de ejecución. El programa debe permitir al usuario indicar en el segundo argumento opcional de la línea de comandos la cantidad de iteraciones. Si el usuario omite este argumento, tome la cantidad de hilos a crear, de tal forma que cada hilo tenga al menos una iteración con que trabajar.

El programa debe imprimir en la salida estándar el número de hilo y las iteraciones que realizó. Por ejemplo, para repartir 10 iteraciones entre 3 hilos, una salida podría ser:

$ bin/parallel_for 3 10
0/3: iteration 0/10
0/3: iteration 1/10
1/3: iteration 4/10
1/3: iteration 5/10
1/3: iteration 6/10
0/3: iteration 2/10
0/3: iteration 3/10
2/3: iteration 7/10
2/3: iteration 8/10
2/3: iteration 9/10

¿Qué tipo de mapeo aplicó por defecto OpenMP? Como buena práctica de programación, impida que OpenMP escoja automáticamente el tipo de memoria entre datos privados o compartidos (default(none)).

Tabla 33. Parallel-for en OpenMP [parallel_for]
Archivo	Descripción	Cambios
parallel_for.cpp	La directiva `parallel for` siempre define una nueva región paralelizada, y por tanto, que siempre crea una nueva cantidad dada de threads, y entre ellos se reparten las iteraciones de un ciclo por contador. Como cualquier región paralela, al finalizar su ejecución, todos los threads se unen al principal o invocador.
Makefile	Facilita la construcción y prueba de la la solución.

3.7.4. Reutilizar hilos (`omp for`)

Si se tienen varias regiones parallel for una tras otra que utilizan la misma cantidad de hilos, es ineficiente crearlos y destruirlos cada vez que se ingresa y sale de estas secciones, en especial si se encuentran dentro de un ciclo, de ahí la utilidad de la directiva for.

Actividad 37. Reutilizar hilos [several_for]

Modifique el programa de Actividad 36 para realizar tres etapas o fases de iteración. Es decir, tres ciclos for independientes uno tras otro. En cada ciclo se realiza la misma cantidad de iteraciones.

Optimice el programa para reutilizar los hilos. Es decir, en cada ciclo no cree ni destruya hilos, sino que créelos antes del primer ciclo y destrúyalos después del tercer ciclo. En cada ciclo los hilos son reutilizados.

El programa debe imprimir en la salida estándar la etapa en la que se encuentra, el número de hilo y las iteraciones que realizó. Las etapas siempre deben aparecer en orden y separadas entre ellas por un único cambio de línea. Por ejemplo, para repartir 5 iteraciones entre 2 hilos en las tres etapas, una salida podría ser:

$ ./several_for 2 5
stage 1: 0/2: iteration 0/5
stage 1: 1/2: iteration 3/5
stage 1: 1/2: iteration 4/5
stage 1: 0/2: iteration 1/5
stage 1: 0/2: iteration 2/5

stage 2: 1/2: iteration 3/5
stage 2: 1/2: iteration 4/5
stage 2: 0/2: iteration 0/5
stage 2: 0/2: iteration 1/5
stage 2: 0/2: iteration 2/5

stage 3: 1/2: iteration 3/5
stage 3: 1/2: iteration 4/5
stage 3: 0/2: iteration 0/5
stage 3: 0/2: iteration 1/5
stage 3: 0/2: iteration 2/5

Tabla 34. Parallel-for en OpenMP [several_for]
Archivo	Descripción	Cambios
several_for.cpp	La directiva `for` no define una nueva región paralela, y por tanto no crea una nueva cantidad de hilos ni los destruye. La directiva `for` debe estar dentro de una región paralelizada (`parallel` o `parallel for`) y puede repetirse tantas veces como guste. La directiva reparte las iteraciones del ciclo que le sigue entre los hilos que se crearon en la región paralela. Es decir, la directiva `for` reutiliza los hilos de la región paralela. La utilidad de esta directiva es evitar el overhead de crear y destruir hilos entre ciclos `for`, uno tras otro, en un código fuente. Implícitamente cada directiva `omp for` incluye una barrera tras la instrucción o bloque que afecta.
Makefile	Facilita la construcción y prueba de la la solución.

Ejercicio 33 [odd_even_sort_serial]

El siguiente código implementa el ordenamiento par-impar (odd-even transposition sort) de un arreglo a con n elementos. Rastree el algoritmo con el arreglo a = [7 4 6 8 3].

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15 for (int phase = 0; phase < n; ++phase) {
	if (phase % 2 == 0) {
		for (int i = 1; i < n; i += 2) {
			if (a[i - 1] > a[i]) {
				swap(&a[i - 1], &a[i]);
			}
		}
	} else {
		for (int i = 1; i < n - 1; i += 2) {
			if (a[i] > a[i + 1]) {
				swap(&a[i], &a[i + 1]);
			}
		}
	}
}

Implemente una versión serial del ordenamiento par-impar (odd-even transposition sort) en una subrutina serial_odd_even_sort(size_t n, double arr[n]) que ordena un arreglo de números flotantes. Escriba un programa de pruebas main() que reciba por argumentos de línea de comandos el tamaño n del arreglo, crea un arreglo de números flotantes de doble precisión en la memoria dinámica, y los inicializa con valores aleatorios. El programa de pruebas ordena el arreglo con su implementación de serial_odd_even_sort().

Puede imprimir el arreglo en la salida estándar para comprobar que realmente se haya ordenado, pero luego deshabilite la impresión para realizar las pruebas de rendimiento. Veririque que su programa no provoque accesos inválidos, fugas de memoria, ni condiciones de carrera.

Ejercicio 34 [odd_even_sort_parallel_for]

Provea una solución concurrente con OpenMP del ordenamiento par-impar. Conjeture cuál o cuáles ciclos pueden ser paralelizados en este algoritmo de ordenamiento. Utilice la directiva parallel for para paralelizar el o los ciclos. Modifique el programa de pruebas para recibir como segundo argumento de línea de comandos la cantidad de hilos que deben emplearse. Asegúrese que su implementación produce resultados correctos y no genere fugas de memoria.

Ejercicio 35 [odd_even_sort_two_for]

Cree una segunda solución concurrente con OpenMP del ordenamiento par-impar. Cree un equipo de hilos y reutilícelo en él o los for que haya paralelizado. Utilice la directiva for para reutilizar el equipo de hilos. Asegúrese que su implementación produce resultados correctos y no genere fugas de memoria.

Ejercicio 36 [odd_even_sort_perf]

Con la herramienta gprof o perf mida el tiempo de ejecución de su implementación serial, parallel-for, y two-for del algoritmo de ordenamiento par-impar con un millón de elementos. Anote las duraciones obtenidas en una hoja de cálculo, con 1 hilo (1), tantos hilos como la mitad de CPUs disponibles (h) en el sistema, igual a la cantidad de CPUs (C), y dos veces la cantidad de CPUs disponibles (2C) en la máquina donde se realizaron las pruebas.

3.7.5. Descomposición y mapeo en OpenMP (`schedule`)

Actividad 38. Descomposición y mapeo en OpenMP [schedule]

Modifique el programa de Actividad 36 para repartir iteraciones entre hilos usando los tipos de mapeo (scheduling) provistos por OpenMP:

static
static,N
dynamic
dynamic,N
guided
guided,N

Recuerde que el programa debe permitir al usuario indicar la cantidad de hilos y de iteraciones como argumentos opcionales en la línea de comandos. Agregue un tercer parámetro que equivale al número N de la lista de arriba, conocido como el "tamaño de bloque" (chunk en terminología de OpenMP). Si se omite, use el tipo de mapeo sin este parámetro.

Cree un arreglo dinámico de enteros, uno para cada iteración. Haga que los hilos marquen en el arreglo las iteraciones que les fueron asignadas, con su número identificador. Por ejemplo si se reparten 7 iteraciones entre 3 hilos, y si al hilo 2 le correspondieron las iteraciones 5 y 6 establecería

arr[5] := 2
arr[6] := 2

Finalmente el programa debe imprimir en la salida estándar una tabla, con el tipo de mapeo en las filas, las iteraciones en las columnas, y los threads en las celdas. Por ejemplo, para repartir 10 iteraciones entre 3 threads, una salida sin N podría ser:

$ ./schedule 3 10
          0 1 2 3 4 5 6 7 8 9
static    0 0 0 0 1 1 1 2 2 2
dynamic   0 1 0 2 1 0 2 1 0 2
guided    0 0 0 0 1 1 2 2 0 1

La siguiente es una salida hipotética con N=2. Haga más corridas y trate de inferir el algoritmo de mapeo de cada planificación provista por OpenMP.

$ ./schedule 3 10 2
          0 1 2 3 4 5 6 7 8 9
static,2  0 0 1 1 2 2 0 0 1 1
dynamic,2 0 0 1 1 0 0 2 2 1 1
guided,2  0 0 0 0 1 1 2 2 0 0

Tabla 35. Mapeo (scheduling) en OpenMP [schedule]
Archivo	Descripción	Cambios
schedule.cpp	Reparte iteraciones entre hilos y guarda el rastro de qué hilo las ejecutó.
Makefile	Facilita la construcción y prueba de la la solución.

Actividad 39. Mapeo en tiempo de ejecución en OpenMP [runtime_schedule]

Cree una versión reducida de Actividad 38 que escoja el tipo de mapeo (scheduling) en tiempo de ejecución con la variable ambiente OMP_SCHEDULE. Por ejemplo:

$ OMP_SCHEDULE=static bin/runtime_schedule 3 10
runtime    0 0 0 0 1 1 1 2 2 2

$ OMP_SCHEDULE=static,1 bin/runtime_schedule 3 10
runtime    0 1 2 0 1 2 0 1 2 0

Tabla 36. Mapeo en tiempo de ejecución en OpenMP [runtime_schedule]
Archivo	Descripción	Cambios
runtime_schedule.cpp	Escoje el tipo de mapeo en tiempo de ejecución de acuerdo al valor de una variable ambiente
Makefile	Facilita la construcción y prueba de la la solución.

3.7.6. Reducciones (`reduction`)

El paralelismo contribuye en incrementar la velocidad en que la máquina procesa colecciones de datos. Dos operaciones comunes derivadas del paradigma de programación funcional con la transformación de los valores de una colección en otros valores (map), y la reducción de los valores de una colección a uno sólo (reduce).

Actividad 40. Promedio concurrente con control de concurrencia [average_mutex]

Haga un programa que lea un conjunto arbitrario de números flotantes de la entrada estándar, calcule concurrentemente el promedio y lo imprima en la salida estándar. La cantidad de números no se conoce de antemano. Para evitar la condición de carrera, use control de concurrencia (exclusión mutua). Sugerencia: cree primero una versión serial. Mida el rendimiento de una ejecución serial y la concurrente. El siguiente ejemplo de ejecución calcula el promedio de los primeros 10 millones de números.

seq 1 10000000 | perf stat bin/average_mutex

Tabla 37. Promedio concurrente con control de concurrencia [average_mutex]
Archivo	Descripción	Cambios
average_serial.cpp	Calcula el promedio de números leídos de la entrada estándar de forma serial.
average_mutex.cpp	Calcula el promedio de números leídos de la entrada estándar con varios hilos serializados con exclusión mutua. Esta implementación es menos eficiente que la versión serial.
Makefile include.mk	Reutiliza el archivo de `Makefile` con un enlace simbólico y un archivo de inclusión.

Actividad 41. Promedio concurrente con variables privadas [average_private]

La solución al ejemplo anterior tiene una serialización innecesaria provocada por el control de concurrencia para evitar una condición de carrera. Una alternativa es usar seguridad condicional (conditionally safety) ¿Qué diseño propondría usted para aplicar los beneficios de la seguridad condicional a la solución de este problema?

Una forma de crear seguridad condicional es con variables privadas declaradas en la pila de cada hilo de ejecución. Utilice este esquema para calcular sumas parciales. Aplique control de concurrencia para calcular la suma total.

Tabla 38. Promedio concurrente con variables privadas [average_private]
Archivo	Descripción	Cambios
average_private.cpp	Cada hilo calcula su suma parcial en una variable local privada con los elementos del arreglo que le correspondieron. Usa exclusión mutua para agregar su suma parcial a la total.
Makefile	Reutiliza el archivo de `Makefile` mediante una inclusión y sobrescribir una variable.

Actividad 42. Promedio concurrente con operaciones atómicas [average_atomic]

En el ejemplo anterior, la región crítica consta de una operación muy elemental, que los procesadores pueden ejecutar de forma excluyente entre sus núcleos, gracias a las operaciones atómicas en su conjunto de instrucciones. Lenguajes de programación como C11/C++11 disponen de decoraciones para instruir al compilador a usar operaciones atómicas. La tecnología OpenMP también dispone de este constructo. Use operaciones atómicas de OpenMP para reemplazar el control de concurrencia en el cálculo de la suma total.

Tabla 39. Promedio concurrente con operaciones atómicas [average_atomic]
Archivo	Descripción	Cambios
average_atomic.cpp	Usa una operación atómica del procesador que es más eficiente que un mecanismo de control de concurrencia provisto por el sistema operativo.
Makefile	Facilita la construcción y prueba de la la solución.

Actividad 43. Reducciones en OpenMP [average_reduction]

Modifique su solución a Actividad 42 para calcular el promedio de forma paralela usando reducciones de OpenMP. Compare su código resultante con la versión serial original.

Tabla 40. Reducciones en OpenMP [average_reduction]
Archivo	Descripción	Cambios
average_reduction.cpp	Utiliza la notación compacta de las reducciones, que es semejante a la versión serial más una decoración con directivas.
Makefile	Facilita la construcción y prueba de la la solución.

Ejercicio 37 [desc_stats]

Haga un programa que lea un conjunto arbitrario de números flotantes de la entrada estándar, calcule concurrentemente y en una pasada por el arreglo los siguientes estadísticos: valor mínimo, promedio, desviación estándar, y máximo. Imprima cada estadístico en la salida estándar. La cantidad de números no se conoce de antemano. Use reducciones de OpenMP.

Ejercicio 38 [desc_stats_median]

Modifique su solución al problema anterior para agregar la mediana. Imprímala antes del promedio. Indague en su lenguaje de programación cómo ordenar concurrentemente el arreglo.

4. Concurrencia distribuida

El paradigma de programación distribuido permite crear programas escalables que aprovechan máquinas que pueden correr procesos y pueden comunicarse a través de redes de computadoras. Se distingue de la distribución compartida en que los hilos pueden acceder a la misma memoria y comparten el mismo reloj. En la concurrencia distribuida, los procesos tienen cada uno su propia memoria exclusiva y los relojes pueden ser distintos, por lo que tienen que comunicarse a través de paso de mensajes.

Existen dos variantes de la distribución. En la distribución heterogénea, los ambientes en el que corre el programa son distintos: diferente hardware, sistema operativo, huso horario, etc., lo que forma una malla de computadoras. En la distribución homogénea, el ambiente (tanto el hardware como el software) debe ser idéntico para todos los procesos del programa, lo que se llama un clúster de computadoras. La distribución homogénea logra conseguir los mayores niveles de paralelismo.

4.1. Distribución simétrica (MPI)

Message Passing Interface (MPI) es una tecnología de distribución homogénea creado por un grupo de académicos con el fin de facilitar el parelismo de aplicaciones científicas, que se convirtió en un estándar de facto. Existen otras tecnologías como Charm++ de más alto nivel.

Cree una carpeta mpi/ en su repositorio de control de versiones. Para el pseudocódigo se utilizará la siguiente convención de paso de mensajes:

// Global constants
process_number    // Number of this process (integer)
process_count     // Number of processes in the team this process belongs to
process_hostname  // Name of the computer where this process is running (text)
any_process       // For accepting messages from any process
any_tag           // For accepting messages classified with any tag

// Send a variable or array (a set of bytes) to the destination process
send(message, count, to_process, tag = 0)
// Receive a set of bytes into a variable from a source process
receive(&message, count, from_process, tag = 0)
// Send a variable or array from the source process to the rest
broadcast(&message, count, from_process)
// Reduce the data value from all processes to a single result value in
// destination process applying the given operation
reduce(data, &result, count, operation, to_process)
// Reduce the data value from all processes to a single result value that will
// be available in all processes
all_reduce(data, &result, count, operation)
// Distributes an array into subsets for each process using block mapping
scatter(entire_array, entire_count, &subset_array, &subset_count, from_process)
// Updates the entire array from the subsets that where assigned to each process
gather(&entire_array, entire_count, subset_array, subset_count, to_process)
// Get the wall time for the calling process
wall_time()
// Make all processes of a team wait until all of them have reached the barrier
wait_barrier()

4.1.1. Hola mundo (proceso)

Actividad 44. Hola mundo en MPI [hello]

Haga que cada proceso del equipo salude, indicando su número, la cantidad de procesos miembros del equipo, y la máquina desde la que se ejecuta.

Hello from main thread of process 0 of 3 on hostname1
Hello from main thread of process 2 of 3 on hostname2
Hello from main thread of process 1 of 3 on hostname2

Dado que existe indeterminismo por la salida estándar, la salida que su programa obtenga sea distinta a la anterior.

Tabla 41. Hola MPI [hello]
Archivo	Descripción	Cambios
hello.pseudo	Diseño en pseudocódigo de la solución.
hello.cpp	Dice "hola mundo" desde uno o varios procesos en una o varias máquinas.
Makefile	Reutiliza el archivo de Makefile usando la directiva `include` y sobrescribe las variables del compilador para usar los scripts `mpicc` y `mpic++`.
hosts_mpich	Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con MPICH, ej.: `mpiexec -np 5 -f hosts_mpich bin/hello`
hosts_openmpi	Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con Open MPI, ej.: `mpiexec --oversubscribe -np 5 --hostfile hosts_openmpi bin/hello`

Para compilar programas con MPI se requiere instalar una implementación de MPI como Open MPI o MPICH, lueg invocar al compiler wrapper mpicc o mpic++ el cual pasa parámetros al compilador de GCC para que ubique los encabezados y las bibliotecas del MPI instalado.

Si se quiere que el programa corra en varios nodos de un clúster, se requiere un archivo que los liste, uno por línea, además el tamaño de bloque, que indica la antidad de la cantidad de procesos a asignar por nodo (slots). La sintaxis varía dependiendo de la implementación. Para Open MPI se indica la cantidad de procesos en la misma línea separado por el texto slots=, por ejemplo:

node1 slots=4
node2 slots=4
node3 slots=2

El archivo anterior indica que se quieren correr 4 procesos en la computadora cuyo nombre es node1, cuatro procesos en node2, y 2 procesos en node3. La implementación MPICH usa una notación más compacta con el separador dos puntos. El ejemplo anterior se escribiría:

node1:4
node2:4
node3:2

Es común que en los clústers de computadoras se ofrezcan archivos preconfigurados como los anteriores o preferiblemente se usen sistemas de colas. Por ejemplo, para el clúster de Arenal de la ECCI, se ofrecen copias en la carpeta /etc/skel/, la cual se copia cuando se crean las cuentas de usuario, por lo que probablemente disponga de ellos en su carpeta de usuario.

Ambas tecnologías reparten los procesos usando un mapeos estáticos distintos. Los números en el archivo de hosts corresponden a tamaños de bloque. Por ejemplo, en MPICH si se crean 13 procesos se asignarán los primeros 4 al node1, los siguientes 4 al node2, los siguientes 2 al node3, y los restantes 3 al node1 como se ve a continuación:

node1: 0 1 2 3 10 11 12
node2: 4 5 6 7
node3: 8 9

Para correr un programa en un clúster con MPICH, se usa el comando

mpiexec -np P -f hosts.txt bin/my_program args

donde P es la cantidad de procesos que se quieren correr en el clúster. En Arenal MPICH está cargado por defecto. Los siguientes comandos cambian el ambiente a Open MPI (comando module) y nótese cómo los argumentos para mpiexec difieren para esta tecnología:

module clear
module load compilers/gcc-9.4.0
module load mpi/openmpi-4.1.1
mpiexec --oversubscribe --bind-to none -np P --hostfile hosts.txt bin/my_program args

El parámetro --oversubscribe indica a Open-MPI que permita crear más procesos que la cantidad de procesos indicados en el archivo de hosts. El parámetro --bind-to indica cuál es el valor de referencia para establecer el máximo de hilos a permitir por proceso. Por defecto se usa la cantidad de procesadores disponibles, mientras que el valor none deshabilita este tope y permite a los programas o usuarios escoger la cantidad de hilos sin restricciones.

Ejercicio 39 [distributed_exeption]

Haga reingeniería (refactoring) para que cuando ocurra una excepción se provea información al invocador referente al proceso en el que ocurrió la excepción. Cree una clase DistributedExeption (o distributed_exeption) que herede de std::runtime_error. Sus atributos sirven para transportar el número de proceso, un código de error, y el mensaje de error. Haga que el número de proceso y el mensaje se impriman en el error estándar, y el código de error sea el valor de retorno de la subrutina main().

4.1.2. Distribución híbrida (proceso-hilo)

Los procesos (distribución) no ejecutan código, sino los hilos (concurrencia) dentro de sí, y los hilos no pueden existir si no es dentro de un proceso. Dado que se puede crear una cantidad arbitraria de procesos y en cada uno de ellos, una cantidad arbitraria de hilos, se tiene un modelo híbrido de ejecución distribuida-concurrente que aproveche las ventajas de cada paradigma.

Actividad 45. Distribución híbrida [hello_hybrid]

El ejemplo de "Hola mundo" lanza un único hilo principal (main thread) en cada proceso ejecutado. Modifique el programa para que cada proceso lance tantos hilos secundarios (secundary thread) como CPUs hay disponibles en la máquina donde se ejecuta. Cada hilo secundario debe imprimir en la salida estándar una línea antecedida por un tabulador en la que salude al usuario. Por ejemplo si se lanzan dos procesos y cada uno crea tres hilos secundarios, se podría obtener una salida como la siguiente:

Hello from main thread of process 0 of 2 on hostname1
	Hello from thread 0 of 3 of process 0 on hostname1
	Hello from thread 2 of 3 of process 0 on hostname1
	Hello from thread 1 of 3 of process 0 on hostname1
Hello from main thread of process 1 of 2 on hostname2
	Hello from thread 1 of 3 of process 1 on hostname2
	Hello from thread 0 of 3 of process 1 on hostname2
	Hello from thread 2 of 3 of process 1 on hostname2

Dado que existe indeterminismo por la salida estándar, la salida que obtenga puede ser muy distinta a la anterior. Sugerencia: Puede usar OpenMP junto con MPI para lograr el modelo de concurrencia híbrida solicitada en esta actividad.

Tabla 42. Hola MPI híbrido [hello_hybrid]
Archivo	Descripción	Cambios
hello_hybrid_pthread.pseudo	Diseño en pseudocódigo de la solución híbrida entre distribución y concurrencia imperativa (Pthreads).
hello_hybrid_omp.pseudo	Diseño en pseudocódigo de la solución híbrida entre distribución y concurrencia declarativa (OpenMP).
hello_hybrid.cpp	Dice "hola mundo" desde el hilo principal e hilos secundarios (OpenMP) en varios procesos (MPI).
Makefile	Agrega la bandera `-fopenmp` del compilador para instrumentalizar el código objeto con OpenMP
hosts_mpich	Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con MPICH, ej.: `mpiexec -np 5 -f hosts_mpich bin/hello_hybrid`
hosts_openmpi	Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con Open MPI, ej.: `mpiexec --oversubscribe --bind-to none -np 5 --hostfile hosts_openmpi bin/hello_hybrid`

En capítulos previos se ha usado la concurrencia para el paralelismo de datos, es decir, repartir trabajo entre hilos mediante descomposición y mapeo. El modelo de ejecución híbrido permite repartir trabajo entre procesos y luego entre hilos. En tecnologías declarativas como OpenMP, la unidad de descomposición (iteraciones) y los tipos de mapeos están implementados de antemano. En tecnologías imperativas, la descomposición y el mapeo es implementado manualmente por las personas desarrolladoras. Este es el caso de MPI, aunque se proveen subrutinas muy elementales para distribuir datos que se verán luego.

Actividad 46. Distribución del rango con argumentos [hybrid_distr_arg]

Modifique el programa de la Actividad 45 (hello_hybrid) para que reciba un rango indicado como dos números enteros [a,b[ en los argumentos de línea de comandos. Su programa debe distribuir (particionar) el rango entre los procesos de forma lo más equitativa posible, y dentro de los procesos debe distribuir los subrangos entre los hilos de ejecución.

El hilo principal de cada proceso debe reportar en la salida estándar el rango asignado al proceso. Use la notación hostname:process.thread: message como prefijo para simplificar la salida. Cada hilo secundario debe reportar su rango asignado antecedido por un tabulador. La siguiente podría ser una interacción con su programa en dos nodos de un clúster, cada uno con un proceso por nodo, y cada nodo con tres CPU:

$ mpiexec -n 2 -f hosts.txt ./hybrid_distr_arg 3 20
hostname1:0: range [3, 12[ size 9
	hostname1:0.0: range [3,6[ size 3
	hostname1:0.1: range [6,9[ size 3
	hostname1:0.2: range [9,12[ size 3
hostname2:1: range [12, 20[ size 8
	hostname2:1.0: range [12,15[ size 3
	hostname2:1.1: range [15,18[ size 3
	hostname2:1.2: range [18,20[ size 2

Reporte además el tamaño del rango asignado a cada proceso e hilo de ejecución. Puede tomar el siguiente código como punto de partida.

Tabla 43. Código inicial para distribuir el rango en argumentos
Archivos	Descripción
hybrid_distr_arg.pseudo	Diseño preliminar en pseudocódigo de la solución.
hybrid_distr_arg.cpp	Código C++ inicial para la distribución del rango en argumentos

Tabla 44. Distribución del rango con argumentos [hybrid_distr_arg]
Archivo	Descripción	Cambios
hybrid_distr_arg.pseudo	Diseño en pseudocódigo de la solución.
hybrid_distr_arg.cpp	Distribuye el rango en los argumentos de línea de comandos entre procesos y entre hilos usando mapeo por bloque.
Makefile	Facilita la construcción y prueba de la la solución.
hosts_mpich	Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con MPICH, ej.: `mpiexec -np 5 -f hosts_mpich bin/hybrid_distr_arg`
hosts_openmpi	Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con Open MPI, ej.: `mpiexec --oversubscribe --bind-to none -np 5 --hostfile hosts_openmpi bin/hybrid_distr_arg`

4.1.3. Comunicación punto a punto (send-receive)

La comunicación punto a punto envía mensajes de un proceso a otro que forman parte del mismo equipo. MPI provee una familia de funciones para enviar y recibir mensajes. Las dos más básicas son: MPI_Send y MPI_Recv.

Actividad 47. Control de concurrencia con comunicación punto a punto [send_recv_ord_sem]

Modifique el ejemplo Actividad 44 (hello) para que los procesos saluden en orden por su identificador (rank). Dado que la función de comunicación punto a punto MPI_Recv implica bloqueo, y la espera es el mecanismo fundamental del control de concurrencia, puede usarse para sincronizar procesos, junto con MPI_Send. La salida será siempre determinística, por ejemplo:

Hello from main thread of process 0 of 3 on a_host
Hello from main thread of process 1 of 3 on other_host
Hello from main thread of process 2 of 3 on a_host

Cada proceso debe escribir en la salida estándar su saludo. Controle la concurrencia de esta impresión con comunicación punto-a-punto simulando semáforos.

Tabla 45. Control de concurrencia con comunicación punto a punto [send_recv_ord_sem]
Archivo	Descripción	Cambios
send_recv_ord_sem.pseudo	Diseño en pseudocódigo de la solución.
send_recv_ord_sem.cpp	Siempre los procesos saludan en orden. El proceso 0 imprime su saludo y avisa al siguiente. Los demás procesos esperan a recibir la señal del proceso previo.
Makefile	Facilita la construcción y prueba de la la solución.
hosts_mpich	Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con MPICH, ej.: `mpiexec -np 5 -f hosts_mpich bin/send_recv_ord_sem`
hosts_openmpi	Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con Open MPI, ej.: `mpiexec --oversubscribe -np 5 --hostfile hosts_openmpi bin/send_recv_ord_sem`

El paso de mensajes en MPI es orientado a arreglos. Es decir, las operaciones pueden enviar no sólo un elemento (escalar), sino varios de ellos (vectorial), siempre y cuando estén serializados en la memoria. También permite separar asuntos de acuerdo al número de proceso (rank).

Actividad 48. Comunicación punto a punto ordenada [send_recv_ord_itm]

Modifique la solución a la Actividad 47 (send_recv_ord_sem) para que los procesos saluden en orden por su identificador (rank) a través de un intermediario. Es decir, los procesos envían su saludo a uno del equipo, quien recibe los saludos y los imprime en la salida estándar en orden.

Al usar un itermediario con comunicación punto a punto, se simula "seguridad condicional". Note que los saludos son información vectorial y no escalar. Tenga presente que no es posible enviar datos discontinuos de la memoria a través de la red en una operación de send/receive.

Tabla 46. Comunicación punto a punto ordenada [send_recv_ord_itm]
Archivo	Descripción	Cambios
send_recv_ord_itm.pseudo	Diseño en pseudocódigo de la solución.
send_recv_ord_itm.cpp	Todos los procesos envían mensajes de saludo al intermediario (proceso 0) quien los recibe en cualquier orden, pero los imprime en orden del número de proceso (rank) en la salida estándar.
Makefile	Facilita la construcción y prueba de la la solución.
hosts_mpich	Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con MPICH, ej.: `mpiexec -np 5 -f hosts_mpich bin/send_recv_ord_itm`
hosts_openmpi	Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con Open MPI, ej.: `mpiexec --oversubscribe -np 5 --hostfile hosts_openmpi bin/send_recv_ord_itm`

La comunicación punto a punto en MPI es indeterminística entre procesos distintos, pero no entre los mismos procesos. Por ejemplo, si varios procesos envían mensajes a un receptor, los mensajes llegarán en cualquier orden. Pero si un proceso A envía varios mensajes a otro proceso B, los mensajes llegarán en el mismo orden en que fueron enviados.

Actividad 49. Comunicación punto a punto no ordenada [send_recv_urd]

Modifique la solución de la Actividad 48 (send_recv_ord_itm) para que usando comunicación punto a punto, los procesos saluden al proceso intermediario y éste reporte los saludos en el orden en que los recibió.

Tabla 47. Comunicación punto a punto no ordenada [send_recv_urd]
Archivo	Descripción	Cambios
send_recv_urd.pseudo	Diseño en pseudocódigo de la solución.
send_recv_urd.cpp	Todos los procesos envían mensajes de saludo al intermediario (proceso 0) quien los recibe e imprime en el orden en que los recibió, y no en el orden de número de proceso (rank).
Makefile	Facilita la construcción y prueba de la la solución.
hosts_mpich	Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con MPICH, ej.: `mpiexec -np 5 -f hosts_mpich bin/send_recv_urd`
hosts_openmpi	Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con Open MPI, ej.: `mpiexec --oversubscribe -np 5 --hostfile hosts_openmpi bin/send_recv_urd`

MPI ofrece una familia de funciones de send y receive que varían principalmente en:

Si permiten a las personas desarrolladoras controlar los buffers de memoria que se usan para enviar o recibir datos, marcadas con una B en su nombre, como MPI_Bsend().
Si se bloquean (por defecto) o no mientras se realiza la operación. Las que no se bloquean están marcadas con una I en su nombre, por ejemplo MPI_ISend(). Estas funciones retornan inmediatamente, pero invocan a un manejador de eventos cuando su operación finalmente haya tenido efecto.
Si la función de envío espera hasta que los datos hayan sido recibidos por completo por el proceso receptor. En tal caso se marcan con una R de ready, como MPI_RSend(). No aplica para las funciones de receive.

La siguiente tabla resume las combinaciones que pueden generarse de las variantes anteriores. Las funciones están ordenadas por la duración de su efecto, de la que tardaría menos hasta la que duraría más.

Function Blocking Description

Send

MPI_Isend()

Nonblocking

Starts copying data to buffer

MPI_Bsend()

Blocking

Allows control of sending buffer

MPI_Ibsend()

Nonblocking

Starts copying to a controlled buffer

MPI_Send()
MPI_SSend()

Blocking

Blocks until data has started to arrive to target

MPI_Rsend()

Blocking

Blocks until data has completely arrived to target

MPI_Irsend()

Nonblocking

Starts sending, callbacks until data has arrived to target

Receive

MPI_Recv()

Blocking

Blocks until all data has been received and copied to process' memory

MPI_Irecv()

Nonblocking

Callbacks when all data has been received and copied to process' memory

MPI_Mrecv()

Blocking

Allow control how message matching is done?

MPI_Imrecv()

Nonblocking

Allow control how message matching is done?

Ejercicio 40 [ping_pong_perfect]

Un ejercicio clásico de paso de mensajes es simular un juego de tenis de mesa (ping-pong) entre dos procesos. Uno lanza la bola al otro, quien la recibe y la regresa al primero, y así sucesivamente. Los dos jugadores son incansables y nunca pierden un servicio. Haga que su programa simule este comportamiento. Si su programa es invocado con una cantidad distinta a dos jugadores, debe reportar un mensaje de error y finalizar.

Ejercicio 41 [ping_pong_realistic]

Adapte su solución al ejercicio anterior para que sea más realista. En el primer argumento de línea de comandos, el usuario indicará el marcador de victoria de la partida. Por ejemplo, si se indica 10, el primer jugador que anote 10 goles ganará la partida y el juego termina.

Los jugadores en esta versión no son perfectos. El segundo y tercer argumento de línea de comandos indica la probabilidad de acierto en cada servicio (tiro o pase) del primer y segundo jugador respectivamente. Por ejemplo, la siguiente ejecución indica que el jugador 1 (proceso 0) tiene una tasa de acierto del 85.5% de los tiros y el jugador 2 de un 88%.

mpiexec -n 2 ping_pong 3 85.5 88
1: 24 1
2: 53 0
3: 11 0
0 wins 2 to 1

En la salida estándar indique una línea por cada ronda y una línea final con el resultado. En cada ronda se indica la cantidad de servicios (pases) jugados y el proceso que la ganó. La última línea indica el marcador final o si hubo un empate.

4.1.4. Lectura distribuida

Actividad 50. Lectura distribuida de la entrada estándar [stdin_sendrecv]

Modifique la solución de la Actividad 49 (send_recv_urd) para que:

Los procesos lean un arreglo de números en la entrada estándar con los cuales trabajar. Luego cada proceso imprime los números que leyó en la salida estándar.
Haga las correcciones para que todos los procesos tengan y puedan efectivamente imprimir el arreglo.
Los procesos reporten en la salida estándar la cantidad de segundos en que tarda su ejecución.

Tabla 48. Lectura distribuida de la entrada estándar [stdin_sendrecv]
Archivo	Descripción	Cambios
stdin_sendrecv.pseudo	Diseño en pseudocódigo de la solución.
stdin_sendrecv.cpp	MPI sólo permite al proceso 0 leer. Este debe reenviar copias de los datos o asignar fracciones de los mismos para que los otros hilos puedan realizar su trabajo. La función `MPI_Wtime()` retorna un valor de doble precisión flotante que indica una cantidad de segundos transcurrida a partir de un punto de referencia que sólo es válido para el proceso que invoca la subrutina.
Makefile	Facilita la construcción y prueba de la la solución.
hosts_mpich	Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con MPICH, ej.: `mpiexec -np 5 -f hosts_mpich bin/stdin_sendrecv`
hosts_openmpi	Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con Open MPI, ej.: `mpiexec --oversubscribe -np 5 --hostfile hosts_openmpi bin/stdin_sendrecv`
input001.txt	Un archivo con algunos números para poder probar redireccionando la entrada, ej: `mpiexec -np 3 -f hosts_mpich bin/stdin_sendrecv < tests/input001.txt`

MPI permite que sólo el proceso 0 lea de la entrada estándar. Más específicamente, la entrada la lee el comando mpiexec, la captura y la envía al proceso 0. Los demás procesos no reciben la entrada, por tanto si intentan leer, se quedarán bloqueados perennemente. Si un proceso debe leer de la entrada estándar, el proceso 0 tendrá que usar comunicación para enviarla a los demás procesos.

Para calcular la duración en segundos del tiempo en la pared use la función MPI_Wtime. La medición del tiempo en los sistemas distribuidos es un problema sumamente complejo, dado que los procesos pueden ejecutarse en máquinas distintas, y por consiguiente, con diferentes relojes no perfectamente sincronizados entre sí. La función MPI_Wtime() reporta un tiempo transcurrido en segundos que un proceso puede usar como referencia para sí mismo, pero no es válido para otros procesos.

Ejercicio 42 [hybrid_distr_stdin]

Modifique el programa del rango distribuido (Actividad 46) para que en caso de que el rango no se especifique en los argumentos de línea de comandos, los lea en la entrada estándar. Sugerencia, use comunicación punto a punto.

Ejercicio 43 [hybrid_distr_wtime]

Modifique el programa del rango del Ejercicio 42 [hybrid_distr_stdin] para que cada proceso reporte en la salida estándar la cantidad de segundos en que tarda su ejecución. Un ejemplo de salida podría ser el siguiente.

$ mpiexec -n 2 -f hosts.txt ./hybrid_distr_wtime 3 20
hostname1:0: range [3, 12[ size 9 in 0.000123s
	hostname1:0.0: range [3,6[ size 3
	hostname1:0.1: range [6,9[ size 3
	hostname1:0.2: range [9,12[ size 3
hostname2:1: range [12, 20[ size 8 in 0.000342s
	hostname2:1.0: range [12,15[ size 3
	hostname2:1.1: range [15,18[ size 3
	hostname2:1.2: range [18,20[ size 2

¿Cuál de las dos formas de especificar el rango consigue menores tiempos de ejecución: en argumento de línea de comandos o la entrada estándar?

4.1.5. Barreras distribuidas

Implementar mecanismos de control de concurrencia distribuida es menos eficiente que en concurrencia de recursos compartidos, por lo que puede explicar su menor número. Las operaciones de send y receive pueden usarse para enviar avisos (signaling) como se hace con los semáforos. MPI ofrece barreras con la subrutina MPI_Barrier() que imponen espera a un equipo de procesos hasta que todos los miembros hayan alcanzado la barrera.

Actividad 51. Carrera con relevos distribuida [relay_race_dist]

Simule una carrera de relevos, donde los competidores son procesos en equipos. Cada equipo consta de dos corredores. Un corredor tomará la estafeta (en inglés, baton) y se posicionará en la línea de salida. El otro corredor esperará en la mitad de la pista a que el primer corredor llegue y le transfiera la estafeta. En tal momento, el segundo corredor seguirá a toda velocidad hasta alcanzar la meta.

Usted puede imponer restricciones sobre la cantidad de procesos con los que deberá ser ejecutada la simulación. Por ejemplo, un número mínimo de procesos que puede ser par o impar de acuerdo a sus decisiones de separación de asuntos. Idee un mecanismo para decidir qué procesos pertenecen al mismo equipo. Por ejemplo, los procesos 1 y 2 podrían conformar el equipo 1, los procesos 3 y 4 al equipo 2, y así sucesivamente. Si se invoca con una cantidad no adecuada de procesos, la simulación deberá detenerse y emitir un mensaje de error que ayude al usuario a escoger el número correcto.

Cada proceso recibirá dos parámetros: la duración en milisegundos que tarda el primer corredor atravesando la etapa 1 de la carrera (entre la salida y la mitdad de la pista), y la duración en milisegundos del segundo corredor atravesando la etapa 2 de la carrera (de la mitad de la pista hasta la meta). Suponga que los corredores de una etapa tardan exactamente esta duración y no un valor generado al azar. Ejemplo de ejecución:

$ mpiexec -np 10 -f hosts.txt bin/relay_race_dist 1100 900
Place 1: team 3 in 2.35075s
Place 2: team 4 in 2.35085s
Place 3: team 5 in 2.35087s
Place 4: team 2 in 2.35089s
Place 5: team 1 in 2.35092s

Puede usar el siguiente código como punto de partida.

Archivo

Descripción

relay_race_dist.pseudo

Pseudocódigo inicial para la carrera de relevos distribuida.

relay_race_dist.cpp

Código inicial para la carrera de relevos distribuida en C++ con MPI.

Tabla 49. Carrera con relevos [relay_race_dist]
Archivo	Descripción	Cambios
relay_race_dist.pseudo	Diseño en pseudocódigo de la solución.
relay_race_dist.cpp	Implementación con MPI de la simulación de la carrera de relevos distribuida.
Makefile	Facilita la construcción y prueba de la la solución.
hosts_mpich	Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con MPICH, ej.: `mpiexec -np 5 -f hosts_mpich bin/relay_race_dist`
hosts_openmpi	Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con Open MPI, ej.: `mpiexec --oversubscribe -np 5 --hostfile hosts_openmpi bin/relay_race_dist`

4.1.6. Comunicación colectiva: broadcast

Actividad 52. Envío y recepción de valores mediante broadcast [stdin_bcast]

Modifique la solución de la Actividad 50 (stdin_sendrecv) para que el proceso intermediario comparta los valores leídos de la entrada estándar con los demás procesos mediante comunicación colectiva.

Tabla 50. Envío y recepción de valores mediante *broadcast* [stdin_bcast]
Archivo	Descripción	Cambios
stdin_bcast.pseudo	Diseño en pseudocódigo de la solución.
stdin_bcast.cpp	Usa las capacidades de comunicación colectiva de MPI para copiar el arreglo que el proceso 0 lee de la entrada estándar en los demás procesos del equipo.
Makefile	Facilita la construcción y prueba de la la solución.
hosts_mpich	Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con MPICH, ej.: `mpiexec -np 5 -f hosts_mpich bin/stdin_bcast`
hosts_openmpi	Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con Open MPI, ej.: `mpiexec --oversubscribe -np 5 --hostfile hosts_openmpi bin/stdin_bcast`
input001.txt	Un archivo con algunos números para poder probar redireccionando la entrada, ej: `mpiexec -np 3 -f hosts_mpich bin/stdin_bcast < tests/input001.txt`

En una difusión (broadcast) un proceso llamado raíz envía datos a todos los demás procesos del equipo. Los demás procesos recibirán, y por tanto, esperarán, por los datos si llegan al broadcast antes que el emisor (raíz). Internamente los procesos crean un árbol de envíos, donde el proceso emisor (raíz) envía los datos a otros dos, y éstos a su vez a otros dos, y así recursivamente hasta completar todos los procesos del equipo. Idealmente todos los procesos del equipo deben ejecutar la invocación al broadcast, de lo contrario, el equipo de procesos se quedaría bloqueado (aunque los procesos "hoja" podrían no provocar este comportamiento).

Ejercicio 44 [hybrid_distr_bcast]

Modifique el programa del rango distribuido en la entrada estándar (Ejercicio 43 [hybrid_distr_wtime]) para que en lugar de usar comunicación punto a punto para enviar el rango, use comunicación colectiva.

4.1.7. Comunicación colectiva: reduce

Actividad 53. Reducción en MPI [lucky_number_reduce]

Escriba un programa donde cada proceso escoge al azar su número de la suerte entre 00 y 99 inclusive. Haga que el proceso 0 reporte el mínimo, el promedio, y el máximo de los números de la suerte escogidos entre todos los procesos. El siguiente puede ser un ejemplo de ejecución:

$ mpiexec -np 5 -f hosts.txt bin/lucky_number_reduce
Process 0: my lucky number is 83
Process 0: all minimum: 10
Process 0: all average: 44.20
Process 0: all maximum: 83
Process 1: my lucky number is 56
Process 2: my lucky number is 10
Process 3: my lucky number is 10
Process 4: my lucky number is 62

Para su solución y generar números pseudoaleatorios, puede usar el siguiente código base en C++.

Archivo Descripción

lucky_number_reduce.pseudo

Pseudocódigo inicial para el diseño de la solución.

lucky_number_reduce.cpp

Código inicial para la implementación de la solución.

UniformRandom.hpp

Clase en C++ para generar números pseudoaleatorios en un rango con distribución uniforme.

UniformRandom.cpp

Ejemplo de uso de la clase anterior. Crea un comando que recibe tres argumentos COUNT MIN MAX y genera COUNT números pseudoaleatorios en el rango [MIN, MAX[ en la salida estándar.

Tabla 51. Reducción en MPI [lucky_number_reduce]
Archivo	Descripción	Cambios
lucky_number_reduce.pseudo	Diseño en pseudocódigo de la solución.
lucky_number_reduce.cpp	Todos los procesos escogen un número de la suerte al azar y lo envían al proceso 0 quien imprime estadísticas. Note que se usa el número de proceso en la semilla para generar números pseudoaletorios para evitar que los procesos escojan el mismo número de la suerte.
UniformRandom.hpp	Clase en C++ para generar números pseudoaleatorios en un rango con distribución uniforme. Es parte del código inicial dado en el enunciado.
Makefile	Facilita la construcción y prueba de la la solución.
hosts_mpich	Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con MPICH, ej.: `mpiexec -np 5 -f hosts_mpich bin/lucky_number_reduce`
hosts_openmpi	Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con Open MPI, ej.: `mpiexec --oversubscribe -np 5 --hostfile hosts_openmpi bin/lucky_number_reduce`

Ejercicio 45 [mpi_reduce_send_recv]

Implemente la reducción de la Actividad 53 con operaciones de send y receive. Su solución no debe hacer un envío de todos los procesos al receptor directamente, dado que no es eficiente. Su solución debe realizar un árbol binario de envíos de la misma forma que MPI_Reduce() trabaja. Es decir, los procesos envían a otros intermediarios quienes realizan la operación de reducción, y éstos a su vez la envían a otros intermediarios, hasta que finalmente el valor resultante queda en el proceso receptor.

Nota: Este ejercicio tiene una complejidad alta y se recomienda idear un modelo solución antes de implementarlo.

4.1.8. Comunicación colectiva: all-reduce

Actividad 54. Reducción en MPI [lucky_number_who]

Modifique su programa de la Actividad 53 (lucky_number_reduce) para que cada proceso escoja al azar su número de la suerte entre 00 y 99 inclusive, y el mismo proceso reporta si su número es el menor o el mayor de los números escogidos por todos los procesos. El siguiente puede ser un ejemplo de ejecución:

$ mpiexec -np 5 -f hosts.txt bin/lucky_number_who
Process 0: my lucky number (83) is greater than the average (36.00)
Process 0: my lucky number (83) is the maximum (83)
Process 1: my lucky number (18) is less than the average (36.00)
Process 2: my lucky number (07) is less than the average (36.00)
Process 2: my lucky number (07) is the minimum (07)
Process 3: my lucky number (46) is greater than the average (36.00)
Process 4: my lucky number (26) is less than the average (36.00)

El reporte de mínimo, máximo y promedio es independiente. Por ejemplo, si sólo un proceso se ejecuta cumplirá los tres criterios:

$ mpiexec -np 1 -f hosts.txt bin/lucky_number_who
Process 0: my lucky number (31) is the minimum (31)
Process 0: my lucky number (31) is equals to the average (31.00)
Process 0: my lucky number (31) is the maximum (31)

Puede usar el siguiente código como punto de partida.

Archivo

Descripción

lucky_number_who.pseudo

Pseudocódigo inicial para el diseño de la solución.

lucky_number_who.cpp

Código inicial para la implementación de la solución.

Tabla 52. Reducción en MPI
Archivo	Descripción	Cambios
lucky_number_who.pseudo	Diseño en pseudocódigo de la solución.
lucky_number_who.cpp	Cada proceso escoge un número de la suerte y lo envía a todos los demás. Pero en lugar de recibir los números enviados, cada proceso recibe el mínimo, la suma y el máximo de los números escogidos. Con estas reducciones cada proceso calcula el promedio y compara su número de la suerte contra estos estadísticos.
UniformRandom.hpp	Clase en C++ para generar números pseudoaleatorios en un rango con distribución uniforme. Es parte del código inicial dado en el enunciado del problema anterior.
Makefile	Facilita la construcción y prueba de la la solución.
hosts_mpich	Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con MPICH, ej.: `mpiexec -np 5 -f hosts_mpich bin/lucky_number_who`
hosts_openmpi	Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con Open MPI, ej.: `mpiexec --oversubscribe -np 5 --hostfile hosts_openmpi bin/lucky_number_who`

4.1.9. Descomposición y mapeo: scatter y gather

MPI ofrece la función MPI_Scatter() que toma un vector de valores y los reparte entre todos los procesos de un equipo, incluyendo al mismo que tiene el vector original. Usa un mapeo estático por bloque.

MPI_Scatter() tiene la limitación de que la cantidad de elementos en el vector tiene que ser múltiplo de la cantidad de procesos P. En caso contrario produce un error. La subrutina MPI_Scatterv() rompe esta limitación, pero requiere que el invocador construya de antemano una estructura de datos que indique los rangos del vector que cada proceso recibirá.

Una vez que un vector ha sido repartido entre procesos, estos realizarán algún trabajo con los valores asignados y probablemente querrán regresar los resultados al proceso que repartió los datos. Las subrutinas MPI_Gather() y MPI_Gatherv() realizan el trabajo de recolectar los datos distribuidos entre los procesos y consolidarlos en el vector original.

Las funciones MPI_Scatter() y MPI_Gather() sufren de una limitación artificial, mientras que la interfaz de las funciones MPI_Scatterv() y MPI_Gatherv es compleja. Por otra parte, las primitivas de send y receive permiten a los desarrolladores implementar los tipos de mapeo tradicionales, como se hizo en la Actividad 46 (hybrid_distr_arg) para el mapeo estático por bloque.

Ejercicio 46 [hybrid_distr_cyclic]

Modifique su solución al Ejercicio 44 [hybrid_distr_bcast] para repartir el rango usando un mapeo cíclico entre los procesos y los hilos.

MPI ofrece otras funcionalidades avanzadas. Por ejemplo, la subrutina MPI_Init_thread() permite escoger si los hilos secundarios dentro de un proceso pueden o no invocar subrutinas de MPI, y en caso afirmativo si éstas se ejecutan con exclusión mutua o no.

MPI ofrece su propio manejo de entrada y salida optimizado para el paralelismo. Por ejemplo, la familia de subrutinas MPI_File_ están diseñadas para que todos los procesos de un equipo puedan abrir o modificar el mismo archivo de forma paralela, en especial si el hardware facilita el acceso paralelo. Esto se contrapone a las primitivas de entrada y salida de los sistemas operativos, que están ideadas para que sólo un proceso acceda un archivo a la vez.

5. Distribución heterogénea: aceleración gráfica

La aceleración por hardware es el uso de la electrónica para optimizar tareas específicas. Por ejemplo, disminuir la cantidad de tiempo de ejecución, disminuir el consumo de energía, o incrementar el tiempo de respuesta, entre otras optimizaciones. Este hardware se conoce como de propósito específico, pues está diseñado para trabajar sólo el contexto para el que fue diseñado. En el extremo opuesto se encuentran las CPUs que son de propósito general y pueden ser programadas para una cantidad arbitraria de contextos. En un punto medio se encuentra hardware como los aceleradores gráficos y los field-programmable gate arrays (FPGA).

Los aceleradores gráficos o GPUs (Graphics Processing Units) sugieron a finales de los 1990 para mejorar la calidad y velocidad de despliegue de imágenes en video juegos, animaciones, y aplicaciones afines. Se caracterizan por un uso masivo del paralelismo conocido como many cores. Este hardware también sirve para solventar problemas científicos y de otros contextos que requieren más paralelismo que el disponible en un procesador de uso general. Sin embargo, a nivel de software, inicialmente la programación de GPUs fue a través de ambientes de programación exclusivos para contextos gráficos, como OpenGL y DirectX, lo que motivó a iniciativas de crear ambientes de programación general usando los aceleradores gráficos, como OpenCL y CUDA.

El Open Computing Language (OpenCL) es un ambiente de programación basado en C y creado hacia el 2009 por un consorcio de compañías de hardware con el ambicioso objetivo de correr en una variedad de plataformas heterogéneas, entre las que se incluyen CPUs, GPUs, FPGAs, digital signal processors (DSP), y otros dispositivos de aceleración por hardware. En el extremo opuesto se encuentra la Compute Unified Device Architecture (CUDA), una extensión para los lenguajes C/C++ y Fortran, creada hacia el 2007 por Nvidia exclusivamente para programación de aceleradores gráficos y sólo los producidos por esta compañía. Esta limitación de CUDA es quizá la explicación de su éxito, dado que está en armonía con un principio de la optimización, de que las soluciones que logran más eficiencia tienden a ser más dependientes del contexto.

Máquina vs dispositivo.

Cree una carpeta ejemplos/gpu en su repositorio personal.

5.1. Transmisión de calor

Actividad 55. Rendimiento de la transmisión de calor [heat_perf]

Descargue los siguientes archivos a una carpeta ejemplos/gpu/heat_perf. Agregue la hoja de cálculo a control de versiones, pero no los casos de prueba (archivos .bin). Llene las celdas en blanco de la hoja de cálculo con las duraciones de ejecución de las actividades en esta sección. Actualice la gráfica para incluir los incrementos de velocidad en un eje secundario.

Actividad 56. Transmisión de calor serial [heat_serial]

Descargue los archivos de la solución serial a una carpeta ejemplos/gpu/heat_serial. Agréguelos a control de versiones. Compile la solución. Realice las cuatro ejecuciones de la columna serial de la hoja de cálculo que descargó en Actividad 55, y anote la cantidad de generaciones y sus duraciones. Un ejemplo de ejecución podría ser:

./heat_serial ../heat_perf/test001.bin 0.1

Sugerencia 1: realice las ejecuciones en terminales distintas simultáneamente. Es decir, no espere a que la anterior finalice para realizar la siguiente.
Sugerencia 2: compare las ejecuciones de su ejecutable generado con GCC y PGI.

Actividad 57. Transmisión de calor OpenMP [heat_openmp]

Copie la solución de Actividad 56 a la carpeta heat_openmp. Modifique la solución para aprovechar los CPU disponibles en la máquina donde se ejecuta la simulación. Use OpenMP como tecnología para paralelizar la simulación.

Ejecute la solución resultante con los dos casos de prueba de Actividad 55 y anote las duraciones en la hoja de cálculo. Verifique que la cantidad de generaciones sea la misma que la versión serial.

Actividad 58. Transmisión de calor OpenAcc [heat_openacc]

Copie la solución de Actividad 56 a la carpeta heat_openacc_cpu. Modifique la solución para paralelizar la simulación con OpenACC. Adapte el Makefile-pgi para generar un ejecutale unificado (unified binary) que incluya código para CPU y GPU. Revise cuidadosamente la salida del compilador. Realice dos tipos de ejecuciones:

Ejecute la solución resultante en CPU con los dos casos de prueba de Actividad 55 y anote las duraciones en la hoja de cálculo. Verifique que la cantidad de generaciones sea la misma que la versión serial. Compare las duraciones con OpenMP.
Ejecute la solución resultante en GPU con los dos casos de prueba de Actividad 55 y anote las duraciones en la hoja de cálculo. Verifique que la cantidad de generaciones sea la misma que la versión serial.

La siguiente podría ser una interacción:

$ make
pgcc -c -g -acc -ta=multicore,tesla -Minfo=accel heat_openacc.c -o heat_openacc.o
pgcc.   -g -acc -ta=multicore,tesla -Minfo=accel heat_openacc.o -o heat_openacc

$ ACC_DEVICE_TYPE=host ./heat_openacc ../heat_perf/test001.bin 0.1
...
$ export ACC_DEVICE_TYPE=nvidia
$ ./heat_openacc ../heat_perf/test001.bin 0.1

Programación concurrente: ejemplos de clase

1. Concurrencia compartida imperativa (Phtreads)

1.1. Hola mundo (thread)

1.2. Hola mundo múltiple (indeterminismo)

1.3. Hola mundo numerado (memoria privada)

1.4. Hola mundo numerado (memoria compartida)

1.5. Hola mundo ordenado (espera activa)

1.6. Posición en la carrera (mutex)

1.7. Hola mundo ordenado (semáforos)

1.8. Concepto de semáforo

1.9. Hola mundo ordenado (seguridad condicional)

1.10. Productor-consumidor

1.10.1. Problema de buffer acotado

1.10.2. Problema de buffer no acotado

1.10.3. Patrón productor-consumidor

2. Concurrencia de tareas

2.1. Primitivas

2.1.1. Algoritmos (pseudocódigo)

2.1.2. Redes de Petri

2.2. Patrones básicos

2.2.1. Avisar/notificar (signaling)

2.2.2. Encuentro (rendezvous)

2.2.3. Exclusión mutua con semáforos (mutex)

2.2.4. Exclusión mutua acotada (multiplex)

2.2.5. Barrera (barrier)

2.2.6. Carrera de relevos (barrera)

2.2.7. Misterio (variable de condición)

2.3. Filósofos comensales

2.4. Lectores y escritores (candado de lectura-escritura)

2.5. Reentrante vs thread-safe

2.6. Otros problemas de sincronización

2.6.1. Formar agua

2.6.2. Parejas de baile (colas con semáforos)

2.6.3. Fumadores de cigarrillos

3. Paralelismo de datos

3.1. Optimización

3.2. Profiling

3.2.1. Callgrind

3.2.2. Gprof

3.2.3. Perf

3.3. Descomposición

3.4. Mapeo

3.4.1. Mapeo por bloque

3.4.2. Mapeo cíclico

3.4.3. Mapeo dinámico

3.5. Métricas

3.5.1. Incremento de velocidad (speedup)

3.5.2. Eficiencia

3.5.3. Ley de Amdahl

3.6. Falso compartido (false sharing)

3.7. Concurrencia compartida declarativa (OpenMP)

3.7.1. Hola mundo (región paralela, directivas)

3.7.2. Hola mundo múltiple (funciones de biblioteca)

3.7.3. Repartir las iteraciones (omp parallel for)

3.7.4. Reutilizar hilos (omp for)

3.7.5. Descomposición y mapeo en OpenMP (schedule)

3.7.6. Reducciones (reduction)

4. Concurrencia distribuida

4.1. Distribución simétrica (MPI)

4.1.1. Hola mundo (proceso)

4.1.2. Distribución híbrida (proceso-hilo)

4.1.3. Comunicación punto a punto (send-receive)

4.1.4. Lectura distribuida

4.1.5. Barreras distribuidas

4.1.6. Comunicación colectiva: broadcast

4.1.7. Comunicación colectiva: reduce

4.1.8. Comunicación colectiva: all-reduce

4.1.9. Descomposición y mapeo: scatter y gather

5. Distribución heterogénea: aceleración gráfica

5.1. Transmisión de calor

3.7.3. Repartir las iteraciones (`omp parallel for`)

3.7.4. Reutilizar hilos (`omp for`)

3.7.5. Descomposición y mapeo en OpenMP (`schedule`)

3.7.6. Reducciones (`reduction`)