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

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:

  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:

// Return parameter text must have at least 48 chars (YYYY/MM/DD hh:mm:ss)
char* format_time(const time_t seconds, char* text, const size_t capacity) {
  const std::tm* gmt = gmtime(&seconds);
  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 interesados 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 siempre 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/proy02
mkdir output
cd output
../bin/proy02 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. 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.

  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.

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.

Referencias

2. Tarea01: serial

Todas las tareas son estrictamente individuales. Se entrega en su repositorio de control de versiones personal.

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 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 todos quieren trabajar.

2.1. Entregables

En su repositorio individual cree una carpeta tareas (o en inglés, homeworks). 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 construir, probar y otras tareas con la solución. Incluye 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

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.

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, agréguelos al .gitignore en la raíz de su repositorio.

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

  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, crea 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 una vez que la matriz 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 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 ("comprender el bosque"). 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, 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 una búsqueda se realiza en forma líneal 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
 @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 cualquiera de las formas permitidas por Doxygen, pero trate de mantener 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 traumante 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 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 cppcheck 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, rómpala 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 son 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 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 la 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 (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 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 puede 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 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 todos los casos de prueba medianos en una máquina del clúster de pruebas designado para el curso. Por ejemplo, si es un nodo esclavo del clúster arenal, los siguientes comandos mostrarían cómo puede realizar esta tarea. Los comentarios a la derecha no debe escribirlos.

ssh CARNET@arenal.ecci.ucr.ac.cr            # Conectarse al cluster
git clone url_mi_repositorio                # Solo la primera vez, o
git pull --rebase                           # Si ya tiene uno
cd mi_repositorio/tareas/programa_a_medir   # Ir a la tarea01 en el nodo master
make clean release                          # Generar un ejecutable optimizado

ssh compute-0-N                             # Login en la maquina esclava
cd mi_repositorio/tareas/programa_a_medir   # Ir a la tarea01 en el nodo esclavo
top                                         # Revise no hayan otros corriendo pruebas
perf stat make test TST_DIR=tests_medium    # Medir cuanto dura la solucion

Los nodos esclavos de arenal están identificados de la forma compute-0-N, donde N es un entero entre 0 y 3. Escoja al azar una de las máquinas y antes de ejecutar las mediciones asegúrese de que nadie más está corriendo tareas pesadas. Puede usar el comando top que es un monitor de procesos para saber el consumo de CPU en esa máquina. Si alguien está usando toda la capacidad deCPU de la máquina, cambie a otra.

El último comando de la lista anterior le indicará la duración en segundos de correr todos los casos de prueba. Esta duración debe ser menor a 1 hora. 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 encontrar 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 en su máquina local y que tiene una duración menor.

  4. Repita la medición de tiempo en la máquina esclava en el clúster 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 una optimización serial 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

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

  • Descripción del problema

  • Entregables

  • Análisis

  • Documentación

Para esta tarea paralelice su programa en C usando Pthreads para que el procesamiento se haga de forma concurrente.

3.1. Correcciones a la 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. Recuerde utilizar 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 puntualmente. Note que cada issue recibe un número que lo identifica.

  2. Corrija un issue a la vez en su repositorio. Modifique los archivos que necesite directamente (no cree una copia de carpeta). 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 número provisto como argumento de línea de comandos, el cual 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 (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 para indicar como colores o encerrar en rectángulos punteados, los datos que se encarga 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 (pseudocódigo).

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

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 pruebe el código con el linter (make lint).

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

make clean asan test
make clean tsan test

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

4.1. Correcciones a las tareas previas

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

Si no lo ha hecho, primero corrija su solución a la tarea anterior (tarea02) en la carpeta tareas/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

Una vez concluidas las correcciones a la tarea02 (y potencialmente tarea01), cree la carpeta tareas/optimized en su repositorio de control de versiones y dentro una carpeta tareas/optimized/report/. En la carpeta report cree un archivo readme.adoc (puede usar otros formatos de documento, pero no se recomiendan formatos minimalistas como Markdown). A este archivo se le referirá como documento de reporte. Puede usar esta plantilla en notación AsciiDoc como punto de partida.

El documento de reporte tendrá cuatro secciones: Optimizaciones seriales, Optimizaciones concurrentes, Comparación de optimizaciones, y _Comparación del grado de concurrencia. En las dos primeras creará tablas y explicaciones, y en las dos últimas creará gráficas y discusiones.

Por cada intento de optimización (iteración del ciclo de optimización) agregará una línea resumen en la tabla y una subsección en el documento. Esta subsección usted ayudará 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 que piensa incrementará el desempeño. Una vez medida la optimización, registre su duración en la tabla, el rendimiento (speedup y eficiencia), y una discusión de las lecciones aprendidas.

4.3. Tipos de optimizaciones

Usted debe realizar al menos tres optimizaciones. Estas optimizaciones pueden clasificarse en seriales o 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 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.

4.4. Optimizaciones seriales

En su documento de reporte, si no la tiene ya, 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 recuerde siempre hacer tres corridas, es decir: en la misma máquina, con los mismos casos de prueba, y tomar la menor duración de tres corridas (en modo release). Anote los tres resultados en la hoja de cálculo, y el mejor resultado en la tabla. 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, si no la tiene ya, 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. 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. Asegúrese de que su tarea02 pasa los casos de prueba pequeños, hace buen uso de la de memoria, y mantener las convenciones de estilo. 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. Recuerde correr su tarea02 con tantos hilos de ejecución como CPUs tenga disponible su sistema contra los casos de prueba pequeños o medianos y en la versión release.

Luego calcule el incremento de velocidad y la eficiencia. 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 hoja de cálculo y 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. Una vez que haya medido la tarea02, copie su carpeta tareas/pthread en tareas/optimized con cuidado de no eliminar el documento de reporte. Nota: Si después de realizar esta copia hace una optimización serial, debe actualizar las tres carpetas de sus tareas.

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 la misma máquina que las optimizaciones previas, con los mismos casos de prueba, tantos hilos como CPUs, y tomando la menor de tres corridas.

Registre sus resultados en su hoja de cálculo, y 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. Recuerde que aparte de la tarea02, debe conseguir otra optimización de esta naturaleza.

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) junto 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 todos los casos de prueba grandes, en una máquina con al menos 8 núcleos de CPU. Puede consultar la cantidad de núcleos de su máquina con el comando lscpu de Linux. Si no dispone de un equipo con estas características, use un nodo esclavo (y no la máquina máster) del clúster asignado para el curso, o una máquina del laboratorio de computadoras para el curso. Anote los resultados en una hoja de cálculo que le facilite realizar las comparaciones. Puede usar la hoja de cálculo modelo como punto de partida.

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. Si lo necesita, puede instalarla con el paquete linux-perf en Debian o perf en RedHat. En Debian requiere permisos de administración para permitir a perf inspeccionar a otros programas. Puede disminuir el nivel de seguridad para correrlo como usuario normal con sudo echo 1 > /proc/sys/kernel/perf_event_paranoid y reiniciar el sistema operativo. Para obtener la duración de todos los casos de prueba puede ejecutar perf stat make test 'ARGS=8' TST_DIR=tests_large donde 8 indica la cantidad de hilos de ejecución entre otros argumentos que pueda necesitar.

Si es posible, 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 tipo de máquina y con un ejecutable release de su solución. Si usa un clúster, debe ser en un nodo esclavo y no la máquina máster. Los siguientes comandos ejemplifican cómo medir en un nodo esclavo, identificado con el número N entre 0 y 3, del clúster Arenal:

ssh CARNET@arenal.ecci.ucr.ac.cr
git clone url_mi_repositorio                # Solo la primera vez
git pull --rebase                           # Si hizo cambios
cd mi_repositorio/tareas/programa_a_medir
make clean && make release -j8

ssh compute-0-N
cd mi_repositorio/tareas/programa_a_medir
nohup perf stat make test 'ARGS=8' TST_DIR=tests_large > large1.txt &
less nohup.out  # Tomar la menor de las tres duraciones anteriores

El programa nohup hace que el comando que le sigue sea ejecutado en segundo plano, y no se detenga si se cierra su conexión con la máquina remota, por ejemplo, por inactividad o un error de red. La salida que un programa genere es redirigida con el operador > al archivo large1.txt, que significa la primera medición de los casos de prueba grandes. Si la salida no es redirigida manualmente, es concatenada al archivo nohup.out. Usted puede cerrar la sesión, regresar una hora después y consultar la salida contenida en el archivo large1.txt o nohup.out (ej.: less large1.txt). Los comandos anteriores puede repetirlos en otros dos nodos esclavos para así alcanzar las 3 mediciones y tomar la menor de ellas para sus análisis.

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

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

4.8. Comparación de optimizaciones

Suponga usted va a comunicar los resultados de sus optimizaciones en un documento científico a 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, suponga 1.0).

El primer gráfico 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. El eje Y primario, ubicado 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. 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.

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 segundo gráfico 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 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 la misma máquina, con los casos de prueba grandes, y tomar la menor duración de tres corridas. Lo que varía en cada medición es la cantidad de hilos de ejecución, obtenidas en función de la constante C definida como la cantidad de núcleos de procesador disponibles en un sistema. Por ejemplo, para un nodo esclavo del clúster Arenal, C equivale a 8 núcleos.

Para realizar las comparaciones, se usarán 6 niveles de concurrencia en función de C, es decir, usted registrará en su hoja de cálculo 6 mediciones de la duración de sus programas, listadas en la tabla a continuación. Dado que para lograr una medición más fiable, debe ejecutar su programa al menos tres veces y tomar la duración de menor duración, en total realizará alrededor de 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 Arenal.

# 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

4

4*

1C

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

8

5

2C

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

16

6

4C

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

32

7

D

Tantos hilos como unidades de descomposición hay en la entrada (en caso de que sea menor que la cantidad máxima de hilos permitida por el sistema operativo)

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. Si no pudiera realizarla, puede suponer es igual a la medición con etiqueta S, y reportarlo en su documento.

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 o quizá make test ARGS=#. Anote la menor de las tres (o más) ejecuciones en su hoja de cálculo.

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

Cree un gráfico 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 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%] Optimización 1 (propuesta libre): Implementación y corrección. Pasar los casos de prueba y obtener incremento de desempeño.

  2. [20%] Optimización 3 (mapeo dinámico): 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, ni 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 Pthreads, por concurrencia declarativa provista por la tecnología de paralelismo de datos OpenMP, para paralelizar el trabajo. 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 no funcionen con esta tecnología con las bibliotecas pre-incluidas con los compiladores, como Google Sanitizers o Valgrind.

