Programación concurrente: ejemplos de clase

1. Concurrencia compartida

La 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. 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 hacer ninguna preparación especial. 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 tres tecnologías para implementar concurrencia compartida: Pthreads, OpenMP, y OpenACC. Éste último es de carácter opcional.

1.1. Concurrencia compartida imperativa (Phtreads)

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.1. Hola mundo (thread)

El siguiente es un "Hola mundo" en Pthreads:

Table 1. Hola mundo en Pthreads [hello]
Archivo	Descripción	Cambios
hello.c	Dice "hola mundo" desde el hilo principal y desde un hilo secundario.

Para compilar con GCC –o un compilador compatible– código fuente que use Pthreads, se debe agregar 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.

1.1.2. Hola mundo múltiple (indeterminismo)

Actividad 1 [hello_w]

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

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 única regla estipulada en el Makefile de abajo.

Table 2. Hola mundo múltiple en Pthreads [hello_w]
Archivo	Descripción	Cambios
hello_w.c	Varios threads dicen "hola mundo" junto con el hilo principal.
Makefile	Un archivo para compilar el código fuente sin tener que recordar los argumentos de invocación al compilador.

1.1.3. Hola mundo numerado (memoria privada)

Actividad 2 [hello_i_of_w_pri]

Cree una nueva versión de su programa "hola mundo" donde cada thread imprime "Hello from thread i of w\n", 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). Sugerencia: cree un registro (estructura) privado para cada thread.

Table 3. Hola mundo numerado [hello_i_of_w_pri]
Archivo	Descripción	Cambios
hello_i_of_w_pri.c	Varios threads saludan indicando su identificador en la salida estándar.
Makefile	El Makefile cambia usa una variable para especificar el nombre del ejecutable y del archivo fuente que facilita modificaciones.

Actividad 3 (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_i_of_w_pri, junto con el nombre de su sistema operativo (por ejemplo, Debian 9 64bits o Fedora 30 64bits).

1.1.4. Hola mundo numerado (memoria compartida)

Actividad 4 [hello_i_of_w_shr]

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

Haga que los datos comunes para todos los threads (el número w) estén en un registro (estructura) compartido para cada thread. Mantenga los datos exclusivos para cada thread (i) se mantengan en el registro privado.
Reporte la duración en segundos que los threads toman en saludar.

Table 4. Hola mundo numerado [hello_i_of_w_shr]
Archivo	Descripción	Cambios
hello_i_of_w_shr.c	Varios threads saludan indicando su identificador en la salida estándar.
Makefile	Cambia el nombre de la carpeta usando la variable.

1.1.5. Hola mundo ordenado (espera activa)

Actividad 5 [hello_ordered_wait]

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 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;

Table 5. Hola mundo ordenado con espera activa [hello_ordered_wait]
Archivo	Descripción	Cambios
hello_ordered_wait.c	Varios threads saludan en orden gracias a la espera activa.
Makefile	Obtiene automáticamente el nombre del ejecutable de la carpeta donde se encuentre el `Makefile`. Asume que existe un archivo `.c` con el mismo nombre de la carpeta. Se agregó la regla `gitignore` que crea el archivo `.gitignore` con el nombre del ejecutable.

Actividad 6 (hello_ordered_rationale)

Ejecute varias veces su solución de hello_ordered_wait con la cantidad máxima de threads que el su sistema operativo le permite. ¿Puede estimar 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_ordered_wait. Indique en qué condiciones sería apremiante utilizar espera activa, o en caso de no haberlas, sugiera soluciones alternativas.

1.1.6. Posición en la carrera (mutex)

Actividad 7 [position_race]

Modifique su solución a Actividad 5 [hello_ordered_wait] para implementar una carrera de threads. Cada vez que un thread 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

Las posiciones tienen que aparecer en orden. Utilice algún mecanismo de control de concurrencia para que el reporte sea correcto.

Table 6. Posición en la carrera [position_race]
Archivo	Descripción	Cambios
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	Sin cambios respecto a la versión anterior

1.1.7. Productor-consumidor (semáforo)

Actividad 8 [producer_consumer]

El problema del productor-consumidor en computación es un problema clásico de control de concurrencia. Se suele presentar de forma semi-concreta, lo que ayudar a identificar otros contextos donde su solución se puede aplicar.

El problema lo tienen dos entes concurrentes, uno que produce algo que el segundo consume. Ambos tienen acceso a un espacio finito 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.

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 números de precisión flotante, usando la notación r.i, donde r es el número de la ronda y i el número del producto en esa ronda, ambos iniciando en 1. Por ejemplo 3.08 es el octavo producto de la tercera 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 r.i generated.

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. Una vez que el consumidor elimina un producto del buffer imprime en la salida estándar el texto r.i consumed. 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.01
Produced 1.02
Produced 1.03
		Consumed 1.01
Produced 2.01
		Consumed 1.02
Produced 2.02
		Consumed 1.03
		Consumed 2.01
		Consumed 2.02
Produced 2.03
		Consumed 2.03

Table 7. Productor-consumidor, versión 1 con `sem_init` [producer_consumer]
Archivo	Descripción	Cambios
producer_consumer.c	Simula el problema del productor-consumidor.
Makefile	Usa variables para el compilador, las banderas, y bibliotecas. Estas variables pueden ser cambiadas desde la línea de comandos cuando se invoca a `make`.

1.1.8. Carrera de relevos (barrera)

Actividad 9 [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.

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). Asuma 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

La simulación reportará sólo los tres primeros equipos en llegar. Recuerde verificar que su solución no produzca fugas de memoria ni condiciones de carrera.

¿Afecta el orden de creación de los equipos el resultado de la carrera? Modifique su solución para crear los equipos en orden inverso y compare los resultados de las ejecuciones. Sugerencia, utilice metaprogramación para escoger en tiempo de compilación el orden de creación de los equipos.

Table 8. Carrera con relevos [relay_race]
Archivo	Descripción	Cambios
relay_race.c	Simula una carrera de relevos con threads. Esta solución se compara contra el ejemplo de posición en la carrera (`[position_race]`).
Makefile	Sin cambios

1.1.9. Misterio (variable de condición)

Actividad 10 [mist]

Rastree la memoria y el procesamiento del siguiente programa en una hoja en blanco. Luego agregue una imagen escaneada o fotografiada del rastro del programa a un archivo mist.md. Use un editor de imágenes para reducir las dimensiones y cantidad de colores del archivo. La imagen no debería requerir más de 100kB.

 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
70
71 #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)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;
}

