Comando de Unix (levdist) programado en C que encuentra los archivos más similares usando la distancia de Levenshtein. Los archivos pueden ser especificados por argumentos de línea de comandos. Si se proveen carpetas, el programa compara todos los archivos en ellas, e incluso, en forma recursiva si se solicita. La ayuda del comando muestra la interfaz con el usuario:

Usage: levdist [-qru][-w W] DIRS|FILES
Finds most similar files using Levenshtein distance

Options:
      --help       Prints this help
      --version    Prints information about this command
  -q, --quiet      Do not print elapsed time (e.g: for testing)
  -Q, --silent     Do not generate output at all (for testing)
  -r, --recursive  Analyze files in subdirectories
  -u, --unicode    Enable Unicode support, ASCII is default
  -w W             Use W workers (threads)

El proyecto será desarrollado de forma individual a lo largo de 4 entregables que se detallan en las respectivas secciones más adelante:

1. levdist-serial: comando completo que calcula distancias en forma serial.
2. levdist-pthreads: compara documentos usando POSIX Threads.
3. levdist-openmp: compara documentos usando OpenMP.
4. levdist-mpi: distribuye las comparaciones entre máquinas.

El código de cada entregable debe agregarlo a su respositorio de control de versiones del curso antes de la fecha límite del entragable. Se provee un código inicial del cual puede iniciar su desarrollo y se explica en la siguiente sección.

1. Versión 0: código inicial

Esta versión implementa alguna funcionalidad básica y común de los comandos de Unix, como analizar argumentos, presentar ayuda, y para conveniencia del estudiante, cargar la lista de archivos en directorios y subdirectorios.

Important
Se modificó el Makefile para no tener que incluir en los casos de prueba la ruta de los archivos relativa al Makefile, sino a la carpeta misma del caso de prueba. Por ejemplo, en lugar de que en el archivo de salida se reporte test/myt_anthems/files/costa_rica.txt se usa simplemente files/costa_rica.txt. De esta forma la entrada y salida de los casos de prueba es más sencilla. Descargue el siguiente archivo. Extráigalo en cualquier lugar de su sistema de archivos. Luego sobreescriba los archivos de su repositorio con los extraídos. Revise los cambios con Git y haga un commit. Si ya hizo la actividad de crear casos de prueba propios (que inician con el prefijo myt_), revise que se ajustan a las rutas relativas al caso de prueba y no al Makefile.

El proyecto incluye además un Makefile que permite hacer algunas operaciones habituales:

make             Equivale a make debug. Use make clean antes de cambiar entre debug y release.
make debug       Genera el ejecutable distlev compilando con opciones de depuración.
make release     Compila el ejecutable con optimizaciones y sin opciones de depuración.
make doc         Genera documentación extrayendo comentarios con Doxygen.
make test        Prueba el ejecutable contra casos de prueba de caja negra en ASCII.
make test_u      Prueba el ejecutable contra casos de prueba de caja negra en Unicode.
make all         Equivale a `make debug doc test`
make memcheck    Busca fugas de memoria en el ejecutable usando los casos de prueba en ASCII.
make memcheck_u  Busca fugas de memoria en el ejecutable usando los casos de prueba en Unicode.
make clean       Elimina archivos generados (y que no deben estar en control de versiones).
make install     Copia el ejecutable en la carpeta ~/bin
make uninstall   Elimina el ejecutable de la carpeta ~/bin

2. Versión 1: serial [25% oct-01]

Descargue el código de la versión inicial y agréguelo a su repositorio de control de versiones en una carpeta levdist-serial. Realice las modificaciones indicadas en las siguientes actividades. Al final de este entregable sólo deberá obtener la carpeta levdist-serial con su solución, en la cual haya realizado las actividades. No debe crear una carpeta por cada actividad.

Actividad 1 [analysis]

Escriba su análisis del problema y describa su solución en el archivo README.md. Ya este archivo contiene algunas sugerencias para completarlo.

  1. Describa el problema que resuelve su comando levdist.

  2. Explique con un manual de usuario cómo se puede invocar su programa.

  3. Explique los pasos para compilar, instalar, y desinstalar el software.

  4. Provea información de autoría, contacto y licencia.