Al igual que las taraes 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).

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. Comparación Pthreads-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 (tarea01) 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 de la tarea01.

Agregue este resultado al gráfico combinado de la Comparación de optimizaciones con el identificador omp en el eje-X. Agregue al documento de reporte un párrafo que compare los resultados de la concurrencia declarativa (OpenMP) contra la concurrencia imperativa (Pthreads).

5.4. Distribución

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 debe leer datos de la entrada estándar pues 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 o hilos, de tal forma que los recursos del clúster se aprovechen lo más equitativamente posible.

Asegúrese en su máquina local de que su solución distribuida con MPI pase los casos de prueba pequeños y medianos usando distintas cantidades de procesos e hilos. Además su implementación no debe generar diagnósticos del linter. Es poco probable que las herramientas de análisis dinámico de código funcionen adecuadamente con MPI.

5.5. Comparación OpenMP-MPI

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

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

Note
 Si realizó las mediciones de rendimiento de la tarea03 en una máquina distinta a la del clúster de la tarea04, haga nuevas mediciones en el clúster de al menos las versiones: optimized, openmp, y mpi. Cree nuevos gráficos y una sección "Comparación de rendimiento distribuido" en su reporte, en lugar de agregar mediciones no comparables a las secciones y gráficos hechos en tareas previas.

