1. Problema: Transferencia de calor

Se necesita una sencilla simulación por computadora que ayude a encontrar el momento de equilibro térmico de una lámina rectangular a la que se le inyecta calor constante por su borde. La lámina (en inglés, plate) corresponde a un rectángulo de dos dimensiones de un mismo material. Para efectos de la simulación, el rectángulo es dividido en \$R\$ filas y \$C\$ columnas ambas de igual alto y ancho \$h\$ como se ve en la Figura 1. Esto genera una matriz cuyas celdas son todas cuadradas, de ancho y alto \$h\$.

proy2.1 plate
Figura 1. Representación matricial de la lámina en la simulación

Cada celda de la matriz almacena una temperatura, la cual puede cambiar en el tiempo. Se usa la notación \$T_{i,j}^k\$ para indicar la temperatura de la celda ubicada en la fila \$i\$, columna \$j\$, en el instante o estado \$k\$. Después de transcurrido un tiempo \$\Delta t\$, la simulación pasará del instante \$k\$ al instante \$k+1\$, y la temperatura en la lámina habrá variado (cambio de estado). Como es sabido, la energía se transfiere de un área más caliente hacia una más fría. La nueva temperatura en la celda \$(i,j)\$ será \$T_{i,j}^{k+1}\$ como se ve en la parte derecha de la Figura 1, y puede estimarse a partir de su temperatura en el instante (o estado) anterior y la temperatura de sus celdas vecinas por la relación:

\$T_{i,j}^{k+1} = T_{i,j}^k + \frac{\Delta t \cdot \alpha}{h^2} (T_{i-1,j}^k + T_{i,j+1}^k + T_{i+1,j}^k + T_{i,j-1}^k - 4T_{i,j}^k)\$

De acuerdo a la relación anterior, la temperatura de una celda en el instante o estado \$k+1\$ indicado por \$T_{i,j}^{k+1}\$, es el resultado de la temperatura que la celda tenía en el instante o estado anterior \$T_{i,j}^k\$ más la pérdida o ganancia de energía que la celda haya sufrido con sus inmediaciones durante ese período \$\Delta t\$. Para efecto de la simulación, las inmediaciones son las cuatro celdas vecinas en forma de cruz como se ve en la Figura 1. Esta transferencia de energía o calor está regida por:

  1. La energía que la celda \$i,j\$ recibe de sus inmediaciones, y se calcula como la suma de las temperaturas de las cuatro vecinas \$T_{i-1,j}^k + T_{i,j+1}^k + T_{i+1,j}^k + T_{i,j-1}^k\$.

  2. La energía que la celda pierde y se distribuye a sus cuatro celdas vecinas, calculada como \$-4T_{i,j}^k\$.

  3. La transferencia no es instantánea, sino que depende del área que recorre. Entre mayor es el área de la celda, más tiempo requerirá la energía para desplazarse y equilibrarse con sus vecinas. Por eso la ganancia y pérdida de energía calculada en los dos puntos anteriores, se divide entre el área de la celda \$h^2\$.

  4. La cantidad de energía transferida es proporcional al tiempo. Es decir, entre más tiempo \$\Delta t\$ se permita entre el estado \$k\$ y el estado \$k+1\$, más energía podrá intercambiar la celda con sus vecinas. Por esto, el intercambio de energía calculado en los puntos anteriores se multiplica por la duración del estado \$\Delta t\$.

  5. La cantidad de energía intercambiada en el periodo de tiempo depende de la calidad conductora de la lámina. Materiales como la madera son lentos para transmitir energía, mientras que los metales son eficientes para este fin. Para reflejar esta realidad, el intercambio de energía calculado en los puntos anteriores se multiplica por la difusividad térmica, que corresponde a una constante α que indica a qué tasa el material logra transmitir energía desde un punto caliente hacia otro frío a través de él. Sus unidades son de área entre tiempo, como \$\frac{m^2}{s}\$ ó \$\frac{mm^2}{s}\$. Por ejemplo, la madera tiene una difusividad cercana a \$0.08\frac{mm^2}{s}\$ mientras que el oro de \$127\frac{mm^2}{s}\$, es decir, el oro transfiere calor aproximadamente 1500 veces más rápido que la madera.

1.1. Simulación de calor

La Figura 2 muestra cuatro instantes o estados de una simulación hipotética de una lámina de oro (difusividad térmica \$α=127\frac{mm^2}{s}\$). Para efectos de la simulación, la lámina fue dividida en 5 filas y 4 columnas, cuyas celdas son de \$h=1000mm\$ de lado, es decir, de un metro de ancho por un metro de alto.

En el estado o instante cero (\$k=0\$) la simulación carga la matriz de un archivo que indica las temperaturas iniciales de cada celda de la lámina. Es importante resaltar que los bordes de la lámina no cambian su temperatura en el tiempo, dado que es el punto donde las personas experimentadoras "inyectan o retiran calor". Por esto los bordes se resaltan con color de fondo en la Figura 2. De esta figura puede verse que en la parte superior se inyecta calor a una temperatura constante de 10 unidades (Celcius, Farenheit, o Kelvin), y conforme se desciende en la lámina, se provee menos calor en los bordes.

proy2.1 sim
Figura 2. Cuatro etapas de la simulación

Supóngase que se quiere actualizar el modelo cada 20 minutos, es decir \$ \Delta t = 1200s = 20min\$. En cada instante o estado, la simulación debe actualizar las celdas internas de la lámina de acuerdo al modelo físico presentado en la sección anterior. En el instante o estado \$k=1\$ habrán transcurrido \$k \Delta t = 1200s = 20min\$. Como puede verse en la Figura 2, las temperaturas en los bordes se mantienen constantes, pero las celdas internas han adquirido energía de los bordes, en especial las celdas en la parte superior. Sin embargo, la celda \$2,2\$ perdió energía pese a que está al lado de un borde de temperatura 6, dado que tres de sus vecinas estaban más frías que ella en el estado previo \$k=0\$.

En el estado \$k=2\$ habrán transcurrido \$k \Delta t = 2 \cdot 1200s = 40min\$. Como puede verse en la Figura 2, las celdas internas han incrementado lentamente su temperatura dado a que son de \$1m^2\$ cada una. Incluso la celda \$2,2\$ ha visto reflejado un incremento. En el estado \$k=3\$ que en la vida real ocurriría una hora después de que inicia el experimento, la temperatura interna sigue creciendo, pero aún no se ha equilibrado con los valores de los bordes.

Se desea que la simulación continúe hasta que se haya alcanzado el punto de equilibrio, lo cual ocurre cuando el calor se ha estabilizado en la lámina. Para esto se proveerá un parámetro épsilon (ε) a la simulación, que representa el mínimo cambio de temperatura significativo en la lámina. En cada estado \$k\$ se actualizan todas las celdas internas de la lámina. Si al menos una de las celdas internas tiene un cambio en su temperatura mayor a ε, indica que no se ha alcanzado aún el equilibrio y la simulación continúa con el siguiente estado \$k+1\$, de lo contrario se detiene y reporta los resultados de la simulación. Por ejemplo, si la simulación de la Figura 2 se corriera con un \$ε=2\$ unidades de temperatura, ésta terminaría en el estado \$k=2\$, dado que el cambio de temperatura más grande del estado \$k=1\$ a \$k=2\$ se da en la celda \$1,1\$, calculada como \$|4.51-2.74|=1.77\$, y es menor que el \$ε=2\$.

El modelo físico presentado en la sección anterior es muy sensible a los parámetros de entrada, y dependiendo de la combinación de valores puede producir resultados incorrectos. El modelo se acerca más a la realidad entre más celdas se usen para representar la lámina (filas y columnas) y más pequeños sean los cambios de tiempo (\$\Delta t\$). Sin embargo acercarse a la realidad impone más presión sobre los recursos de la máquina, lo que hace la simulación más lenta, por lo que se desea una versión paralelizada de la simulación, que pueda encontrar el punto de equilibrio térmico en el menor tiempo posible.

1.2. Programa de simulación

Se necesita que la solución concurrente sea invocada desde la línea de comandos con los siguientes argumentos:

  1. El nombre de un archivo de trabajo (job). Es obligatorio. Si no se provee, se debe emitir un mensaje de error.

  2. La cantidad de hilos de ejecución. Es opcional, y si se omite, se debe suponer la cantidad de CPUs disponibles en el sistema. Nota: Esta funcionalidad se implementa en la tarea02.

Por ejemplo, la siguiente invocación indica que se quiere realizar todas las simulaciones indicadas en el archivo de trabajo job001.txt con 16 hilos de ejecución.

bin/heatsim jobs/job001.txt 16

Nota: Cuando un usuario indica el nombre de un archivo, puede agregar la ruta (relativa o absoluta) donde éste se encuentra. A nivel de programación en C/C++ no es necesario hacer un trabajo adicional para poder abrir los archivos, simplemente se usa el texto provisto por el usuario como nombre del archivo a abrir. El sistema operativo se encarga automáticamente de resolver las rutas relativas o absolutas.

1.3. Archivo de trabajo

