Tareas: Conjetura de Goldbach

En 1742 Christian Goldbach de Prusia le escribió una carta al matemático suizo Leonhard Euler con una conjetura:

Euler no pudo demostrar la conjetura, ni tampoco cientos de matemáticos convirtiéndolo en el problema abierto más intrigante en la historia de la teoría de números. Algunas novelas y películas hacen alusión a la conjetura, y entre los años 2000 y 2002 se ofreció un premio de un millón de dólares a quien lograse demostrarla, premio que no fue reclamado. En el 2013, tras 271 años de su aparición, el matemático peruano Harald Helfgott propuso una demostración para la conjetura débil que está actualmente sometida a revisión de pares, y en caso de validarse convertiría la conjetura débil en teorema.

Para esta entrega se necesita un programa procedimental en C que reciba una lista de números enteros en la entrada estándar y calcule todas las sumas de Goldbach que equivalen a cada número, de manera serial. Su programa producirá como resultado en la salida estándar un resumen de cuántos números fueron ingresados y cuántas sumas en total se encontraron.

Luego imprimirá una lista con los números en el el mismo orden en que fueron ingresados. Cada línea de la lista contiene un número ingresado seguido por la cantidad de sumas de Goldbach que tiene. Si el número ingresado es negativo, se considerará como que el usuario quiere que el programa además liste todas las sumas del correspondiente número positivo. A continuación se muestra un ejemplo de la salida esperada para na entrada dada.

Ejemplo de entrada:

Salida esperada:

Note que las sumas deben estar ordenadas por sus valores, del menor a mayor. Su programa debe poder calcular números de 64 bits con signo, es decir, entre 0 y 2^63-1 . Si se provee un número fuera de este rango, el programa debe imprimir el texto "NA" en la salida estándar. Si se provee un texto que no sea un número, el programa debe reportar el mensaje "invalid input" en el error estándar, y terminar su ejecución. Es decir, no continuar procesando más números.

En su repositorio individual cree una carpeta tareas/goldbach_serial/ para esta tarea. Debe mantenerse la estructura de archivos y directorios característica de un proyecto de Unix, resumido en la siguiente tabla. En las secciones siguientes encontrará detalles de cada archivo o carpeta.

Haga buen uso del repositorio de control de versiones. Cada commit debe tener un cambio con un significado, un mensaje significativo, y “no romper el build”. No haga “megacommits” que implementan muchas funcionalidades distintas y acumuladas en varios días de desarrollo. Recuerde los lineamientos estipulados en la carta al estudiante.

Sea severamente cuidadoso(a) al agregar archivos a control de versiones. No agregue archivos ejecutables, código binario, o carpetas que surgieron de la salida de un programa automatizado. Además de los archivos que tienen “No” en la columna “Versionado”, haga que su .gitignore ignore archivos generados por el sistema operativo, como .DS_Store en macOS o thumbs.db en Windows.

Su solución debe ser una obra intelectual propia por la naturaleza individual de la tarea. Si reutiliza código de alguna fuente, dé el respectivo crédito. Por ejemplo, si son unas pocas líneas, basta un comentario en el código fuente que diga: // Adaptado de <URL>. Si reutiliza varios archivos, la referencia debe estar en su README.md, en una sección de “Créditos”, donde liste el nombre de la biblioteca, el creador, la dirección electrónica, la licencia, si la tiene. Nota: no es necesario dar crédito a los ejemplos y materiales provistos por los docentes en este curso.

En un archivo README.md en notación Markdown, o si lo prefiere readme.adoc en notación AsciiDoc (es indiferente el uso de mayúsculas o minúsculas en el nombre del archivo), plasme el resultado de la fase de análisis. Si no conoce el formato Markdown o AsciiDoc, asegúrese de seguir un manual o buscar un tutorial, ya que la buena calidad del código también será evaluada. Por ejemplo, un párrafo en estas notaciones se forma al separar por dos cambios de línea y no por uno. Su documento de análisis debe incluir:

Para que su código sea fácil de paralelizar en tareas posteriores, su diseño de esta tarea no debe entrelazar el cálculo de las sumas de Goldbach con las impresiones, sino que las subrutinas de lectura, cálculo de las sumas, e impresión deben estar separadas e invocarse en secuencia en ese orden. Por consiguiente, necesitará diseñar una estructura de datos que almacene en memoria dinámica los números ingresados, y las sumas encontradas que serán impresas.

