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.

fig goldbach v3
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.

file 7z Descargar Goldbach versión 0

El cálculo se hace en la interfaz (clase MainWindow), lo cual mezcla lógica del dominio (modelo) con la interfaz gráfica (vista). Más adelante se pide corregir el problema de la interfaz que se congela. Los siguientes son los archivos que conforman el proyecto:

Table 1. Goldbach versión 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.

Goldbach.pro

Proyecto de Qt que lista los archivos que forman parte de la aplicación y cómo compilarlos.
Actividad 1 [goldbach]

Cuando se ingresa un número relativamente grande, la interfaz de la aplicación de Goldbach se congela. Existe un botón de detener (Stop) ideado para permitir al usuario detener el cálculo de sumas. Sin embargo, este botón no reacciona porque se congela también. Indague, en forma individual, posibles soluciones a este problema y corrija el código fuente para que cuando se presiona el botón Stop se detenga el cálculo de sumas de Goldbach.

Agregue su solución a su repositorio de control de versiones, en una subcarpeta actividades/Goldbach.

1.2. Versión 1: interfaz reactiva ineficiente

file 7z Descargar Goldbach versión 1

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. Por ejemplo:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
long long MainWindow::calculateEvenGoldbach(long long number)
{
	long long results = 0;
	for ( long long a = 2; a < number; ++a )
	{
		if ( ! isPrime(a) ) continue;
		long long b = number - a;
		if ( b >= a && isPrime(b) )
			this->appendResult( tr("%1: %2 + %3").arg(++results).arg(a).arg(b) );

		// Update the progress bar
		this->updateProgressBar((a + 1) * 100 / number);
		// If user cancelled, stop calculations
		if ( this->isStopped() )
			return results;

		// Process all pending events in the queue
		QApplication::processEvents(); (1)
	}
	return results;
}

  1. Procesa los eventos pendientes en la cola y retorna cuando la cola se vacía

Sólo la implementación del MainWindow.cpp cambió respecto a la versión anterior:

Table 2. Goldbach versión 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.

MainWindow.cpp

Implementación de la ventana principal.

file diff

Goldbach.pro

Proyecto de Qt que lista los archivos que forman parte de la aplicación y cómo compilarlos.
Actividad 2 [goldbach]

Aunque en la versión 1 la interfaz gráfica responde a eventos de usuario, el rendimiento decayó significativamente. Indague sobre hilos de ejecución. Implemente un trabajador que herede de QThread y encuentre las sumas de Goldbach. Libere a la vista (MainWindow) de la responsabilidad de encontrar las sumas.

Indague sobre manejo de eventos en Qt (signals-and-slos). Use eventos para que cada vez que el trabajdor encuentre una suma, emita una señal (evento) que la vista use para agregar la suma encontrada al campo de texto de resultados. Implemente otra señal donde el trabajador reporte cada vez que ha incrementado un 1% en la búsqueda de las sumas. Implemente una tercera señal donde el trabajador avisa a la vista cuando ha concluido la búsqueda de sumas, para que la vista pueda re-habilitar los botones para iniciar un nuevo cálculo.

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

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.

file 7z Descargar Goldbach versión 2

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

Table 3. Goldbach versión 2
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.

file diff

MainWindow.cpp

Implementación de la ventana principal. Delega el cálculo de las sumas de Goldbach al hilo de ejecución.

file diff

GoldbachWorker.h

Encabezado del hilo de ejecución.

GoldbachWorker.cpp

Implementación del hilo de ejecución.

Goldbach.pro

Proyecto de Qt que lista los archivos que forman parte de la aplicación y cómo compilarlos.

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

Actividad 3 [goldbach]

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

Incremente 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, cree W - 1 hilos, donde W es la cantidad de núcleos disponibles en la máquina, indicada por QThread::idealThreadCount(). Se resta 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);

No tiene sentido que todos los trabajadores busquen las mismas sumas. Implemente paralelismo de datos, de tal forma que cada hilo pruebe distintos primos tratando de encontrar sumas. Los tres números que recibe 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 división de datos, puede tomar la siguiente sugerencia. Note que el ciclo más externo en GoldbachWorker::calculateEvenGoldbach() buscaría valores primos para a entre:

2
3
4
5
6
7
8
9

Puede considerar los valores anteriores como los datos a dividir. Si se lanzan w = 3 trabajadores, encuentre relaciones matemáticas para dividir las ocho a anteriores entre los w = 3 trabajadores. Modifique el código fuente para que cada hilo sólo pruebe un subconjunto de los datos.

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. Reporte también la duración total del proceso (ya lo hace la interfaz gráfica).