El archivo de trabajo (job file) es un archivo de texto que lista varias láminas y los parámetros de simulación que las personas experimentadoras quieren investigar en cada una de ellas. El siguiente es un ejemplo de un archivo de trabajo job001.txt:

plate001.bin 1200 127 1000 2
plate001.bin 1200 127 1000 1.5
plate002.bin 60 0.08 450 0.75

Cada línea del archivo de trabajo contiene una simulación independiente de las demás. Una simulación consta de los siguientes parámetros separados por espacios en blanco:

  1. Nombre del archivo que contiene la lámina en su estado inicial. El contenido de este archivo se explica más adelante. La ubicación del archivo de simulación es relativo al archivo de trabajo. Por ejemplo si el anterior es el contenido del archivo de trabajo jobs/job001.txt significa que plate001.bin se encuentra también en la subcarpeta jobs/plate001.bin. Una alternativa para trabajar con rutas se ofrece más adelante.

  2. La duración de cada etapa \$\Delta t\$ en segundos.

  3. La difusividad térmica α del material medida en unidades de área entre tiempo, por ejemplo: \$\frac{m^2}{s}\$ ó \$\frac{mm^2}{s}\$. Puede suponer que las unidades de tiempo siempre son las mismas que las usadas en el parámetro anterior.

  4. Las dimensiones \$h\$ de las celdas medidas en las mismas unidades de área que el parámetro anterior pero lineales (distancia).

  5. La sensitividad del punto de equilibrio ε, en las mismas unidades de temperatura que se usaron en el archivo de la lámina.

Su programa debe realizar todas las simulaciones indicadas en el archivo de trabajo. Una simulación involucra cargar la lámina como una matriz en memoria, y actualizarla a lo largo de varios estados hasta que se haya alcanzado el punto de equilibrio térmico. Una vez que esto ocurre se debe hacer un reporte a las personas investigadoras, como se indica en la próxima sección.

Nota: Como se indicó anteriormente, los archivos de láminas son relativos al archivo de trabajo. Puede usar procesamiento de cadenas para extraer el prefijo del archivo de trabajo. Alternativamente puede solicitar un tercer argumento en línea de comandos al programa de simulación que indica la ruta donde se encuentran todos los archivos. Por ejemplo:

bin/heatsim job001.txt 16 jobs

La instrucción anterior usaría jobs/ como prefijo de ruta de todos los archivos. Es decir, provocaría que el programa busque el archivo de trabajo jobs/job001.txt. Para cada lámina dentro de job001.txt también se utilizaría el prefijo, es decir jobs/plate001.bin, jobs/plate002.bin, etc.

1.4. Archivo de reporte

El archivo de reporte provee estadísticas resultado de ejecutar cada simulación. Su nombre tiene la forma job###.tsv, donde ### es el mismo número del archivo de trabajo. Cada vez que se invoca el programa de simulación, se crea o sobrescribe el archivo de reporte correspondiente. El archivo de reporte es de texto y tiene un formato similar al archivo de trabajo:

plate001.bin  1200   127  1000  2        2  0000/00/00  00:40:00
plate001.bin  1200   127  1000  1.5      3  0000/00/00  01:00:00
plate002.bin    60  0.08   450  0.75 56907  0000/01/09  12:27:00

Las líneas del archivo de reporte coinciden con las del archivo de trabajo. Cada línea del reporte contiene los mismos valores del archivo de trabajo, pero separados por tabuladores, y agrega dos resultados (columnas):

  1. La cantidad de estados \$k\$ que transcurrieron hasta alcanzar el punto de equilibrio.

  2. El tiempo transcurrido \$k\Delta t\$ hasta alcanzar el punto de equilibrio, pero reportado en formato legible para humanos YYYY/MM/DD hh:mm:ss donde, por sencillez, los meses son siempre de 30 días.

Para formatear el tiempo transcurrido en segundos, puede usar la siguiente función. (Este programa muestra un ejemplo de uso).

// Copyright 2025 Jeisson Hidalgo-Cespedes <jeisson.hidalgo@ucr.ac.cr> CC-BY-4
#include <assert.h>
#include <stdio.h>
#include <time.h>

/**
 * @brief Convert given amount of @a seconds to an aproximate text
 * YYYY/MM/DD hh:mm:ss
 * 
 * @param seconds Amount of seconds elapsed from any point in time, no need
 * from 1970-Jan-01 00:00:00 GMT
 * @param text Pointer to a buffer of at least 48 chars
 * @param capacity Capacity of the pointed buffer array must be 48 or greater
 * @return The pointer to text
 */
char* format_time(const time_t seconds, char* text, const size_t capacity) {
  assert(text);
  assert(capacity >= 48);
  // Disable cpplint warning, gmtime is thread-safe
  const struct tm gmt = *gmtime(&seconds);  // NOLINT(runtime/threadsafe_fn)
  // We use sprintf instead of strftime because seconds are a relative elapsed
  // time from an arbitrary point in time, not from 1970-Jan-01 00:00:00 GMT
  snprintf(text, capacity, "%04d/%02d/%02d\t%02d:%02d:%02d", gmt.tm_year - 70,
      gmt.tm_mon, gmt.tm_mday - 1, gmt.tm_hour, gmt.tm_min, gmt.tm_sec);
  return text;
}

Las personas experimentadoras están también interesadas en conocer el estado de la lámina una vez que haya alcanzado el punto de equilibrio. Por eso la simulación debe crear –o sobrescribir si ya existe– un archivo binario con el estado de la matriz en el punto de equilibrio, y con el nombre plate###-k.bin donde k corresponde al número de estado donde se alcanzó el equilibrio. Este archivo tiene el mismo formato que cualquier otro archivo de lámina, y por lo tanto, podría ser usado como punto de partida de nuevas simulaciones.

Nota: Usted debe decidir dónde se escriben los archivos de resultado. Se ofrecen a continuación tres alternativas no excluyentes.

  1. En la carpeta actual. Los archivos de resultado se escriben en la carpeta actual, es decir, de dónde se llama al ejecutable. Se puede suponer que en esa carpeta actual tienen permisos de escritura. Por ejemplo:

    cd /path/to/heatsim
mkdir output
cd output
../bin/heatsim job.txt 8 /path/to/input

    Provocaría que el programa lea la orden de trabajo /path/to/input/job.txt, con láminas como /path/to/input/plate.bin, y escriba los archivos de salida en /path/to/proy02/output/.

  2. En la misma carpeta de entrada (no recomendado). El reporte se escribe en la misma carpeta donde se encuentra el archivo de trabajo. Para este fin puede hacer manipulación de cadenas de caracteres, o usar el tercer argumento de línea de comandos. Este esquema no es recomendado, dado que los casos de prueba pueden estar en una carpeta compartida de sólo lectura.

  3. Cuarto argumento. Agregar un cuarto argumento de línea de comandos que indique la ruta donde se escriben los archivos de salida, por ejemplo:

    bin/heatsim job001.txt 16 tests output

    Realizaría el trabajo tests/job001.txt, con láminas como tests/plate001.bin, y escribiría el reporte en output/job001.tsv y láminas resultantes como output/plate001-2.bin.

El enfoque recomendado es recibir un cuarto argumento opcional de línea de comandos que indique la ruta donde se escriben los archivos de salida. Si este argumento se omite, se utilizará la carpeta actual como ruta de salida.

1.5. Archivo de lámina

Las láminas son matrices que se almacenan en archivos binarios que tienen una estructura sencilla. Los primeros ocho bytes son un entero sin signo \$R\$ que indica la cantidad de filas de la matriz. Los segundos ocho bytes son un entero sin signo \$C\$ que indica la cantidad de columnas de la matriz. A partir de los 16 bytes anteriores, continúan \$R\cdotC\$ números flotantes de doble precisión con la temperatura inicial de cada una de las celdas de la matriz, en el orden habitual de filas y columnas. Todos los valores se encuentran en little-endian.

Nota: Su código fuente debe emplear entrada y salida binaria y no de texto. Por ejemplo, en C se deben usar los procedimientos fread() y fwrite() en lugar de entrada y salida con formato como scanf() y printf().

Importante: Las matrices que las personas investigadoras simulen pueden ser muy grandes debido a la necesidad de una alta granularidad para poder acercar la fidelidad de la simulación a la realidad. Su programa debe hacer un cuidadoso y eficiente manejo de memoria y de errores.

1.6. Casos de prueba

Cree al menos un caso de prueba manual. Es decir, un caso de prueba pequeño en el que usted realice los cálculos a mano. Su caso de prueba puede ser de una matriz pequeña, y que alcance el equilibrio térmico en pocos estados. Escriba manualmente el archivo de lámina, el archivo de trabajo, y el archivo de reporte esperado. Incluya estos archivos en la carpeta tests/ de su proyecto.

Para conveniencia se proveen estos casos de prueba. Puede descargarlos en una carpeta externa a su tarea. Si gusta puede agregar los casos de prueba pequeños (job00*) o medianos (job01*) a control de versiones. Sin embargo, por ninguna razón agregue a control de versiones los casos de prueba grandes (job02*).