Para este diseño elabore un diagrama de la estructura de datos para un ejemplo de entrada con al menos tres líneas (un par de al menos dos sumas, un impar de al menos dos sumas, y un número inválido o N/A). Puede pensar en este diagrama como un rastreo de memoria o como los diagramas típicos de estructuras de datos que realizó en cursos previos de programación. El modelo resultante, es decir, los tipos de datos de la estructura, represéntelo en UML.

Exporte sus diagramas a archivos .svg o .png y almacénelos en la carpeta design/. En esta misma carpeta cree un archivo design/README.md o design/readme.adoc. En este archivo incruste las imágenes de diseño. Además provea una descripción que ayude a una persona ajena al proyecto a comprender su diseño general (“comprender el bosque”). Tip: Puede poner un hiperenlace desde el README.md de la tarea hacia su design/readme.md, lo cual permitirá navegabilidad entre los documentos del proyecto.

Su solución debe ser modular. Debe al menos tener las subrutinas de lectura, cálculo de sumas de Goldbach, impresión, y subrutina principal. La del cálculo de las sumas probablemente necesitará subdividirla. Para cada subrutina diseñe una solución en pseudocódigo en uno o varios archivos con extensión .pseudo en la carpeta design/. Si usa notación AsciiDoc, incruste estos archivos en su documento de diseño (design/readme.adoc), sino enlácelos con hiperenlaces desde su archivo de Markdown.

Las declaraciones de subrutinas y tipos de datos (e.j struct) públicos deben estar en archivos .h, y deben estar documentados con Doxygen en inglés o español. Doxygen requiere un archivo de configuración (por defecto llamado Doxyfile), que sí debe estar en control de versiones. Se puede generar un archivo de configuración con el comando doxygen -s -g. Para que este Doxyfile sea reutilizable, genérelo en la carpeta common/ de su repositorio:

Puede agregar el archivo generado a control de versiones y hacer un commita. Luego edite el Doxyfile para que extraiga símbolos del lenguaje de programación C. Estos son algunos cambios sugeridos:

Para reutilizar el Doxyfile, vaya a la carpeta de su tarea. Cree otro archivo vacío también con el nombre Doxyfile con el siguiente contenido:

Los archivos de salida de Doxygen deben generarse en una carpeta doc/ y ésta NO se debe agregar a control de versiones. Asegúrese de que el reporte que genera Doxygen en la salida estándar, no incluya diagnósticos (warnings). Además de documentar las interfaces, documente el código no trivial en los cuerpos de las subrutinas.

Nótese que la documentación de subrutinas tiene dos partes. La primera es la interfaz de la subrutina, que debe hacerse en Doxygen. Aquí importa el qué hace la subrutina: Una oración que resume qué hace la subrutina, y puede tener una sección de detalles; qué parámetros recibe (valores esperados), qué valor retorna, qué pasa cuando se envían valores no válidos (ej. fuera de rango), y cualquier otro detalle que alguien que invoque su subrutina necesita saber, por ejemplo, si el cálculo de números primos es por fuerza bruta o algún otro algoritmo. Un ejemplo corto de documentación de una subrutina podría ser:

Si tiene dos subrutinas que tienen prácticamente la misma documentación, por ejemplo, los mismos parámetros, no redunde la documentación. Haga referencia a la subrutina ya documentada. Por ejemplo:

Nótese que en este segundo ejemplo se usaron comentarios en línea (///) en lugar de multi-línea (/* …​ */), por ser pocas líneas. Pero es sólo con propósitos ilustrativos. En su código usted pude escoger entre cualquiera de las formas permitidas por Doxygen, pero trate de mantener la consistencia.

La segunda parte es la implementación de la subrutina. Esto se documenta como comentarios normales (NO de Doxygen) dentro del cuerpo de la subrutina. Aquí importa el cómo, de tal forma que si alguien lee los comentarios dentro del cuerpo, obtiene un algoritmo en alto nivel (lenguaje natural) de la solución implementada. Por lo tanto, tome el texto de sus archivos de diseño (.pseudo), péguelo en el archivo fuente (.c) correspondiente, y convierta el texto en comentarios. En la fase de implementación escribirá código C cada instrucción del pseudocódigo. Un ejemplo de este proceso puede verse en video “Punto de entrada, declaraciones de variables” que es parte de una secuencia de videos titulados "Diseño procedimental #".

Implemente su diseño (diagramas UML y pseudocódigo) en el lenguaje de programación C. Recuerde aplicar buenas prácticas de programación. Por ejemplo, las variables globales están prohibidas en esta y todas las evaluaciones del curso. Corra el linter con frecuencia para apegarse a la convención de estilos de Google para C/C++. Esta convención usa dos espacios para indentar (sangría) y bloques de código entre llaves egipcias. Los siguientes son algunos detalles técnicos que encontrará.

Asegúrese de verificar el funcionamiento de su programa con los casos de prueba que se adjuntan. Los casos están clasificados en tres grupos de acuerdo a la cantidad de procesamiento que requieren. Puede agregar los casos pequeños y medianos a control de versiones si gusta, pero no los casos de prueba grandes. Se recomienda enfáticamente crear casos de prueba propios y agregarlos a control de versiones.

El Makefile genérico, que probablemente ya tenga en la carpeta common/ de su repositorio, permite probar su solución contra todos los casos de prueba con la orden make test. Conviene instalar el programa icdiff para obtener una comparación con colores (sudo apt icdiff). Los siguientes commandos son de especial utilidad:

Su programa debe hacer buen uso de los recursos. Por ejemplo, no debe generar fugas de memoria, ni accesos inválidos, ni usar memoria no inicializada. Estas pruebas puede realizarlas herramientas de análisis dinámico de código como Valgrind y Google Sanitizers.

Una vez que haya finalizado la solución, realice la entrega creando un tag con el identificador tarea01 (ó hw01) asociado al último commit de la entrega. Por ejemplo:

(Rubros en revisión)

Si no lo ha hecho, primero corrija su solución a la tarea01 en la carpeta tareas/goldbach_serial/ (no copie ni cree una carpeta nueva) para aplicar las observaciones que obtuvo durante la revisión de la misma, de manera que no se propaguen las deficiencias identificadas de la tarea01 en la tarea02. Recuerde utilizar issues de su sistema de control de versiones de la siguiente forma.

Una vez que haya corregido la tarea01, cree un tag tarea01fix (ó hw01fix) asociado al último commit de las correcciones, y asegúrese enviarlo al repositorio remoto (git push --tags). Luego pase a la versión concurrente (tarea02).

En su repositorio personal copie la carpeta tareas/goldbach_serial/ y su contenido como tareas/goldbach_pthread. Haga un commit con este cambio.

El programa concurrente recibirá la lista de números enteros en la entrada estándar e imprimirá el resumen y las sumas de Goldbach de cada uno de ellos, en el mismo orden y de la misma forma que la versión serial lo hace. Es decir, el programa concurrente debe pasar los mismos casos de prueba que la versión serial. La diferencia con la versión serial, es que la solución a esta tarea debe calcular las sumas de Goldbach de manera concurrente utilizando hilos que se reparten el trabajo, y por lo tanto, debe tener un incremento en el desempeño corroborable.

Su programa concurrente debe permitir al usuario invocarlo con un número provisto como argumento de línea de comandos, el cual indica la cantidad de hilos de ejecución que realizarán el cálculo de las sumas de Goldbach. Si este número no se provee, se debe asumir la cantidad de núcleos (CPUs) disponibles en la máquina. Recuerde actualizar su README.md para indicar que su solución usa hilos, y que el usuario puede proveer este parámetro opcional.

Importante. Al disponer de varios hilos de ejecución, debe repartir el trabajo lo más equitativamente posible entre ellos. Haga que los hilos trabajen de forma lo más paralela posible, y por consiguiente, evitar el control de concurrencia innecesario. Recuerde que además su solución debe imprimir los resultados en el orden esperado. Se recomienda evitar la serialización de los hilos y usar una estrategia de seguridad condicional (conditionally safe).

Su solución debe tener un buen diseño concurrente expresado en diagramas y pseudocódigo:

Implemente su diseño concurrente en el lenguaje de programación C con la tecnología Pthreads. Recuerde aplicar buenas prácticas de programación, estilo de código (linter), y documentar las subrutinas tanto su interfaz (Doxygen) como su implementación (pseudocódigo).

En esta versión no haga optimizaciones a los algoritmos para encontrar las sumas, la tarea03 se encargará de ello. La versión concurrente debe implementar el mismo algoritmo para encontrar las sumas que la versión serial. Simplemente debe repartir el trabajo lo más equitativamente posible entre los hilos de ejecución.

La versión concurrente debe registrar un incremento de velocidad. Es decir, la duración de la versión concurrente con un caso de prueba mediano o grande debe ser menor o igual que la duración de la versión serial. Importante: no agregue los casos de prueba grandes a control de versiones (por el contrario, puede incluirlos en su archivo .gitignore).

Haga que su solución pueda encontrar las sumas de Goldbach de números de cualquier longitud (más de 64 bits). Puede utilizar una biblioteca de aritmética de precisión arbitraria, como The GNU Multiple Precision Arithmetic Library (GMP), para la cual hay disponibles tutoriales en línea (ej.: University de Colorado Boulder). También puede consultar este ../../2021b/faq/gmp/gmp.c[ejemplo de uso en C].

Asegúrese de instalar la biblioteca y su código fuente en su distribución de Linux (ej.: sudo apt install libgmp-dev). Actualice el Makefile para que el preprocesador pueda incluir los encabezados (si es necesario) y el linker pueda enlazar los binarios de la biblioteca (LIBS=-lgmp).

Su programa debe tratar los números usando la aritmética más eficiente. Por ejemplo, al leer los números de la entrada estándar, si estos son pequeños use la aritmética de precisión fija. Si el número en la entrada desborda esta aritmética, trate de usar aritmética de precisión arbitraria. Si tampoco cumple el formato de estos números, debe considerarse como una línea inválida.

De igual forma, los hilos deben poder calcular las sumas de Goldbach usando la aritmética correspondiente. Si el número es relativamente pequeño usar aritmética de precisión fija dado que es más eficiente porque es provista por el hardware. De lo contrario, usar aritmética de precisión arbitraria, que es más lenta dado que es provista por el software (la biblioteca de terceros).

Asegúrese de verificar el funcionamiento de su programa con los casos de prueba. Antes de implementar precisión arbitraria, use los mismos casos de prueba de la tarea01. Para probar la precisión arbitraria, use los que se adjuntan. Se recomienda enfáticamente crear más casos de prueba.

Además de probar el buen uso de memoria (asan, msan, ubsan, memcheck), asegúrese de hacer un buen uso de la concurrencia (tsan, helgrind). Apéguese a la convención de estilos y con frecuencia pruebe el código con el linter (make lint).

Recuerde que puede probar los ejecutables instrumentalizados contra los casos de prueba. Para generar un ejecutable con un sanitizer hay que compilar todos los fuentes con el sanitizer. Si ya se tiene un ejecutable construido sin sanitizer o un sanitizer diferente, es mejor borrar (make clean) todos los archivos objeto viejos (.o) y recompilar todos los fuentes. Por ejemplo, para construir un ejecutable con asan sanitizer y probarlo, y luego otro con thread sanitizer y probarlo sería:

(Rubros en revisión)

Recuerde que en todos los rubros se evalúan las buenas prácticas de programación.

Esta tarea es una secuencia de tarea01 y tarea02. Debe apegarse a las reglas de entrega de la tarea02 y tarea01, a excepción de los cambios solicitados en este enunciado.

Si no lo ha hecho, primero corrija su solución a la tarea anterior (tarea02) en la carpeta tareas/goldbach_pthread/ (no copie ni cree una carpeta nueva) para aplicar las observaciones que obtuvo durante la revisión de la misma, de manera que no se propaguen las deficiencias identificadas de la tarea02 en la tarea03. Siga el mismo procedimiento indicado en Section 2.1.

Una vez concluidas las correcciones a la tarea02, copie su solución concurrente tareas/goldbach_pthread a la carpeta tareas/goldbach_optimized en su repositorio de control de versiones. Cree una carpeta tareas/goldbach_optimized/report/.

Dentro de la carpeta report cree un archivo readme.ext cuya estensión varía si es en formato de Markdown, AsciiDoc, o LaTeX. A este archivo se le referirá como documento de reporte. Conviene crear un enlace desde tareas/goldbach_optimized/README.md a su documento de reporte para que facilite la navegación.

Importante: El documento de reporte tendrá una sección por cada optimización solicitada en este enunciado. Dentro de cada optimización cree una subsección para cada iteración del método sugerido para optimizar. En cada iteración documente el diseño de la modificación que piensa incrementará el desempeño, el rendimiento (speedup y eficiencia) del código antes y después de modificarlo, y una discusión de las lecciones aprendidas.

Asegúrese de verificar el funcionamiento de su programa con los casos de prueba pequeños o medianos antes de iniciar las mediciones con los casos de prueba grandes. Pruebe el buen uso de memoria (asan, msan, ubsan, memcheck) y de la concurrencia (tsan, helgrind) junto con los casos de prueba pequeños y medianos. Por ejemplo, para construir un ejecutable con el Address Sanitizer, probarlo, y luego otro con Thread Sanitizer y probarlo se puede con:

Recuerde mantener la convención de estilos (make lint).

Para todas las mediciones de rendimiento use todos los casos de prueba de la carpeta tests_large/ en una máquina con al menos 8 núcleos de CPU. Puede consultar la cantidad de núcleos de su máquina con el comando lscpu de Linux. Si no dispone de un equipo con estas características, use un nodo esclavo (y no la máquina máster) del clúster Arenal o una máquina del laboratorio de computadoras para el curso. Anote los resultados en una hoja de cálculo que le facilite realizar las comparaciones. Puede usar la hoja de cálculo modelo como punto de partida.

Para medir el tiempo de ejecución con precisión de nanosegundos, instale la herramienta perf (paquete linux-perf en Debian o perf en RedHat). En Debian requiere permisos de administración para permitir a perf inspeccionar a otros programas, puede requerir configuración adicional para correrlo como usuario normal (como crear el archivo sudo echo 1 >/proc/sys/kernel/perf_event_paranoid y reiniciar el sistema operativo). Para obtener la duración de todos los casos de prueba puede ejecutar perf stat make test ARG=8 TST_DIR=tests_large en su máquina de 8 o más núcleos de CPU.

Para cada medición concurrente deben realizarse tres corridas y tomar la menor de ellas (para la medición serial basta una corrida). Todas las ejecuciones deben realizarse en la misma máquina. Si usa Arenal, debe ser en un nodo esclavo (no la máquina máster), identificado con el número N entre 0 y 3 en los siguientes comandos:

El programa nohup hace que el comando que le sigue, sea ejecutado en segundo plano y no se detenga si se cierra su conexión con la máquina remota, por ejemplo, por inactividad o un error de red. La salida que un programa genere es enviada al archivo nohup.out. Por lo tanto, usted puede cerrar la sesión, regresar una hora después y consultar la salida contenida en el archivo nohup.out (ej.: less nohup.out).

Si su programa corre en el clúster de Arenal y ocurre una de las siguientes situaciones: (1) está corriendo en el nodo máster, o (2) tiene más de una hora de ejecutarse en un nodo de esclavo. Entonces, debe detenerlo de inmediato como se indica a continuación.

Para detener un proceso, puede usar el comando ps -eu | grep make que le listará los procesos que tiene corriendo en la máquina que tienen make en su nombre. El primer número que vea de resultado es el process ID, usualmente referido como PID. Para matarlo puede usar el comando kill PID reemplazando PID por el número de proceso. Si eso no lo detiene, agregue kill -9 PID. También puede intentar con el comando pkill que en lugar del número de proceso recibe el nombre del mismo, algo como pkill make.

La primera optimización es propuesta libremente por usted, siempre y cuando demuestre empíricamente que incrementa el desempeño. Esta optimización se debe realizar sobre el cálculo de las sumas de Goldbach. Realice todos los pasos del ../material/#optimization[método sugerido para optimizar^], como se indica a continuación.

En el paso 1, para poder comparar posteriormente, tome como punto de partida los resultados de la versión serial. Es decir, realice una medición de tiempo como se indica en la Section 3.4 usando su solución serial de la tarea01 con los casos de prueba pequeños o medianos. Nota: Si usted modificó/optimizó el algoritmo para calcular las sumas de Goldbach en la tarea02, mida su solución de la tarea02 con 1 hilo de ejecución.

En el paso 2 realice un análisis dinámico de rendimiento (profiling). Ejecute su solución de goldbach_optimized con la herramienta callgrind con un caso de prueba mediano y sólo 1 hilo de ejecución. Visualice la salida con KCachegrind y determine las regiones de código que más demandan procesamiento o aquellas que las invocan. Haga una captura de pantalla y agréguela a su documento de reporte y explique resumidamente cómo el diseño de su optimización piensa disminuir este consumo.

En el paso 3 y 4 documente rápidamente (un párrafo o menos) en qué consiste la optimización en su documento de reporte. Luego implemente en código la potencial mejora.

En el paso 5 recuerde siempre hacer tres corridas, es decir: en la misma máquina, con los mismos casos de prueba, con sólo 1 hilo secundario de ejecución, y tomar la menor duración de tres corridas. Anote los resultados en su hoja de cálculo y estime el incremento de velocidad y eficiencia. Escriba en su documento de reporte estos valores. Si no logró incrementar el rendimiento, conjeture en su discusión a qué se podría deber ese resultado y repita el ciclo de optimización.

Paralelizar el consumo de procesamiento de una solución es ya una optimización. Por lo tanto, el trabajo realizado en la tarea02 es una optimización de paralelismo de datos. Esta optimización está también implementada en goldbach_optimized. Corra esta solución con tantos hilos de ejecución como CPUs tenga disponible su sistema contra los casos de prueba pequeños o medianos. Asegúrese de pasarlos, no provocar fugas o accesos inválidos de memoria, y mantener las convenciones de estilo.

Realice la segunda medición de tiempo como se indica en la Section 3.4 usando goldbach_optimized. Use las mismas condiciones que la optimización 1, los mismos casos de prueba, y con tantos hilos secundarios como CPUs hay disponibles en la máquina. Agregue sus resultados a la hoja de cálculo. Más adelante esta medición le proveerá evidencia del incremento de desempeño logrado gracias a la concurrencia.

La tercera optimización es implementar mapeo dinámico para la asignación de trabajo a los hilos de ejecución. Usted debe escoger la unidad de descomposición que provea el mayor incremento de desempeño. Por ejemplo, si escoge como unidad de descomposición los números que se leyeron de la entrada estándar, estos serán repartidos de forma dinámica entre los hilos secundarios.

Su implementación del mapeo dinámico debe seguir el patrón productor-consumidor, donde el productor puede ser el hilo principal, y los consumidores son los hilos secundarios. La cantidad de hilos secundarios debe poderse ajustar mediante un argumento de línea de comandos. Si éste se omite, se debe asumir la cantidad de núcleos de procesador disponibles en el sistema.

Sugerencias. De acuerdo al patrón, la comunicación entre los productores y consumidores se realiza mediante un buffer acotado o no, que puede ser un arreglo circular o una cola thread-safe. Sin embargo, si implementa además seguridad condicional (un arreglo de resultados), puede simplificar el buffer, por ejemplo, mediante un contador entero protegido por mutex.

Siga todos los pasos del método sugerido para optimizar. Como paso 1, la medición que realizó en la optimización 2 servirá como punto de partida. Nota: Para la optimización 3 no es necesario realizar el paso 2 de profiling. El paso 3 corresponde a implementar este mapeo dinámico. Las mediciones en el paso 5 debe realizarlas en la misma máquina que las dos optimizaciones previas, con los mismos casos de prueba, tantos hilos como CPUs, y siempre tomando la menor de tres corridas.

Ya que ha realizado varias optimizaciones, compárelas entre ellas para determinar cuál aportó más al incremento del desempeño o genera mejor eficiencia. Todas las mediciones han de ser comparables, por tanto, deben realizarse en la misma máquina, con los mismos casos de prueba, y tomar la menor duración de tres corridas. Las versiones de sus programas goldbach_x a medir son:

Nota: A la tabla anterior puede agregar optim04, optim05, y subsiguientes, si realizó varias iteraciones por el método sugerido para optimizar que lograran incrementar el desempeño.

Todas las mediciones deben realizarse con los casos de prueba grandes, y tantos hilos como la cantidad de núcleos disponibles en el sistema (ocho para el nodo esclavo del clúster Arenal), a excepción de la versión serial. Si no tiene alguna de las mediciones anteriores realícela y agréguela a la hoja de cálculo. Para todas las mediciones calcule el incremento de velocidad respecto a la versión serial, y la eficiencia.

Cree un gráfico en la hoja de cálculo. En el eje X muestre la versión del programa, correspondiente a la columna “Versión” de la tabla (serial, optim1, pthread, dynamic). El gráfico debe ser combinado con dos ejes Y. El eje Y primario, ubicado a la izquierda del gráfico, indica la duración de las mediciones en segundos. Este debe ser el eje de referencia para serie de mediciones de tiempo. El eje Y secundario, a la derecha del gráfico, indica el incremento de velocidad (speedup) y aunque no tiene unidades puede indicar la palabra “veces”. Este debe ser el eje de referencia para la serie de incrementos de velocidad.

Distinga visualmente las series (duración, speedup, eficiencia). Por ejemplo, puede usar líneas continuas para las primeras y punteadas para las segundas.

Cree en su hoja de cálculo un segundo gráfico que permita comparar el speedup en el eje Y primario contra la eficiencia en el eje Y secundario.

Incluya una sección “Comparación de optimizaciones” en su documento de reporte. Haga una discusión de máximo 500 palabras, en la que compare las versiones de su solución e indique qué produjo el mayor incremento de desempeño. Exporte los gráficos a formato SVG o PNG e incrústelos en la sección de discusión.

Ahora que dispone de programas medibles, uno de los aprendizajes más enriquecedores es poder compararlos en diversas circunstancias, como diferente hardware, casos de prueba, y grado de concurrencia, entre otros. En esta sección podrá comparar sus soluciones respecto a este último rubro.

Todas las mediciones han de ser comparables, por tanto, deben realizarse en la misma máquina, con los casos de prueba grandes, y tomar la menor duración de tres corridas. Lo que varía en cada medición es la cantidad de hilos de ejecución, obtenidas en función de la constante C definida como la cantidad de núcleos de procesador disponibles en un sistema. Por ejemplo, para un nodo esclavo del clúster Arenal, C equivale a 8 núcleos.

Para realizar las comparaciones, se usarán 6 niveles de concurrencia en función de C, es decir, usted registrará en su hoja de cálculo 6 mediciones de la duración de sus programas, listadas en la tabla a continuación. Dado que para lograr una medición más fiable, debe ejecutar su programa al menos tres veces y tomar la duración de menor duración, en total realizará alrededor de 16 ejecuciones de sus programas. En la última columna de la siguiente tabla se muestra la cantidad de hilos para el nodo esclavo del clúster Arenal.

La medición 1 en la tabla (1) corresponde a la medición que realizó de su programa serial (goldbach_serial) con los casos de prueba grandes. Las restantes seis mediciones deben realizarse con goldbach_optimized con tres ejecuciones de los casos de prueba. Lo que varía en cada medición es la cantidad de hilos a crear, el cual es el argumento con que se invoca su programa en línea de comandos o make test ARG=#. Anote la menor de las tres (o más) ejecuciones en su hoja de cálculo. Posiblemente ya tiene varias de estas mediciones realizadas.

Una vez que tenga todas las mediciones calcule el incremento de velocidad (speedup) de cada medición respecto a la serial (incluso la serial misma). Calcule también la eficiencia de cada medición.

Cree un gráfico en la hoja de cálculo. En el eje X muestre la cantidad de hilos que realizaron los cálculos durante la ejecución del programa, correspondiente a la columna “Leyenda” de la tabla (1, hC, 1C, 2C, 4C y D). El gráfico debe ser combinado con dos ejes Y. El eje Y primario, ubicado a la izquierda del gráfico, indica el incremento de velocidad (speedup) y aunque no tiene unidades puede indicar la palabra “veces”. Éste debe ser el eje de referencia para la serie de incrementos de velocidad. El eje Y secundario, a la derecha del gráfico, indica la eficiencia obtenida por cada nivel de concurrencia. De esta forma permitirá comparar el incremento de desempeño (speedup) contra la eficiencia. Distinga visualmente las series de speedup de las de eficiencia. Por ejemplo, puede usar líneas continuas para las primeras y punteadas para las segundas.

Finalmente, cree una sección "Grado de concurencia" en su reporte, y realice un análisis de los resultados obtenidos. Exporte los gráficos a formato SVG o PNG e incrústelos como imágenes. Esta discusión debe ser concisa, de máximo 500 palabras, con su interpretación de los gráficos. A partir de sus resultados responda a la pregunta ¿cuál es la cantidad de hilos óptima para conseguir el mejor rendimiento?. Considere tanto el incremento de velocidad como la eficiencia en su respuesta.

Recuerde que en todos los rubros se evalúan las buenas prácticas de programación. En todos los rubros que generan documentación se evalúa el buen uso de la comunicación escrita, tal como lo estipula la carta al estudiante.

Si no lo ha hecho, primero corrija su solución a la tarea03 en la carpeta tareas/goldbach_optimization/ (no copie ni cree una carpeta nueva) para aplicar las observaciones que obtuvo durante la revisión de la misma, de manera que no se propaguen las deficiencias identificadas de la tarea03 en la tarea04. Siga el mismo procedimiento indicado en Section 2.1.

Una vez concluidas las correcciones a la tarea03, copie su solución concurrente tareas/goldbach_optimization a la carpeta tareas/goldbach_omp_mpi en su repositorio de control de versiones. Recuerde que gracias a la tarea03, esta carpeta ya incluye el documento de reporte al cual se le harán modificaciones en esta tarea04.

Reemplace la concurrencia imperativa implementada con Pthreads, por concurrencia declarativa provista por la tecnología de paralelismo de datos OpenMP, para paralelizar el trabajo de las sumas de Goldbach. Asegúrese de que su implementación pasa los casos de prueba, y no genera diagnósticos del linter (es probable que otras herramientas de análisis dinámico de código no funcionen con esta tecnología).

Al igual que la tarea02, haga que los hilos trabajen de forma lo más paralela posible, y por consiguiente, evitar control de concurrencia innecesario. Recuerde que además su solución debe imprimir los resultados en el orden esperado. Se recomienda evitar la serialización de los hilos y usar una estrategia de seguridad condicional (conditionally safe).

La cantidad de hilos es controlada por argumento de línea de comandos. En caso de omitirse se debe suponer la cantidad de CPU disponibles en la máquina donde corre el programa.

Como hubo un cambio en la implementación de la concurrencia, compare el rendimiento de su implementación con OpenMP contra la de Pthreads siguiendo el mismo procedimiento para obtener mediciones que aplicó en la tarea03. Utilice tantos hilos como núcleos de CPU hay en el sistema con los casos de prueba grandes que usó para la tarea03.

Calcule el incremento de velocidad (speedup) y la eficiencia respecto a la versión serial (tarea01). Agregue este resultado al gráfico combinado de la Comparación01 con el identificador openmp en el eje-X. Agregue al documento de reporte en la sección de "Comparación de optimizaciones" un párrafo que compare los resultados de la concurrencia declarativa (OpenMP) contra la concurrencia imperativa (Pthreads).

Para hacer su solución escalable y aprovechar un clúster de computadoras, distribuya el trabajo de calculo de sumas utilizando la tecnología MPI. Tome en cuenta que su programa debe leer los números de la entrada estándar y no de archivos ni argumentos de línea de comandos. Esto impone restricciones que afectan el diseño de su solución.

Descomponga la unidad de trabajo a distribuir, ésta puede tener la misma o mayor granularidad que la unidad usada para OpenMP. Implemente un mapeo dinámico usando paso de mensajes para repartir las unidades de trabajo entre los procesos o hilos, de tal forma que los recursos del clúster se aprovechen lo más equitativamente posible.

Asegúrese en su máquina local de que su solución distribuida con MPI pase los casos de prueba pequeños y medianos usando distintas cantidades de procesos e hilos. Además su implementación no debe generar diagnósticos del linter.

Compare el rendimiento de su solución distribuida con los casos de prueba grandes que usó en la tarea03. En este caso, es necesario usar un ambiente distribuido (como el clúster de Arenal), y no una máquina individual. Cree tantos procesos como nodos esclavos hayan en el clúster, y en cada proceso tantos hilos como CPUs hayan disponibles en el nodo. Dado que uno de los procesos se encargará del mapeo exclusivamente, éste puede correr en el nodo máster.

Mida la duración de la versión distribuida, calcule el incremento de velocidad y la eficiencia respecto a la versión OpenMP. Agregue los resultados a su gráfico de la Comparación01, de tal forma que en el eje-x se pueda comparar la versión distribuida (mpi) con las versiones previas (OpenMP, Pthreads, serial) que sean comparables, y por lo tanto, que hayan corrido en el mismo hardware. Agregue a su discusión un párrafo con el análisis de los hallazgos que obtuvo con la versión distribuida.

Recuerde que en todos los rubros se evalúan las buenas prácticas de programación. En los rubros que generan documentación se evalúa el buen uso de la comunicación escrita, tal como lo estipula la carta al estudiante.