5.6. Evaluación

  1. [20%] Concurrencia declarativa: 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. [15%] Comparación Pthreads-OpenMP: Hoja de cálculo con las mediciones, incrementos de velocidad, eficiencia, y gráfico combinado. Coherencia de la discusión de resultados y el correspondiene gráfico.

  5. [15%] Comparación OpenMP-MPI: Hoja de cálculo con las mediciones, incrementos de velocidad, eficiencia, y gráfico combinado. Coherencia de la discusión de resultados y el correspondiene gráfico.

  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.

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.

6. Tarea05: roundabout_sync

En esta tarea usted usará mecanismos de sincronización vistos en el curso para resolver un problema de concurrencia de tareas.

6.1. Simulación de rotonda

Simule el tráfico en una rotonda con entradas y salidas en los cuatro puntos cardinales (Figura 3), la cual es transitada por vehículos que corresponden a hilos de ejecución. El reto es que la simulación refleje un comportamiento correcto y realista, donde los vehículos logran circular desde su punto de entrada hasta su punto de salida sin colisionar.

roundabout problem
Figura 3. Visualización de la rotonda

La simulación recibe en la entrada estándar un entero que indica la capacidad de cada uno de los cuatro segmentos de la rotonda. Un segmento es un tramo circular que inicia en una entrada de la rotonda y termina en la próxima salida de la rotonda. En el ejemplo de entrada 1, la capacidad de segmento es de 2, lo cual significa que en cada uno de los cuatro segmentos de la rotonda sólo caben a lo sumo dos vehículos al mismo tiempo sin colisionar. Si en esta rotonda hubiere en un momento tres o más vehículos en el tramo, es porque habría ocurrido una colisión. Nótese que la capacidad total de la rotonda es la suma de la capacidad de cada uno de sus cuatro segmentos.