Estos casos de prueba están disponibles en el clúster del curso (Poás) en la dirección /opt/ohpc/pub/cursos/paralela.

Referencias

2. Tarea01: serial

Provea una solución serial (secuencial) al problema planteado en la sección Section 1.

Nota: En esta y las siguientes secciones se proveen detalles de cómo debe presentar su solución. Por la extensión del texto puede parecer abrumador. Tenga presente en todo momento que estas instrucciones no son con un fin cortoplacista de la evaluación de un curso, ni que el producto es para la persona docente, sino de tratar de emular un ambiente de desarrollo similar al que encontrará en un contexto laboral.

Trate de pensar que acaba de acordar con un/a cliente real que usted le va a desarrollar un software que resuelve las necesidades planteadas al inicio de este documento. Piense que de verdad eso acaba de ocurrir hoy. Usted está comprometido/a en las próximas 12 semanas a entregarle avances a este cliente de un producto de calidad y eficiente por las altas sumas de dinero que el software vale. Piense en el conocimiento que dispone hoy para lograr esta meta.

El fin de estas instrucciones es ayudarle a usted a adquirir nociones y habilidades que le permitan crear productos de calidad y eficientes para sus clientes reales, no para docentes. Piense que su docente es una persona que ha decidido dedicar parte de su tiempo y conocimiento a ayudarle a usted a lograr conviertirse cada vez más en ese/a profesional con quien colegas y clientes quieren trabajar.

2.1. Entregables

En su repositorio individual cree una carpeta tareas (o en inglés, homework/ o hw/). Dentro de ella cree una carpeta 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.

Recurso Descripción Versionado

bin/

Ejecutables

No

build/

Código objeto (.o) temporal

No

design/

Diseño de la solución en UML, redes de Petri, pseudocódigo, u otros

Sí

doc/

Documentación generada por doxygen

No

src/

Código fuente (.h y .c)

Sí

test/

Casos de prueba

Sí

Makefile

Automatiza la construcción, prueba y otras tareas con la solución. Debe incluir el Makefile genérico de la carpeta /common/ de su repositorio

Sí

Doxyfile

Configura Doxygen para extraer documentación del código fuente. Puede obtenerse con make doc. Debe incluir al ../../common/Doxyfile

Sí

readme.adoc

Describe el problema resuelto y el manual de usuario. Puede usar Markdown si prefiere.

Sí

.gitignore

Ignora los recursos que NO deben estar en control de versiones (columna Versionado), como casos de prueba grandes. No redunde líneas del .gitignore en la raíz del repositorio.

Sí

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 sobre el uso de control de versiones.

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. Si Git le reporta archivos generados por el sistema operativo, como .DS_Store en macOS o thumbs.db en Windows, haga a Git ignorarlos desde el .gitignore en la raíz de su repositorio.

Su solución debe ser una obra intelectual de su propia autoría 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 utiliza inteligencia artificial generativa, indique en el comentario el modelo de lenguaje natural y la consulta usada. Si reutiliza código a lo largo de varios archivos, la referencia debe estar en su readme.adoc, en una sección de "Créditos", donde liste el nombre de la biblioteca, quien la creó, 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.

2.2. Análisis

En un archivo readme.adoc en notación AsciiDoc (preferible) o readme.md en notación Markdown, plasme el resultado de la fase de análisis. Si no conoce el formato Markdown o AsciiDoc, asegúrese de seguir un manual o 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:

  1. Una descripción del problema a resolver. Se recomienda resumir o adaptar partes de este enunciado pero no copiarlas exactamente igual, ya que el enunciado va dirigido al estudiantado, mientras que el readme va dirigido a sus clientes y no a docentes. Una persona que lea el readme debería poder entender el problema que su solución resuelve. Una vez escrito, pruebe su readme con personas ajenas al proyecto. Por ejemplo, puede pedirle a familiares que lean el documento y luego hacerles preguntas de comprensión. Naturalmente puede hacer referencia a este enunciado, por ejemplo, a través de un enlace en su readme. No haga capturas de imágenes de las fórmulas, sino escríbalas en notación LaTeX (puede copiar el código LaTeX del documento original).

  2. Un manual de uso, que indica cómo construir (compilar) la solución. Provea ejemplos de cómo correr el programa, sea de forma interactiva, o en lote redireccionando la entrada estándar, o pasando argumentos de línea de comandos. No es necesario hacer capturas de pantalla de la terminal, se puede copiar y pegar la salida en un bloque de código de Markdown o AsciiDoc.

  3. Una sección de créditos, donde indica su nombre e información de contacto (correo institucional). Si utiliza recursos de terceros, como imágenes o archivos de código fuente, provea en esta sección el respectivo crédito.

2.3. Diseño

Dentro de la carpeta para su tarea, cree una subcarpeta para el diseño. Si usa el Makefile reutilizable, puede generar esta carpeta y archivos iniciales con el comando make project=design.

Para que su código sea fácil de paralelizar en tareas posteriores, su diseño no debe entrelazar las subrutinas del dominio del problema con las lecturas o impresiones. Es decir, su programa debe realizar primero la lectura de la entrada y cargarla a alguna estructura de datos. Luego realiza en la estructura de datos el trabajo que resuelve el problema planteado en la Section 1. Los resultados serán guardados en la estructura de datos misma. Finalmente, imprime los resultados almacenados en la estructura de datos hacia la salida y libera los recursos consumidos por la estructura de datos.

Tenga en cuenta restricciones de memoria. Por ejemplo, si tiene que trabajar con matrices muy grandes, puede ocurrir que no se pueda cargar dos o más de ellas en la memoria principal. En tal caso tendría que serializar el procesamiento de una matriz tras otra. Sin embargo, en el futuro podría tener varios hilos trabajando en paralelo en partes distintas de la matriz una vez que ésta esté cargada en la memoria.

Para este diseño elabore un diagrama de la estructura de datos para un caso de prueba pequeño. 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 o de los que aparecen en los libros de programación. Por ejemplo, represente arreglos como una secuencia de cajas enumeradas, o matrices como tablas, listas como nodos (rectángulos) enlazados con flechas, etc. Su diagrama no requiere ser formal, pero sí que le ayude a explicar a otra persona cómo piensa distribuir la memoria para resolver el problema. Si los tiene, represente los registros de memoria, también llamados estructuras (struct) u objetos, y sus relaciones de composición y herencia con UML.

Exporte sus diagramas a archivos .svg (recomendado) o .png y almacénelos en la carpeta design/. En el archivo design/readme.adoc o design/readme.md 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 (el diseño es como un mapa de una ciudad). Si no lo tiene ya, coloque un hiperenlace desde el readme de la tarea (documento de análisis) hacia su design/readme.adoc, lo cual permitirá navegabilidad entre los documentos del proyecto.

Su solución debe ser modular. Debe al menos tener las subrutinas de lectura, dominio del problema, impresión, y subrutina principal. Dado que su solución es procedimental, diseñe en pseudocódigo el algoritmo solución principal que resuelve el problema. Concéntrese en la esencia de la solución, y obvie detalles técnicos. Por ejemplo, puede suponer que se puede leer una matriz completa con una instrucción de lectura, de que su memoria se libera automáticamente, que los datos ingresados siempre son correctos, entre otros. Escriba su diseño en uno o varios archivos con extensión .pseudo en la carpeta design/. Incruste o enlace estos archivos .pseudo en su documento de diseño (design/readme.adoc).

2.4. Documentación

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. Puede usar el Makefile para generarlo en la carpeta common/ de su repositorio y preconfigurarlo con los siguiente comandos, donde los textos entre paréntesis angulares deben ser reemplazados por sus valores efectivos:

cd <path/to/repo>
cd common
make doc
git add Doxyfile
git commit -m 'Reutilizable Doxyfile'

Edite el Doxyfile para que extraiga símbolos del lenguaje de programación C. Estos son algunos cambios sugeridos (puede que el Makefile ya haya configurado algunos de ellos):

PROJECT_NAME           = "<A name for your project>"
PROJECT_NUMBER         = 1.0.0
PROJECT_BRIEF          = "<A sentence describing your project>"
OUTPUT_DIRECTORY       = doc
CREATE_SUBDIRS         = YES
OPTIMIZE_OUTPUT_FOR_C  = YES
EXTRACT_ALL            = YES
EXTRACT_PRIVATE        = YES
EXTRACT_PRIV_VIRTUAL   = YES
EXTRACT_PACKAGE        = YES
EXTRACT_STATIC         = YES
EXTRACT_LOCAL_METHODS  = YES
QUIET                  = YES
INPUT                  = src
RECURSIVE              = YES
HAVE_DOT               = YES

Una vez hechos esos cambios, recuerde hacer otro commit. 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:

@INCLUDE = ../../common/Doxyfile

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). Una vez configurado Doxygen, documente su código fuente conforme lo escribe.

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 su subrutina realiza una búsqueda lineal o binaria. Un ejemplo corto de documentación de una subrutina podría ser:

/**
 @brief Read @a value_count double values from stdin and store them in @a values array
 @param value_count Number of elements to be read from stdin
 @param values Array of elements. It must not be NULL. It must have enough
 capacity to store @a value_count elements, otherwise it will crash.
 @return An error code:
   0 for success.
   1 if EOF is found before @a value_count values are read
   2 if a valid double value cannot be read from stdin
*/
int read_values(const size_t value_count, double values[]);

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:

/// @brief Print all values of @a values array to standard output
/// @see read_values()
int print_values(const size_t value_count, double values[]);

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 las formas permitidas por Doxygen, pero mantenga la consistencia.

La segunda parte es documentar la implementación de la subrutina. Se hace con comentarios normales (no de Doxygen) dentro del cuerpo de la subrutina, es decir, describir los algoritmos implementados dentro de las llaves \{…}. En las interfaces importa documentar el qué, en las implementación importa el cómo. Piense que su código fuente debe ser auto-explicable. Si usted no está para explicar el código y alguien nuevo(a) en su proyecto debe hacer una modificación, basta con que lea los comentarios en los cuerpos de las subrutinas para que entienda el algoritmo implementado sin tener que estudiar el código fuente.

No se trata de documentar por documentar. Su objetivo con esta parte de la tarea es aprender a crear código fuente de calidad bien explicado para sus futuros clientes y colegas de trabajo. En las revisiones de las tareas y proyectos su propósito es tratar de recibir realimentación de sus docentes y asistentes en qué medida está logrando desarrollar esta habilidad de documentar. Piense en lo tortuoso que es tener que trabajar con código fuente mal diseñado y mal documentado. Su propósito es aprender crear lo contrario, código que sus clientes desean y que sus colegas estarán encantados(as) de trabajar con usted.

2.5. Implementación

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. También subrutinas de terminación abrupta como exit().

Corra el linter con frecuencia para apegarse a una convención de estilos. En el curso se usará la convención de Google para C/C+\+ por ser popular y proveer herramientas para ayudar a verificarla. Pero en realidad la convención en sí no es lo importante, sino la habilidad de poder apegarse a una convención cualquiera y poder mantener consistente una base de código fuente. Para las empresas esto es tan importante que no apegarse a la convención puede ser causal de despido. La documentación de la convención de estilo de Google para C/C++ es pública y puede estudiarla. Para obtener un reporte de la herramienta cpplint puede emitir el comando make lint.

Algunos consejos para evitar problemas comunes son los siguientes. Use dos espacios para indentar (sangría) en lugar de cuatro espacios o tabuladores. Si una línea de código supera los 80 caracteres, divídala en dos líneas e inicie la segunda con doble nivel de indentación (por lo tanto, sangría de 4 espacios en blanco respecto a la anterior). Use llaves egipcias para delimitar los bloques de código. Cree bloques de código también para condicionales y ciclos de una única instrucción. Separe los operadores binarios de los operandos con un espacio en blanco, no así los operadores unarios. Preceda los comentarios en línea con dos espacios en blanco. Por ejemplo:

/// Inicie el texto de todo comentario con un espacio
int print_values(const size_t value_count, double* values) {
  for (size_t index = 0; index < value_count; ++index) {
    if (fscanf(stdin, "%lf", values + index) != 1) {
      return 1;  // Note los dos espacios antes del comentario
    }
  }
  return 0;
}

Las siguientes subsecciones incluyen algunos detalles técnicos de implementación que posiblemente enfrentará.

2.5.1. Validación de entrada

Aplique la buena práctica de programación defensiva. Su programa debe defenderse de entradas inválidas o mal intencionadas, como números incorrectos, muy grandes, o textos que no son números. Para probar si hubo un error de lectura deben hacerse las verificaciones de la subrutina que esté usando para entrada/salida, por ejemplo el valor de retorno de scanf() o fread().

Además, inmediatamente después de invocar un procedimiento que puede fallar, conviene revisar la variable global errno declarada en el encabezado <errno.h> disponible en ambientes Unix, ya que algunas subrutinas de entrada y salida escriben en ella códigos de error. Nota: Después de procesar una entrada inválida, conviene limpiar la variable errno para la siguiente lectura, si usa esta variable en su código.

2.5.2. Enteros de tamaño fijo

El linter de Google sugiere que use tipos de datos enteros cuyo tamaño no dependa de la arquitectura. Es decir, en lugar de usar int que en algunas arquitecturas es de 2 bytes y en otras es de 4 bytes, use un tipo que siempre es de una cantidad fija de bytes indiferentemente de la arquitectura, como int16_t o int32_t respectivamente. La biblioteca estándar C define estos tipos en el encabezado <stdint.h>.

El paso seguido es hacer que la entrada y salida también se adapte a los tamaños fijos de los enteros. En C++ no hay que hacer cambio alguno, ya que su E/S es genérica, pero en C se usan constantes de formato definidas en el encabezado <inttypes.h>. Esas constantes tienen la forma SCNxN para lectura (scanf) y PRIxN para impresión (printf), donde x indica si es con signo (i) o sin signo (u), mientras que N indica la cantidad de bits. Por ejemplo, el siguiente programa de C usa un tipo de datos dependiente de la arquitectura (4 o 8 bytes):

unsigned long value = 0;
if (scanf("%lu", &value) == 1) {
  printf("value = %lu\n", value);
}

Si se quiere que el entero sea de 4 bytes sin signo, el mismo programa sería:

#include <stdint.h>
#include <inttypes.h>

uint32_t value = 0;
if (scanf("%" SCNu32, &value) == 1) {
  printf("value = %" PRIu32 "\n", value);
}

2.5.3. Estructuras de datos

La biblioteca estándar de C no tiene contenedores genéricos. Las personas programadoras normalmente los implementan de forma casera, o reutiliza código de terceros. Por ejemplo, un arreglo dinámico se puede implementar con realloc(), y colas simplemente enlazadas usando registros de memoria (struct) y punteros. En C estas estructuras no tienden a ser genéricas, sino estar "mezcladas" con los tipos de datos que almacenan. En los vídeos del taller de C++ a C se provee ejemplos de estos dos contenedores.

2.6. Pruebas

Asegúrese de verificar el funcionamiento de su programa con los casos de prueba que le puedan proveer los docentes. Sin embargo, es parte de su objetivo aprender a crearlos, pues es una responsabilidad de las personas profesionales en informática y no de sus clientes. Por eso se recomienda crear casos de prueba propios y no sólo depender de los provistos.

Los casos probablemente estarán clasificados en grupos de acuerdo a la cantidad de procesamiento que requieren. Puede agregar casos de prueba pequeños y medianos a control de versiones si gusta, pero no los casos de prueba grandes, en especial si ocupan más de 100kB.

El Makefile provisto permite probar con la orden make test su solución contra todos los casos de prueba que se encuentren en la subcarpeta tests/. El comando funcionará siempre y cuando los casos de prueba se encuentren como parejas de archivos numerados, por ejemplo input001.txt y output001.txt (así trabaja el Makefile reutilizable, no necesariamente podría coincidir con los requerimientos del problema que daba resolver). Para comparar la salida de su solución contra las salidas esperadas, debe primero instalar los programas comparadores. Esto se puede lograr en una distribución basada en Debian o RedHat con el comando sudo make instdeps.

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 pueden realizarlas herramientas de análisis dinámico de código como Valgrind y Google Sanitizers. El Makefile provisto provee acciones para facilitar el trabajo. La siguiente secuencia de comandos es solicitada comúnmente durante las revisiones de tareas y proyectos.

make clean asan test
make clean debug memcheck
make lint
make doc

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:

git tag -a tarea01 -m 'Entrega de la tarea01'
git push --tags

2.7. Optimización

Enfóquese primero en resolver el problema por corrección ("correctitud"), y por tanto, pasar los casos de prueba. Una vez que el problema esté resuelto, mida la duración de su solución con el caso de prueba más grande que disponga. Puede usar una máquina del laboratorio asignado para el curso. Por ejemplo:

cd repo/tareas/serial                    # Ir a la carpeta de la tarea01
make clean release                       # Generar un ejecutable optimizado
perf stat bin/serial tests/job020.txt    # Medir cuanto dura la solucion

El último comando del listado anterior le indicará la duración en segundos de correr el caso de prueba grande. Esta duración debe ser menor a 1 hora y en tal caso anótela en el archivo readme.adoc de la tarea. Si su solución tarda más de este tiempo, detenga el proceso (Ctrl+C), y modifique su código para incrementar la eficiencia de la solución. A modo de recomendación:

  1. Escoja un caso de prueba pequeño. Tome una hoja de papel. Rastree el algoritmo que implementó en su solución y trate de no brincarse pasos.

  2. Trate de determinar qué instrucciones o pasos son innecesarios para llegar a la solución y reducir la cantidad de procesamiento innecesario. Modifique su algoritmo.

  3. Implemente su nuevo algoritmo. Pruebe que pasa los casos de prueba pequeños y que tiene una duración menor.

  1. Repita la medición de tiempo en la máquina del laboratorio para determinar si supera o no el tiempo límite. Una vez que logre una duración inferior al límite, no continúe optimizando su código. En la tarea03 tendrá oportunidad de realizar más optimizaciones de forma sistemática.