Verifique que la salida que genera su solución paralela (las sumas encontradas) sea correcta y completa, aunque no lo haga en orden. Puede comparar contra la salida que genera la Versión 0: interfaz congelada.

1.4. Versión 3: interfaz no se satura

La tercera versión utiliza un QListView que no almacena las sumas encontradas (los datos), sino que el modelo las guarda en un arreglo. La vista solicita al modelo sólo los datos que el usuario le pide mostrar. De esta forma, la vista no se satura con cantidades gigantescas de datos que el o los threads produzcan.

file 7z Descargar Goldbach versión 3

Los cambios que se hicieron con respecto a la versión 2 fueron:

Table 4. Goldbach versión 3
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. La ventana principal no administra los workers, sino una clase controladora de modelos llamada GoldbachCalculator.

file diff

MainWindow.cpp

Implementación de la ventana principal. Delega el cálculo de las sumas de Goldbach al controlador de workers (GoldbachCalculator).

file diff

GoldbachCalculator.h

Controla los hilos de ejecución. Almacena las estructuras de datos donde los hilos escriben los resultados.

GoldbachCalculator.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 controlador de modelos GoldbachCalculator.

file diff

GoldbachWorker.cpp

Implementación del hilo de ejecución.

file diff

Goldbach.pro

Proyecto de Qt que lista los archivos que forman parte de la aplicación y cómo compilarlos.
Actividad 4 [goldbach]

  1. Actualice su solución de Goldbach para que la interfaz gráfica no se sature por los datos que generan los múltiples hilos de ejecución. Debe agregar el controlador de modelos GoldbachCalculator o implementar una clase afín.

  2. Utilice estructuras de datos que permitan a los hilos de ejecución escribir sus resultados sin interrumpir a otros.

  3. Ajuste los métodos heredados de QAbstractListModel en GoldbachCalculator para que la interfaz QListView pueda obtener los resultados en el orden esperado.

Actividad 5 [goldbach]

Modifique su solución para que la barra de progreso en la interfaz gráfica se actualice conforme los workers progresan en su cálculo de sumas. Tenga en cuenta las siguientes consideraciones.

  1. Un worker debería emitir un evento sólo cuando realmente ha tenido un incremento de un 1% o más, con el fin de no saturar la cola de eventos de la interfaz.

  2. Cada worker informa su progreso al GoldbachCalculator. Este debe tener alguna forma de estimar el porcentaje de progreso de todos los workers en conjunto y reportarlo a la interfaz gráfica, sólo cuando realmente haya ocurrido un incremento de un 1% o más.

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

  4. Sugerencia: cuando el GoldbachCalculator recibe la primera señal de algún GoldbachWorker que ha tenido un avance de al menos un 1%, puede invocar 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.

1.5. Versión 4: testing

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 3, pero incluye el programa casero (GoldbachTester) y algunos casos de prueba pequeños.

