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