2.8. Evaluación

  1. [5%] Buen uso de control de versiones (ej.: commits). Estructura de archivos y directorios. Ignorar archivos generados.

  2. [10%] Análisis (readme): Descripción del problema. Manual de usuario. Créditos.

  3. [20%] Diseño de la solución: Diagrama de memoria. Diagrama de UML. Pseudocódigo.

  4. [10%] Documentación de subrutinas y registros (doxygen) y algoritmos en los cuerpos de subrutinas.

  5. [30%] Implementación y corrección de los algoritmos y estructuras de datos (pasar los casos de prueba).

  6. [10%] Buen uso de la memoria y recursos (sanitizers).

  7. [15%] Modularización en subrutinas y archivos (.h, .c). Apego a una convención de estilos (cpplint).

3. Tarea02: pthread

Paralelice su programa en C usando Pthreads para que el procesamiento se haga de forma concurrente y logre incrementar la velocidad de respuesta. Esta tarea es una secuencia de la tarea01. Continúe el apego a las reglas de entrega de la tarea01.

3.1. Correcciones a la tarea anterior

Si no lo ha hecho, primero corrija su solución a la tarea01 en la carpeta tareas/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. Utilice issues de su sistema de control de versiones de la siguiente forma.

  1. Por cada observación que recibió durante la revisión (sea que las haya anotado o que visualice la grabación de la revisión), cree un issue en el sistema de alojamiento de control de versiones (ej.: git.ucr o github). Inicie el título del issue con el número de la tarea, por ejemplo "Tarea01: cambiar arreglo estático por dinámico". Describa en el issue el problema identificado. Note que cada issue recibe un número que lo identifica.

  2. Corrija un issue a la vez en su repositorio. Modifique los archivos y pruebe que pase los casos de prueba pequeños. Para cada corrección cree un commit y en el mensaje refiera el número del issue. Si es el último commit que resuelve el issue, ciérrelo desde el mensaje de commit. Por ejemplo, el mensaje:

    git commit -m 'Store results in dynamic array instead of a static one. Close #13'

    cerraría el issue identificado con 13. De esta forma el issue y el commit quedan ligados en el sistema de control de versiones y facilita la rastreabilidad.

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

3.2. Descripción del problema (Tarea02)

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

El programa concurrente recibirá los mismos datos en la entrada estándar y deberá imprimir los resultados 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 realizar su trabajo de forma concurrente, utilizando hilos que se reparten el trabajo, y por lo tanto, debe tener un incremento en el desempeño verificable.

Su programa concurrente debe permitir a la persona usuaria invocarlo con un argumento de línea de comandos adicional, que indica la cantidad de hilos de ejecución que realizarán el procesamiento. Si este número no se provee, se debe suponer la cantidad de núcleos (CPUs) disponibles en la máquina. Recuerde actualizar su readme.ext para indicar que su solución usa hilos, y quien lo usa puede proveer este argumento opcional.

3.3. Diseño concurrente

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 siempre que sea posible (conditionally safe).

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

  1. Resalte en su diagrama de la estructura de datos qué datos le corresponden a cada hilo de ejecución. Puede suponer por sencillez que dispone de dos hilos de ejecución. Use algún mecanismo visual, como colores o encerrar en rectángulos punteados, para indicar los datos que se encarga de procesar cada hilo.

  2. El diseño en pseudocódigo debe centrarse en la lógica concurrente (lo nuevo en esta tarea) y no los detalles algorítmicos utilizados para calcular los resultados (lo ya resuelto en la tarea01). Debe usar la misma notación de pseudocódigo que se ha usado en las lecciones del curso. Su pseudocódigo debe considerar la creación de estructuras de datos, lectura de datos, creación de hilos, e impresión de resultados. Los hilos secundarios se encargan de repartirse el trabajo en la estructura de datos. Los hilos invocarán subrutinas para encontrar los resultados que pueden estar definidas en otros archivos de pseudocódigo.

3.4. Implementación concurrente

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.

En esta versión no haga optimizaciones a los algoritmos que implemente, la tarea03 se encargará de ello. La versión concurrente debe implementar el mismo algoritmo 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 respecto a la duración de la ejecución serial que anotó en el readme.adoc con el caso de prueba grande. Recuerde, no agregue los casos de prueba grandes a control de versiones (por el contrario, puede incluirlos en su archivo .gitignore).

3.5. Pruebas

Asegúrese de verificar el funcionamiento de su programa con los casos de prueba. 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 revise el código con el linter (make lint).

3.6. Evaluación

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

  1. [5%] Buen uso del repositorio (commits, ignores, tags) y directorios.

  2. [5%] Análisis: agregar concurrencia al README.md.

  3. [15%] Diseño de la solución concurrente: diagrama de memoria y pseudocódigo.

  4. [5%] Documentación de interfaces (doxygen) e implementaciones (algoritmos).

  5. [30%] Implementación y corrección de la concurrencia (pasar los casos de prueba).

  6. [10%] Buen uso de la memoria (memcheck, asan, msan, ubsan).

  7. [10%] Buen uso de la concurrencia (helgrind, tsan).

  8. [10%] Incremento del desempeño con los casos de prueba.

  9. [10%] Modularización en subrutinas y archivos (.h, .c). Apego a una convención de estilos (cpplint).

4. Tarea03: optimized

Realice optimizaciones de su solución para incrementar el desempeño respecto a las versiones anteriores (serial y pthread). Es requerido proveer evidencia de este incremento con datos, gráficas, y su respectiva discusión textual, en un documento de reporte. Además estudie el rendimiento de su solución ante diferentes niveles de concurrencia.

En todas las optimizaciones es obligatorio seguir el método sugerido para optimizar. Este método es cíclico, y se deberá iterarlo hasta conseguir al menos tres optimizaciones que logren incrementar el desempeño de la solución. Al menos dos de estas optimizaciones deben ser concurrentes.

4.1. Correcciones a las tareas previas

Esta tarea es una secuencia de tarea01 y tarea02. Si no lo ha hecho, primero corrija su solución a la tarea anterior (tarea02) en la carpeta tareas/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 3.1.

Importante. Antes de copiar su tarea02 para la tarea03, asegúrese de que tanto la tarea01 como la tarea02 implementen el mismo algoritmo de la lógica del dominio. Es decir, el trabajo que realiza el hilo principal de la tarea01 y el trabajo que realizaría el hilo secundario 0 es exactamente el mismo si se corre la tarea02 con sólo un hilo secundario desde la línea de comandos. Este principio es necesario para que las comparaciones de rendimiento tengan validez estadística. Esto implica que si usted modificó/optimizó el algoritmo en la tarea02, debe actualizar la tarea01 también.

4.2. Documento de reporte

Cree la carpeta tareas/report/ en su repositorio de control de versiones. En la carpeta report cree un archivo readme.adoc. A este archivo se le referirá como documento de reporte. Puede tomar esta plantilla como punto de partida. Cree un enlace desde la tabla de tareas en el readme.adoc de su repositorio personal a su documento de reporte para que facilite la navegación. El documento de reporte tendrá cinco secciones con la siguiente estructura:

1. Optimizaciones seriales
   Tabla 1. Mediciones seriales
   Iteración 1. Título de la iteración
   ...
   Iteración N. Título de la iteración
2. Optimizaciones concurrentes
   Tabla 2. Mediciones concurrentes
   Iteración 1. Título de la iteración
   ...
   Iteración N. Título de la iteración
3. Comparación de optimizaciones
   Gráfico 1. Duraciones contra el incremento de velocidad
   Gráfico 2. Incremento de velocidad contra la eficiencia
4. Comparación del grado de concurrencia
   Gráfico 3. Comparación del grado de concurrencia
5. Comparación entre clústeres
   Tabla 3. Mediciones entre clústeres

En las dos primeras secciones creará tablas y explicaciones, y en las dos últimas secciones creará gráficas y discusiones. Por cada intento de optimización (iteración del ciclo de optimización) agregará una subsección en el documento. Esta subsección usted ayudará a la persona lectora a entender la optimización realizada, con un texto resumido (un párrafo), el diseño o el código fuente que explique la modificación pensada para incrementar el desempeño. Una vez medida la optimización, registre duraciones en una tabla de la sección, métricas de rendimiento (speedup y eficiencia), y una discusión de las lecciones aprendidas.

4.3. Tipos de optimizaciones

Usted debe realizar al menos tres optimizaciones, de las cuales al menos dos deben ser concurrentes:

Una optimización serial modifica el algoritmo que resuelve el problema y hace que el único hilo que lo ejecuta, el hilo principal, termine su trabajo más rápido. Los siguientes podrían ser ejemplos hipotéticos: quitar cálculos innecesarios en los ciclos o recursiones, reutilizar memoria en lugar de crearla y liberarla repetidamente, cambiar la estructura de datos por otra, almacenar resultados intermedios, entre muchas otras.