Después de la capacidad del segmento, la simulación recibe un par ordenado de letras por cada vehículo. La primera letra indica el punto cardinal por el que ingresa el vehículo a la rotonda, y la segunda letra indica la dirección a la que se dirige, es decir, el punto cardinal por donde saldrá de la rotonda. Por ejemplo, SO corresponde a un vehículo que ingresa por la entrada sur y se dirige hacia la salida oeste tras realizar un giro de 270 grados en dirección antihorario.

Ejemplo de entrada 1
2

EO
SE
NN
ON

La simulación debe obligatoriamente crear un hilo de ejecución por cada vehículo en la entrada estándar. Los vehículos deben obligatoriamente respetar las capacidades de los segmentos, de tal forma que nunca ocurran accidentes de tránsito. Dado que no existirán accidentes en la simulación, todos los vehículos deben poder hacer su recorrido satisfactoriamente. Su simulación no puede serializar a los vehículos ni permitir que estos entren en un bloqueo mutuo, una condición de carrera, u otras anomalías.

Para confirmar que cada vehículo realiza el recorrido correcto, debe guardar su trayectoria a través de cada segmento de la rotonda, es decir, el punto cardinal cuando ingresa a la rotonda, cada punto cardinal que logra pasar dentro de la rotonda, y finalmente el punto cardinal cuando sale de la rotonda. Una vez que la simulación haya finalizado, es decir, todos los vehículos de la entrada hayan hecho su recorrido, la simulación debe imprimir los recorridos de los vehículos en la salida estándar, de forma enumerada y en el mismo orden en fueron ingresados en la entrada estándar. Para el ejemplo de entrada 1, la salida esperada sería la siguiente.

Ejemplo de salida 1
1 EO: E N O
2 SE: S E
3 NN: N O S E N
4 ON: O S E N

En la vida real quienes conducen hacen sus recorridos a distintas velocidades. Para reflejar este fenómeno permita que la simulación reciba dos argumentos de línea de comandos, que indican la cantidad mínima y máxima en milisegundos que un vehículo tarda en recorrer un segmento de la rotonda. Cada vez que un vehículo inicia el recorrido de un tramo, genera un número pseudoaleatorio en este rango y duerme esta cantidad de milisegundos representando el tiempo que conduce (drive) por el tramo. Si estos argumentos se omiten, suponga cero milisegundos.

Para confirmar que la solución es concurrente e indeterminística, provea un modo detallado de ejecución (en inglés, verbose mode). Este modo se activa cuando se provee el argumento de línea de comandos -v a la simulación. Cada vez que un vehículo logra ingresar a un segmento de la rotonda, lo reporta en una línea de la salida estándar precedido por su número de vehículo. En el siguiente ejemplo, la primera línea (1: E) indica que el vehículo 1 (generado por la entrada EO) logró ingresar a la rotonda por el este y ahora está en el tramo entre el este y el norte. La cuarta línea (1: N) ocurre cuando este primer vehículo logró pasar en frente de la entrada norte y ahora se encuentra en el tramo entre el norte y el oeste. Finalmente la quinta línea (1: O) indica que el vehículo atravesó la salida oeste, y por lo tanto, logró hacer su recorrido satisfactoriamente, por lo que no se esperan más eventos suyos. Si lo desea, puede además imprimir en cada evento cuántos segundos (con resolución de nanosegundos) han transcurrido desde que el vehículo fue creado.

Ejemplo de salida detallada
1: E
3: N
2: S
1: N
1: O
...
3 N

1 EO: E N O
2 SE: S E
3 NN: N O S E N
4 ON: O S E N

6.2. Diseño de la solución

