Programación concurrente: ejemplos de clase

1. Conjetura de Goldbach

Aplicación gráfica que encuentra las sumas de primos que equivalen a un número dado, de acuerdo a la Conjetura de Goldbach.

Figure 1. Calculadora de Goldbach con las sumas de 15

1.1. Versión 0: interfaz congelada

En esta versión la interfaz gráfica se queda congelada si se ingresan números enteros grandes. El cálculo se hace en la interfaz (clase MainWindow), lo cual mezcla lógica del dominio (modelo) con la interfaz gráfica (vista). Se llama versión 0 porque no puede entregarse a un cliente. Los siguientes son los archivos que conforman el proyecto:

Table 1. Goldbach versión 0.0
Archivo	Descripción	Cambios
main.cpp	Instancia el controlador, la ventana principal, e inicia la ejecución del programa.
MainWindow.h	Encabezado de la ventana principal.
MainWindow.cpp	Implementación de la ventana principal.
MainWindow.ui	Diseño de la interfaz de la ventana principal.
Goldbach.pro	Proyecto de Qt que lista los archivos que forman parte de la aplicación y cómo compilarlos.

1.2. Versión 1: interfaz reactiva ineficiente

1.2.1. Versión 1.0

Para hacer que la interfaz gráfica reaccione a los eventos, existe una solución rápida en el paradigma de programación orientada a eventos, que consiste en procesar los eventos pendientes de la cola cada vez que se realiza el cálculo de las sumas con invocar a QApplication::processEvents(). Sólo la implementación del MainWindow.cpp cambió respecto a la versión anterior:

Table 2. Goldbach versión 1.0
Archivo	Descripción	Cambios
main.cpp	Instancia el controlador, la ventana principal, e inicia la ejecución del programa.
MainWindow.h	Encabezado de la ventana principal.
MainWindow.cpp	Implementación de la ventana principal. Invoca a `QApplication::processEvents()`.
MainWindow.ui	Diseño de la interfaz de la ventana principal.
Goldbach.pro	Proyecto de Qt que lista los archivos que forman parte de la aplicación y cómo compilarlos.

1.2.2. Versión 1.1

La versión 1.1 implementa la barra de progreso. El progreso se calcula considerando el avance sobre el componente a de la suma par a + b = n o de la impar en a + b + c = n, donde a, b, c son naturales primos y n es el número natural ingresado por el usuario.

Table 3. Goldbach versión 1.1
Archivo	Descripción	Cambios
main.cpp	Instancia el controlador, la ventana principal, e inicia la ejecución del programa.
MainWindow.h	Encabezado de la ventana principal. Declara la barra de progreso.
MainWindow.cpp	Implementación de la ventana principal. Implementa barra de progreso.
MainWindow.ui	Diseño de la interfaz de la ventana principal.
Goldbach.pro	Proyecto de Qt que lista los archivos que forman parte de la aplicación y cómo compilarlos.

1.3. Versión 2: separación de asuntos

1.3.1. Versión 2.0

Aunque en la versión 1 la interfaz gráfica responde a eventos de usuario, el rendimiento decayó significativamente. La versión anterior mezcla la lógica del dominio (modelo) con la interfaz gráfica. Esta separación de asuntos debe hacerse y no sólo en dos clases distintas, sino que también la deben realizar distintos trabajadores (workers) de acuerdo al paradigma de programación concurrente, lo cual se hace en la versión 2 de este proyecto.

La vista se libera de la lógica del dominio, que pasa a la clase GoldbachWorker. Cuando el usuario ingresa un número y presiona el botón Start, la vista crea un hilo de ejecución (execution thread) el cual busca sumas de primos que coincidan con el número. La vista le solicita al trabajador que cada vez que encuentra una suma, le avise. Es decir, cada vez que el trabajador encuentra una suma, éste emite el evento (signal) sumFound() el cual invoca al manejador de eventos (slot) appendResult() en la vista. Este encadenamiento se hace con una conexión de signals-and-slots.

El hilo de ejecución GoldbachWorker es un objeto porque el API de Qt lo implementa de esta forma. El hilo debe sobreescribir el método run() el cual es similar a un main(). A partir del momento en que a un QThread se le invoca el método start(), el thread inicia la ejecución de su run() mientras que la vista no espera a que termine, sino que continúa ejecutando las instrucciones posteriores al start().