Actividad 2 [quiet]

Haga a su comando reaccionar a las opciones -q ó --quiet, que solicitan imprimir en la salida estándar sólo los resultados de las comparaciones de Levenshtein de los archivos. Es decir, debe omitir el mensaje que indica la duración en segundos y la cantidad de workers usada. Esta opción es requerida para hacer pruebas de caja negra.

Haga a su comando reaccionar a las opciones -Q ó --silent, la cuales instruyen al comando realizar las comparaciones pero no imprimir resultado alguno en la salida estándar. Esta opción es requerida para hacer pruebas de fugas de memoria.

Recuerde documentar los símbolos que agregue a su solución y apegarse a la convención de estilo (snake_case).

Actividad 3 [arg_files]

Modifique su comando para que pueda recibir tanto directorios como archivos en la entrada estándar. Si el usuario provee archivos, su comando los agrega a la lista de archivos a comparar, en lugar de considerarlo un directorio y tratar de listar su contenido. Indague sobre la función stat() y la macro S_ISREG. Esta función brinda otros detalles sobre los archivos que le pueden ser útiles más adelante.

Actividad 4 [add_tests]

Estudie cómo el Makefile invoca a su programa para probar los casos de prueba con make test -n. Estudie los casos de prueba provistos en el código inicial. Agregue a su repositorio al menos tres casos de prueba, los cuales varíen significativamente por los siguientes criterios:

  1. La longitud de los archivos.

  2. El número de archivos.

  3. El número de subcarpetas.

Cada caso de prueba debe estar en una subcarpeta dentro del directorio test de su repositorio. Use el prefijo myt_ para sus casos de prueba. Por ejemplo, si el caso de prueba contiene himnos de varios países, podría llamar la carpeta myt_anthems.

El profesor anunciará cuándo estén disponibles otros casos de prueba para descarga. Puede obtenerlos y extraerlos en una carpeta en su sistema, pero no los debe agregar a control de versiones en su repositorio.

Actividad 5 [comp_colecc]

Su comando debe realizar comparaciones de cada archivo contra todos los demás. Implemente una estructura de datos que le permita administrar las comparaciones y luego ordenarlas de la pareja más similar a la menos similar. Instancie la estructura de datos como un atributo que las funciones controladoras puedan administrar (en los archivos levdist.h y levdist.c).

Asegúrese de que su implementación no produce fugas de memoria. Documente sus estructuras y subrutinas, tanto la interfaz (documentación de Doxygen) como instrucciones no obvias en la implementación. Asegúrese de que la documentación sea extraída correctamente por Doxygen y que esta herramienta no reporte errores o advertencias.

Actividad 6 [lev_impl]

Indague sobre el algoritmo para calcular la distancia de Levenshtein y sus variantes. Implemente alguna variante en C. Dedique una pareja de archivos levenshtein.h y levenshtein.c para esta implementación. Recuerde documentar estos archivos y dar crédito a la fuente de dónde tomó el algoritmo.

El algoritmo de la distancia de Levenshtein compara dos cadenas. Provea una subrutina que compare dos archivos. Puede asumir que los archivos son de texto ASCII puro. La subrutina recibe la ruta de dos archivos a comparar, carga sus contenidos, los compara con su implementación de la distancia de Levenshtein, y retorna la distancia de los dos archivos.

Actividad 7 [order_comp]

Utilice las subrutinas de la actividad anterior para comparar todas las parejas de archivos que el usuario indique al invocar el comando. Debe producir en la salida estándar la lista de comparaciones ordenada de la pareja más similar a la menos similar, usando el formato de valores separados por tabuladores, algo como:

32	path/file1.ext	path/file3.ext
80	path/file2.ext	path/file3.ext
153	path/file1.ext	path/file2.ext

Donde la primera columna indica la distancia de Levenshtein, la segunda y tercera columnas corresponden a los archivos comparados.