Diseñe primero una solución al problema de la rotonda utilizando los mecanismos de sincronización (control de concurrencia) vistos en clase. Puede usar metáforas visuales (opcional) y pseudocódigo.

6.3. Metáforas visuales

Sugerencia 1: Puede usar un semáforo en cada punto cardinal como se muestra en la Figura 4. Cada semáforo regula el paso tanto de los vehículos que intentan ingresar a la rotonda por el punto cardinal como de los vehículos que ya circulan dentro de la rotonda y que se dirigen por el segmento hacia dicho punto cardinal (señalado con flechas para el semáforo sur en la Figura 4). El valor del semáforo representa la cantidad de vehículos que pueden circular de manera segura por el segmento de la rotonda que continúa después del semáforo.

roundabout initial
Figura 4. Sugerencia de semáforos para controlar la concurrencia en la rotonda

Sugerencia 2: Almacene los semáforos en un arreglo, de tal forma que pueda usar lógica modular para acceder a ellos de manera circular.

6.4. Pseudocódigo

Diseñe una solución en pseudocódigo. Utilice la nomenclatura que se ha mostrado durante las lecciones del curso. Puede suponer que nunca se correará la simulación con más de 2000 vehículos. Puede tomar el siguiente pseudocódigo como punto de partida.

procedure main(argc, argv[])
  // Analyze arguments
  shared const drive_min_delay = integer(argv[1]) if argc >= 2 else 0
  shared const drive_max_delay = integer(argv[2]) if argc >= 3 else 0
  shared const verbose = true if argc >= 4 and argv[3] = "-v" else false
  // Vehicle capacity in each segment of the roundabout
  shared const segment_capacity = read_integer(stdin)
  // Create vehicles
  declare vechicles := reserve_threads(2000)
  while input enter_from, exit_to do
    apppend_thread(vechicles, vehicle, enter_from, exit_to)
  end while
  join_threads(vechicles)
end procedure

procedure vehicle(enter_from, exit_to)
  // ...
  drive()
  // ...
end procedure

procedure drive()
  sleep(random_between(drive_min_delay, drive_max_delay))
end procedure

La subrutina drive() indica que el conductor se encuentra circulando por un tramo de la vía. Se debe invocar en todas las siguientes situaciones: cuando se ingresa en la rotonda (si estaba esperando), cuando se mueve hacia el próximo segmento de la rotonda (si ya estaba circulando en su interior), o cuando se sale de la rotonda (si ha llegado a la salida que debe tomar). Para efectos de la simulación, la implementación de esta subrutina corresponde a una espera pasiva de una cantidad aleatoria de milisegundos en un rango dado por argumentos de línea de comandos.

6.5. Implementación

Implemente su solución al problema de la rotonda en la tecnología concurrente de su elección. Puede escoger el lenguaje de programación y bibliotecas a su gusto. Aplique las prácticas usadas en tareas previas, como el uso adecuado de control de versiones, estructura de directorios, construcción de de la solución (Makefile), modularización, documentación, y buenas prácticas de programación.

6.6. Pruebas

Asegúrese de verificar el funcionamiento de su programa con los casos de prueba provistos. Se recomienda crear más casos de prueba. Asegúrese de utilizar herramientas de análisis dinámico de código (ej.: Google Sanitizers, Valgrind, etc.), si dispone de ellas.

Corra la simulación en modo detallado y corrobore que los eventos reportados sean válidos, y que no ocurran accidentes en la rotonda, bloqueos mutuos, ni otras anomalías.

6.7. Evaluación

  1. [30%] La solución permite que todos los vehículos logren ingresar a la rotonda, moverse correctamente en la dirección hacia la que transitan, y tomar la salida correcta. Diseño [15%], implementación [15%].

  2. [20%] La solución evita que ocurra bloqueo mutuo (deadlock) o espera infinita por recursos. Diseño [10%], implementación [10%].

  3. [10%] La solución garantiza que cada segmento de la rotonda pueda alojar a lo sumo la cantidad de vehículos que indique su capacidad. Diseño [5%], implementación [5%].

  4. [15%] La solución guarda un registro de la trayectoria de cada vehículo y lo muestra correctamente en la salida estándar. Diseño [5%], implementación .[10%]

  5. [10%] Buen uso de la memoria y la concurrencia (herramientas de análisis dinámico de código). Apego a una convención de estilos (linter).

  6. [15%] La solución pasa los casos de prueba. Muestra un comportamiento realista en modo detallado -v.

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.