Una optimización concurrente afecta cómo trabajan los hilos o procesos de tal forma que la solución resuelva el problema en menos tiempo. Ejemplos podrían ser: evitar que hilos/procesos se queden sin trabajo mientras otros continúan, evitar crear y destruir hilos repetitivamente, disminuir el control de concurrencia con operaciones atómicas o seguridad condicional, entre muchas otras.

La tarea02 es en sí una optimización concurrente que ya usted realizó. Aparte de tarea02, idee al menos dos optimizaciones nuevas, y al menos una de las nuevas debe ser concurrente. Los siguientes podrían ser ejemplos de optimizaciones, siempre y cuando logren un incremento de velocidad:

  1. Una optimización serial.

  2. La paralización de la tarea02.

  3. El complemento del tipo de mapeo.

  4. Propuesta libre.

4.4. Optimizaciones seriales

En la primera sección de su documento de reporte, cree una tabla resumen como la siguiente al inicio de la sección "Optimizaciones seriales". Los valores en la siguiente tabla son ficticios con propósitos ilustrativos.

Iter. Etiqueta Duración (s) Speedup Descripción corta

-

Serial0

758.821081239

1.00

Versión serial inicial (Tarea01)

1

 — 

913.281827102

0.83

Aplastar matrices en arreglos

2

Serial1

688.282103853

1.10

No hacer cálculos innecesarios

La primera línea de la tabla debe ser su versión serial original de la Tarea01. La medición de su duración es importante, dado que será la línea base (baseline) para calcular los incrementos de velocidad de las optimizaciones seriales. En el paso 1 del método sugerido para optimizar, realice una medición de tiempo como se indica más adelante en la Section 4.7 usando su solución serial (en modo release) de la tarea01 con los casos de prueba grandes. Anote los resultados en la primera línea de la tabla. Se le llamará a esta medición Serial0 como lo indica la columna "Etiqueta" de la tabla. Redacte qué siente que está bien o al contrario, podría mejorarse en la subsección correspondiente.

Para cada optimización serial que quiera realizar, repita los pasos 2 a 7 del método sugerido para optimizar, como se indica a continuación.

  1. En el paso 2 realice un análisis dinámico de rendimiento (profiling). Ejecute su solución de la tarea01 con la herramienta callgrind con un caso de prueba pequeño o 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. Puede ser que su propuesta de optimización afecte las regiones de código críticas de rendimiento, lo cual es un buen indicio. Sino, la visualización puede ayudarle a ajustar la propuesta o idear una nueva.

  2. En el paso 3 y 4 documente resumidamente en un párrafo o menos, en qué consiste la optimización en su documento de reporte. Luego implemente en código la potencial mejora. Asegúrese de que la solución pasa los casos de prueba pequeños o medianos (en modo debug), no hace mal uso de la memoria ni otras malas (Sanitizers, Valgrind).

  3. En el paso 5, si puede haga tres corridas, pero dado que las versiones seriales pueden tardar tiempo significativo, al menos una es suficiente. Haga las mediciones siempre en la misma máquina, con los mismos casos de prueba, en modo release, y anote en la tabla la menor duración de las corridas. Estime el incremento de velocidad, del cual depende la acción a tomar:

    • Si logró incrementar el desempeño (\$\text{speedup}_i > \text{speedup}_{i-1}\$), llame a esta medición con la etiqueta \$\text{Serial}_i\$, donde \$i\$ corresponde al número de intento/iteración contando sólo las iteraciones que han logrado incrementar el desempeño. Importante: Actualice también el código fuente de la tarea02 para aplicar el algoritmo mejorado.

    • Si no logró incrementar el rendimiento (\$\text{speedup}_i \le \text{speedup}_{i-1}\$), conjeture en su discusión a qué se podría deber ese comportamiento y repita el ciclo de optimización a partir del paso 2. No nombre esta iteración con una etiqueta en la tabla resumen para ayudar a distinguirlas visualmente de las iteraciones que sí incrementaron el rendimiento.

Puede repetir el método sugerido para optimizar para crear más mejoras seriales. La última iteración que consiga un incremento de velocidad se le llamará Versión serial final y será usada como línea base para las optimizaciones concurrentes.

4.5. Optimizaciones concurrentes

En su documento de reporte, cree una tabla resumen como la siguiente al inicio de la sección "Optimizaciones concurrentes". Los valores en la siguiente tabla son ficticios con propósitos ilustrativos.

Iter. Etiqueta Duración (s) Speedup Eficiencia Descripción corta

-

Serial1

688.2821039

1.00

1.00

Versión serial final

1

Conc1

260.0088227

2.65

0.33

Versión concurrente inicial (Tarea02)

2

 — 

263.7898106

2.61

0.33

Barreras en lugar de join

3

Conc2

139.5902018

4.93

0.62

Mapeo dinámico

4

Conc3

89.84906109

7.66

0.96

Mapeo estático por bloque

La primera línea de la tabla debe ser su versión serial final. Su duración será la línea base (baseline) para calcular los incrementos de velocidad de las optimizaciones concurrentes. Simplemente copie los valores de la tabla serial a la tabla concurrente. Todas las mediciones concurrentes deben hacerse utilizando tantos hilos como núcleos de CPU hay disponibles en el sistema. Esta cantidad de hilos es una constante que requerirá para calcular la eficiencia.

Paralelizar una solución es ya una optimización. Por lo tanto, el trabajo realizado en la tarea02 es la primera optimización concurrente de paralelismo de datos. Etiquétela como Conc1 y mida su ejecución contra los casos de prueba grandes como se indica en la sección Section 4.7.

Luego calcule el incremento de velocidad y la eficiencia sobre la versión serial final. Para que esta comparación sea válida, la tarea02 debe implementar exactamente el mismo algoritmo solución que la versión serial final de la tarea01. Es decir, la única diferencia entre estas dos versiones debe ser la repartición del trabajo entre hilos. Si la tarea01 y la tarea02 implementan diferentes algoritmos, puede ocurrir que obtenga una eficiencia superior a 1.0, lo cual es conceptualmente incorrecto para una paralelización. Agregue sus resultados a la tabla resumen.

4.6. Mapeo estático y dinámico

Compare el efecto del mapeo estático contra el dinámico. Requerirá implementar el método complementario al que usó en la tarea02. Copie la carpeta tareas/pthread a tareas/optimized y haga un commit.

Si en la tarea02 usted realizó mapeo dinámico, escoja e implemente en tareas/optimized el mapeo estático que piense incrementará más el desempeño de su solución (por bloque, cíclico, o bloque-cíclico). Si en la tarea02 implementó mapeo estático, modifique el código fuente de tareas/optimized para implementar uno de los dos siguientes mapeos dinámicos:

  1. Mediante variables compartidas protegidas. Por ejemplo, un contador entero protegido por mutex puede indicar cuál es la próxima unidad de trabajo pendiente de realizar. El próximo hilo que obtenga el mutex, tomará esa unidad de trabajo, incrementará el contador, y trabajará en la unidad que consiguió.

  2. Mediante el patrón productor-consumidor. El hilo principal puede tomar el rol de productor de trabajo, y los hilos secundarios el rol de consumidores de trabajo. Recuerde que 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.

Siga los pasos 3 a 7 del método sugerido para optimizar para medir el efecto del mapeo complementario. El paso 3 corresponde a implementar este mapeo complementario, verificar los casos de prueba, buen uso recursos (Sanitizers y Valgrind), y la convención de estilo (linting). Las mediciones en el paso 5 debe realizarlas en el mismo ambiente de ejecución que las optimizaciones previas, con los mismos casos de prueba, tantos hilos como CPUs, y tomando la menor de tres corridas.

Registre sus resultados y agregue la línea correspondiente de la tabla resumen. Haga la discusión respectiva en el documento de reporte. Rotule el mapeo que consiguió el mayor incremento de desempeño. Puede realizar más optimizaciones concurrentes.

4.7. ¿Cómo medir el tiempo de ejecución?

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) con los casos de prueba pequeños y medianos. Recuerde también mantener la convención de estilos (make lint).

Para todas las mediciones de rendimiento use los casos de prueba grandes, en una máquina del clúster para el curso. Consulte la cantidad de núcleos de la máquina de ejecución en la documentación del clúster (ej.: guía de uso de Poás) o con el comando lscpu de Linux. 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 (almacénela en tareas/report/).

Si su solución (el código fuente en C) no reporta el tiempo de ejecución con precisión de nanosegundos, use la herramienta perf. Esta herramienta se usa antecedida a su comando, por ejemplo perf stat tareas/optimized tests/job020.txt.

Para cada medición concurrente realice tres corridas y tome la menor de ellas. Para la medición serial basta una corrida. Todas las ejecuciones deben realizarse en el mismo ambiente de ejecución y con un ejecutable release de su solución. Recuerde que en el clúster puede usar el sistema de colas para correr su solución independientemente en tres máquinas en paralelo.

4.8. Comparación de optimizaciones

Suponga usted va a comunicar los resultados de sus optimizaciones en un documento científico o en una presentación a una junta de la gerencia. Una forma eficiente y eficaz de comunicar sus aportes es mediante gráficas. Elabore dos gráficas. Una para comparar las duraciones contra el incremento de velocidad, y otra para comparar el incremento de velocidad contra la eficiencia. Necesitará acopiar los siguientes datos:

Versión Descripción

SerialI

La versión serial inicial (Tarea01)

SerialF

La versión serial final (reemplace F por el número de iteración)

Conc1

La versión concurrente inicial (Tarea02)

ConcI

Cada optimización concurrente que logró incrementar el desempeño (reemplace I por el número de iteración)

Puede cambiar las etiquetas, en especial las ConcI, por nombres más significativos, como static_map, dynamic_map, que ayuden rápidamente a identificar las optimizaciones en el gráfico. Para cada una de las versiones anteriores necesitará su duración en segundos, su incremento de velocidad, y su eficiencia (para las versiones seriales, la eficiencia es 1.0).

El Gráfico 1, de duraciones contra el incremento de velocidad, permitirá comparar la evolución del software, para determinar cuáles versiones duraron menos y aportaron más al incremento del desempeño. En el eje X muestre la versión del programa, correspondiente a la columna "Versión" de la tabla anterior (SerialI, SerialF, Conc1, …​). El gráfico debe ser combinado, con dos ejes Y, ambos deben estar rotulados e indicar sus unidades:

  1. En el eje Y primario, a la izquierda del gráfico, ubique la duración de las mediciones en segundos. Este debe ser el eje de referencia para serie de mediciones de tiempo. Su etiqueta puede ser "Duración (s)".

  2. En el eje Y secundario, a la derecha del gráfico, indique 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.

El gráfico tendrá dos series, una para la duración y otra para el incremento de velocidad (speedup). Distinga visualmente las series tanto con colores como patrones. Por ejemplo, puede usar líneas continuas para las duraciones y punteadas para los incrementos de velocidad.

El Gráfico 2, de incremento de velocidad contra la eficiencia, permitirá comparar qué tan eficiente fue el uso de recursos para alcanzar mayores tasas de incremento de velocidad. Tiene las mismas características del gráfico anterior, excepto que en el eje Y primario ubique la eficiencia en lugar de la duración. La eficiencia no tiene unidades pero puede considerarse como un porcentaje. Para efectos de presentación puede multiplicarla por 100 y reportarla como "Eficiencia (%)".

Incruste ambos gráficos, en formato SVG (preferible) o PNG, a la sección Comparación de optimizaciones de su documento de reporte. Agregue un título (caption) a cada gráfico. Haga una discusión de un párrafo (o máximo 500 palabras) para cada gráfico. Piense esta discusión como si explicara sus hallazgos a otra persona. De hecho, una excelente manera es efectivamente explicar a otra persona, grabarse, y luego transcribir su exposición de forma resumida. Puede también explicar como contando una historia, algo como "Yo inicié con un software serial (SerialI) que con datos grandes tardaba \$h_1\$ horas. Luego lo modifiqué para que no hiciera cálculos innecesarios y logré que durara \$h_2\$ horas…​". Concluya resaltando la versión de su solución qué produjo el mayor incremento de desempeño.

4.9. Comparación del grado de concurrencia

En esta sección trate de responder una pregunta científica ¿afecta el grado de concurrencia en el desempeño y eficiencia de una solución de software? Para responderla, mida su solución concurrente final contra diferentes niveles de concurrencia.

Todas las mediciones han de ser comparables, por tanto, deben realizarse en el mismo ambiente de ejecución, 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 Poás, C equivale a 4 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 18 ejecuciones de sus programas. En la última columna de la siguiente tabla se muestra, a modo de ejemplo, la cantidad de hilos para un nodo esclavo del clúster Poás.

# Etiqueta Descripción Hilos

1*

S

Versión serial final

1

2

1

Un solo hilo

1

3

hC

Tantos hilos como la mitad de CPUs hay en la computadora que ejecuta el programa

2

4*

1C

Tantos hilos como CPUs hay en la computadora que ejecuta el programa

4

5

2C

Dos hilos por cada CPU que hay en la computadora que ejecuta el programa

8

6

4C

Cuatro hilos por cada CPU que hay en la computadora que ejecuta el programa

16

7

D

Tantos hilos de ejecución como el mínimo entre: (a) las unidades de descomposición hay en la entrada, y (b) la cantidad máxima de hilos permitida por el sistema operativo (~32000)

D

La mediciones marcadas con asterisco en la tabla anterior, ya las realizó en la comparación de optimizaciones de la sección anterior. La medición 1 (con etiqueta S) corresponde a la versión serial final y la medición 4 (etiqueta 1C) corresponde a la versión concurrente final. Las demás requieren mediciones nuevas, pero todas con la versión concurrente final.

La medición 1 en la tabla (con etiqueta 1) corresponde a medir la versión concurrente final con un único hilo de ejecución. Basta con una única ejecución. Las restantes seis mediciones deben realizarse con la versión concurrente final de su carpeta optimized, con al menos dos ejecuciones de los casos de prueba grandes. 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. Anote la menor de las ejecuciones en su hoja de cálculo.

Una vez que tenga cada medición calcule el incremento de velocidad (speedup) y la eficiencia respecto a la versión serial final (con etiqueta S). Cree un tercer gráfico en el documento, que permita comparar como se afecta el incremento de velocidad y la eficiencia del uso de recursos a diferentes niveles de concurrencia. En el eje X indique la cantidad de hilos que realizaron los cálculos durante la ejecución del programa, correspondiente a la columna "Etiqueta" de la tabla (S, 1, hC, 1C, 2C, 4C y D). El gráfico debe ser combinado con dos ejes Y:

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

  2. El eje Y secundario, a la derecha del gráfico, indica la eficiencia obtenida por cada nivel de concurrencia.

Distinga visualmente las series de speedup de las de eficiencia con colores y formas. Por ejemplo, puede usar líneas continuas para las primeras y punteadas para las segundas.

Incruste el gráfico en formato SVG (preferible) o PNG a su documento de reporte. Provea una discusión 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.

4.10. Evaluación

  1. [20%] Primera optimización (ej.: serial, mapeo complementario u otra): Implementación y corrección. Pasar los casos de prueba y obtener incremento de desempeño.

  2. [20%] Segunda optimización (ej.: propuesta libre): Implementación y corrección. Pasar los casos de prueba y obtener incremento de desempeño.

  3. [10%] Documentación en el reporte de las iteraciones realizadas siguiendo el método sugerido para optimizar (al menos las dos optimizaciones anteriores) que incluye: diseño de la optimización, speedup/eficiencia antes y después, y lecciones aprendidas.

  4. [15%] Comparación de optimizaciones: Hoja de cálculo con las mediciones, incrementos de velocidad, eficiencia, y gráficos combinados. Discusión de resultados y gráficos en el documento de reporte.

  5. [15%] Comparación del grado de concurrencia: Hoja de cálculo con las mediciones, incrementos de velocidad, eficiencia, y gráficos combinados. Discusión de resultados y gráficos en el documento de reporte.

  6. [10%] Buen uso de la memoria (memcheck, asan, msan, ubsan) y la concurrencia (helgrind, tsan).

  7. [5%] Documentación de interfaces (doxygen) e implementaciones (algoritmos).

  8. [5%] Apego a una convención de estilos (cpplint). Modularización en subrutinas y archivos (.h, .c). Buen uso del repositorio (commits, ignores, tags) y directorios, como se ha indicado en tareas anteriores.

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.

5. Tarea04: omp_mpi

En las tareas anteriores usted escribió programas que reciben los datos y calculan resultados de forma serial (tarea01), concurrente con Pthreads (tarea02), y comparó el rendimiento entre ellas (tarea03). Estas soluciones aprovechan los recursos concurrentes de una única máquina, pero no escalan, no aprovechan varias computadoras disponibles en una organización o un clúster de computadoras.

En esta tarea su objetivo es evaluar una tecnología declarativa y distribuir el trabajo entre varias máquinas usando dos tecnologías: OpenMP y MPI. Su programa recibirá datos en el mismo formato que las tareas previas, y deberá producir los resultados en el mismo orden, de tal forma que pase los casos de prueba.

5.1. Correcciones a la Tarea03

Si no lo ha hecho, primero corrija su solución a la tarea03 en la carpeta tareas/optimized/ (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 3.1.

5.2. Concurrencia declarativa

Una vez concluidas las correcciones a la tarea03, copie su solución concurrente tareas/optimized a la carpeta tareas/omp_mpi en su repositorio de control de versiones.

Reemplace la concurrencia imperativa implementada con hilos de ejecución de Pthreads, por concurrencia declarativa provista por la tecnología de paralelismo de datos OpenMP. Asegúrese de que su implementación con OpenMP pase los casos de prueba, y no genera diagnósticos del linter. Es probable que herramientas de análisis dinámico de código (Google Sanitizers o Valgrind) no funcionen con OpenMP debido a incompatibilidad entre las bibliotecas (a menos de que se recompile la biblioteca de OpenMP con instrumentalización).

Al igual que las tareas previas, 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).

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

