Tareas: factorización prima

Factorizar números enteros en sus componentes primos es una tarea repetitiva y tediosa, en especial para números grandes. Sin embargo, también lo es para las computadoras tradicionales. La seguridad de sus comunicaciones privadas, datos sensibles y su dinero en el banco depende de esta dificultad, ya que están protegidos por números difíciles de factorizar.

Todo número entero positivo se clasifica en tres categorías: uno, primo, o compuesto. Un número primo es un número entero divisible solamente por 1 y por él mismo, como es el caso de 17. Los números compuestos son aquellos que tienen más de dos divisores, se pueden descomponer y representar como una multiplicación de factores primos. Por ejemplo, el número 10 se puede representar como 2 x 5, el número 100 como 2 x 2 x 5 x 5 o como 2^2 x 5^2 usando notación de potencias. El número 1 es especial y no se considera en ninguna de las dos categorías anteriores.

Para esta entrega se necesita un programa en C que reciba una lista de números enteros en la entrada estándar y calcule su factorización prima de manera serial. Su programa producirá como resultado una lista en la salida estándar con los números en el mismo orden en que fueron ingresados. Cada línea de la salida contiene un número ingresado seguido de su factorización prima. Los exponentes se deben anteceder por el carácter ^. Note que los exponentes 1 no se deben escribir. A continuación se muestra un ejemplo de la salida esperada para la entrada dada.

Ejemplo de entrada:

Salida esperada:

Su programa debe poder factorizar números positivos de 64 bits con signo, es decir, entre 0 y 2^63-1 (int64_t de la biblioteca <stdint.h>). Si en una línea se provee un número fuera de este rango o un texto que no es un número, el programa debe imprimir el texto "invalid number" en la salida estándar, y continuar procesando el resto de líneas.