Actividad 8 [test_comp]

Asegúrese de que su solución serial pasa todos los casos de prueba, no genere fugas de memoria, ni errores al extraer la documentación.

Algunos casos de prueba podrían requerir la implementación de funcionalidad adicional que no fue mencionada en las actividades previas.

Actividad 9 [perf_serial]

Mida la duración en segundos de la versión serial en modo "release" de su solución en dos computadoras, una del laboratorio 104-IF y otra un nodo "phi" del CENAT. Como datos de entrada utilice:

  1. La carpeta con todos los casos de prueba de los compañeros en forma recursiva.

  2. El caso de prueba crime_suspect. Sólo compare dos archivos y estime la duración total linealmente (por regla de 3).

Almacene sus resultados en una hoja de cálculo, los cuales establecen la línea base (serial) para comparar las optimizaciones posteriores y realizar un gráfico combinado. Guarde su hoja de cálculo en una carpeta levdist-serial/perf/.

Actividad 10 [opcional: unicode]

Agregue soporte para archivos de texto en Unicode. Por ejemplo, la distancia de Levenshtein entre la cadena "papa" y la cadena "papá" es de 2 cambios si las cadenas se interpretan en ASCII puro, pero de 1 cambio si se interpretan en Unicode.

Cuando su comando se invoque con la opción -u, su programa interpretará todos los archivos provistos por argumentos de línea de entrada (y subcarpetas), como archivos de texto con esta codificación. Si la opción -u no se provee, el programa asume que la codificación es ASCII puro. Oportunamente el profesor proveerá un conjunto de casos de prueba en Unicode para quienes implementen esta funcionalidad opcional.

3. Versión 2: Pthreads [30% oct-29]

El objetivo de la versión 2 es lograr un comando más eficiente, que pueda encontrar las distancias entre archivos en un tiempo menor, aprovechando los recursos del equipo donde se ejecuta. Copie su directorio levdist-serial como levdist-pthreads. Agréguelo a control de versiones.

Actividad 11 [duration2]

Modifique su programa para reportar dos duraciones:

  1. La duración total del programa, que incluye el cargado de los archivos, ordenar e imprimir los resultados, y la eliminación de las estructuras en memoria dinámica. Ya este cálculo está implementado en el código fuente provisto (versión 0).

  2. La duración de únicamente comparar los archivos usando el algoritmo de Levenshtein.

La salida de su programa podría tener la forma:

Total time 3.289217000s, comparing time 2.701982001s, 4 workers

Esta separación permitirá tener un indicio de los efectos del cargado de los archivos a través de una red, como ocurre en un cluster. Sugerencia: modifique la versión serial para que no reporte la cantidad de trabajadores, sino que advierta que se trata de la versión serial:

Total time 3.289217000s, comparing time 2.701982001s, serial version
Actividad 12 [prof_cpu1]

Realice un análisis dinámico de código (profiling) para determinar las subrutinas de su programa que consumen más CPU, y en ellas las líneas de código que ejecutan más instrucciones. Utilice la herramienta callgrind para estudiar el comportamiento de su programa contra un caso de prueba mediano, por ejemplo: desiderata.

Utilice una herramienta de visualización (ej: KCachegrind) para estudiar las bitácoras generadas por la herramienta de profiling. Haga una captura de pantalla de la subrutina que consume más CPU. Haga otra captura de pantalla de el árbol de llamados hacia esa subrutina que consume más CPU. Indique sus resultados en un documento optimizations.md, en el cual incluya las capturas de pantalla. Guarde estos archivos en la carpeta levdist-pthreads/perf/.

Actividad 13 [prof_time1]

Realice un análisis dinámico de código (profiling) para determinar el tiempo que consume cada subrutina. Utilice la herramienta gprof para estudiar el comportamiento de su programa contra todos los casos de prueba recopilados por el profesor.

¿Coinciden los resultados con el tiempo reportado por el programa? ¿Reflejan los resultados el consumo de CPU reportado por callgrind? Responda en su documento levdist-pthreads/perf/optimizations.md.