¿Qué trabajo realiza la función mistery()? Explique.

1.1.10. Arreglo reentrante y thread-safe (candado de lectura-escritura)

Actividad 11 [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 memcheck de valgrind):

Descargar Arreglo dinámico versión 1

Table 9. Arreglo reentrante [array_reentrant]
Archivo	Descripción	Cambios
main.c	Respecto al código dado, se cambió `array_t` para que fuese el tipo de un registro en lugar de un puntero.
array.h	El registro que contiene los atributos (campos) de un arreglo se hace opaco (sus campos son privados para los usuarios, por lo que no se declaran en la interfaz `.h`).
array.c	Las variables estáticas/globales se reemplazan por campos en registros. La función `array_create()` coloca el registro en la memoria dinámica, de tal forma que puede ser usado por invocaciones posteriores de subrutinas de la biblioteca. Al estar en memoria dinámica, una "instancia" de un arreglo no interfiera con otra. Esto lo hace reentrante. La función `array_destroy()` se encarga de liberar la memoria del arreglo y del registro.
array.pro	Un proyecto de Qt para quien guste usar este IDE.
Makefile	Este `Makefile` compila cada archivo `.c` en un `.o` separado, lo cual acelera el tiempo de compilación si varios fuentes en el proyecto no han cambiado. Se compara contra el ejemplo de la carrera de relevos por ser el último ejemplo visto, aunque este `Makefile` no fue una adaptación del anterior.