En su repositorio personal cree una carpeta tareas/primefact_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.

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), 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 los factores con las impresiones, sino que las subrutinas de lectura, cálculo de factores (potencias), 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, las factorizaciones encontradas, y 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 número compuesto de al menos dos potencias, un primo, y un número inválido). 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 factores primos (potencias), impresión, y subrutina principal. La del cálculo de factores 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 y se debe configurar para el lenguaje de programación C. Estos son algunos cambios sugeridos:

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:

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. 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 disponible en la sección `Archivos'' del aula virtual, 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).

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.

Si no lo ha hecho, primero corrija su solución a la tarea01 en la carpeta tareas/primefact_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 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/primefact_serial/ y su contenido como tareas/primefact_pthread. Haga un commit con este cambio.

El programa concurrente recibirá la lista de números enteros en la entrada estándar e imprimirá la descomposición prima 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 factorizaciones primas 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 los factores primos. 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 de factorización (ej.: usar una criba), la tarea03 se encargará de ello. La versión concurrente debe implementar el mismo algoritmo de factorización 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).

Los sistemas que aprovechan la factorización prima, por ejemplo, para proveer seguridad en las telecomunicaciones, no usan números de 64 bits, sino de 1024, 2048 o más bits. Haga que su solución pueda encontrar la factorización prima de números de cualquier longitud. 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 ejemplo de uso en C.

Asegúrse 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 la factorización prima 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).

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 todo. Por ejemplo, para construir un ejecutable con asan sanitizer y probarlo, y luego otro con thread sanitizer y probarlo sería algo como

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

Esta tarea es una secuencia de la tarea02 y debe apegarse a las reglas de entrega de la tarea02, a excepción de los cambios solicitados en este enunciado. También se mantienen los lineamientos de las siguientes secciones de la tarea01:

La primera optimización es implementar mapeo dinámico de los números. Es decir, los hilos secundarios se reparten los números que se leyeron de la entrada estándar de forma dinámica. 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.

De acuerdo al patrón, la comunicación entre los productores y consumidores se realiza mediante un buffer acotado o no, que puede ser 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, haga una medición en la máquina de pruebas de la tarea02 con tantos hilos secundarios como núcleos dispone tomando la menor duración de tres corridas. Nota: Para esta optimización no es necesario realizar el paso 2 de profiling. El paso 3 corresponde a este mapeo dinámico. Las mediciones en el paso 5 debe realizarlas en la misma máquina, con los mismos casos de prueba, y siempre tomando la menor de tres corridas.

La segunda optimización es propuesta libremente por la persona estudiante, siempre y cuando demuestre empíricamente que incrementa el desempeño. Esta optimización se debe realizar sobre el código de la primera optimización. Realice todos los pasos del método sugerido para optimizar. En el paso 1 tome como punto de partida los resultados de la optimización 1.

En el paso 2 realice un análisis dinámico de rendimiento (profiling) para asegurarse de que su propuesta de optimización impacta directa o indirectamente las líneas de código más críticas en consumo de CPU. Para realizar el análisis dinámico de código, ejecute su solución actual con la herramienta callgrind con un caso de prueba mediano. 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 la potencial mejora. En el paso 5 recuerde siempre hacer tres corridas en las mismas condiciones que la optimización 1, es decir: en la misma máquina, con los mismos casos de prueba, con tantos hilos secundarios como CPUs hay disponibles en la máquina, 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.

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 primefact a medir son:

Nota: A la tabla anterior puede agregar optim03, optim04, 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 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 (tarea01, tarea02, optim01, optim02). 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.

Puede, y se recomienda, crear un segundo gráfico que permite 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 el gráfico a formato SVG o PNG e incrústelo en la 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 mismos casos de prueba, 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 7 niveles de concurrencia en función de C, es decir, usted registrará en su hoja de cálculo 7 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á al menos 21 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 (S) corresponde a la menor de tres (o más) ejecuciones de su programa serial (primefact_serial) con los casos de prueba. Las restantes seis mediciones deben realizarse con el programa que obtuvo tras la Optimización02 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. Note que la Optimización02 ya obtuvo la medición para 1C.

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 (S, 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, realice un análisis de los resultados obtenidos en la parte final de su documento de reporte. 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/primefact_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. Recuerde utilizar issues de su sistema de control de versiones de la siguiente forma.

Una vez que haya corregido la tarea03, cree un tag tarea03fix asociado al último commit de las correcciones, y asegúrese enviarlo al repositorio remoto (git push --tags). Luego pase a las optimizaciones (tarea03).

Una vez concluidas las correcciones a la tarea03, copie su solución concurrente tareas/primefact_optimization a la carpeta tareas/primefact_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 la tarea04.

Utilice la tecnología de paralelismo de datos OpenMP para paralelizar el trabajo de la factorización prima. Asegúrese de que su implementación pasa los casos de prueba, y no genera diagnósticos de las herramientas de validez como el linter.

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.

Nota: Si toma como código base la tarea03, deberá reemplazar el código de Pthreads por OpenMP. Si usa como código base su solución serial (tarea01), asegúrese de aplicarle las optimizaciones que realizó en tareas posteriores y de que éstas pasen los casos de prueba.

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, utilizando tantos hilos como núcleos de CPU hay en el sistema con el caso de prueba que usó para la tarea03.

Calcule el incremento de velocidad (speedup) y la eficiencia. Cree un gráfico combinado con esas dos secuencias (siguiendo las mismas indicaciones de la tarea03). Agréguelo a un documento de reporte en una sección de "Concurrencia declarativa (OpenMP)" donde incluya una discusión no mayor a 500 palabras explicando los resultados obtenidos en las mediciones.

Para hacer su solución escalable y aprovechar un clúster de computadoras, distribuya el trabajo de factorización utilizando la tecnología MPI. Tome en cuenta que su programa debe leer los números a factorizar 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 de que su solución distribuida con MPI pase los casos de prueba 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 el caso de prueba que usó en la tarea03. En este caso, es necesario usar un ambiente distribuido, y por tanto el clúster de Arenal. Cree tantos procesos o hilos como CPUs hayan disponibles en los nodos secundarios del clúster. 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 (la cual también debe correr en un nodo esclavo del clúster). Agregue los resultados a su gráfico, de tal forma que en el eje-x se pueda comparar la versión distribuida de 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 análisis de los resultados 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.