Actividad 14 [prof_cache1]

Realice un análisis dinámico de código (profiling) para determinar las instrucciones que provocan más fallos de caché. Utilice la herramienta cachegrind de valgrind para estudiar el comportamiento de su programa contra todos los casos de prueba recopilados por el profesor.

Explique en su documento optimizations.md las razones que provocan más fallos de caché en el algoritmo original de Levenshtein.

Actividad 15 [parallel_design]

Asegúrese de comprender bien el algoritmo de la Distancia de Levenshtein. Puede recurrir a documentos, videos, u otros materiales (por ejemplo, este video). Realice manualmente la comparación de dos cadenas (en papel) de longitud entre 4 y 6 caracteres. Mientras avanza en el cálculo de las comparaciones, piense en formas en que varios trabajadores pueden hacer este cálculo concurrentemente. Sugerencia: ubique los caracteres de la cadena más corta verticalmente en las filas, y la cadena más larga horizontalmente en las columnas.

Escoja una optimización para implementar el algoritmo de Levenshtein concurrentemente y explíquela en su documento optimizations.md. Puede explicar su elección con ejemplos. De ser posible, escoja una optimización que aproveche el procesamiento paralelo y no requiera alojar toda la matriz de Levenshtein en la memoria principal, sino trozos de la misma.

Estudie (y asegúrese de comprender) el algoritmo propuesto por (Guo et al. 2013) "Parallel Algorithm for Approximate String Matching with k Differences" ↗️ que utiliza una matriz adicional para eliminar una de las tres dependencias que tiene cada celda en el algoritmo original de Levenshtein. Haga un rastreo del algoritmo con las mismas cadenas que escogió para el algoritmo original de Levenshtein. Agregue una imagen escaneada o fotografía de ambos rastreos a su archivo optimizations.md. Edite las imágenes para que ocupen poco espacio antes de agregarlas a control de versiones (unos 20kB o menos por imagen).

Actividad 16 [parallel_impl]

Implemente el algoritmo paralelo de Guo et al. 2013 usando la biblioteca Pthreads. Asegúrese de utilizar los mecanismos de sincronización de hilos (ej: mutex, semáforos, variables de condición, o candados de lectura-escritura) correctamente.

Debe modificar el algoritmo para que la primera fila tenga valores incrementales y no cero, con el fin de comparar las cadenas completas y no hasta una diferencia máxima permitida k, o bien, parametrizar el algoritmo con k=m. Tras implementar su optimización concurrente, asegúrese de que su solución pase todos los casos de prueba y no produzca fugas de memoria.

Actividad 17 [perf_pthreads]

Mida la duración en segundos de la versión concurrente en modo "release" de su solución en dos computadoras, una del laboratorio 104-IF y otra un nodo "phi" del CENAT. En ambas máquinas utilice:

  1. La cantidad de threads equivalente a la cantidad de CPUs disponibles en el hardware.

  2. El doble de la cantidad anterior.

Como datos de entrada utilice los mismos con los que midió la versión serial, es decir:

  1. La carpeta con todos los casos de prueba acopiados por el profesor en forma recursiva.

  2. El caso de prueba crime_suspect, pero esta vez compare todos los archivos de la subcarpeta dna recursivamente, es decir levdist -r dna.

Almacene sus duraciones en la hoja de cálculo.

Actividad 18 [pthr_markers]

Calcule en su hoja de cálculo los siguientes indicadores:

  1. El incremento de velocidad (speedup) S=TserialTparallel.

  2. La eficiencia como la relación entre el incremento de velocidad y la cantidad w de trabajadores E=Sw=TserialwTparallel.

Actividad 19 [pthr_graph]

Refleje en varios gráficos combinados la siguiente información:

  1. Los datos de entrada (varios, ADN).

  2. La cantidad de trabajadores utilizados.

  3. Las duraciones de las corridas.

  4. El incremento de velocidad (speedup).

  5. La eficiencia.