Table 4. Goldbach versión 2.0
Archivo	Descripción	Cambios
main.cpp	Instancia el controlador, la ventana principal, e inicia la ejecución del programa.
MainWindow.h	Encabezado de la ventana principal. Instancia un hilo de ejecución `GoldbachWorker` como atributo.
MainWindow.cpp	Implementación de la ventana principal. Delega el cálculo de las sumas de Goldbach al hilo de ejecución.
GoldbachWorker.h	Encabezado del hilo de ejecución.
GoldbachWorker.cpp	Implementación del hilo de ejecución.
MainWindow.ui	Diseño de la interfaz de la ventana principal.
Goldbach.pro	Proyecto de Qt que lista los archivos que forman parte de la aplicación y cómo compilarlos.

1.3.2. Versión 2.1

La versión 2.1 re-implementa el botón de Stop. Detener un worker no es usual. A modo de metáfora, es como contratar formalmente un trabajador y asignarle un trabajo. Lo natural es esperar a que termine su trabajo. Si una parte le pide que se detenga, implica romper el contrato. En la computadora hay dos formas de terminar un thread: matándolo, lo cual es una medida extrema que debe evitarse. La segunda es enviándole el mensaje al thread que debe parar. Éste entonces chequea periódicamente si se le ha pedido o no terminar. La clase QThread implementa el método requestInterruption() para indicarle a los threads que deben terminar. Las clases que hereden de QThread pueden preguntar periódicamente si se ha cancelado el trabajo con isInterruptionRequested().

Table 5. Goldbach versión 2.1
Archivo	Descripción	Cambios
main.cpp	Instancia el controlador, la ventana principal, e inicia la ejecución del programa.
MainWindow.h	Guarda un puntero al `GoldbachWorker` como atributo para poder cancelarlo luego.
MainWindow.cpp	Envía el mensaje `requestInterruption()` al thread cuando el usuario presiona `Stop`.
GoldbachWorker.h	Encabezado del hilo de ejecución.
GoldbachWorker.cpp	Chequea en cada iteración de los ciclos "pesados" si el usuario ha cancelado el cálculo para romperlos.
MainWindow.ui	Diseño de la interfaz de la ventana principal.
Goldbach.pro	Proyecto de Qt que lista los archivos que forman parte de la aplicación y cómo compilarlos.

1.4. Versión 3: interfaz no se satura

1.4.1. Versión 3.0

La versión 2 cumple el objetivo de separar los asuntos en dos trabajadores. La actualización de la interfaz la realiza el hilo principal y la búsqueda de sumas de Goldbach la realiza el hilo trabajador. Sin embargo, el worker encuentra sumas más rápido de lo que la interfaz tarda en pintarlas en la pantalla. Por tanto, el worker satura la cola de eventos del hilo principal y la interfaz reacciona lento de nuevo.

La tercera versión cambia el control a uno que implemente el patrón modelo-vista. Siguiendo el ejemplo de Qt llamado "Fetch more", se utiliza un QListView que no almacena las sumas encontradas (los datos), sino que un modelo las guarda en un arreglo. Por tanto se crea la clase GoldbachModel que actúa como la fuente de datos (sumas) para el QListView y además controla al worker. La vista solicita al modelo sólo los datos que el usuario le pide mostrar. De esta forma, la vista "va a la velocidad del usuario humano" y no se satura con cantidades gigantescas de datos que el thread produzca.

Table 6. Goldbach versión 3.0
Archivo	Descripción	Cambios
main.cpp	Instancia el controlador, la ventana principal, e inicia la ejecución del programa.
MainWindow.h	La ventana principal ya no administra los workers, sino que lo delega a una clase llamada `GoldbachModel`.
MainWindow.cpp	Delega el cálculo de las sumas de Goldbach al modelo `GoldbachModel`.
GoldbachModel.h	Fuente de datos (sumas) para la interfaz gráfica. Internamente delega el cálculo de las sumas a un hilo de ejecución. Almacena las estructuras de datos en arreglos en memoria, donde el hilos escribe los resultados directamente sin usar eventos.
GoldbachModel.cpp	Delega el cálculo de las sumas de Goldbach a los hilos de ejecución, y responde a las solicitudes de resultados hechas por la interfaz gráfica.
GoldbachWorker.h	Para incrementar la eficiencia, el hilo de ejecución disminuye la comunicación. Cada vez que encuentra una suma de Goldbach, la agrega a un contenedor que recibe del `GoldbachModel`.
GoldbachWorker.cpp	Implementación del hilo de ejecución.
MainWindow.ui	Diseño de la interfaz de la ventana principal. Cambia el `QPlainTextEdit` por un `QListView`.
Goldbach.pro	Proyecto de Qt que lista los archivos que forman parte de la aplicación y cómo compilarlos.

