Índice
La organización del desarrollo de este laboratorio es la siguiente:
├── .docimg -> imagenes para el informe
├── img -> imagenes para pattern matching
├── profiling -> resultados de profiling
├── src
│ ├── bin -> archivos binarios
│ ├── img_to_dots.py -> lee una imagen, la convierte a una matriz en greyscale y la escribe en un archivo
│ ├── parallel.c -> pattern matching de imagenes paralelizado
│ └── procedural.c -> pattern matching de imagenes procedural
├── get_img_pixels.sh -> script para ejecutar _img_to_dots.py_ sobre 2 imagenes
├── makefile -> genera todo lo necesario para el desarrollo del trabajo
├── README.md -> informe de lo realizado
└── test.sh -> para testing de los programas paralelo y procedural
- crear ejecutables
$ make
- generar matrices greyscale de una imagen
$ python3 ./src/img_to_dots.py [img path] [output file] [show|noshow]
- ejecutar programa procedural
$ ./src/bin/procedural [full img matrix txt file] [template img matrix txt file]
- ejecutar programa paralelo
$ ./src/bin/paralela [full img matrix txt file] [template img matrix txt file]
- ejecutar ambos con las imagenes por defecto del laboratorio
$ ./test.sh L . [show|noshow]
Para obtener una representacion amigable de la imagen desarrolle un pequeño script en python que se sirve de la libreria OpenCV.
Este script lee una imagen que le pasamos como argumento al programa y la transforma a una matriz en escala de grises. Luego escribe en un archivo de texto las dimensiones de la imagen de la forma "height width" y linea por linea el valor de gris de cada pixel de la imagen. Por último, opcionalmente se muestra la imagen leída.
Para poder trabajar con dicha matriz, el programa en C, mediante la funcion read_image_pixels hace lo siguiente:
- Lee el archivo de texto con la matriz de los pixeles
- Guarda en punteros recibidos como parametros las dimensiones de la matriz
- Aloca la memoria necesitada para poder guardar todos los valores
- Lee linea por linea el texto mediante getline
- Lee cada valor de la linea obtenida, lo convierte a int y lo guarda en la posicion adecuada en la matriz
- Devuelve la matriz alocada y rellenada
Siguiendo e interpretando las instrucciones en la consigna del laboratorio llegué un algoritmo que, aunque muy lentamente, resolvía el problema:
- Se crea una ventana del tamaño del patron que se quiere encontrar en la imagen completa
- Con un doble for loop se va recorriendo toda la matriz de la imagen completa hasta los limites en x e y menos los respectivos valores de ancho y alto del template.
- Con otro doble for loop interior se llena a la ventana creada con los valores de la imagen original del cuadro en que nos encontramos y se procede a calcular la distancia euclideana del pixel que estamos viendo de la imagen completa con el que le correspondería en el template. Cada distancia se suma por fila y despues al final se suman todas las distancias de cada fila y obtenemos la distancia total de la ventana comparada de la imagen completa con respecto al template. Una vez la tenemos, comparamos con el mínimo obtenido anteriormente. Al final tenemos el valor de la minima distancia y la esquina superior izquierda de donde se encuentra en la imagen completa.
Si bien el algoritmo funcionaba y daba resultados correctos, cuando se trataba de imagenes relativamente grandes el tiempo de ejecución era de varios minutos. Por eso seguí tratando de optimizarlo, siendo las siguientes algunas de las optimizaciones:
- eliminar operaciones y asignaciones innecesarias
- a medida de que va sumando la distancia comparar con el mínimo anterior, si ya se pasó se descarta esa iteración y se pasa a la siguiente
- atoi vs naive: realicé el profiling de la función read_image_pixels con estas distintas formas de convertir string a int, obteniendo con atoi un tiempo promedio de la función de 1.6 segs con la función significando el 41% de ese tiempo, y con naive un promedio de 0.74 segs y un 30.6% de ese tiempo lo usa la función.
De esta manera pude lograr bajar los tiempos de ejecución al orden de los segundos, en promedio aproximadamente 24 s.
Una vez que tuve un algoritmo serial con el que estaba conforme, me dediqué a paralelizarlo mediante OpenMP para obtener mejores resultados en performance. Lo primero fue ver donde estaban los hotspots del programa y trabajar sobre ellos.
- Por lejos, el mayor consumo de tiempo de ejecución se da en la función template_matching que es donde se realiza el algoritmo. Al haber 4 nested fors lo que hice fue crear una sección paralela que los englobe e ir haciendo profiling de paralelizar cada for con distintos schedules y clausulas. Encontré que la mayor performance la obtengo cuando paralelizo el for más externo:
- schedule dynamic para que cuando un thread termine no tenga que esperar nada y enseguida agarre otro chunk
- tamaño de chunk 128
- clausula nowait para eliminar la barrera interna al final del for ya que no es necesaria y nos ahorramos bastante overhead
- tiene una sección critical para calcular la minima distancia y evitar race conditions
- Luego decidí paralelizar la lectura y asignacion de los pixeles de las imagenes obtenidas ya que las funciones atoi y strtok consumían un tiempo considerable. Para eso cree una seccion paralela que engloba un for:
- clausula ordered ya que necesito leer en orden las filas del archivo de texto leido
- schedule static ya que van a entrar en orden.
- tamaño de chunk 1 porque si fuera mas grande cada thread deberia esperar a que termine el anterior por la clausula ordered
- clausula nowait para eliminar la barrera interna al final del for ya que no es necesaria y nos ahorramos bastante overhead
A continuacion se muestra un grafico donde se compara el speedup obtenido del programa paralelo con distinta cantidad de threads respecto del serial.
| N° threads| speedup |
|-----------|---------|
| 1 | 1 |
| 2 | 1.5 |
| 4 | 2.134 |
| 8 | 7.62 |
| 16 | 7.73 |
| 32 | 7.9 |
| 64 | 7.87 |
| 128 | 7.52 |
Como se observa, al poner 2 threads ya hay una mejora y fui haciendo profiling con 2^n numero de threads para ver el maximo rendimiento practico para este problema con esta implementación. Vemos que el pico se alcanza con 32 threads, y a partir de ahí la mejora empieza a decaer porque lo que se gana en velocidad de computo ya es menor que lo que se gasta en overhead en creación, eliminación y switch de threads.
Al principio del trabajo, cuando trabaja serialmente utilizaba gprof como el trabajo anterior. Luego, cuando empecé con paralelización me di cuenta que obtenía resultados incorrectos ya que gprof reporta el tiempo total de cada core utilizado. Luego me empecé a servir del comando time para medir tiempo de ejecución y la función omp_get_wtime para mayor precisión. Para tener más detalles, me puse a investigar y encontré la herramienta Arm MAP: Scalable Profiler for Server/HPC Developers que da una licensia gratis por 7 días y la utilicé mientras pude. Esta herramienta te da la posibilidad de hacer profiling de programas con OpenMP y te da las siguientes posibilidades:
- Observar en que tipo de operaciones se divide el tiempo de ejecución
- En que momento de la ejecución se da cada tipo de operación
- ver que porcentaje del tiempo de ejecución consume cada instrucción
- El porcentaje de consumo de tiempo de cada función
Para facilitarme el desarrollo y testear las distintas versiones del programa cree dos bash scripts:
- get_img_pixels: ejecuta el script python para leer las imagenes (completa y template) que se las paso como argumento
- test.sh: ejecuta get_img_pixels con las imagenes que le indique y luego ejecuta la versión paralela, procedural o ambas del programa de pattern matching y guarda su resultado en archivos de texto.