5.3. Optimización declarativa OpenMP

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 en la versión release.

Calcule el incremento de velocidad (speedup) y la eficiencia respecto a la versión serial final. Para que esta comparación sea válida, el algoritmo que realizan los hilos de ejecución con OpenMP debe ser exactamente el mismo algoritmo del dominio del problema que realiza el hilo principal en la versión serial final.

En la sección de Comparación de optimizaciones de su documento de reporte (en la carpeta tareas/report/), agregue este resultado como una fila más de la Tabla 1, y a los gráficos 1 y 2, con el identificador omp en el eje-X. Agregue en esta sección un párrafo que compare los resultados de la concurrencia declarativa (OpenMP) contra la concurrencia imperativa (Pthreads).

5.4. Distribución de procesamiento

Para hacer su solución escalable y aprovechar un clúster de computadoras, distribuya el trabajo utilizando la tecnología MPI. Tome en consideración si su programa lee datos de la entrada estándar, esta tecnología 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 concurrencia con OpenMP. Implemente un mapeo dinámico usando paso de mensajes para repartir las unidades de trabajo entre los procesos, 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. Es poco probable que las herramientas de análisis dinámico de código funcionen adecuadamente con MPI.

5.5. Optimización distribuida MPI

Compare el rendimiento de su solución distribuida con los casos de prueba grandes que usó en la tarea03. Para estas mediciones con MPI es necesario usar un ambiente distribuido, es decir, el clúster designado para el curso (Poás). Haga dos mediciones distribuidas:

  1. Distribución pura (con identificador MpiP): Cree tantos procesos como CPUs hayan disponibles en el clúster, y en cada proceso un único hilo. Es decir, si en una máquina hay 4 CPUs, se crearán 4 procesos. Use todas las máquinas esclavas del clúster.

  2. Distribución híbrida (con identificador MpiH): Cree tantos procesos como nodos esclavos hayan en el clúster, y en cada proceso tantos hilos como CPUs hayan disponibles en el nodo. Es decir, si en una máquina hay 4 CPUs, correrá en ella un único proceso con 4 hilos.

Mida la duración de las versiones distribuidas, calcule los incrementos de velocidad y las eficiencias respecto a la versión serial final. Agregue los resultados a la Tabla 2 y a los gráficos 1 y 2 en la sección Comparación de optimizaciones en su documento de reporte, usando los identificadores anteriores. De esta forma el eje-x permite comparar las soluciones distribuidas (MpiP y MpiH) con las versiones previas (OpenMP, Pthreads, serial). Agregue a su discusión un párrafo con el análisis de los hallazgos que obtuvo con las versiones distribuidas.

5.6. Comparación en segundo clúster

Repita la medición de la versión serial final (SerialF) y de la versión distribuida que logró el mejor desempeño (MpiP o MpiH) en otro clúster a elección de cada estudiante. Puede ser el clúster institucional de la UCR o el clúster Kabré del Centro Nacional de Alta Tecnología (CeNAT).

Agregue una sección Comparación entre clústeres en su documento de reporte, donde incluya las tres mediciones obtenidas en el segundo clúster en una Tabla 3. Compare los resultados con los del primer clúster. ¿Son similares o distintas las métricas de incremento de desempeño y eficiencia respecto al clúster del curso (Poás)? Discuta las posibles razones de similitud o diferencias observadas entre los clústeres.

5.7. Evaluación

  1. [20%] Concurrencia declarativa (OpenMP): Implementación y corrección. Pasar los casos de prueba y obtener incremento de desempeño respecto de su versión serial.

  2. [20%] Distribución: Implementación y corrección. Pasar los casos de prueba y obtener incremento de desempeño respecto de la versión no distribuida.

  3. [20%] Mapeo dinámico de la carga de trabajo usando paso de mensajes.

  4. [10%] Comparación declarativa OpenMP: Hoja de cálculo con las mediciones. Documento de reporte con incrementos de velocidad, eficiencia, y gráfico combinado. Coherencia de la discusión de resultados y el correspondiente gráfico.

  5. [20%] Comparaciones distribuidas MPI: Hoja de cálculo con las mediciones de los dos tipos de distribución. Documento de reporte con incrementos de velocidad, eficiencias, y gráficos combinados. Coherencia de la discusión de resultados y el correspondiene gráfico. Comparación entre dos clústeres.

  6. [5%] Documentación de interfaces (doxygen) e implementaciones (algoritmos).

  7. [5%] Apego a una convención de estilos (cpplint). Modularización en subrutinas y archivos (.h, .c). Buen uso del repositorio (commits, ignores, tags) y directorios, como se ha indicado en tareas anteriores.

6. Tarea05: mem_distr

6.1. Distribución de memoria

En la tarea04 usted distribuyó el procesamiento entre varias máquinas usando paso de mensajes. Sin embargo, no todos los problemas de paralelismo de datos giran en torno al procesamiento y al incremento del desempeño. En algunos de ellos, el problema radica en que la cantidad de memoria principal requerida es tanta que las estructuras de datos no caben en la RAM de una única máquina, pero sí si se distribuye entre la memoria principal de varias máquinas. En este contexto el objetivo no es lograr un incremento del desempeño, sino en simplemente lograr que la solución se logre ejecutar con estas limitaciones de memoria.

Intente correr su solución actual con el caso de prueba job030.txt disponible en el clúster asignado para el curso. Es probable que obtenga un error de ejecución por falta de memoria principal libre. Su objetivo en la tarea05 es mejorar su solución para ejecutar simulaciones de calor con matrices que superen la capacidad de memoria de una sola máquina.

Primero corrija las anomalías que pueda tener pendientes de la tarea04, tal como se indica en Section 3.1. Luego copie la carpeta tareas/omp_mpi a tareas/mem_distr en su repositorio personal de control de versiones.

6.2. Evaluación

A diferencia de la tarea04, la tarea05 siempre va a suponer que las láminas no caben en la memoria principal de una máquina. Todos los procesos del equipo trabajarán en paralelo en la misma lámina, una a la vez, hasta terminar el archivo de trabajo. Cada proceso se encargará de una parte de la lámina. Es decir, usted deberá ajustar su solución para que:

  1. [10%] El documento de análisis indique las capacidades de la solución. Los artefactos de diseño señalan la distribución de memoria entre procesos e hilos. El pseudocódigo (o autómtatas de estados finitos) indican el paso de mensajes necesario para resolver el problema.

  2. [20%] Los procesos realicen las simulaciones del archivo de trabajo de forma coordinada y paralela. Su solución debe generar los resultados correctos y pasar los casos de prueba. Debe generar el reporte y los archivos de lámina correspondientes de forma correcta. Compara el rendimiento con la versión de distribución de procesamiento (sección Section 6.3).

  3. [10%] Decidir una unidad de descomposición y un algoritmo que mapee regiones de la lámina entre los procesos que actualizarán esas regiones, de tal manera, que el trabajo sea el más equitativo posible.

  4. [10%] Usar una distribución híbrida, de tal forma que la actualización de la región de la lámina que le corresponde a un proceso no la realice únicamente el hilo principal, sino un equipo de hilos que trabajen de forma balanceada.

  5. [20%] Dado que la memoria principal es el recurso crítico, cada proceso debe crear la cantidad mínima de memoria necesaria para su parte de la lámina. Esto implica que cada proceso deberá estudiar el archivo binario de lámina, y cargar de éste sólo la parte que le corresponde. Si aún no es posible cargar su parte de la lámina, el proceso debe finalizar con un mensaje de error que ayude a la persona usuaria a encontrar un ambiente de ejecución que logre soportar la carga.

  6. [20%] Dado que cada proceso sólo conoce una parte de la lámina, pero depende de regiones vecinas, debe idear el paso de mensajes mínimo entre procesos para que puedan realizar cada actualización de la simulación. De igual forma, la sincronización entre procesos para saber cuándo pasar a la siguiente actualización de la lámina, o pasar a la siguiente simulación.

  7. [10%] Buen uso del repositorio de control de versiones. Modularización en archivos y subrutinas. Documentación de interfaces (doxygen) y de implementaciones. Apego a una convención de estilos (cpplint).

6.3. Distribución de memoria vs procesamiento

La solución que distribuye memoria debería ser capaz de realizar simulaciones de forma correcta aunque las láminas quepan en la memoria principal de la máquina donde se ejecutan. Sin embargo, hay un pulso de fuerzas sobre el comportamiento esperado. Por una parte, se esperaría que su rendimiento decaiga debido al incremento en el paso de mensajes entre procesos. Por otra parte, el rendimiento podría incrementar dado que la unidad de descomposición es más fina. Verifique empíricamente cuál de las dos hipótesis se cumple con los datos de prueba usados para medir las soluciones.

Mida el tiempo de ejecución de su solución a la tarea05 con los casos de prueba grandes usados en la tarea04. Agregue una línea a la Tabla 2 y a los gráficos 1 y 2 con los resultados obtenidos, identificados como MpiM. Agregue a la discusión u párrafo de interpretación del rendimiento observado de la versión que distribuye memoria respecto a la versión que distribuye procesamiento.