1.4.2. Versión 3.1

La versión 3.1 implementa dos funcionalidades:

Re-implementa el botón Stop. Cuando el usuario presiona Stop, la interfaz gráfica envía un evento (signal) al modelo y éste lo retransmite al hilo de ejecución.
Actualiza la barra de progreso. El trabajador guarda un atributo entero para poder determinar si ha incrementado un 1% en la búsqueda de las sumas. Sólo en tal caso, emite un evento (señal) que el modelo recibe. El modelo lo retransmite a la interfaz gráfica. Este método de detectar un 1% de progreso no es eficiente.

Table 7. Goldbach versión 3.1
Archivo	Descripción	Cambios
main.cpp	Instancia el controlador, la ventana principal, e inicia la ejecución del programa.
MainWindow.h	La ventana principal.
MainWindow.cpp	Cuando se presiona el botón `Stop` avisa al objeto `GoldbachModel`.
GoldbachModel.h	Declara métodos para detener al `GoldbachWorker` y retransmitir el porcentaje de progreso.
GoldbachModel.cpp	Implementa métodos para detener al `GoldbachWorker` y retransmitir el porcentaje de progreso.
GoldbachWorker.h	Declara un atributo para saber cuándo ha incrementado un 1% de progreso
GoldbachWorker.cpp	Avisa cuando ha incrementado en al menos un 1% de progreso
MainWindow.ui	Cambia el título de la ventana de `MainWindow` a `Goldbach`.
Goldbach.pro	Proyecto de Qt que lista los archivos que forman parte de la aplicación y cómo compilarlos.

1.5. Versión 4: múltiples trabajadores

1.5.1. Versión 4.0

La versión 3 cumple el objetivo de separar los asuntos en dos trabajadores. La actualización de la interfaz la realiza el hilo principal y la búsqueda de sumas de Goldbach la realiza el hilo trabajador. Si una computadora tiene varios núcleos (CPU), por ejemplo 16 núcleos, el programa anterior sólo usa dos núcleos y desaprovecha los restantes (14 núcleos ociosos en el ejemplo).

La versión 4 incrementa el rendimiento de la calculadora de Golbach aprovechando todos los núcleos de la computadora donde se corre el programa. En lugar de crear un hilo trabajador, se crean W hilos, donde W es la cantidad de núcleos disponibles en la máquina, indicada por QThread::idealThreadCount(). Si se quiere, se puede restar uno para dejar un núcleo disponible para el hilo principal que debe actualizar la interfaz gráfica. El siguiente código muestra la idea general de cómo lanzar varios hilos.

1
2
3
4
5
6
7 int ideal = QThread::idealThreadCount() - 1;
for ( int current = 0; current < ideal; ++current  )
{
	GoldbachWorker* worker = new GoldbachWorker(number, current, ideal, this);
	// Hacer las conexiones para reaccionar cuando el worker:
	// (1) encuentra una suma, (2) incrementa el porcentaje, (3) termina
}

Cuando se crea, cada hilo recibe el número ingresado por el usuario (number), el número de trabajador (workerNumber), la cantidad de hilos que están buscando sumas para el mismo número (workerCount) y el objeto padre (parent):