Actividad 12 [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

Table 10. Arreglo *thread safe* con mutex [array_thrsafe_mutex]
Archivo	Descripción	Cambios
main.c	Programa dado que prueba que crea varios threads y estos realizan operaciones concurrentemente sobre el arreglo.
array.h	Dado que el registro es opaco, la interfaz del arreglo se mantiene inalterada. Sólo se cambio el orden de declaración de las subrutinas.
array.c	Agrega un mutex al registro y hace que las funciones públicas se invoquen con exclusión mutua en el arreglo.
array.pro	Un proyecto de QtCreator para quien guste usar este IDE.
Makefile	Idéntico al anterior.

Actividad 13 [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:

Table 11. Arreglo *thread safe* con candados de lectura-escritura [array_thrsafe_rwlock]
Archivo	Descripción	Cambios
main.c	Programa dado que prueba idéntico.
array.h	Dado que el registro es opaco, la interfaz del arreglo se mantiene inalterada.
array.c	Cambia el mutex por un candado de lectura y escritura. Las funciones públicas que modifican el arreglo bloquean el candado para escritura, y las que sólo leen del arreglo lo bloquean para lectura.
array.pro	Un proyecto de QtCreator para quien guste usar este IDE.
Makefile	Idéntico al anterior.

Actividad 14 [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:

Table 12. 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.

Table 13. Rendimiento de los arreglo *thread safe* [array_thrsafe_perf]
Archivo	Descripción	Cambios
main.c	Programa dado que prueba que crea un arreglo de acuerdo a los argumentos del usuario, varios threads y estos realizan operaciones concurrentemente sobre el arreglo.
array_mutex.h	Se renombraron los identificadores para evitar colisión.
array_mutex.c	Se renombraron los identificadores para evitar colisión.
array_rwlock.h	Se renombraron los identificadores para evitar colisión.
array_rwlock.c	Se renombraron los identificadores para evitar colisión.
array.pro	Un proyecto de QtCreator para quien guste usar este IDE.
Makefile	Idéntico al anterior.
array_thrsafe_perf.ods	Hoja de cálculo con los resultados de ejeción del experimento en una computadora con 8 núcleos lógicos.

1.2. Problemas de sincronización

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 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 el paralelismo de tareas genere resultados correctos a través de la aplicación de mecanismos 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 el profesional de la computación. Están basados en el libro libre The Little Book of Semaphores escrito por Allen B. Downey.

1.2.1. Rutas de ejecución

Actividad 15 [execution_paths]

Dos threads ejecutan las siguientes tareas. Liste todas las rutas de ejecución indicando el valor final de la variable shared_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.

Thread A Thread B

1
2 shared_x := 5
print(shared_x)

1 shared_x := 7

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

Actividad 16 [for_count]

Suponga que el hilo de ejecución principal crea w=100 hilos secundarios con los siguientes códigos. (1) ¿Cuál es el valor más grande que la variable compartida count podría llegar a obtener? (2) ¿Cuál es el menor valor que la variable compartida count podría llegar a obtener?

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

main:
	// create 100 threads running secondary()
	create_thread(secondary, 100)

secondary:
	for i := 1 to 100:
		temp := count
		count := temp + 1

Table 15. Contador en ciclos [for_count]
Archivo	Descripción	Cambios
for_count.md	Conjetura los potenciales resultados.

1.2.2. Definición original 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 := 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

// Declares a shared variable by all threads (ie. stored in shared_data record)
shared shared_x := initial_value

// Main subroutine that will be executed by the main thread
main:
	// Create 3 threads that will execute the secondary function concurrently
	create_threads(secondary, 3)

secondary:
	// A subroutine that will be executed by secondary threads

1.2.3. Avisar/notificar (signal)

Actividad 17 [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).

Main thread thread_a thread_b

1
2 create_thread(thread_a, 1)
create_thread(thread_b, 1)

1 statement a1

1 statement b1

Table 16. Avisar/notificar [signaling]
Archivo	Descripción	Cambios
signaling.alg.c	Usa un semáforo que indica cuando la instrucción `a1` ha sido ejecutada.

1.2.4. Encuentro (rendezvous)

Actividad 18 [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.

Main thread thread_a thread_b

1
2 create_thread(thread_a, 1)
create_thread(thread_b, 1)

1
2 statement a1
statement a2

1
2 statement b1
statement b2

Table 17. Encuentro [rendezvous]
Archivo	Descripción	Cambios
rendezvous1.alg.c	Usa dos semáforos para asegurar que dos threads han llegado a cierto punto. En esta versión, los dos threads avisan apenas hayan terminado de ejecutar las instrucciones `a1` o `b1`.
rendezvous2.alg.c	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.
rendezvous3.alg.c	En esta versión ambos threads esperan a que el otro haya terminado de ejecutar su instrucción. No es una solución porque genera un bloqueo mutuo (deadlock).

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

Actividad 19 [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 shared count := 0

main:
	create_thread(thread_a)
	create_thread(thread_b)

thread_a:
	count := count + 1

thread_b:
	count := count + 1

Table 18. Exclusión mutua [sem_mutex]
Archivo	Descripción	Cambios
sem_mutex.alg.c	Un semáforo inicializado en 1 imita a un mutex. Cuando el semáforo tiene el valor 1 indica que el mutex está disponible, y el valor 0 que está bloqueado. Tiene la diferencia de que un mutex no debe superar el valor 1, y de que un mutex sólo puede ser incrementado por el mismo thread que lo decrementó.

Actividad 20 [sem_mutex_symmetric]

Note que en la actividad anterior ambos threads ejecutaban el mismo código, a lo que se le llama una solución simétrica, en contraposición a la solución asimétrica donde los threads ejecutan código distinto (separación de asuntos o paralelismo de tareas).

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 shared count := 0

main:
	thread_count := read_integer()
	create_thread(secondary, thread_count)

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

Table 19. Exclusión mutua simétrica [sem_mutex_symmetric]
Archivo	Descripción	Cambios
sem_mutex.alg.c	El semáforo usado adecuadamente obliga a una serialización de los hilos.

1.2.6. Exclusión mutua acotada (multiplex)

Actividad 21 [multiplex]

Modifique la solución a la actividad Actividad 20 [sem_mutex_symmetric] para que permita un límite superior de n threads ejecutando la sección crítica. 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.

Table 20. Exclusión mutua acotada [multiplex]
Archivo	Descripción	Cambios
sem_mutex.alg.c	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?

1.2.7. Barrera con semáforos (barrier)

Actividad 22 [sem_barrier]

Generalice su solución a la actividad Actividad 18 [rendezvous] para asegurar que una cantidad arbitraria de threads no continúen su ejecución hasta que todos hayan alcanzado (ejecutado) el punto de encuentro. Es decir, si se crean n threads, los primeros n - 1 threads que lleguen deberían bloquearse hasta que el thread en la posición n llegue al punto de encuentro. En tal momento todos los n threads podrán continuar ejecutándose concurrentemente. A este patrón se le conoce como barrera (barrier). Sugerencia: puede tomar como punto de partida el siguiente código.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13 // How many threads have arrived to the barrier
shared count := 0
// Protects the increment of the count
shared mutex := semaphore(1)
// Locked (0) until all threads arrive, then it is unlocked (1)
shared barrier := semaphore(0)

main:
	thread_count := read_integer()
	create_thread(secondary, thread_count)

secondary:
	// Adapt rendezvous solution here

Table 21. Barrera de una pasada con semáforos [sem_barrier]
Archivo	Descripción	Cambios
sem_barrier.alg.c	Implementa una barrera de una pasada. Es decir, después de usada, la barrera no se debe reutilizar.

Actividad 23 [sem_barrier_reusable]

Haga que su solución a la actividad Actividad 22 [sem_barrier] 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 usar el patrón torniquete. Un torniquete (turnstile) 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. Se puede lograr un torniquete haciendo que los threads esperen por un semáforo, y una vez que pasen, habiliten el paso al siguiente:

1
2
3
4
5
6
7 shared turnstile := semaphore(0)

secondary:
	...
	wait(turnstile)
	signal(turnstile)
	...

Table 22. Barrera reusable con semáforos [sem_barrier_reusable]
Archivo	Descripción	Cambios
sem_barrier_reusable.alg.c	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.
sem_barrier_reusable_2.alg.c	Pseudocódigo que convierte la barrera en código reusable.

La segunda implementación permite reutilizar barreras. Es decir en la solución de nuevos problemas puede suponer que tiene disponible barreras con la siguiente interfaz:

1
2
3
4
5
6
7 main:
	shared my_barrier := barrier(3)

secondary:
	...
	wait(mybarrier)
	...

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

Actividad 24 [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.

Table 23. Parejas de baile (parte 1) [dancing_pairs_1]
Archivo	Descripción	Cambios
dancing_pairs_1a.alg.c	En el fondo esta solución es simplemente un encuentro (rendezvous). Cuando una persona llega a su fila A, enviará una señal a la otra fila B indicando que está listo para formar pareja. Si la fila B está vacía, la persona se quedará esperando hasta que alguien llegue a la fila B y le envíe una señal. Sin embargo, puede ocurrir que varios hombres bailen sin pareja o entre ellos, o viceversa. Busque una ruta de ejecución que produzca este comportamiento.
dancing_pairs_1b.alg.c	La versión anterior fue realizada en clase, donde un valor negativo en la cola de hombres significa la cantidad de mujeres esperando a que llegue un hombre (y viceversa). Esta es otra versión simétrica donde un valor negativo en la cola de hombres indica la cantidad de hombres esperando por ella (y viceversa).

Actividad 25 [dancing_pairs_2]

Si es necesario, modifique su solución al problema Actividad 24 [dancing_pairs_1] 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.

Table 24. Parejas de baile (parte 2) [dancing_pairs_2]
Archivo	Descripción	Cambios
dancing_pairs_2a.alg.c	Solución propuesta por Julián y Roy.
dancing_pairs_2b.alg.c 🖼	Solución propuesta por Kevin Wang Qiu
dancing_pairs_2c.alg.c	Solución propuesta por Roy Rojas.

Actividad 26 [dancing_pairs_3]

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

Actividad 27 [dancing_pairs_4]

Opcional. Modifique su solución al problema Actividad 26 [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.

Actividad 28 [dancing_pairs_5]

Opcional. Modifique su solución al problema Actividad 27 [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.

Actividad 29 [dancing_pairs_6]

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

1.2.9. Filósofos comensales

(Pendiente)

1.2.10. Fumadores de cigarrillos

Originalmente presentado por Suhas Patil. Four threads are involved: an agent and three smokers. The smokers loop forever, first waiting for ingredients, then making and smoking cigarettes. The ingredients are tobacco, paper, and matches.

We assume that the agent has an infinite supply of all three ingredients, and each smoker has an infinite supply of one of the ingredients; that is, one smoker has matches, another has paper, and the third has tobacco.

The agent repeatedly chooses two different ingredients at random and makes them available to the smokers. Depending on which ingredients are chosen, the smoker with the complementary ingredient should pick up both resources and proceed. For example, if the agent puts out tobacco and paper, the smoker with the matches should pick up both ingredients, make a cigarette, and then signal the agent.

To explain the premise, the agent represents an operating system that allocates resources, and the smokers represent applications that need resources. The problem is to make sure that if resources are available that would allow one more applications to proceed, those applications should be woken up. Conversely, we want to avoid waking an application if it cannot proceed.

You are not allowed to modify the agent code. If the agent represents an operating system, it makes sense to assume that you don’t want to modify it every time a new application comes along.

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 30 [cigarette_smokers_1]

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

Sugerencia. The solution proposed by Parnas uses three helper threads called “pushers” that respond to the signals from the agent, keep track of the available ingredients, and signal the appropriate smoker. it uses additional variables and semaphores:

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)

The boolean variables indicate whether or not an ingredient is on the table. The pushers use tobacco_sem to signal the smoker with tobacco, and the other semaphores likewise.

1.3. Concurrencia compartida declarativa (OpenMP)

OpenMP es una tecnología desarrollada por varias empresas para implementar concurrencia de manera más declarativa y menos imperativa. Es una especificación para 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 ejemplos/openmp en su repositorio personal de control de versiones para el curso.

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

El siguiente es un "Hola mundo" en OpenMP. Por elección de los estudiantes, se cambia el lenguaje de programación de C a C++.

Table 25. Hola mundo en OpenMP [hello]
Archivo	Descripción	Cambios
hello.cpp	Dice "hola mundo" desde hilos secundarios en OpenMP. En esta tecnología el hilo principal sólo crea y espera por los hilos secundarios por 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 14 [array_thrsafe_perf].

Para compilar con GCC o un compilador compatible debe habilitarse 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

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

Actividad 31 [hello_w]

Modifique el programa de "hola mundo" para permitir al usuario indicar la cantidad de threads como argumento de la línea de comandos. Si el usuario omite este argumento, asuma la cantidad de CPUs disponibles en el sistema. Indague en la especificación cómo obtener el número de procesadores disponibles en OpenMP o bien, la cantidad sugerida de threads a iniciar.

Table 26. 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	Igual al ejemplo anterior.

1.3.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 threads. La instrucción o bloque paralelizado es ejecutado por todos los _threads 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 threads, pero a diferencia de omp parallel, omp parallel for reparte las iteraciones del ciclo entre los threads creados:

Actividad 32 [parallel_for]

Modifique el programa de Actividad 31 [hello_w] para repartir iteraciones entre threads. 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 CPUs disponibles en el sistema.

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

$ ./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

Table 27. 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	Igual al ejemplo anterior.

1.3.4. Reutilizar hilos (`omp for`)

Si se tienen varias regiones parallel for una tras otra que utilizan la misma cantidad de threads, es ineficiente crearlos y destruirlos cada vez que se ingresa y sale de estas secciones, de ahí la utilidad de la directiva for.

Actividad 33 [several_for]

Modifique el programa de Actividad 32 [parallel_for] 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 threads. Es decir, en cada ciclo no cree ni destruya threads, sino que créelos antes del primer ciclo y destrúyalos después del tercer ciclo. En cada ciclo los threads son reutilizados.

El programa debe imprimir en la salida estándar la etapa en la que se encuentra, el número de thread y las iteraciones que realizó. Las etapas siempre deben aparecer en orden. Por ejemplo, para repartir 5 iteraciones entre 2 threads 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

Table 28. 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 threads 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 threads que se crearon en la región paralela. Es decir, la directiva `for` reutiliza los threads de la región paralela. La utilidad de esta directiva es evitar el overhead de crear y destruir threads 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	Igual al ejemplo anterior.

1.3.5. Ordenamiento par-impar

Actividad 34 [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. Asegúrese con memcheck de que su programa no haga accesos inválidos ni fugas de memoria.

Actividad 35 [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 threads que deben emplearse. Asegúrese que su implementación produce resultados correctos y no genere fugas de memoria.

Actividad 36 [odd_even_sort_two_for]

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

Actividad 37 [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 (ver apartado siguiente). Anote las duraciones obtenidas en una hoja de cálculo, con 1 thread, 0.5xCPU, 1xCPU, y 2xCPU, donde CPU es la cantidad de CPUs disponibles en la máquina donde se realizaron las pruebas.

1.3.6. Medición de duraciones con `gprof` y `perf`

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

La herramienta perf provee información menos detallada que gprof, pero tiene la ventanja de que no es necesario modificar el ejecutable. Para obtener la duración se puede anteceder el comando con perf stat de la forma:

perf stat ./executable args

1.3.7. Descomposición y mapeo (`schedule`)

Actividad 38 [schedule]

Modifique el programa de Actividad 32 [parallel_for] para repartir iteraciones entre threads 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". 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] := 7

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

ToDo: Agregar un usleep() en cada iteración dado por parámetro double, que puede ser constante, proporcional a la iteración (un factor), o proporcional al número de thread.

Table 29. Mapeo (scheduling) en OpenMP [schedule]
Archivo	Descripción	Cambios
schedule.cpp	Reparte iteraciones entre threads y guarda en arreglos qué thread hizo cada iteración.
Makefile	Makefile para compilar el código fuente.

1.3.8. Reducciones (`reduction`)

Actividad 39 [average]

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. Use reducciones de OpenMP.

Table 30. Reducciones en OpenMP [average]
Archivo	Descripción	Cambios
average.cpp	Calcula el promedio de números leídos de la entrada estándar y almacenados en un arreglo dinámico. Usa varios threads para calcular las sumas. Usa reducciones para agregar las sumas parciales de cada thread a la suma total.
Makefile	Makefile para compilar el código fuente.

Actividad 40 [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 estádistico en la salida estándar. La cantidad de números no se conoce de antemano. Use reducciones de OpenMP.

Actividad 41 [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.

2. 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.

2.1. Distribución homogénea: 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 ejemplos/mpi/ en su repositorio de control de versiones.

2.1.1. Hola mundo (proceso)

El siguiente es un "Hola mundo" en MPI:

Table 31. Hola MPI
Archivo	Descripción	Cambios
hello.cpp	Dice "hola mundo" desde uno o varios procesos en una o varias máquinas.
Makefile	Para compilar programas con MPI se requiere instalar una implementación de MPI como `open-mpi` o `mpich`, luego conviene invocar al script `mpicc` o `mpic++` el cual pasa parámetros al compilador de GCC para que ubique los encabezados y las bibliotecas del MPI instalado.
hosts.txt	Si se quiere que el programa corra en varios nodos de un clúster, se requiere un archivo que los liste. Este archivo está diseñado para mpich y el clúster arenal de la ECCI. Después de generado el ejecutable se puede invocar con `mpiexec -n W -f hosts.txt ./hello`, donde `W` es la cantidad de procesos que se quieren correr en el clúster.

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

Actividad 42 [hello_hybrid]

El ejemplo de "Hola mundo" lanza un único main thread en cada proceso ejecutado. Modifique el programa para que cada proceso lance tantos secundary thread como CPUs hay disponibles en la máquina donde se ejecuta. Cada thread 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 threads, 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 (condición de carrera), 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.

Table 32. Hola MPI híbrido
Archivo	Descripción	Cambios
hello_hybrid.cpp	Dice "hola mundo" desde el hilo principal e hilos secundarios en varios procesos.
Makefile	Agrega las banderas para habilitar OpenMP. La bandera `-std=c11` indica al compilador sólo permitir lo acordado en el estándar C 2011. La bandera `-std=gnu11` habilita el estándar C 2011 más las extensiones de GCC. En versiones nuevas del compilador, `gnu11` es el estándar por defecto, pero en versiones viejas del compilador es `gnu99`.
hosts.txt	Nodos mpich del clúster arenal de la ECCI, para poder invocar con `mpiexec -n W -f hosts.txt ./hello`, donde `W` es la cantidad de procesos que se quieren correr.

Actividad 43 [hybrid_distr_arg]

Modifique el programa de la actividad anterior 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.

Table 33. Distribución del rango con argumentos
Archivo	Descripción	Cambios
hybrid_distr_arg.cpp	Reparte un rango de valores dado por argumento de línea de comandos entre procesos e hilos.
Makefile	Makefile para compilar el código fuente
hosts.txt	Nodos mpich del clúster arenal de la ECCI, para poder invocar con `mpiexec -n W -f hosts.txt ./hello`, donde `W` es la cantidad de procesos que se quieren correr.

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

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

Actividad 44 [send_recv_ord]

Modifique el ejemplo Hola mundo (proceso) para que los procesos saluden en orden por su identificador (rank). Use comunicación punto a punto.

Table 34. Comunicación punto a punto ordenada
Archivo	Descripción	Cambios
send_recv_ord.cpp	Todos los procesos envían mensajes de hola al proceso 0 quien los recibe e imprime en orden de rank en la salida estándar, y no en el orden en que fueron recibidos.
Makefile	Un makefile genérico para compilar con MPI.
hosts.txt	Nodos mpich del clúster arenal de la ECCI, para poder invocar con `mpiexec -n W -f hosts.txt ./hello`, donde `W` es la cantidad de procesos que se quieren correr.

Actividad 45 [send_recv_ord_sem]

Dado que las funciones MPI_Send y MPI_Recv implican bloqueo, y la espera es el mecanismo fundamental del control de concurrencia, pueden usarse para sincronizar procesos.

Modifique la solución a la actividad Actividad 44 [send_recv_ord] para que los procesos saluden en orden por su identificador (rank), pero cada proceso escribe en la salida estándar su saludo. Controle la concurrencia de esta impresión con comunicación punto-a-punto simulando semáforos.

Table 35. Control de concurrencia con comunicación punto a punto
Archivo	Descripción	Cambios
send_recv_ord_sem.cpp	Todos los procesos envían mensajes de hola al proceso 0 quien los recibe e imprime en orden de rank en la salida estándar, y no en el orden en que fueron recibidos.
Makefile	Un makefile genérico para compilar con MPI.
hosts.txt	Nodos mpich del clúster arenal de la ECCI, para poder invocar con `mpiexec -n W -f hosts.txt ./hello`, donde `W` es la cantidad de procesos que se quieren correr.

Actividad 46 [send_recv_urd]

Modifique la solución de Actividad 44 [send_recv_ord] para que usando comunicación punto a punto, los procesos saluden al proceso 0 y éste reporte los saludos en el orden en que los recibió.

Table 36. Comunicación punto a punto no ordenada
Archivo	Descripción	Cambios
send_recv_urd.cpp	Todos los procesos envían mensajes de hola al proceso 0 quien los recibe e imprime en el orden en que los recibió, y no en el orden de _rank. Los cambios a la derecha son respecto a la versión que imprime los mensajes en orden.
Makefile	Un makefile genérico para compilar con MPI.
hosts.txt	Nodos mpich del clúster arenal de la ECCI, para poder invocar con `mpiexec -n W -f hosts.txt ./hello`, donde `W` es la cantidad de procesos que se quieren correr.

2.1.4. Lectura distribuida y tiempo de pared

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.

Actividad 47 [hybrid_distr_stdin]

Modifique el programa del rango distribuido (Actividad 43 [hybrid_distr_arg]) 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. ¿Qué salida produce al proveer el rango de la actividad anterior en la entrada estándar a su programa?

Haga las modificaciones necesarias para que el programa pueda leer el rango en la entrada estándar y distribuirlo entre los procesos e hilos en el clúster. Sugerencia, use comunicación punto a punto.

Table 37. Distribución del rango leído en la entrada estándar
Archivo	Descripción	Cambios
hybrid_distr_stdin.cpp	Reparte un rango de valores dado leído de la entrada estándar entre procesos e hilos.
Makefile	Makefile para compilar el código fuente
hosts.txt	Nodos mpich del clúster arenal de la ECCI, para poder invocar con `mpiexec -n W -f hosts.txt ./hello`, donde `W` es la cantidad de procesos que se quieren correr.

Para calcular la duración en segundos del tiempo en la pared use la función MPI_Wtime.

Actividad 48 [hybrid_distr_wtime]

Modifique el programa del rango anterior 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

Table 38. Duración de pared en MPI
Archivo	Descripción	Cambios
hybrid_distr_wtime.cpp	Mide el tiempo de ejecución repartiendo un rango de valores, sea dado por argumentos o leído de la entrada estándar entre procesos e hilos. Esperablemente lo segundo requiere más tiempo.
Makefile	Makefile para compilar el código fuente
input001.txt	Rango para leer de la entrada estándar y reducir el tiempo que tarda un humano en digitar. Se puede invocar de la forma `mpiexec -n W -f hosts.txt ./hybrid_distr_wtime < input001.txt.
hosts.txt	Nodos mpich del clúster arenal de la ECCI, para poder invocar con `mpiexec -n W -f hosts.txt ./hybrid_distr_wtime`, donde `W` es la cantidad de procesos que se quieren correr.

2.1.5. Comunicación colectiva: broadcast

Actividad 49 [hybrid_distr_bcast]

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

Table 39. Broadcast en MPI
Archivo	Descripción	Cambios
hybrid_distr_bcast.cpp	El proceso 0 lee el rango de la entrada estándar (puesto que es el único en MPI que puede hacerlo), si no se provee en los argumentos de línea de comandos. Luego envía copias del rango a los demás procesos con la subrutina MPI_Bcast. Esta subrutina es típicamente más eficiente que ejecutar un ciclo de envíos (`MPI_Send()`) en el proceso emisor, y una invocación a `MPI_Recv()` en los procesos receptores. Internamente `MPI_Bcast()` propaga un conjunto de envíos en forma de árbol desde el emisor (raíz) hasta los receptores (hojas).
Makefile	Makefile para compilar el código fuente
input001.txt	Rango para leer de la entrada estándar y reducir el tiempo que tarda un humano en digitar. Se puede invocar de la forma `mpiexec -n W -f hosts.txt ./hybrid_distr_bcast < input001.txt.
hosts.txt	Nodos mpich del clúster arenal de la ECCI, para poder invocar con `mpiexec -n W -f hosts.txt ./hello`, donde `W` es la cantidad de procesos que se quieren correr.

2.1.6. Comunicación colectiva: reduce

Actividad 50 [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. Puede adaptar su solución a Actividad 45 [send_recv_ord_sem] para que la salida aparezca ordenada. El siguiente puede ser un ejemplo de ejecución:

$ mpiexec -n 5 -f hosts.txt ./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

Table 40. Reducción en MPI
Archivo	Descripción	Cambios
lucky_number_reduce.cpp	Todos los procesos escogen un número de la suerte al azar. Note que se usa el número de proceso en la semilla para generar números pseudoaletorios, de lo contrario, es probable que todos los procesos escojan el mismo número de la suerte..
Makefile	Un makefile genérico para compilar con MPI.
hosts.txt	Nodos mpich del clúster arenal de la ECCI, para poder invocar con `mpiexec -n W -f hosts.txt ./lucky_number_reduce`, donde `W` es la cantidad de procesos que se quieren correr.

2.1.7. Comunicación colectiva: all-reduce

Actividad 51 [lucky_number_who]

Escriba un programa donde cada proceso escoge 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 -n 5 -f hosts.txt ./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 -n 1 -f hosts.txt ./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)

Table 41. Reducción en MPI
Archivo	Descripción	Cambios
lucky_number_who.cpp	Cada proceso escoge un número de la suerte y lo envía a todos los demás. Cada proceso recibe el mínimo, la suma y el máximo de los números escogidos. Cada proceso calcula el promedio y compara su número de la suerte contra los estadísticos anteriores.
Makefile	Un makefile genérico para compilar con MPI.
hosts.txt	Nodos mpich del clúster arenal de la ECCI, para poder invocar con `mpiexec -n W -f hosts.txt ./lucky_number_who`, donde `W` es la cantidad de procesos que se quieren correr.

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

Cree una carpeta ejemplos/gpu en su repositorio personal.

2.2.1. Transmisión de calor

Actividad 52 [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.

Table 42. Rendimiento de la transmisión de calor [heat_perf]
Archivo	Descripción	Cambios
heat_perf.ods	Hoja de cálculo para anotar duraciones de ejecución de las actividades siguientes.
heat-tests-large.7z	Algunos casos de prueba binarios.

Actividad 53 [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 52 [heat_perf], 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.

Table 43. Transmisión de calor serial [heat_serial]
Archivo	Descripción	Cambios
heat_serial.c	(Versión serial de libro/documentación)
heat_serial.c	Recibe dos argumentos: un archivo binario que contiene una matrix de flotantes de doble precisión, y un epsilon. Simula transmisión de calor desde el borde de la matriz sobre toda la superficie, hasta que el calor se equilibre. Es decir, hasta que ninguna diferencia supere el epsilon.
Makefile	Un makefile para compilar con GCC.
Makefile-pgi	Un makefile para compilar con PGI (antiguamente The Portland Group). Establece la variable PATH dependiente del laboratorio 102-IF. Para usarlo use la opción `-f` como en `make -f Makefile-pgi`.

Actividad 54 [heat_openmp]

Copie la solución de Actividad 53 [heat_serial] 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 52 [heat_perf] 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 55 [heat_openacc]

Copie la solución de Actividad 53 [heat_serial] 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 52 [heat_perf] 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 52 [heat_perf] 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