file 7z Descargar Goldbach versión 4

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 (GoldbachCalculator 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 5. GoldbachTester en la versión 4
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.

GoldbachTester.cpp

El controlador de pruebas busca casos de prueba en las carpetas dadas por argumentos de línea de comandos y por cada caso instancia un objeto GoldbachCalculator. Este programa es agresivamente concurrente, lo cual puede ser más ineficiente que su versión serial.

GoldbachCalculator.h

Controla los hilos de ejecución. Se agregó un método getAllSums() que retorna un contenedor con las sumas consolidadas encontradas por los workers.

file diff

GoldbachCalculator.cpp

La implementación del método getAllSums() en esta versión sólo retorna las sumas que encontró el único worker en este ejemplo, pero si se tienen varios workers deben unirse los resultados en orden. Esta subrutina no tiene que ser eficiente, dado que sólo es invocada por el programa de pruebas.

file diff

GoldbachTester.pro

Proyecto de Qt que indica generar una aplicación de línea de comandos en lugar de una aplicación gráfica.

222.txt

Ejemplo de un caso de prueba par. Generado con la versión 0 de Goldbach.

45.txt

Ejemplo de un caso de prueba impar. Generado con la versión 0 de Goldbach.
Actividad 6 [goldbach]

Cree al menos 8 casos de prueba. Descargue la versión 0 ó 1 de la calculadora de Goldbach, compile y corra una instancia del programa. Escoja números pares e impares en los rangos de la tabla de abajo. Para cada número escogido, cree un archivo usando el número como nombre y agregue la extensión .txt. Por ejemplo, si escogió el número 131, cree un archivo 131.txt. Copie el resultado generado por la Calculadora de Goldbach v0 ó v1 y escríbalo como contenido del archivo. Guarde sus archivos en una carpeta actividades/Goldbach/test.

Table 6. Rangos de números sugeridos para generar casos de prueba

]-∞, 0[

[0, 100[

[100, 1000[

[1000, 10000[
Actividad 7 [goldbach]

Ajuste su solución de Goldbach para incorporar el programa de pruebas hecho en clase. Debe adaptar el método GoldbachCalculator::getAllSums() para consolidar los resultados de los hilos de ejecución en el orden correcto y el formato usado en los casos de prueba. No es necesario que este método sea eficiente, ya que es utilizado sólo por el programa de pruebas.

Verifique con el programa de pruebas que las modificaciones que hizo en los ejercicios anteriores, en especial la optimización al separar los cálculos en varios hilos, produzcan resultados correctos.

[En el momento en que esté disponible] Descargue el archivo comprimido con los casos de prueba generados por usted y otros compañeros. Extraiga el archivo en alguna carpeta de su computadora, pero no en su repositorio. Invoque el programa de pruebas con esa carpeta por parámetro en la línea de comandos y asegúrese de que su solución de Goldbach pase todos los casos de prueba.

Actividad 8 [goldbach]

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.

Actividad 9 [goldbach]

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.6. Versión 5: 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ítica 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.

fig callgrind v4 isprime
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

  1. Medir el rendimiento del código antes de realizar las modificaciones.

  2. Analizar el código para detectar las regiones críticas a optimizar (profiling).

  3. Hacer las modificaciones que se cree incrementarán el rendimiento en las regiones críticas.

  4. Asegurarse de que las modificaciones sean correctas (correr el programa de pruebas).

  5. Medir el rendimiento del código después de realizar las modificaciones y comparar para determinar si hubo una ganancia.

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

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

Actividad 10 [goldbach]

Elabore y agregue a su repositorio de control de versiones una hoja de cálculo (en formato Open Document) donde pueda registrar sus intentos por incrementar el rendimiento. Escoja y escriba en las columnas al menos dos números grandes a probar, uno par y otro impar. En el ejemplo de abajo se escogieron 22222222 y 111111.

Table 7. Ejemplo de una hoja de cálculo con datos hipotéticos

Número:

22222222

111111

Modo:

Debug

Release

Debug

Release

Intento

Tiempo

Speedup

Tiempo

Speedup

Tiempo

Speedup

Tiempo

Speedup

Serial

44.88

 — 

42.11

 — 

75.55

 — 

70.33

 — 

Thread

10.22

4.39

9.8

4.5

14.88

5.08

12.89

5.46

<isPrime>

…​

…​

…​

…​

…​

…​

…​

…​

<even/odd>

…​

…​

…​

…​

…​

…​

…​

…​

En las filas anote los intentos, tanto los que incrementaron el rendimiento como aquellos que no. Deberá implementar al menos tres intentos que incrementen el rendimiento. Para cada uno de ellos agregue un comentario en la primera columna que explique rápidamente el cambio hecho en el código fuente, y en caso de fallar, una posible explicación de la causa.

Agregue un gráfico (de líneas) que visualice los incrementos de rendimiento de los intentos. Trate de combinar los tiempos (eje primario) con los speedups (eje secundario).

Actividad 11 [goldbach]

Siga el método sugerido para realizar las optimizaciones. Haga todas las pruebas en la misma máquina.

La primera medición llamada "serial", equivale a la Versión 1: interfaz reactiva ineficiente. Puede descargar el código fuente de este sitio, compilarlo, hacer las mediciones, anotarlas en la hoja de cálculo, y luego eliminar el código fuente de la versión 1. No agregue esta versión a su repositorio de control de versiones.

Deberá realizar al menos tres optimizaciones/iteraciones que incrementen el rendimiento:

  1. La primera optimización corresponde a dividir el cálculo serial en varios hilos de ejecución. Localice el commit donde implementó este cambio correctamente y regrese el repositorio a este estado con un git checkout id. Compile, revise que pase los casos de prueba, haga las mediciones, anótelas en la hoja de cálculo. Luego regrese el repositorio al último commit con git checkout master.

  2. La segunda iteración es una optimización que haga al método crítico isPrime(). Puede modificar el algoritmo o sustituirlo por otro. Recuerde realizar la iteración completa del método sugerido.

  3. La tercera iteración es una optimización a los métodos calculateEvenGoldbach() y calculateOddGoldbach(), por ejemplo, para reducir el número de invocaciones a isPrime() o balancear la carga entre los workers.

Recuerde agregar un comentario explicativo en la hoja de cálculo de cada iteración, tanto de las optimizaciones que incrementaron el rendimiento como aquellas que no.

2. Concurrencia de memoria compartida

Cree una carpeta 2-memcompartida/ en su repositorio de control de versiones.

2.1. Phtreads

El siguiente es un "Hola mundo" en Pthreads:

Table 8. Hola versión 0
Archivo Descripción Cambios

hello.c

Dice "hola mundo" desde el hilo principal y un hilo secundario.

Cree una carpeta 2-memcompartida/pthreads en su repositorio de control de versiones. Para cada una de las siguientes actividades, cree una subcarpeta que utilice el nombre dado entre corchetes.

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

Actividad 13 [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: utilice un registro (estructura) compartida por los threads.

Actividad 14 [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 y mutex como únicos mecanismos de sincronización permitidos para esta actividad.

Actividad 15 [hello_ordered_sem]

Haga que los threads saluden siempre en orden utilizando semáforos como mecanismo de sincronización.

Actividad 16 [hello_perf]

Utilizando los argumentos en línea de comandos, ubique la cantidad máxima de threads que su sistema operativo le permite crear.

Mida con esta cantidad máxima de threads la duración de su solución con espera activa (Actividad 14 [hello_ordered_wait]) y su solución con semáforos (Actividad 15 [hello_ordered_sem]). ¿Hubo un incremento de velocidad (speedup)? Anote sus resultados en una hoja de cálculo.

Actividad 17 [trapezoidal_serial]

Implemente una subrutina que recibe una función f como parámetro, un punto a, un punto b y una cantidad n y aproxima serialmente el área bajo la curva de la función f usando la regla trapezoidal con n trapezoides. Es decir, aproxima la integral

\$A=\int_{a}^{b}f(x)d_x\$

Implemente una función main() que recibe por argumentos de línea de comandos los números a, b y n e invoque la subrutina para calcular el área bajo la curva. Escoja una función f(x) cualquiera e impleméntela en su código fuente. Imprima el resultado en pantalla y la duración en realizar el cálculo. Escriba en una hoja de cálculo las duraciones obtenidas con n múltiplos de 1000.

Actividad 18 [trapezoidal_pthreads]

Modifique su solución a la actividad anterior para recibir un argumento adicional que indica la cantidad de trabajadores (threads) en la línea de comandos. Si no es especifica, asuma la cantidad de CPUs disponibles en el equipo.

Modifique su subrutina que calcula el área bajo la curva para que la estimación con los trapecios sea realizada por la cantidad de workers especificada.

Agregue a su hoja de cálculo las duraciones de la versión concurrente.

Actividad 19 [trapezoidal_perf]

Corra su solución concurrente de la actividad anterior, con el doble, el triple, y cuatro veces la cantidad de CPUs disponibles en el sistema. Anote a su hoja de cálculo las duraciones.

Estime en su hoja de cálculo los incrementos de velocidad (speedup) y la eficiencia.

Haga un gráfico combinado de los incrementos de velocidad y la eficiencia (ejes-y) contra la cantidad de trabajadores usada (1, CPUs, 2xCPUs, 3xCPUs, 4xCPUs).

Actividad 20 [collatz_concurrente]

Suponga que su equipo de trabajo debe resolver una modificación de la Conjetura de Collatz. Se quiere saber si un conjunto de números tienen o no órbita finita con las siguientes reglas:

  1. Si el número \$x_i\$ es par, se divide entre dos.

  2. Si el número \$x_i\$ es impar, se multiplica por su antecesor y se le suma su sucesor: \$x_{i-1} \cdot x_i + x_{i+1}\$

  3. El conjunto es circular, es decir, el anterior al primero es el último, y el sucesor del último es el primero.

Dado que los conjuntos pueden ser muy grandes y las órbitas extensas, su equipo pensó en una solución concurrente. Suponga que un(a) colega escribió el siguiente código en C.

 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
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

#include "pthread_barrier.h"

static size_t worker_count = 3;
static size_t number_count = 3;
static size_t* numbers = NULL;
static size_t current_step = 0;
static size_t max_steps = 10;
static pthread_t* workers = NULL;
static pthread_barrier_t barrier;

void* calculate(void* data)
{
	const size_t my_id = (size_t)data;
	const size_t next = (my_id + 1) % worker_count;
	const size_t prev = (size_t)((long long)my_id - 1) % worker_count;

	while ( current_step < max_steps && numbers[my_id] > 1 )
	{
		if ( numbers[my_id] % 2 == 0 )
			numbers[my_id] /= 2;
		else
			numbers[my_id] = numbers[prev] * numbers[my_id] + numbers[next];

		pthread_barrier_wait(&barrier);

		if ( my_id == 0 )
			++current_step;
	}
	return NULL;
}

int main()
{
	//scanf("%zu", &number_count);
	numbers = malloc( number_count * sizeof(size_t) );
	for ( size_t index = 0; index < number_count; ++index )
		scanf("%zu", &numbers[index]);

	pthread_barrier_init(&barrier, NULL, (unsigned)worker_count);

	workers = malloc(worker_count * sizeof(pthread_t));
	for ( size_t index = 0; index < worker_count; ++index )
		pthread_create(&workers[index], NULL, calculate, (void*)index);

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

	pthread_barrier_destroy(&barrier);

	if ( current_step > max_steps )
		printf("No converge in %zu steps", max_steps);
	else
		printf("Converged in %zu steps", current_step);

	return 0;
}

Rastree la memoria y el procesamiento del programa. Asuma tres valores en la entrada estándar. ¿Resuelve el código anterior el problema planteado?

Actividad 21 [collatz_concurrente]

Haga las correcciones necesarias para que el programa de la actividad anterior resuelva el problema planteado.

Actividad 22 [collatz_concurrente]

Haga que el programa pueda trabajar con una cantidad arbitraria de datos y distribuya estos entre una cantidad arbitraria de threads.

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

 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.

Actividad 24 [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):

file 7z Descargar Arreglo dinámico versión 1

Actividad 25 [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 26 [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 27 [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:

  1. La cantidad inicial de elementos en el arreglo (size_t).

  2. La cantidad de operaciones a realizar en el arreglo (size_t).

  3. El porcentaje de operaciones que son inserciones en el arreglo (double).

  4. El porcentaje de operaciones que son eliminaciones en el arreglo (double).

  5. El porcentaje de operaciones que son búsquedas en el arreglo (double).

  6. La cantidad de trabajadores (threads) a probar (size_t).

  7. 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 9. Duraciones

threads

distribution

array

1 thread

1xCPU

2xCPU

4xCPU

10-10-80

mutex

rwlock

.1-.1-99.8

mutex

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

El siguiente es un "Hola mundo" en OpenMP:

Table 10. Hola versión 0
Archivo Descripción Cambios

hello.c

Dice "hola mundo" desde el hilo principal e hilos secundarios en OpenMP.

Cree una carpeta 2-memcompartida/openmp en su repositorio de control de versiones. Para cada una de las siguientes actividades, cree una subcarpeta que utilice el nombre dado entre corchetes.

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

Actividad 29 [trapezoidal_openmp]

Copie su solución al ejercicio Actividad 17 [trapezoidal_serial], es decir, la carpeta pthreads/trapezoidal_serial a la carpeta openmp/trapezoidal_openmp. Modifique el código para recibir un argumento adicional que indica la cantidad de trabajadores (threads) en la línea de comandos. Si no se especifica, asuma la cantidad de CPUs disponibles en el equipo.

Modifique la invocación de su subrutina que calcula el área bajo la curva con directivas de OpenMP para que sea ejecutada por la cantidad especificada de workers. Modifique la implementación de su subrutina para que la estimación con los trapecios sea realizada en forma coordinada por los threads lanzados por OpenMP.

No utilice variables globales. Almacene el resultado de la suma en una variable local a main() y pase un puntero a la subrutina que calcula un trozo del segmento \$a,b\$. La subrutina debe calcular la suma parcial en una variable local. Serialice el código que agrega el resultado parcial a la variable total en el main(). Indague sobre la directiva critical de OpenMP para definir secciones críticas de código.

Actividad 30 [trapezoidal_perf]

Copie su hoja de cálculo de la carpeta pthreads/trapezoidal_perf a la carpeta openmp/trapezoidal_perf. Corra su solución con OpenMP de la actividad anterior, con igual, el doble, el triple, y cuatro veces la cantidad de CPUs disponibles en el sistema. Anote a su hoja de cálculo las duraciones.

Estime en su hoja de cálculo los incrementos de velocidad (speedup) y la eficiencia.

Agregue los resultados obtenidos con OpenMP como una serie en su gráfico combinado de los incrementos de velocidad y la eficiencia (ejes-y) contra la cantidad de trabajadores usada (1, CPUs, 2xCPUs, 3xCPUs, 4xCPUs).

Los siguientes son ejemplos de las directivas parallel for y for en OpenMP:

Table 11. 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 paralelizada, al finalizar su ejecución, todos los threads se unen al principal o invocador. 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.

several_for.c

La directiva for no define una nueva región paralelizada, y por tanto no crea una nueva cantidad de threads ni los destruye. La directiva for tiene que 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.
Actividad 31 [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 ( 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 32 [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 33 [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 34 [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.

Table 12. OpenMP’s parallel-for scheduling
Archivo Descripción Cambios

main.c

Programa que cuenta la cantidad de números primos entre 2 y un número dado por primer argumento en línea de comandos.

Makefile

Permite compilar el programa anterior
Actividad 35 [cntprimes_serial]

Descargue el código fuente de la tabla anterior. Compile el programa. Invoque el programa con el argumento 25 millones. Use la herramienta de profiling perf para obtener la duración del programa, de la forma:

perf stat ./cntprimes_serial 25000000

Anote la duración obtenida de esta versión serial en una hoja de cálculo en una carpeta cntprimes_perf. Esta carpeta debe estar al mismo nivel que cntprimes_serial.

Actividad 36 [cntprimes_block]

Copie la carpeta cntprimes_serial a cntprimes_block. Paralelice la solución para que utilice varios threads usando la directiva parallel for de OpenMP. Recuerde agregar el argumento -fopenmp en las banderas de compilación de su Makefile. Recuerde también indicar el tipo de las variables compartidas con default(none).

Si los ciclos a parelizar tienen una reducción, utilice la cláusula reduction en lugar de declarar una región crítica. Mida la duración de nuevo con perf y anote los resultados en su hoja de cálculo en la carpeta cntprimes_perf. Calcule el incremento de velocidad (speedup) obtenido.

Actividad 37 [cntprimes_cyclic]

Copie la carpeta cntprimes_block a cntprimes_cyclic. Distribuya los ciclos entre los threads usando planificación (scheduling) en tiempo de ejecución (runtime). Desde la línea de comandos use la variable ambiente OMP_SCHEDULE para probar el rendimiento de varias cláusulas de scheduling. Por ejemplo:

export OMP_SCHEDULE="static,1"
perf stat ./cntprimes_cyclic 25000000

Anote en su hoja de cálculo en cntprimes_perf las duraciones que obtiene con al menos las siguientes planificaciones:

static
static,1
static,N
dynamic
dynamic,1
dynamic,N
guided
guided,1
guided,D

Escoja varios valores para N y D, como la mitad y la totalidad de la cantidad de threads o la mitad de la cantidad de datos. Resalte en su hoja de cálculo el scheduling que obtuvo el mejor rendimiento y escriba un comentario que explique por qué lo consiguió.

3. Concurrencia de memoria distribuida

Cree una carpeta 3-memdistribuida/ en su repositorio de control de versiones. La tecnología que se usará en esta etapa será Message Passing Interface (MPI), la cual se considera de bajo nivel. Exiten otras tecnologías como Charm++ de más alto nivel, pero sólo se cubrirá en este curso MPI.

3.1. MPI

El siguiente es un "Hola mundo" en MPI:

Table 13. Hola MPI versión 0
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 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.

Dentro de su carpeta 3-memdistribuida/ cree una carpeta mpi y para cada una de las siguientes actividades cree una subcarpeta con el mismo nombre que la actividad.

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

Actividad 39 [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 14. Comunicación punto a punto en MPI
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.

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.

file diff

Makefile

Un makefile genérico para compilar los dos programas anteriores.
Actividad 40 [hybrid_distr_stdin]

Modifique el programa de la actividad anterior 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, indague sobre las funciones MPI_Send y MPI_Recv. Tras corregir el programa, agregue la salida que produce a su archivo output.md.

Actividad 41 [prime_hybrid_sep]

Aproveche el código de la actividad anterior para construir un programa híbrido (es decir, que use procesos e hilos) para calcular la cantidad de números primos en un rango indicado por el usuario en los argumentos de línea de comandos o en la entrada estándar si no se proveen argumentos. Cada proceso (el hilo principal de cada proceso) debe reportar la cantidad de primos que encontró, el subrango en que trabajó el proceso, la cantidad de segundos que tardó, y la cantidad de hilos que ejecutó para encontrar primos. La siguiente podría ser una salida.

$ mpiexec -n 2 -f hosts.txt ./prime_hybrid_sep 3 20
Process 0 on hostname1 found 4 primes in range [3, 12[ in 0.000154874s with 3 threads
Process 1 on hostname2 found 3 primes in range [12, 20[ in 0.00204510s with 3 threads

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

Actividad 42 [prime_hybrid_int]

En la actividad anterior, cada proceso reporta la cantidad de primos que encuentra en su rango asignado. Sin embargo, al usuario le interesa conocer la cantidad de primos en el rango total. Designe un proceso para que reporte la salida al usuario (usualmente aquel con rank 0). Haga que los demás procesos envíen la cantidad de primos que encontraron al proceso designado. El proceso designado debe calcular la cantidad de primos, la duración de ese proceso, y reportarlas al usuario en la salida estándar.

$ mpiexec -n 2 -f hosts.txt ./prime_hybrid_int 3 20
7 primes found in range [3, 20[ in 0.000510781s with 2 processes and 6 threads

Sugerencia: haga que cada proceso envíe también la cantidad de threads que ejecutó, para que el proceso designado pueda sumarlos y reportarlos al usuario.

Actividad 43 [prime_process]

En las actividades anteriores ha implementado un modelo híbrido, que utiliza memoria distribuida y compartida para encontrar primos. Simplifique su implementación utilizando sólo memoria distribuida. Es decir, cada proceso sólo lanza el hilo principal y éste es quien realiza el conteo de primos.

$ mpiexec -n 6 -f hosts.txt ./prime_process 3 20
7 primes found in range [3, 20[ in 0.000584510112s with 6 processes

Haga cinco corridas de su solución a la actividad anterior (Actividad 42 [prime_hybrid_int]) y esta actividad con la misma cantidad de trabajadores. Por ejemplo, si en la actividad anterior ejecutó 6 threads, en esta actividad cree 6 procesos. Tome la menor duración de cada actividad. Use rangos grandes de primos. ¿Cuál solución produjo la menor duración? Agregue sus salidas a un archivo output.md.

Actividad 44 [hot_potato_loser]

Cuando los procesos (que son entidades independientes) pueden comunicarse entre ellos, permite que realicen actividades competitivas o colaborativas como las personas, por ejemplo, jugar entre ellos. Escriba un programa que enseñe a los procesos a jugar la papa caliente. Los procesos forman un anillo (ring) en orden 0, 1, …​, W-1, 0, 1, …​.

El programa recibe un número entero positivo por argumento que es la papa. El proceso 0 toma la papa, la decrementa y la pasa al proceso siguiente (1). El proceso 1 recibe la papa, la decrementa y la pasa al siguiente y así sucesivamente.

Si un proceso al decrementar la papa se le convierte en 0, le explota y el proceso pierde el juego. El proceso reporta en la salida estándar que la papa le explotó. Luego pasa la papa al siguiente proceso y sale del juego.

Los demás procesos reciben la papa negativa, que les indicará que el juego terminó. Los procesos pasarán la papa y terminarán su ejecución.

Sugerencia: Si lo prefiere puede hacer que el proceso reciba la papa, si esta es cero le explotará. Si la papa es positiva, la decrementa y la pasa al proceso siguiente; y así sucesivamente.

Actividad 45 [hot_potato_winner]

En el juego real, cuando la papa le explota a un jugador, éste sale el juego, pero la papa sigue circulando hasta que un único jugador queda vigente y gana el juego. Idee un mecanismo que permita a los procesos saber cuando un proceso salió de juego pero otros aún siguen activos. Al proceso que le explota la papa, la pasa al siguiente y cada vez que la recibe de nuevo, no la decrementa, sino que la pasa sin modificarla al próximo jugador.

Cuando un proceso detecta que es el último en el juego, reporta en la salida estándar que es el feliz ganador, y antes de terminar su ejecución, pasa la papa al siguiente jugador para que sepa que el juego finalizó, y también éste pueda terminar su ejecución. Y así repetitivamente, hasta que el último jugador activo termine su ejecución.

Actividad 46 [hot_potato_collatz]

Los procesos de computadora son muy astutos y pueden estimar a quién el usuario le da el gane cuando escoge el tamaño de la papa. Para confundir un poco a los procesos y desalentar favoritismos del usuario, haga que su programa reciba dos parámetros: la papa y el número del proceso que recibirá inicialmente la papa.

Cuando un proceso pasa la papa a otro, no la decrementa, sino que pasa el siguiente número de Collatz de la papa, es decir, 3n+1 si la papa es impar y n/2 si la papa es par. Si la papa llega a ser 1, explota y el proceso sale del juego. Pero antes de salir pasa la papa original al próximo proceso para que los demás sigan jugando hasta que sólo quede un jugador.

El ganador puede establecer la papa en 0 y pasarla a los restantes jugadores para que sepan que el juego ha concluido.

Table 15. Comunicación colectiva en MPI
Archivo Descripción Cambios

broadcast.c

El proceso 0 lee un entero de la entrada estándar (puesto que es el único en MPI que puede hacerlo). Luego envía una copia del entero 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).

wall_time1.c

Ejemplo que utiliza comunicación punto a punto y barreras para reportar al usuario el tiempo aproximado en que corrió la tarea que se quiere medir, la cual corre en varios nodos de un clúster.

wall_time2.c

El mismo ejemplo anterior que utiliza comunicación colectiva. MPI_Reduce provoca que todas los procesos hoja se van enviando sus resultados y agregándolos hasta que llegue al proceso raíz.

file diff

wall_time3.c

El mismo ejemplo anterior de comunicación colectiva pero con MPI_Allreduce(). Esta subrutina hace la reducción normal desde los datos de los procesos hojas hasta el resultado en el proceso raíz, y luego el resultado se distribuye hacia los procesos hoja. De esta forma, todos los procesos quedan con el valor resultado de la reducción.

file diff
Actividad 47 [hot_potato_broadcast]

Copie su solución de Actividad 46 [hot_potato_collatz]. Modifíquela para que en lugar de usar comunicación punto a punto (un anillo), los procesos usen comunicación colectiva. Es decir, cada vez que un evento ocurre a un proceso, no lo comunica al siguiente sino que lo comunica a todos los jugadores.

Idee un protocolo para que los procesos puedan jugar a la papa caliente mediante este esquema. Por ejemplo, puede hacer que los procesos comuniquen siempre un registro, el cual tenga campos para indicar el tipo de evento ocurrido (la acción: como pasar la papa, salir del juego porque le explotó la papa, o se encontró un ganador), quien es el próximo proceso jugando, y así por el estilo. Sugerencia: diseñe primero una máquina de estados (un autómata de estados finito) y agréguela a un documento design.md.

Recuerde no utilizar variables globales. Asegúrese de que su solución no produzca fugas de memoria ni accesos inválidos. Sugerencia: corra valgrind localmente con uno o dos procesos. Si quiere probar en varias máquinas puede emitir un comando como el siguiente:

mpiexec -n <W> -f hosts.txt valgrind --log-file=hot_potato_collatz-%p.log ./hot_potato_collatz <ARGS>
Actividad 48 [prime_process_reduction]

Copie su solución a la actividad Actividad 43 [prime_process] y modifíquela para que en lugar de que sea el proceso 0 quien realiza la suma de conteo de números primos, se haga mediante una reducción de MPI. Haga también que si el rango se recibe en la entrada estándar, el proceso 0 la comunique mediante broadcast a los demás procesos. Asegúrese de que el programa produzca la salida esperada.

Encuentre la máxima cantidad de procesos que su clúster le permite. Haga cinco corridas de cada una de sus soluciones a las actividades Actividad 42 [prime_hybrid_int], Actividad 43 [prime_process], y Actividad 48 [prime_process_reduction] con esta cantidad de trabajadores. Tome la menor duración de cada actividad. Use un rango grande de primos. ¿Cuál solución produjo la menor duración? Agregue las tres salidas que duraron menos a un archivo output.md.

4. Ejemplos extra

Ejemplos de temas que no corresponden al curso pero que son útiles para la "Programación paralela y concurrente".

Table 16. Ejemplos extra
Archivo Descripción Cambios

load_matrix.c

Carga una matriz de un archivo y lo imprime en otro archivo. Si no se proveen nombres de archivo, se usa la entrada o salida estándar.

date_validator.c

(Incompleto) Implementa una subrutina is_valid_date() que recibe un texto por parámetro y retorna un booleano indicando si el texto contiene una fecha válida o no. El algoritmo utiliza una máquina de estados (autómata de estados finito) elaborado en clase a modo de ejemplo.