4. Versión 3: OpenMP [20% dic-01]

El objetivo de este entregable es producir un comando aproximadamente similar en eficiencia al entregable con Pthreads, pero utilizando menor cantidad de código fuente, gracias a la tecnología OpenMP. Por tanto, esta solución debería ser más fácil de producir, leer, y darle mantenimiento en el tiempo. Copie una de sus soluciones anteriores, la serial o más probablemente Pthreads, a la carpeta levdist-openmp y agréguela a control de versiones.

Actividad 20 [impl_omp]

Gracias a los análisis de rendimiento que realizó en el entrable anterior, es conocida la subrutina que requiere trabajo de optimización. En este entregable implemente el algoritmo paralelo de Guo et al. 2013 (página 260) usando directivas y subrutinas de OpenMP.

Si parte de la versión serial, recuerde modificar el algoritmo para que la primera fila tenga valores incrementales y no cero, con el fin de comparar las cadenas completas y no hasta una diferencia máxima permitida k, o bien, parametrizar el algoritmo con k=m.

Tras implementar su optimización concurrente con OpenMP, asegúrese de que su solución pase todos los casos de prueba y no produzca fugas de memoria. Si valgrind le reporta still reachable memory, revise que las subrutinas involucradas no correspondan a su código fuente, de lo contrario, ignórelas, dado que probablemente se trate de bibliotecas dinámicas de terceros que aún no han sido desalojadas de la memoria principal.

Actividad 21 [perf_omp]

Mida la duración en segundos de la versión concurrente con OpenMP en modo "release" de su solución en dos computadoras, una del laboratorio 104-IF y otra un nodo "phi" del CeNAT. En ambas máquinas utilice:

  1. La cantidad de threads equivalente a la cantidad de CPUs disponibles en el hardware.

  2. El doble de la cantidad anterior.

Como datos de entrada utilice los mismos con los que midió la versión serial y de Pthreads, es decir:

  1. La carpeta con todos los casos de prueba acopiados por el profesor en forma recursiva.

  2. El caso de prueba crime_suspect. Puede comparar una pareja de archivos y estimar proporcionalmente el tiempo que tardaría comparar todos los archivos de la subcarpeta dna en forma recursiva (levdist -r dna).

Almacene sus duraciones en la hoja de cálculo en la carpeta perf de su proyecto.

Actividad 22 [markers_omp]

Calcule en su hoja de cálculo los siguientes indicadores:

  1. El incremento de velocidad (speedup) respecto a la versión serial S=TserialTparallel.

  2. La eficiencia como la relación entre el incremento de velocidad y la cantidad w de trabajadores E=Sw=TserialwTparallel.

Actividad 23 [graph_omp]

Agregue a su(s) gráfico(s) combinados una serie con las mediciones obtenidas con la versión de OpenMP. Recuerde que los gráficos combinados deben reflejar la siguiente información:

  1. Los datos de entrada (varios, ADN).

  2. La cantidad de trabajadores utilizados.

  3. Las duraciones de las corridas.

  4. El incremento de velocidad (speedup).

  5. La eficiencia.

5. Versión 4: MPI [25% dic-15]

Los entregables anteriores aprovechan la concurrencia de una única máquina, pero no el poder de cómputo de otras máquinas vecinas ociosas. Su objetivo es producir una solución que aproveche paralelamente el poder de cómputo de una red de máquinas implementando concurrencia de memoria distribuida y la tecnología Message Passing Interface (MPI).

Copie la solución de concurrencia de memoria compartida (Pthreads u OpenMP) por el criterio que prefiera (ej: rendimiento o fácil mantenimiento) en la carpeta levdist-mpi y agréguela a control de versiones.

Actividad 24 [design_mpi]

Diseñe un esquema para que distribuya (scheduling) las parejas de archivos a comparar entre las máquinas disponibles en el clúster. Debe escoger un esquema dinámico o estático (como bloques, cíclico, o híbrido). Por ejemplo, si se deben comparar cuatro archivos (adn1.txt a adn4.txt) y se tienen cuatro nodos, una distribución estática por bloques podría hacer las siguientes asignaciones:

node0: adn1-adn2 adn1-adn3
node1: adn1-adn4 adn2-adn3
node2: adn2-adn4
node3: adn3-adn4

Una asignación dinámica distribuye en tiempo de ejecución, en función de las duraciones de cada comparación. Cada vez que un proceso queda ocioso toma la siguiente pareja de comparaciones disponible, y así repetitivamente hasta que las parejas se hayan acabado. Los procesos se comunicarían mediante la red para saber cuáles comparaciones están disponibles o completadas.

La elección del esquema de distribución es sumamente importante y crítico para su aplicación. Indique su elección en un archivo design.md y justifíquela muy fundamentadamente. Por ejemplo, tome en consideración lo aprendido de los esquemas de OpenMP y sus resultados de rendimiento en actividades de los entregables anteriores. Sugerencia: haga una comparación de las ventajas y desventajas para su proyecto de cada esquema de distribución, y luego realice la elección.

Una vez que haya elegido su esquema de distribución, explique el algoritmo que los procesos seguirán desde antes y después de realizar las comparaciones de Levenshtein. Su algoritmo debe considerar si uno o todos los procesos harán lo siguiente, y cómo lo harán:

  1. realizarán el análisis de argumentos,

  2. levantarán el listado de archivos,

  3. administrarán la estructura de datos con las parejas de archivos a comparar,

  4. distribuirán (scheduling) las parejas de archivos

  5. integrarán los resultados, y

  6. ordenarán y presentarán de los resultados al usuario.

Además del algoritmo en pseudocódigo, explique una ejecución mediante un ejemplo arbitrario. Puede usar una tabla para rastrear los pasos del algoritmo ejecutados concurrentemente por cada proceso. Asuma que todos los procesos se inician exactamente al mismo tiempo. Puede escoger tamaños de archivos y duraciones proporcionales de comparación de cada pareja de archivos. Agregue su rastreo a control de versiones, como una imagen escaneada o un archivo de hoja de cálculo.

Actividad 25 [impl_mpi]

Implemente su solución escogida en la actividad anterior usando la biblioteca MPI. Asegúrese de que su solución pase todos los casos de prueba y no produzca fugas de memoria.

Actividad 26 [perf_mpi]

Mida la duración en segundos de la versión distribuida con MPI en modo "release" de su solución en el clúster del CeNAT. Utilice:

  1. La cantidad de threads equivalente a la cantidad de CPUs disponibles en el hardware.

  2. El doble de la cantidad anterior.

Como datos de entrada utilice los mismos con los que midió las versiones anteriores, es decir:

  1. La carpeta con todos los casos de prueba acopiados por el profesor en forma recursiva.

  2. El caso de prueba crime_suspect. Debe comparar todas las parejas de archivos.

Almacene sus duraciones en la hoja de cálculo en la carpeta perf de su proyecto.

Actividad 27 [markers_mpi]

Calcule en su hoja de cálculo los siguientes indicadores:

  1. El incremento de velocidad (speedup) respecto a la versión serial S=TserialTparallel.

  2. La eficiencia como la relación entre el incremento de velocidad y la cantidad w de trabajadores E=Sw=TserialwTparallel.

La cantidad de trabajadores w corresponde al número total hilos que se ejecutaron. Recuerde que todo proceso siempre tiene al menos un hilo principal.

Actividad 28 [graph_mpi]

Agregue a su(s) gráfico(s) combinados una serie con las mediciones obtenidas con la versión distribuida de MPI. Recuerde que los gráficos combinados deben reflejar la siguiente información:

  1. Los datos de entrada (varios, ADN).

  2. La cantidad de trabajadores utilizados.

  3. Las duraciones de las corridas.

  4. El incremento de velocidad (speedup).

  5. La eficiencia.

Para el caso de prueba de ADN, las corridas anteriores (serial, Pthreads y OpenMP) deben tener las duraciones estimadas (por regla de tres) de todas las parejas de archivos.