1
2
3
4 class GoldbachWorker : public QThread
{
  public:
    explicit GoldbachWorker(long long number, int workerNumber, int workerCount, QObject *parent = nullptr);

Table 8. Goldbach versión 4.0
Archivo	Descripción	Cambios
main.cpp	Instancia el controlador, la ventana principal, e inicia la ejecución del programa.
MainWindow.h	La ventana principal.
MainWindow.cpp	Implementa la ventana principal.
GoldbachModel.h	En lugar de un `GoldbachWorker` tiene una colección de ellos. En lugar de un arreglo de resultados, tiene un arreglo de arreglos de resultados, uno por cada `GoldbachWorker`.
GoldbachModel.cpp	Crea W workers. Busca resultados que pide la interfaz dentro de los arreglos para resultados.
GoldbachWorker.h	Declara atributos para saber el número de trabajador y cuántos más con él están calculando sumas del mismo número.
GoldbachWorker.cpp	Inicializa los atributos para saber el número de trabajador y cuántos más con él están calculando sumas del mismo número.
MainWindow.ui	Diseño de la interfaz con el usuario.
Goldbach.pro	Proyecto de Qt que lista los archivos que forman parte de la aplicación y cómo compilarlos.

1.5.2. Versión 4.1

En la versión 4.0 la barra de progreso crece y decrece debido a que los hilos de ejecución reportan sus porcentajes de incremento, y estos no necesariamente lo hacen a la misma velocidad. La versión 4.1 corrige este problema. Cada vez que un worker informa su progreso al GoldbachModel, éste estima el porcentaje de progreso de todos los workers en conjunto como el mínimo de todos. El mínimo es una medida más realista porque sigue el principio de que "un equipo de trabajadores es tan rápido como el más lento de todos".

Para poder calcular el mínimo porcentaje de progreso, el GoldbachModel almacena un arreglo de porcentajes, uno por cada trabajador. Los trabajadores además de indicar su porcentaje de progreso, indica su número de trabajador para que el GoldbachModel sepa cuál porcentaje actualizar en el arreglo.

Cuando el GoldbachModel recibe la primera señal de algún GoldbachWorker que ha tenido un avance de al menos un 1%, invoca a fetchMore( QModelIndex() ). Esto provoca que la vista tenga que actualizarse con algunos datos. De esta forma el usuario puede iniciar la exploración de los datos usando la barra de desplazamiento (scroll) o las flechas en el teclado.

Algo similar ocurre con terminar los cálculos de suma. En la versión 4.o, cuando un trabajador termina, se informa a la interfaz gráfica que rehabilite los campos para iniciar otro cálculo, lo cual es incorrecto. Otros trabajadores no han terminado. El GoldbachModel corrige este problema contando cuántos trabajadores han terminado. Cuando este conteo alcanza la cantidad total de trabajadores, se informa a la interfaz que el cálculo ha finalizado.

Table 9. Goldbach versión 4.1
Archivo	Descripción	Cambios
main.cpp	Instancia el controlador, la ventana principal, e inicia la ejecución del programa.
MainWindow.h	La ventana principal.
MainWindow.cpp	Implementa la ventana principal.
GoldbachModel.h	Declara un arreglo de porcentajes de progreso y un contador de trabajadores que han terminado de realizar cálculos.
GoldbachModel.cpp	Calcula el mínimo de los porcentajes de progreso y si ese mínimo incrementa en 1% o más avisa a la interfaz. Avisa cuando todos los hilos de ejecución han terminado de hacer cálculos.
GoldbachWorker.h	Avisa su número de trabajador cuando tiene un 1% o más de progreso
GoldbachWorker.cpp	Reporta su número de trabajador cuando incrementa su progreso.
MainWindow.ui	Diseño de la interfaz con el usuario.
Goldbach.pro	Proyecto de Qt que lista los archivos que forman parte de la aplicación y cómo compilarlos.

1.5.3. Versión 4.2

En las versiones 4.0 y 4.1 se crean W hilos de ejecución, tantos como el número de CPU disponibles en el sistema donde corre el programa. Sin embargo, todos los hilos de ejecución hacen el mismo trabajo. Es decir, todos encuentran todas las sumas de primos del número N. Por tanto, los resultados aparecen en la interfaz W veces, lo cual es incorrecto, el programa es igual de lento que las versiones anteriores, y se hace un consumo injustificado de recursos.

No tiene sentido que todos los trabajadores busquen las mismas sumas. Este problema se resuelve con paralelismo de datos, de tal forma que cada hilo pruebe distintos primos tratando de encontrar sumas. El paralelismo requiere diseñar dos pasos: descomposición y mapeo de los datos. La descomposición divide los datos en trozos que pueden ser trabajados en paralelo. El mapeo asocia los trozos con los trabajadores.

Se sugiere que los hilos de ejecución se repartan los valores de a en los que buscan sumas, donde a proviene de las fórmulas a + b = n y a + b + c = n. Los tres números que recibe cada GoldbachWorker por parámetro en el constructor le servirán para hacer la división.

Por ejemplo, si el número ingresado por el usuario es 10, se tienen que encontrar todos los primos a y b tal que 10 = a + b. Para hacer la descomposición de datos, puede tomar la siguiente sugerencia. El ciclo más externo en GoldbachWorker::calculateEvenGoldbach() buscaría valores primos para a entre:

Es decir, 10 - 2 = 8 valores de a para repartir. Supóngase que se lanzan w = 3 trabajadores. Si se repartiera el trabajo equitativo, cada trabajador recibiría div(8, 3) = 2 unidades de trabajo. Pero quedarían mod(8, 3) = 2 unidades por repartir. Este residuo se puede repartir a los dos primeros trabajadores, los cuales tendrían 2 + 1 = 3 unidades de trabajo y el último trabajador tendría 2 unidades. De esta forma, las a se repartirían al trabajador con índice i de la siguiente forma:

a	i
2	0
3	0
4	0
5	1
6	1
7	1
8	2
9	2

Al hacer que las primeras a sean calculadas por el primer trabajador, las subsecuentes a por el segundo trabajador, y así sucesivamente, se garantiza que los resultados se mantengan en orden en el arreglo de arreglos de sumas.

Dado que los GoldbachWorker deben calcular en qué a deben iniciar y finalizar su trabajo, necesitan una función matemática. La siguiente tabla obtiene el inicio s (de start) y el final f (de finish) a partir del ejemplo de la tabla anterior:

i	s	f
0	2	5
1	5	8
2	8	10

De esta forma un hilo de ejecución debe buscar sumas en el rango entero [s, f[. Se necesitan dos funciones matemáticas s y f que puedan obtener estos dos valores, en función de la cantidad de trabajo/datos D, la cantidad de trabajadores W, el número de trabajador i, y el número del trabajo donde todos deben iniciar B. Estas relaciones se pueden deducir como:

\$ s(D, W, i, B) = B + i \cdot \text{div}(D - B, W) + \min( i, \mod(D - B, W) ) \$

\$ f(D, W, i, B) = s(D, W, i + 1, B) \$

La versión 4.2 implementa:

La descomposición y mapeo de trabajo entre los hilos de ejecución, con las funciones reutilizables calculateStart() y calculateFinish().
Corrige el error por cero en el porcentaje de progreso. Aunque este cálculo sigue siendo ineficiente.
Corrige el número de resultado reportado al usuario. Este número se escribe antes de dos puntos en cada suma resultado, por ejemplo el 1 en 1: 3 + 7.
Evita desde la interfaz gráfica que se inicie el cálculo de números inválidos.

Table 10. Goldbach versión 4.2
Archivo	Descripción	Cambios
main.cpp	Instancia el controlador, la ventana principal, e inicia la ejecución del programa.
MainWindow.h	La ventana principal.
MainWindow.cpp	Evita iniciar los cálculos para números inválidos, pues haría que los hilos de ejecución se caigan.
GoldbachModel.h	Administra los hilos de ejecución y provee resultados a la interfaz gráfica.
GoldbachModel.cpp	Reporta la cantidad correcta de sumas cuando terminan los cálculos. Reporta el número correcto de cada suma resultado.
GoldbachWorker.h	Declara funciones estáticas reutilizables para calcular el inicio y final de los datos que se debe distribuir entre trabajadores.
GoldbachWorker.cpp	Declara funciones estáticas reutilizables para calcular el inicio y final de los datos que se debe distribuir entre trabajadores. Usa esas funciones para calcular el inicio y final del trabajador en los dos ciclos. Corrige el error por cero calculando el porcentaje de progreso. No reporta el número de resultado de cada suma encontrada, esto lo hará el `GoldbachModel`.
MainWindow.ui	Diseño de la interfaz con el usuario.
Goldbach.pro	Proyecto de Qt que lista los archivos que forman parte de la aplicación y cómo compilarlos.

1.6. Versión 5: testing

1.6.1. Versión 5.0

De nada sirve hacer un programa más rápido o consumir mucha menos memoria, si produce resultados incorrectos. Ante la falta de un framework para pruebas de software concurrente, se creó un un programa casero de pruebas de caja blanca. Esta versión es la misma que la versión 4, pero incluye el programa casero (GoldbachTester) y algunos casos de prueba pequeños.

El programa de pruebas usa Qt, pero en lugar de usar interfaz gráfica tiene una interfaz de línea de comandos, por conveniencia y para probar que las clases del modelo (GoldbachModel y GoldbachWorker) son independientes de la interfaz. El programa recibe por parámetro carpetas que contienen casos de prueba:

./GoldbachTester test_folder1 test_folder2 ... test_folderN

Se tomó como convención que un caso de prueba es un archivo de texto cuyo nombre es el número a probar, y cuyo contenido son las sumas de Goldbach usando el mismo formato de salida de la Versión 0: interfaz congelada.

Table 11. GoldbachTester versión 5.0
Archivo	Descripción	Cambios
test.cpp	Contiene el `main()` que instancia el controlador de pruebas e inicia las pruebas.
GoldbachTester.h	Encabezado de la clase controladora que representa al programa de pruebas como un todo. Utiliza un atributo para contar cuántos modelos han terminado de hacer cálculos y por lo tanto, saber cuándo terminar el ciclo de eventos.
GoldbachTester.cpp	Entra en el ciclo de eventos y se sale de éste hasta que hayan terminado todos los modelos. Cada vez que un modelo termina, compara las sumas que encontró con las del caso de prueba.
GoldbachModel.h	Controla los hilos de ejecución. Se agregó un método `fetchAllSums()` que retorna un contenedor con las sumas consolidadas encontradas por los workers.
GoldbachModel.cpp	La implementación del método `fetchAllSums()` une los resultados en orden. Esta subrutina no tiene que ser eficiente, dado que sólo es invocada por el programa de pruebas. No crea una cantidad negativa de hilos de ejecución si se llama con un número negativo.
GoldbachTester.pro	Proyecto de Qt que indica generar una aplicación de línea de comandos en lugar de una aplicación gráfica.
100.txt	Ejemplo de un caso de prueba par. Generado manualmente con un ejemplo de Wikipedia.
15.txt	Ejemplo de un caso de prueba impar. Generado con la versión 0 de Goldbach.

1.6.2. Potenciales mejoras

Haga que cada hilo cuente su duración mientras está encontrando las sumas en el rango de valores que le toca. Imprima en la salida o error estándar (o algún control en la interfaz gráfica) su duración.
Implemente una forma alterna de calcular el porcentaje de incremento. Recuerde que las divisiones o módulos son operaciones muy caras en tiempo de ejecución.
Modifique el programa de pruebas para que presente un mensaje de ayuda cuando se invoca sin parámetros, por ejemplo:
```
./GoldbachTester
Usage: GoldbachTester test_folder1 test_folder2 ... test_folderN
```
Haga que el programa de pruebas no entre en el ciclo de eventos si no se encuentran casos de prueba en las carpetas dadas en línea de comandos.
El programa de pruebas hecho en clase reporta en la salida estándar un resultado para cada archivo probado. El programador debe recorrer toda la salida en busca de errores, lo cual es tedioso cuando la cantidad de casos de prueba es considerable. Modifique el programa de pruebas para que produzca una salida más ejecutiva para el programador. Por ejemplo, si el programa pasa todos los casos de prueba, podría indicar:
```
./GoldbachTester test
87 test cases: 87 passed (100%), 0 failed (0%).
```

Si el programa falla uno o más casos de prueba, imprima detalles que ayuden al programador a encontrar el fallo, por ejemplo:

./GoldbachTester test
test case 870 failed at line 31:
	expected: "31: 263 + 607"
	produced: "31: 269 + 601"

test case 5431 failed at line 15379:
	expected: "15378: 1789 + 1811 + 1831"
	produced: ""

27 test cases: 25 passed (93%), 2 failed (7%).

1.7. Versión 6: profiling optimizations

Para incrementar el rendimiento de una aplicación se optimizan las secciones críticas de consumo de recursos. El paradigma de programación concurrente ofrece un mecanismo para optimizar, que consiste en la división de tareas o datos entre varios trabajadores (workers). Sin embargo, existe una regla valiosa que indica que no se debe sobre-optimizar. La sobre-optimización puede ser más dañina que no optimizar del todo, ya que el código se torna de difícil lectura y mantenimiento. Por tanto se debe hacer un balance.

Resulta especialmente útil para los profesionales en computación disponer de herramientas que ayuden a localizar los puntos críticos de código que consumen abundantes recursos, en especial cuando la cantidad de código fuente es abrumadora (miles o millones de líneas de código). Un tipo de herramientas de análisis dinámico de código, llamadas profiling tools pueden ayudar en esta necesidad. Son herramientas que mientras un ejecutable corre, guardan estadísticas de eventos o consumo de un recurso particular, como procesamiento, memoria dinámica, fallos de caché, uso de red, etc. Estas estadísticas ayudan a los programadores a comprender el comportamiento de los programas y ubicar las áreas críticas de código que se deben optimizar.

En clase se presentó Valgrind, la herramienta de profiling de facto para Linux, ya que este sistema operativo es el más utilizado en clústers de super-computación del mundo. Valgrind consta de un conjunto de herramientas, cada una recaba distintos datos sobre un programa en ejecución. La herramienta callgrind registra la cantidad de instrucciones de procesador que ejecuta cada trozo del programa. Si se incluye el código fuente en el ejecutable, calgrind reporta las líneas que consumen más instrucciones de procesador. Por eso conviene compilar en "modo debug":

# Ir al directorio donde esta el codigo fuente
cd ~/Documents/repositorio/actividades/Goldbach

# Crear una carpeta para archivos binarios
mkdir build-goldbach-debug
cd build-goldbach-debug/

# Compilar en "debug mode" con 4 procesos al mismo tiempo
/opt/Qt5.11.1/5.11.1/gcc_64/bin/qmake ../Goldbach.pro CONFIG+=debug
make -j4

# Pide al valgrind correr el ejecutable y hacer contabilidad de las
# instrucciones ejecutadas en el procesador
valgrind --tool=callgrind --separate-threads=yes ./Goldbach

# callgrind genera archivos de texto con la contabilidad de instrucciones
# kcachegrind visualiza el código fuente y su consumo de instrucciones
kcachegrind &

La herramienta KCachegrind permite al desarrollador 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. Para el ejemplo de Goldbach, no es sorpresa que sea el método GoldbachWorker::isPrime(), dado que es una base de código muy pequeña y con algoritmos fáciles de comprender. La siguiente figura muestra una captura de pantalla de KCachegrind tras analizar la ejecución de la Calculadora de Goldbach con el número 11111.

Figure 2. Visualización de KCachegrind de las líneas que consumen más procesamiento en Goldbach

En la esquina superior izquierda muestra un gráfico de consumo por cada thread. 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.

El desarrollador estará tentado a hacer modificaciones en el código para optimizar el consumo de recursos. Sin embargo, por cada cambio debe asegurarse de que se mantenga la correctitud y que realmente se haya alcanzado un mayor rendimiento. Conviene seguir un método:

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.

Para determinar si hubo una ganancia de rendimiento, se puede utilizar una medida relativa llamada speedup \$S\$ (incremento de velocidad), que se calcula como la relación entre el tiempo que tarda una computación serial (\$T_\text{serial}\$) contra el tiempo que tarda la misma computación en paralelo (\$T_\text{parallel}\$):

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

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.

2. Concurrencia compartida

La concurrencia de memoria compartida, 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.

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

2.1.1. Hola mundo (thread)

El siguiente es un "Hola mundo" en Pthreads:

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

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

2.1.3. Hola mundo numerado (memoria privada)

Actividad 2 [hello_i_of_w]

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) para cada thread.

Table 14. Hola mundo numerado [hello_i_of_w]
Archivo	Descripción	Cambios
hello_i_of_w.c	Varios threads saludan indicando su identificador en la salida estándar.
Makefile	El Makefile cambia el nombre del ejecutable y del archivo fuente.

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

2.1.4. Hola mundo ordenado (memoria compartida) con espera activa

Actividad 4 [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 15. 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	Se agregaron dos reglas típicas: una por defecto que genera todos los productos (`make all`) y otra para eliminar los archivos binarios (`make clean`).

Actividad 5 (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.

2.1.5. Posición en la carrera (mutex)

Actividad 6 [position_race]

Modifique su solución a Actividad 2 [hello_i_of_w] para implementar una carreara 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 16. 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	Cada vez que se cambia de proyecto, hay que cambiar el nombre de los archivos fuente y del ejecutable. Esta versión usa variables automáticas para hacer las reglas reutilizables entre proyectos, además de una variable definida (`APPNAME`) que puede cambiarse de ejercicio en ejercicio.

2.1.6. Productor-consumidor (semáforo)

Actividad 7 [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 100 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 17. Productor-consumidor, versión 1 con `sem_init` [producer_consumer]
Archivo	Descripción	Cambios
producer_consumer.c	Simula el problema del productor-consumidor.
Makefile	Asume que el nombre de la carpeta es el nombre del ejecutable y de que existe un archivo `.c` con el mismo nombre de la carpeta.

La versión anterior utiliza semáforos no nombrados. Son regiones de la memoria alojadas con sem_init() y liberadas con sem_destroy(). En macOS, estos semáforos están desaprobados (deprecated). La siguiente versión modifica la anterior para usar semáforos nombrados, los cuales 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 continuarán usándolos o fallarán.

Table 18. Productor-consumidor, versión 2 con semáforos nombrados [producer_consumer]
Archivo	Descripción	Cambios
producer_consumer_2.c	Usa semáforos nombrados para resolver el problema del productor-consumidor.
Makefile	Idéntico a la versión anterior.

2.1.7. Carrera de relevos (barrera)

Actividad 8 [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 19. 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	Agrega la regla `make gitignore` para ignorar el ejecutable en control de versiones (crea o reemplaza el archivo `.gitignore`). Usa variables de facto para controlar el compilador, banderas de compilación, y bibliotecas.

2.1.8. Misterio (variable de condición)

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

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

Actividad 10 [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 20. 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. El usuario tiene que colocar los registros en un lugar seguro de la memoria de tal forma que una "instancia" de un arreglo no interfiera con otra. Esto lo hace reentrante.
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 11 [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

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

Actividad 13 [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 21. 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.2. OpenMP

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.

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

El siguiente es un "Hola mundo" en OpenMP:

Table 22. Hola mundo en OpenMP
Archivo	Descripción	Cambios
hello.c	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 10 [array_reentrant].

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

cc -g -Wall -Wextra -fopenmp source.c -o executable

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

Actividad 14 [omp_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 23. Hola mundo múltiple en OpenMP
Archivo	Descripción	Cambios
hello_w.c	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.

2.2.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:

Table 24. Parallel-for en OpenMP
Archivo	Descripción	Cambios
parallel_for.c	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.

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

Table 25. Parallel-for en OpenMP
Archivo	Descripción	Cambios
several_for.c	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.

2.2.5. Ordenamiento par-impar

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

Table 26. Ordenamiento par-impar
Archivo	Descripción	Cambios
odd_even_sort_two_for.c	Fragmento de código discutido en clase que utiliza las directivas de OpenMP para paralelizar el ordenamiento par-impar.

Actividad 18 [odd_even_sort_perf]

Con la herramienta gprof 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 thread, 1xCPU, y 2xCPU, donde CPU es la cantidad de CPUs disponibles en la máquina donde se realizaron las pruebas.

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

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

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

3.1.1. Hola mundo (proceso)

El siguiente es un "Hola mundo" en MPI:

Table 27. Hola MPI
Archivo	Descripción	Cambios
hello.c	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.

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

Actividad 19 [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 28. Hola MPI híbrido
Archivo	Descripción	Cambios
hello_hybrid.c	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 20 [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 29. Distribución del rango con argumentos
Archivo	Descripción	Cambios
hybrid_distr_arg.c	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.

3.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 21 [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 30. Comunicación punto a punto ordenada
Archivo	Descripción	Cambios
send_recv_ord.c	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 22 [send_recv_urd]

Modifique el ejemplo anterior 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 31. Comunicación punto a punto no ordenada
Archivo	Descripción	Cambios
send_recv_urd.c	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.

3.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 23 [hybrid_distr_stdin]

Modifique el programa del rango distribuido (Actividad 20 [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? Copie el resultado en un archivo output.md.

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. Tras corregir el programa, agregue la salida que produce a su archivo output.md.

Table 32. Distribución del rango leído en la entrada estándar
Archivo	Descripción	Cambios
hybrid_distr_stdin.c	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 24 [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

(Ejemplo pendiente)

3.1.5. Comunicación colectiva: broadcast

Actividad 25 [hybrid_distr_bcast]

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

Table 33. Broadcast en MPI
Archivo	Descripción	Cambios
hybrid_distr_bcast.c	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
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.

3.1.6. Comunicación colectiva: reduce

Actividad 26 [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 -n 5 -f hosts.txt ./lucky_number_reduce
Process 2: my lucky number is 10
Process 0: my lucky number is 83
Process 3: my lucky number is 10
Process 1: my lucky number is 56
Process 4: my lucky number is 62
Process 0: all minimum: 10
Process 0: all average: 44.20
Process 0: all maximum: 83

Table 34. Reducción en MPI
Archivo	Descripción	Cambios
lucky_number_reduce.c	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. Las diferencias se comparan contra Hola mundo (proceso).
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.

3.1.7. Comunicación colectiva: all-reduce

Actividad 27 [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 2: my lucky number (07) is the minimum (07)
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 0: my lucky number (83) is greater than the average (36.00)
Process 4: my lucky number (26) is less than the average (36.00)
Process 3: my lucky number (46) is greater than the average (36.00)
Process 0: my lucky number (83) is the maximum (83)

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 35. Reducción en MPI
Archivo	Descripción	Cambios
lucky_number_who.c	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 ./hello`, donde `W` es la cantidad de procesos que se quieren correr.