Paralelización y optimización de algoritmos de stereo matching

UNIVERSIDADE DE SANTIAGO DE COMPOSTELA ESCOLA TÉCNICA SUPERIOR DE ENXEÑARÍA PARALELIZACIÓN Y OPTIMIZACIÓN DE ALGORITMOS DE STEREO MATCHING Autor: Aleixo Cambeiro Barreiro Directores: Juan Carlos Pichel Campos Francisco Fernández Rivera Grao en Enxeñaría Informática Julio 2015 Traballo de fin de Grao presentado na Escola Técnica Superior de Enxeñaría da Universidade de Santiago de Compostela para a obtención do Grao en Enxeñaría Informática D. Juan Carlos Pichel Campos, Profesor do Departamento de Electrónica e Computación da Universidade de Santiago de Compostela, e D. Francisco Fernández Rivera, Profesor do Departamento de Electrónica e Computación da Universidade de Santiago de Compostela, INFORMAN: Que a presente memoria, titulada Paralelización y optimización de algoritmos de Stereo Matching, presentada por D. Aleixo Cambeiro Barreiro para superar os créditos correspondentes ao Traballo de Fin de Grao da titulación de Grao en Enxeñaría Informática, realizouse baixo nosa dirección no Departamento de Electrónica e Computación da Universidade de Santiago de Compostela. E para que así conste aos efectos oportunos, expiden o presente informe en Santiago de Compostela, a 8 de Xullo de 2015: O director, O codirector, O alumno, Juan Carlos Pichel Campos Francisco Fernández Rivera Aleixo Cambeiro Barreiro ÍNDICE 1. INTRODUCCIÓN ............................................................................................................ 1 1.1. Stereo Matching .................................................................................................... 1 1.2. Usos del Stereo Matching e importancia de su optimización ............................... 4 1.3. Objetivos del proyecto .......................................................................................... 4 1.4. Arquitecturas consideradas ................................................................................... 5 2. GESTIÓN DEL PROYECTO .............................................................................................. 6 2.1. Alcance ................................................................................................................... 6 2.1.1. Descripción del alcance .................................................................................. 6 2.1.2. Criterios de aceptación del producto ............................................................. 6 2.1.3. Productos entregables del proyecto .............................................................. 6 2.1.4. Exclusiones del proyecto ................................................................................ 7 2.1.5. Restricciones del proyecto ............................................................................. 7 2.1.6. Supuestos del proyecto .................................................................................. 7 2.2. Casos de uso .......................................................................................................... 7 2.3. Requisitos ............................................................................................................ 13 2.3.1. Requisitos funcionales .................................................................................. 13 2.3.2. Requisitos no funcionales ............................................................................. 15 2.4. Metodología ........................................................................................................ 15 2.4.1. Programación Extrema ..................................................................................... 16 2.5. Planificación temporal ......................................................................................... 17 2.5.1. Estructura de Descomposición del Trabajo .................................................. 17 2.5.2. Diagrama de Gantt ........................................................................................... 20 2.6. Gestión de riesgos ............................................................................................... 22 2.6.1. Identificación y categorización ..................................................................... 22 2.7. Gestión de la configuración ................................................................................. 25 2.7.1. Identificación de los elementos de configuración ....................................... 25 2.7.2. Herramientas de gestión de configuración .................................................. 26 2.8. Análisis de costes ................................................................................................. 27 3. HERRAMIENTAS USADAS ............................................................................................ 31 3.1. Herramientas de desarrollo software ................................................................. 31 3.2. Herramientas para el desarrollo de la documentación ....................................... 34 4. ARQUITECTURA DEL SOFTWARE ................................................................................ 37 4.1. Front-end Java Swing ........................................................................................... 38 4.2. Línea de comandos desde consola ...................................................................... 43 4.3. Back-end en C++ .................................................................................................. 44 4.4. Mediciones de rendimiento ................................................................................ 44 4.5. Algoritmos de Stereo Matching ........................................................................... 44 4.6. Librería de tratado de imágenes ......................................................................... 44 4.7. Sistema de archivos ............................................................................................. 45 5. ALGORITMOS ESTUDIADOS ........................................................................................ 46 5.1. Pixel-wise Matching ............................................................................................. 46 5.2. Patch-wise Matching ........................................................................................... 48 5.2.1. Sum of Absolute Differences ........................................................................ 50 5.2.2. Adaptive Support-Weight ............................................................................. 52 5.3. Semi-Global Matching ......................................................................................... 55 6. ARQUITECTURAS HARDWARE CONSIDERADAS .......................................................... 59 6.1. Intel Xeon E5-2630Lv2 ......................................................................................... 59 6.2. Intel Xeon Phi 7120P ............................................................................................ 60 7. IMPLEMENTACIÓN PARALELA Y OPTIMIZACIÓN ........................................................ 64 7.1. Pixel-wise Matching y Patch-wise Matching ....................................................... 64 7.2. Semi-Global Matching ......................................................................................... 64 7.2.1. Direcciones ................................................................................................... 66 7.2.2. Franjas .......................................................................................................... 66 7.2.3. Combinación de direcciones y franjas .......................................................... 69 8. ANÁLISIS DE RENDIMIENTO ........................................................................................ 70 8.1. Cluster Intel Xeon E5-2630Lv2 ............................................................................. 70 8.1.1. Pixel-wise Matching ...................................................................................... 70 8.1.2. Patch-wise Matching .................................................................................... 72 8.1.3. Semi-Global Matching .................................................................................. 75 8.2. Intel Xeon Phi 7120P ............................................................................................ 82 8.2.1. Pixel-wise Matching ...................................................................................... 83 8.2.2. Patch-wise Matching .................................................................................... 84 8.2.3. Semi-Global Matching .................................................................................. 87 8.3. Comparación de los resultados para ambas arquitecturas ................................. 96 9. CONCLUSIONES ........................................................................................................... 98 APÉNDICE A - MANUAL DE USUARIO ........................................................................... 100 A.1. Ejecución por línea de comandos ..................................................................... 100 A.2. Ejecución mediante interfaz gráfica .................................................................. 102 BIBLIOGRAFÍA ............................................................................................................... 103 1 1. INTRODUCCIÓN El tema principal que aborda este trabajo es el Stereo Matching, así como la optimización de algunos de los algoritmos más relevantes de este campo. Por lo tanto, es vital comprender en qué consiste este antes de profundizar en la materia. Además de su naturaleza, también es interesante conocer sus usos principales para entender la importancia de la optimización de rendimiento, objetivo de este estudio. 1.1. Stereo Matching Se conoce como Stereo Matching o Stereo Vision al proceso de extracción de información sobre la profundidad de los objetos de una escena, basado en la comparación de varias imágenes de esta tomadas desde diferentes puntos. A efectos de ilustración, se adjunta en la Figura 1.1 el siguiente par de imágenes con el correspondiente mapa de profundidad de la escena para la vista de la izquierda: FIGURA 1.1: EJEMPLO DE STEREO MATCHING: (A) IMAGEN BASE (IZQUIERDA), (B) IMAGEN DERECHA, (C) MAPA DE PROFUNDIDAD 2 Esto se puede conseguir conociendo la posición de las proyecciones de un mismo punto en dos imágenes de la misma escena, así como las posiciones relativas de las cámaras que las han obtenido y sus parámetros intrínsecos (relativos a la lente, deben ser obtenidos mediante calibración experimental de la máquina). Con estos datos podemos deducir la posición del punto original en un espacio tridimensional. Esta nos permite conocer la profundidad del objeto en la escena respecto a la posición de cada cámara. Existe un factor fundamental que permite simplificar enormemente este proceso: la geometría epipolar [1]. Esta se basa en el concepto de línea base, la cual se define como aquella que conecta los centros de dos cámaras, y consiste en la geometría de la intersección de los planos que tienen esta recta como eje con los planos de proyección correspondientes a las susodichas cámaras. Dentro de ella se definen tres entidades básicas:  Epipolo: punto de intersección de la línea base con un plano de proyección.  Plano epipolar: cualquier plano que contenga la línea base.  Línea epipolar: intersección de un plano epipolar con un plano de proyección. Con esto, tenemos la garantía de que, dada una proyección x de un punto X de la escena en una de las imágenes, contenidos ambos en un plano epipolar 𝜋, la proyección x’ sobre la otra imagen también se encontrará, si existe, en el mismo plano. Esto significa que pertenecerá a la línea epipolar correspondiente a 𝜋, como podemos ver en la representación gráfica de la Figura 1.2. En dicha figura podemos ver los dos planos de formación de imágenes, correspondientes a sendas cámaras, y sobre ellos los elementos arriba definidos: para un punto X se muestra su proyección x en el primero de los planos, y una posible proyección del punto, cuya posición tridimensional es una incógnita, sobre la línea epipolar correspondiente en el segundo plano, l’. También se muestra la línea base entre los dos centros, así como los epipolos (e y e’) que esta genera en ambas proyecciones. 9 Nombre Lanzar ejecución Descripción El sistema deberá comportarse como se describe en el siguiente caso de uso cuando un usuario trate de ejecutar el programa. Precondición Ninguna. Secuencia normal Paso Acción 1 El usuario establece los parámetros de ejecución que utilizará el algoritmo que vaya a lanzar vía línea de comandos. 2 El sistema utilizará esos parámetros para cargar las imágenes correspondientes. 3 El sistema utilizará los parámetros para lanzar el algoritmo elegido en la versión requerida. 4 El sistema realizará las medidas pertinentes sobre la ejecución del algoritmo. 5 El sistema guardará el mapa de profundidad en el destino elegido. 6 El sistema guardará los resultados de las mediciones en el destino elegido, si se ha estipulado alguno. Postcondición Se ha ejecutado uno de los algoritmos implementados, realizado medidas sobre él, guardado el mapa de profundidad resultante y, si así se ha estipulado, los resultados de las mediciones. Excepciones Paso Excepción 1 1-A: Si los parámetros elegidos no son válidos, se cancela la ejecución y se muestra un mensaje de error. 2 2-A: Si no se pueden cargar las imágenes estipuladas, se cancela la ejecución y se muestra un mensaje de error. 5 5-A: Si no se puede guardar el mapa de profundidad se cancela la ejecución y se muestra un mensaje de error. 6 6-A: Si no se pueden guardar los resultados se cancela la ejecución y se muestra un mensaje de error. Estabilidad Media Importancia Alta 10 ID UC-02 Nombre Cargar imágenes Descripción El sistema deberá comportarse como se describe en el siguiente caso de uso cuando se vayan a cargar las imágenes elegidas. Precondición Ninguna. Secuencia normal Paso Acción 1 El sistema llama a una librería auxiliar para la carga de imágenes. 2 El sistema almacena las imágenes cargadas en memoria. Postcondición Las imágenes de entrada se encuentran en memoria. Excepciones Paso Excepción 1 1-A: Si no se pueden cargar las imágenes de entrada, se cancela la ejecución y se muestra un mensaje de error. Estabilidad Alta Importancia Alta ID UC-03 Nombre Ejecutar un algoritmo Descripción El sistema deberá comportarse como se describe en el siguiente caso de uso cuando se vaya a ejecutar el algoritmo elegido. Precondición Se han establecido los parámetros de forma correcta y cargado las imágenes de entrada. 11 Secuencia normal Paso Acción 1 El sistema lanza la ejecución del algoritmo elegido. 2 El algoritmo procesa las imágenes de entrada en base a los parámetros establecidos y genera un mapa de profundidad como salida. 3 El sistema almacena en memoria el mapa de profundidad generado. Postcondición El mapa de profundidad resultante del procesamiento de las imágenes de entrada de acuerdo a los parámetros establecidos se encuentra en memoria. Excepciones – Estabilidad Alta Importancia Alta ID UC-04 Nombre Medir rendimiento de la ejecución Descripción El sistema deberá comportarse como se describe en el siguiente caso de uso cuando se ejecute el algoritmo elegido. Precondición Ninguna. Secuencia normal Paso Acción 1 El sistema lanza la ejecución del algoritmo elegido con los parámetros seleccionados. 2 El sistema mide los resultados de la ejecución. 3 El sistema almacena en memoria los resultados de la ejecución. Postcondición Las medidas realizadas sobre la ejecución del algoritmo se encuentran en memoria. Excepciones – Estabilidad Alta Importancia Alta 12 ID UC-05 Nombre Guardar mapa de profundidad Descripción El sistema deberá comportarse como se describe en el siguiente caso de uso cuando se vaya a almacenar el mapa de profundidad resultante de la ejecución de un algoritmo. Precondición El sistema dispone del mapa de profundidad en memoria y se ha establecido la ruta donde debe ser almacenado. Secuencia normal Paso Acción 1 El sistema llama a una librería auxiliar para almacenar el mapa de profundidad como una imagen en el sistema de archivos. Postcondición Se ha almacenado el mapa de profundidad resultante del procesamiento de un par de imágenes mediante uno de los algoritmos como una imagen en el sistema de archivos. Excepciones Paso Excepción 1 1-A: Si no se puede realizar una escritura en la ruta especificada, se cancela la ejecución y se muestra un mensaje de error. Estabilidad Alta Importancia Alta ID UC-06 Nombre Guardar resultados en fichero Descripción El sistema deberá comportarse como se describe en el siguiente caso de uso cuando se vayan a volcar a un fichero las mediciones realizadas sobre la ejecución de un algoritmo. Precondición El sistema dispone de las mediciones en memoria y se ha seleccionado la opción de guardarlas en un archivo, estableciendo la ruta del fichero donde han de ser volcadas. Secuencia normal Paso Acción 1 El sistema imprime en formato legible los resultados de las mediciones en un archivo de texto en la ruta especificada. Postcondición Las medidas realizadas sobre la ejecución del algoritmo se encuentran en formato legible en el archivo de texto correspondiente a la ruta especificada. 13 Excepciones Paso Excepción 1 1-A: Si no se puede realizar una escritura en la ruta especificada, se cancela la ejecución y se muestra un mensaje de error. Estabilidad Media Importancia Media 2.3. Requisitos En base a los objetivos fijados y a las reuniones realizadas con los tutores del proyecto, se ha identificado una serie de requisitos que habrá de cumplir el software que se quiere desarrollar para que cumpla con los criterios de aceptación establecidos. Estos se dividen en dos grandes categorías: funcionales y no funcionales. Para su clasificación, se le ha asignado un identificador a cada uno, consistente en el prefijo RF para los funcionales y RNF para los no funcionales, seguidos del número correspondiente. También se aporta para cada uno una breve descripción y el nivel de importancia para el proyecto, que puede ser Necesario, si se considera imprescindible para la consecución del proyecto, o Deseable, si no es imprescindible pero ayudaría a mejorar la calidad del producto. 2.3.1. Requisitos funcionales Los requisitos funcionales representan aquellas funcionalidades o tareas que se espera que el software desarrollado vaya a cumplir. Se listan a continuación los que se han identificado para este proyecto: ID RF-01 Descripción Implementación del algoritmo de Stereo Matching conocido como Pixel-wise Matching, así como de su versión optimizada. Importancia Necesario ID RF-02 Descripción Implementación del algoritmo de Stereo Matching conocido como Patch-wise Matching en su versión basada en SAD (Sum of Absolute Differences), así como de su versión optimizada. Importancia Necesario ID RF-04 14 Descripción Implementación del algoritmo de Stereo Matching conocido como Patch-wise Matching en su versión basada en ASD (Adaptive Support Weight), así como de su versión optimizada. Importancia Necesario ID RF-05 Descripción Implementación del algoritmo de Stereo Matching conocido como Semi-Global Matching, así como de su versión optimizada. Importancia Necesario ID RF-06 Descripción Lectura y carga de las imágenes utilizadas como entrada para la ejecución de los algoritmos de Stereo Matching. Importancia Necesario ID RF-07 Descripción Escritura en el sistema de archivos de las imágenes resultantes de la aplicación de los distintos algoritmos. Importancia Necesario ID RF-08 Descripción Obtención de medidas de rendimiento de la ejecución de cada uno de los algoritmos. Importancia Necesario ID RF-09 Descripción Posibilidad de escritura en formato legible de los resultados de la ejecución de los algoritmos en un fichero de texto. Importancia Deseable ID RF-10 Descripción Posibilidad de selección de los parámetros de ejecución de los algoritmos. Importancia Necesario ID RF-11 Descripción Posibilidad de paso de parámetros de ejecución por línea de comandos para poder establecerlos sin necesidad de re-compilación. Importancia Deseable 15 2.3.2. Requisitos no funcionales Los requisitos no funcionales representan características requeridas del sistema, proceso de desarrollo, servicio prestado o cualquier otro aspecto del desarrollo que no implique específicamente la construcción de una funcionalidad. Se listan a continuación los que se han identificado para este proyecto: ID RNF-01 Descripción El software deberá correr de forma correcta sobre las arquitecturas elegidas, que serán sistemas basados en Linux. Importancia Necesario ID RNF-02 Descripción Las versiones mejoradas de los diferentes algoritmos deberán ofrecer incrementos en el rendimiento respecto a las implementaciones base. Importancia Deseable ID RNF-03 Descripción El software incluirá un front-end que cubra las funcionalidades básicas del software para lanzarlo desde una interfaz gráfica. Importancia Deseable 2.4. Metodología Antes de transformar estos requisitos en bloques de actividades y asignarles dependencias y flujo temporal, es importante definir la metodología con la que se ha de abordar el proyecto. Para ello, consideraremos las características de este último y analizaremos qué modelo de ciclo de vida se adapta mejor a la presente situación. El proyecto tiene un enfoque individual, de modo que no existe la necesidad de ponerse de acuerdo con un equipo o explicar los puntos de vista de cada integrante, por lo que no será necesario profundizar demasiado en el diseño o los procesos de ingeniería del software: con que el alumno tenga claro lo que va a desarrollar y cómo, es suficiente. Por otra parte, a pesar de que no se espera que los requisitos sean cambiantes, dado que el proyecto es en esencia un estudio de investigación y, como tal, carece de cliente que pueda cambiar de opinión frecuentemente; el plazo límite de entrega es rígido y, por lo tanto, un factor limitante considerable. El alcance podría verse limitado por un desarrollo menos veloz de lo previsto, lo que obligaría a adaptar la planificación a los cambios. Estas modificaciones deberían poder realizarse en el menor tiempo 16 posible ya que, de otro modo, el tiempo invertido en redistribuir la susodicha planificación podría obligar a reducir el alcance de nuevo. El anterior riesgo de modificación del alcance para adaptarse al plazo podría verse acentuado por el hecho de que se tratará con un campo de investigación en el que el alumno carece de experiencia, utilizando algunas tecnologías con las que no está familiarizado en profundidad, como puede ser OpenMP. También hay que tener en cuenta que se probarán diferentes enfoques de optimización y que, si no se obtienen los resultados esperados, podría ser necesaria la inclusión de algún otro. Por todo lo anterior, no se espera que las estimaciones temporales iniciales sean extremadamente precisas. Respecto al tamaño, en lo referente al código desarrollado este proyecto podría considerarse como bastante reducido, lo que refuerza lo que ya se había dicho con anterioridad: se espera que no sea necesaria una documentación intensiva y que un estilo de programación ágil, sin mucha carga en los procesos de ingeniería de software, se vea favorecido. Dadas las características anteriores, se puede concluir que el ciclo de vida que mejor se adaptará al presente proyecto será aquel que permita un desarrollo ágil, ligero en los apartados de ingeniería de software, diseño y documentación, y que permita una planificación flexible y adaptativa en función de la velocidad de avance. Un método iterativo permitiría, además, introducirse en los aspectos desconocidos rápidamente para calcular el tiempo que lleva en realidad su desarrollo y tener lo antes posible una estimación fiable del trabajo restante. Todo esto lleva a pensar que la metodología idónea en este caso es la conocida como Programación Extrema, cuyas características se exponen en el siguiente punto. 2.4.1. Programación Extrema La Programación Extrema [9] es una metodología ágil que se centra en el desarrollo del código: la filosofía que encierra es la de desarrollo y prueba continuos, adaptando de forma dinámica la planificación cuando los requisitos cambian o la velocidad de avance no es la esperada, utilizando el código como la propia documentación cuando esto sea posible, y reduciendo la carga de los procesos de ingeniería de software. Este modelo de ciclo de vida software está pensado para el trabajo en equipos pequeños o medianos, y se basa en el seguimiento de buenas prácticas, que se pueden resumir en los siguientes puntos:  Revisión y mejora continuas del código  Simplicidad del diseño  Iteraciones cortas 17  Entregas continuas para testeo del avance El código, por lo tanto, se desarrollará en pequeñas iteraciones que nos permitan verificar y validar los módulos desarrollados antes de incluir otros nuevos, y reducir o aumentar el alcance en función de la velocidad de avance relativa a la planificación, que será ligera y fácilmente adaptable. 2.5. Planificación temporal En este apartado se aborda la identificación de los bloques de trabajo principales que se han de llevar a cabo para que el proyecto tenga éxito, así como las previsiones para su distribución a lo largo del tiempo. Esto se conseguirá por medio de un esquema del tipo EDT (Estructura de Descomposición del Trabajo) para el primer fin, y un diagrama de Gantt para el segundo. 2.5.1. Estructura de Descomposición del Trabajo Un esquema de tipo EDT consiste en una representación jerárquica de los principales bloques de actividades necesarias para la correcta compleción del proyecto que se hayan identificado, desglosándolas por niveles hasta llegar a un nivel de granularidad manejable para una planificación temporal. En la figura 2.2 se adjunta como una imagen la Estructura de Descomposición del Trabajo generada para este proyecto: 18 FIGURA 2.2: ESTRUCTURA DE DESCOMPOSICIÓN DEL TRABAJO 25 ID RS-08 Descripción La inexperiencia en las tecnologías utilizadas, como OpenMP, así como en el estudio de los algoritmos de Stereo Matching, ralentiza el proceso de desarrollo. Probabilidad Media Impacto Alto Indicador Se ha dedicado más tiempo del estipulado en la planificación al aprendizaje de una de las tecnologías utilizadas en el proyecto. Plan de prevención Reducir el uso de tecnologías desconocidas a aquellas que sean necesarias y buscar las alternativas mejor documentadas. Realizar, asimismo, una planificación pesimista del tiempo que hará falta para familiarizarse con ellas. Plan de contingencia Tratar de utilizar una alternativa más sencilla para el propósito correspondiente, o reducir el alcance del proyecto si es pertinente y necesario. 2.7. Gestión de la configuración En este apartado se explica la metodología seguida durante el proyecto en lo que a gestión de la configuración respecta. Esto incluye la identificación de los elementos de configuración y la selección de las herramientas informáticas utilizadas para mantener sus versiones. Cabe añadir que la función del proceso de gestión de la configuración en este proyecto es meramente la de mantener un control de versiones, ya que no se realizará trabajo de forma concurrente por parte de varias personas: el alumno será el único que modifique los elementos de configuración. Esto se ha tenido en cuenta a la hora de realizar la planificación de la gestión de configuración, adaptándola a los fines que realmente tendrá, aligerando el peso de este proceso durante el desarrollo del proyecto. 2.7.1. Identificación de los elementos de configuración Los elementos de configuración identificados son los siguientes:  Código fuente  Memoria del proyecto  Planificación del proyecto  Diseño del software construido Todos estos elementos, excepto el código fuente, por motivos de simplificación del desarrollo, se regirán por la siguiente nomenclatura: 26 <Tipo de documento>_<DDMMAA>_<Descripción>_v<Versión> Los tipos de documentos son los que se recogen en la tabla siguiente: Tipo de documento Descripción Código Memoria del proyecto Documento base con la información principal del proyecto desarrollado. MDP Planificación del proyecto Documento con la planificación temporal de las actividades del proyecto. PTP Diseño del software codificado Documento que incluye diferentes diagramas utilizados para la implementación del software objeto de este proyecto. DSC 2.7.2. Herramientas de gestión de configuración En la selección del software de soporte a la gestión de configuración para este proyecto, se ha hecho una distinción fundamental entre los elementos de configuración en dos categorías: el código fuente de la aplicación y la documentación. Para controlar el versionado de los archivos del código fuente, se ha considerado que la herramienta más cómoda es un repositorio de tipo GIT; y se ha optado por alojarlo en la web BitBucket [10] para simplificar su compartición con los tutores del proyecto. Esto facilita en gran medida tareas como recuperar configuraciones anteriores del código fuente, analizar las diferencias existentes entre ellas o mezclar diferentes versiones de la configuración de forma interactiva. Por otra parte, para mantener las diferentes versiones de la documentación se ha utilizado Google Drive [11], que permite recuperar las últimas versiones guardadas de cada archivo, compartirlas de forma sencilla y mantener una cómoda estructura en carpetas integrada con el sistema de archivos mediante su cliente de escritorio. Además, es un sistema gratuito que ofrece una cantidad de espacio de almacenamiento elevada en su versión básica. Se ha prescindido de la utilización de GIT para esta finalidad por varios motivos:  Es más simple modificar los archivos directamente en el sistema de ficheros, sin perder la posibilidad de recuperar versiones anteriores.  Las conexiones entre ficheros no son tan importantes como en el código fuente, que es probable que necesite que todos los archivos estén en la versión correspondiente de forma simultánea para poder compilarlos. 27  Un repositorio GIT no ayuda con la diferenciación entre versiones de archivos binarios, considerando los ficheros con formato de Word como tales. 2.8. Análisis de costes En este apartado se analiza el coste económico proveniente de la realización de este proyecto. Se ha planteado como un estudio hipotético en el que el alumno es un trabajador asalariado para obtener una cifra aproximada más realista. Para este análisis, se han identificado las siguientes fuentes de gastos potenciales:  Estación de trabajo: Para el desarrollo de este proyecto se han utilizado como estaciones de trabajo un ordenador portátil, propiedad del alumno, que no ha supuesto ningún coste adicional por lo tanto; y un equipo de sobremesa adquirido por el CITIUS, por un precio de 1.100€.  Servidor de ejecución: Parte de las pruebas han sido realizadas sobre un servidor Xeon y su coprocesador Xeon Phi, propiedad del CITIUS. Estos ya habían sido adquiridos con otros fines, y su utilización para este proyecto no supone ningún coste adicional. La amortización del equipo supone una cantidad poco significativa y no se incluye en el estudio.  Placa Parallella: Se ha trabajado con esta placa a lo largo del proyecto, y consiste en un microprocesador multinúcleo portátil. Este ha sido entregado de forma gratuita al CITIUS para su promoción por parte de la empresa vendedora, de modo que no ha supuesto coste alguno.  Software utilizado: Todo el software utilizado para el desarrollo de este proyecto es gratuito, excepto la suite de ofimática Microsoft Office 2010 en su versión Home, que estaba instalada en el ordenador portátil del alumno y en su momento costó 119€. No obstante, la amortización de este software a través de su uso para todo tipo de proyectos ha comenzado hace cuatro años, lo que hace que la cantidad que se debería amortizar en este sea despreciable, con lo que no se computará en la suma de costes. 28  Mano de obra: Como ya se ha mencionado, para aportar realismo a estos datos se ha considerado que el alumno es un trabajador pagado. Para esta estimación, se ha establecido como su rol el de Analista Programador. Tras una investigación en diferentes portales de búsqueda de trabajo, como por ejemplo InfoJobs [12] o Job and Talent [13], se ha establecido que esto supondría un sueldo por hora de aproximadamente 16,51€. El desglose de los costes relativos al uso de esta mano de obra en las diferentes actividades planificadas puede verse en la siguiente tabla extraída del informe realizado de forma automática por el software de planificación: ID Actividad Coste 0 Trabajo de Fin de Grado 6.809,55€ 1 Estudio previo 1.702,59€ 1.1 Identificación de algoritmos del estado del arte 429,26€ 1.2 Estudio de propiedades de los algoritmos 610,87€ 1.3 Selección de arquitecturas objetivo 231,14€ 1.4 Estudio de las arquitecturas objetivo 431,32€ 2 Implementación 2.979,64€ 2.1 Pixel-wise Matching 542,77€ 2.1.1 Codificación secuencial 501,50€ 2.1.2 Codificación paralela 41,27€ 2.2 Patch-wise Matching 658,33€ 2.2.1 Codificación secuencial 617,06€ 2.2.2 Codificación paralela 41,27€ 2.3 Semi-Global Matching 1.365,79€ 2.3.1 Codificación secuencial 584,04€ 2.3.2 Codificación paralela 781,75€ 2.4 Adaptación a las arquitecturas objetivo para mejorar el rendimiento 412,75€ 3 Análisis de resultados 850,27€ 3.1 Medición de rendimiento en la ejecución sobre los datos de muestra 412,75€ 3.2 Estimación y justificación de la mejoría obtenida 437,52€ 4 Elaboración de la memoria 1.277,05€ 4.1 Recopilación de resultados 203,90€ 4.2 Redacción de la memoria 1.073,15€ Esto nos deja con el siguiente desglose de costes para los paquetes de trabajo definidos en la sección del esquema EDT: 29  1.1.1 Identificación de algoritmos del estado del arte: 429,26€  1.1.2 Estudio de propiedades de algoritmos: 610,87€  1.1.3 Selección de arquitecturas objetivo: 231,14€  1.1.4 Estudio de las arquitecturas elegidas: 431,32€  1.2.1 Codificación secuencial de los algoritmos estudiados: 1.702,59€  1.2.2 Codificación paralela de los algoritmos estudiados: 864.29€  1.2.3 Adaptación a las arquitecturas objetivo para mejorar el rendimiento: 412,75€  1.3.1 Medición de rendimiento en la ejecución sobre los datos de muestra: 412,75€  1.3.2 Estimación y justificación de la mejoría obtenida: 437,52€  1.4.1 Recopilación de resultados: 203,90€  1.4.2 Redacción de la memoria: 1.073,15€ Además de los costes recogidos en los puntos anteriores, hay que tener en cuenta otros gastos indirectos como puede ser el consumo eléctrico, tanto de los servidores como de las estaciones de trabajo utilizadas. Siguiendo las políticas de la USC, se ha decidido calcular estos como un 20% del total [14]. En base a todo lo anterior, se puede deducir la siguiente tabla de costes del proyecto por fuentes potenciales: 30 Fuente Coste estimado Estación de trabajo 1.100€ Servidor de ejecución 0€ Placa Parallella 0€ Software utilizado 0€ Mano de obra 6.809,55€ Costes indirectos 1.581,91€ TOTAL 9491,46€ 31 3. HERRAMIENTAS USADAS En este apartado se analizan las herramientas que se han utilizado durante el desarrollo del proyecto, explicando la funcionalidad de cada una y los motivos de su elección. Separaremos, por lo tanto, las susodichas herramientas en distintas categorías para su tratamiento. 3.1. Herramientas de desarrollo software Dado que las arquitecturas objetivo para la ejecución del software desarrollado corren sistemas basados en Linux, se ha decidido utilizar este sistema operativo para las labores de construcción del mencionado programa. Se ha optado por la distribución Ubuntu, que es la que utilizan todas las susodichas arquitecturas, para minimizar problemas de compatibilidad. La popularidad de esta distribución, además, garantiza que el producto podrá ser exportado a muchos otros sistemas de forma directa. Este sistema ya se encuentra instalado en la estación de trabajo del CITIUS por defecto, y había sido instalado con anterioridad por el alumno en su ordenador portátil personal. El sistema operativo utilizado ha condicionado la selección de las herramientas de desarrollo software. Estas han sido las que se listan a continuación:  Gedit: Se ha utilizado este editor de texto para la escritura del código fuente, así como para la visualización de los ficheros de texto con resultados generados por este. Viene instalado de serie con la distribución de Ubuntu y es un editor muy flexible y completo, con todas las funcionalidades necesarias para el desarrollo de software a pequeña escala. Se había considerado como alternativa el IDE NetBeans, pero ha sido descartado porque la versión del repositorio de Ubuntu carece de módulo para desarrollo en C/C++, y la versión descargable desde la web no es muy estable y se ha podido comprobar que tiene fallos ocasionales que hacen muy incómodo utilizarlo. Por otra parte, el software desarrollado es de tamaño reducido, con lo cual no se ha considerado necesaria la utilización de una herramienta IDE para la gestión del desarrollo.  G++/Comando make/ICC: En lo referente a la compilación del código generado, se ha optado por estas herramientas. El comando make de los sistemas Linux simplifica en gran medida la sistematización de una compilación reiterada con diversos parámetros que no varían, como las librerías utilizadas o el nombre del archivo de output; que pueden agruparse en un makefile. Por otra parte, G++ es el compilador más 32 popular de C++ en sistemas Linux: viene instalado de serie en la distribución Ubuntu, está ampliamente testado, resulta sencillo de utilizar y es muy completo, cubriendo todas las necesidades previstas en el desarrollo de este proyecto. No obstante, para la compilación del código en el procesador Xeon y en el coprocesador Xeon Phi se ha utilizado la herramienta de Intel, ICC, que debería generar un código optimizado para estas arquitecturas y proporciona especialmente muchas facilidades para el desarrollo orientado al Xeon Phi: permite la compilación cruzada desde el Xeon hacia la arquitectura del Xeon Phi para el posterior envío del ejecutable (se comportan como máquinas separadas) y ejecución nativa en el coprocesador; así como la compilación directa con secciones offload, cuyo procesamiento recaerá sobre el coprocesador, dejando para la máquina principal el resto de cálculos.  Cliente por consola de SSH/SCP: El alumno no dispone de acceso local directo al servidor que contiene las arquitecturas que se consideran en el trabajo, de modo que el trabajo en esta máquina se realiza mediante acceso remoto utilizando el cliente por consola de SSH que viene instalado de serie en la distribución Ubuntu. Por otra parte, el acceso a Internet desde este servidor está filtrado, y no se permite la conexión al repositorio GIT remoto en BitBucket, por lo que la transferencia del código fuente para compilar se realiza mediante el cliente por consola de SCP que también viene pre-instalado en la citada distribución. Además, como ya se ha dicho, el procesador y el coprocesador funcionan como máquinas diferentes, de modo que para trabajar de forma nativa con el Xeon Phi se realiza un acceso remoto desde el Xeon mediante SSH y para el envío del ejecutable compilado en el procesador principal se utiliza SCP.  Red VPN del CITIUS y cliente VPN de Ubuntu: El acceso remoto a la estación del servidor solamente se puede realizar desde la red interna del CITIUS. Es por ese motivo que para el trabajo desde fuera del CITIUS el alumno ha utilizado el servicio de red VPN del CITIUS, al que se accede a través del cliente VPN integrado en la distribución de Ubuntu utilizada (14.04).  Librería OpenMP [15]: Se ha decidido utilizar el framework OpenMP para el desarrollo de las versiones paralelas de los algoritmos. Es un estándar ampliamente testado y su eficiencia ha sido demostrada. La documentación disponible es muy extensa, y tiene un soporte muy 33 importante por parte de la comunidad. Su utilización es realmente sencilla ya que, por ejemplo, con un cambio mínimo como puede ser una línea de código con una directiva, se puede paralelizar de forma eficiente un bucle con un reparto equitativo de las iteraciones entre varios hilos, mucho más breve y conciso que alternativas como puede ser la librería POSIX Threads, sin perder por ello opciones de personalización. También se encarga automáticamente de la gestión de muchos aspectos de la paralelización, liberando al programador de esta tarea, que puede muchas veces ser realizada de forma óptima o muy eficiente por la propia máquina.  Librería de tratado de imágenes: Se ha utilizado una librería externa para gestionar la interacción con imágenes: proporciona métodos sencillos para cargarlas en memoria, operar con ellas como matrices de píxeles y guardarlas como ficheros en el sistema de archivos. Se dispone del código fuente, que es compilado como parte del propio programa. Es muy sencilla en su manejo: solamente se necesitan un par de funciones con sintaxis muy clara y el acceso a las matrices de píxeles se ha simplificado mediante el uso de macros. No obstante, cubre todas las necesidades del software desarrollado, reconociendo el formato de imágenes con el que se trabaja (PGM, en escala de grises).  GIT: Como ya se ha explicado en el apartado de gestión de la configuración, para el control de versiones del código fuente se ha utilizado la herramienta GIT, con un repositorio online en la página BitBucket. Para el acceso a este, se han considerado diversos clientes gráficos disponibles en los repositorios de Ubuntu. No obstante, todas estas herramientas han resultado tener una integración bastante pobre con repositorios remotos, por lo que se ha decidido utilizar directamente el cliente por consola, disponible también en el repositorio de Ubuntu. Este es, además, mucho más flexible y completo que las versiones gráficas, y permite un control mayor de las acciones por parte del usuario. A pesar de esto, la carencia de interfaz gráfica resulta inconveniente en algunos puntos, como la revisión del historial de commits realizados o la comparación entre diferentes versiones de un mismo archivo o diferentes commits. Para suplir estas faltas, se ha utilizado el software Giggle, aunque su uso se ha restringido a front-end de visualización, delegando, como ya se ha dicho, la interacción con el repositorio remoto en la aplicación de consola. 34  Visualizador de imágenes de GNOME: Para la visualización de los mapas de profundidad resultantes del procesamiento de pares de imágenes de entrada, así como para la de estas últimas, se ha utilizado la herramienta de visualización de imágenes de GNOME, que viene instalada por defecto en la distribución Ubuntu utilizada.  NetBeans IDE: A pesar de que la mayoría del código se ha desarrollado utilizando el editor de texto Gedit y compilación manual por consola por los motivos que ya se han explicado, se ha utilizado esta herramienta para el desarrollo de un front-end en Java Swing para la aplicación. Esto se debe a que las ya mencionadas carencias de la versión para Linux de este entorno de desarrollo integrado no afectan a los módulos de producción en Java. Por lo tanto, se ha considerado que el desarrollo sería mucho más rápido utilizando esta herramienta por las funcionalidades que incorpora, como el auto-completado o la generación automática de código pero, especialmente, por la paleta que permite el desarrollo de interfaces gráficas basadas en Java Swing de forma muy sencilla, directa y visual, con la posibilidad de utilización mediante un sistema de drag & drop. 3.2. Herramientas para el desarrollo de la documentación El desarrollo de la documentación de este proyecto se ha llevado a cabo de forma íntegra en el ordenador portátil personal del alumno. La elección del sistema operativo utilizado con esta finalidad se ha basado en la disponibilidad de herramientas compatibles, así como en la disponibilidad del propio sistema operativo. En el ya mencionado ordenador, se encontraba instalado con anterioridad para otros fines Windows 7 Home Premium, en su versión de 64 bits, el cual ha sido seleccionado como base para el desarrollo de la documentación. Las herramientas utilizadas para el desarrollo de la documentación de este proyecto son las que se listan a continuación:  WBS Tool: Esta herramienta web se ha utilizado para la generación del esquema de tipo Estructura de Descomposición del Trabajo (WBS por sus siglas en inglés), requerido en la parte de gestión del proyecto. Se ha elegido por la sencillez y agilidad de uso que permite, así como por el hecho de ser una herramienta gratuita que cumple con todas las funciones necesarias: crear una representación gráfica de la descomposición del proyecto en bloques de trabajo, que se pueda 41 FIGURA 4.4: PANTALLA DE RESULTADOS DEL FRONT-END 42 FIGURA 4.5: PANTALLA DE RESULTADOS DEL FRONT-END CON DATOS DE RENDIMIENTO Como se puede ver, se ha optado por un diseño minimalista, mediante un formulario con el mínimo número de campos necesarios para funcionar, sin incluir todas las opciones que ofrece la interacción directa por línea de comandos. También se puede observar que el número de campos visibles varía en función de los parámetros seleccionados. En lo referente a la pantalla de resultados, como se puede observar, muestra la imagen base del par sobre el que se ha realizado la computación junto al mapa de profundidad generado para ella. Ambas imágenes se escalan para que encajen en los correspondientes paneles, respetando las proporciones entre ancho y alto originales. 43 Por otra parte, se incluye un área de texto en la que, en caso de haber seleccionado la opción de almacenar los resultados de la ejecución, estos se muestran en un formato de texto legible. 4.2. Línea de comandos desde consola Como ya se ha mencionado, esta es la opción que permite una máxima flexibilidad de uso, a costa de una menor agilidad y comodidad. Incluye todas las posibles opciones de personalización diseñadas para lanzar los algoritmos, como se puede observar en la pantalla de ayuda de la Figura 4.6 que se ofrece al hacer una introducción de parámetros que no se adapta a la sintaxis esperada: FIGURA 4.6: AYUDA POR LÍNEA DE COMANDOS Este componente se ha añadido pensando en aportar la posibilidad de desarrollar un front-end completamente independiente del programa, que pueda usar cualquier tipo de tecnología que permita hacer una llamada al sistema operativo para lanzar un archivo ejecutable con determinados parámetros. En este caso, como ya se ha explicado, se ha aprovechado mediante una GUI basada en Java Swing. En cualquier caso, aunque no se hubiese desarrollado un front-end, esto permitiría la entrada de parámetros en tiempo de ejecución, sin tener que compilar todo el código fuente cada vez que se quiere modificar alguno. 44 4.3. Back-end en C++ El grueso de la funcionalidad de este software se encuentra en este componente, que recibe parámetros de ejecución por medio de la interfaz de línea de comandos. Desde aquí se gestiona la lectura de los mencionados parámetros, la solicitud de carga y guardado de imágenes, la ejecución de las mediciones de rendimiento sobre los algoritmos de Stereo Matching, así como la de estos mismos, y el almacenamiento de los resultados, si procede. Este componente se ha escrito en C++ para integrar en él los bloques de código de procesamiento Stereo Matching y mediciones. 4.4. Mediciones de rendimiento Este componente se encuentra integrado como parte del código del back-end, y consiste en una estructura que permite realizar medidas de rendimiento sobre la ejecución de los algoritmos objeto de este estudio, caracterizado este por el tiempo necesario para llevar a cabo la computación. Se ha diseñado de modo que permita hacer un número arbitrario de medidas independientes sobre la misma ejecución, definido por una constante en tiempo de compilación. De este modo, se puede medir en una sola prueba el rendimiento de varias secciones del algoritmo, lo que resulta muy útil para comparar por secciones las ganancias obtenidas a través del proceso de paralelización y optimización. Por lo tanto, los resultados aportados por este componente para una ejecución del programa consisten en un vector de tiempos de ejecución por áreas de código. 4.5. Algoritmos de Stereo Matching Este componente es el más importante de la arquitectura, ya que contiene el objeto de este estudio. Está constituido por las diferentes versiones de los algoritmos de Stereo Matching, incluidas simultáneamente como diferentes funciones en un mismo archivo de código fuente para que el back-end pueda llamar a una u otra en base a los parámetros que haya recibido como entrada. Este bloque es el determinante para la elección de la tecnología de implementación del back-end, ya que tiene unos requerimientos de rendimiento muy importantes, por lo que se ha decidido que su programación debe realizarse en C++, más complejo que otros lenguajes modernos, pero con un gran nivel de control sobre las operaciones que la máquina lleva a cabo y gran eficiencia demostrada en incontables benchmarks comparativos. Estos algoritmos serán explicados en detalle en el capítulo 5. 4.6. Librería de tratado de imágenes Para evitar la pérdida de tiempo en el desarrollo de software para manipular imágenes en el formato que se ha elegido para este estudio (PGM) y centrarnos en la 45 construcción de los componentes dentro del ámbito de interés definido por el proyecto, se ha decidido delegar esta funcionalidad en una librería externa. Todas las llamadas para cargar y guardar imágenes se realizan, por lo tanto, a través de este componente, que ofrece una interfaz sencilla para esto, así como macros que permiten acceder de forma simple a los contenidos como matrices de píxeles. Esta librería se ha obtenido en forma de código fuente, que es compilado con el programa desarrollado por el alumno. 4.7. Sistema de archivos Este componente consiste en el propio sistema de archivos del sistema operativo, en el cual se encuentran las imágenes de entrada para los algoritmos, y al cuál se debe acceder para la escritura de los mapas de profundidad generados, así como los resultados de rendimiento si procede. Todos los accesos relacionados con imágenes se realizan, como ya se ha dicho, a través de la librería externa, mientras que los archivos de texto se generan directamente desde el back-end. 46 5. ALGORITMOS ESTUDIADOS En esta parte se identificarán los algoritmos que se han elegido para este proyecto de fin de grado, y se realizará un análisis de sus propiedades, así como una explicación sobre su funcionamiento. Cabe recordar que estos algoritmos solamente tratan el emparejamiento de píxeles entre dos imágenes y la construcción de mapas de profundidades relativas. Como ya se ha explicado con anterioridad, el cálculo de distancias reales está fuera del alcance definido para este proyecto. También es importante tener en cuenta el hecho de que se trabaja con imágenes pre-procesadas en las que las líneas epipolares coinciden con las filas de píxeles y para las cuales se dispone de un rango de búsqueda calculado experimentalmente. Los algoritmos seleccionados son el Pixel-wise Matching [2], el Patch-wise Matching [3] en dos de sus variantes, y el Semi-Global Matching [2]. 5.1. Pixel-wise Matching Es el algoritmo más simple de Stereo Matching. Se ha elegido como método de introducción al desarrollo de software en este campo. A pesar de que su precisión es muy limitada y nunca se utiliza de forma directa, sí puede servir como base para la implementación de algoritmos o para aprovechar su salida como punto de partida para un proceso que optimice el resultado, como en el caso del Semi-Global Matching. El funcionamiento del algoritmo consiste en los siguientes pasos (suponiendo una comparación de izquierda a derecha, para la inversa simplemente se cambia el orden): 1. Para cada píxel de la imagen base: a. Se compara con la misma posición de la otra imagen, así como las que estén dentro del rango de búsqueda hacia la izquierda, en base a sus valores de intensidad (dado que la cámara se ha movido hacia la derecha, si el píxel con el que se corresponde no está ocluido, deberá estar en la línea epipolar hacia la izquierda de esas coordenadas). b. Se elige el primer píxel con la intensidad más similar al original como mejor candidato de emparejamiento. c. Se almacena la distancia entre las coordenadas del píxel original y las del mejor candidato en una matriz de resultados. 2. Para cada píxel de la matriz de resultados: 47 a. Se multiplica su valor de disparidad por un factor de escala para cubrir el mayor rango de valores posibles teniendo en cuenta que este resultado será almacenado como una imagen con 256 tonos de gris. Aplicados los pasos anteriores, tenemos como resultado una imagen en escala de grises que representa el mapa de profundidades relativas calculado para la escena, donde el gris más claro (mayores valores de disparidad) representa los puntos más cercanos a la cámara, y el gris más oscuro, los más lejanos. Podemos ver a continuación una imagen que ilustra este proceso en la Figura 5.1: FIGURA 5.1: ILUSTRACIÓN PIXEL-WISE MATCHING Como se puede ver, el orden de complejidad es muy reducido: simplemente se recorre la imagen haciendo un número fijo de comparaciones por cada píxel, determinado por el rango de búsqueda. Su principal desventaja es su falta de precisión, debida a la ambigüedad en el uso de un único valor de intensidad en una escala tan limitada y sensible a cambios en la iluminación, por ejemplo. Sin embargo, este es un algoritmo muy veloz y su implementación es muy sencilla. En la Figura 5.2 se incluye un ejemplo de resultado obtenido por medio de este algoritmo para la vista izquierda de un par de imágenes dadas, junto al mapa de profundidad utilizado como ground truth (resultado perfecto): 48 FIGURA 5.2: RESULTADOS PARA PIXEL-WISE MATCHING: (A) IMAGEN IZQUIERDA, (B) IMAGEN DERECHA, (C) MAPA DE PROFUNDIDAD CALCULADO, (D) GROUND TRUTH Como ya se había mencionado, los resultados obtenidos son muy pobres, con un 82.4556% de píxeles erróneos, sin contar los ocluidos, según el mapa de profundidad tomado como correcto, con una tolerancia igual al factor de escala. 5.2. Patch-wise Matching Este algoritmo representa una evolución directa del presentado en el punto anterior, como se puede ver en el siguiente desglose por pasos de su funcionamiento: 1. Para cada píxel de la imagen base: a. Se establece a su alrededor un parche rectangular de un tamaño prefijado. Para valores fuera de la imagen, se establece un valor de intensidad predeterminado. b. Se eligen los píxeles candidatos a emparejamiento en base al mismo criterio que el algoritmo anterior. c. Se compara este parche con otros del mismo tamaño establecidos alrededor de cada uno de los píxeles candidatos. Para esta comparación pueden seguirse 49 diferentes estrategias, que dan lugar a variaciones de este algoritmo de entre las cuales dos se contemplan en este estudio y se explicarán a continuación. d. Se elige como mejor candidato aquél cuyo parche haya tenido una mayor afinidad con el del píxel base, y se toma su separación en coordenadas respecto a las del original como medida de disparidad, agregándola a la matriz de resultados. 2. Para cada píxel de la matriz de resultados: a. Se multiplica su valor de disparidad por un factor de escala para cubrir el mayor rango de valores posibles teniendo en cuenta que este resultado será almacenado como una imagen con 256 tonos de gris. En la imagen de la Figura 5.3 se puede ver una ilustración de este proceso: FIGURA 5.3: ILUSTRACIÓN PATCH-WISE MATCHING Este método proporciona una mayor precisión que el Pixel-wise Matching debido a que hay más información disponible acerca de cada uno de los candidatos, lo que puede reducir en gran medida la ambigüedad para puntos parecidos. Esta mejoría depende fuertemente del sistema de comparación de parches utilizados. Por otra parte, hay que tener en cuenta que, en el tiempo que el algoritmo Pixel-wise Matching usaba para hacer una comparación entre dos píxeles, en este deben compararse dos parches, lo que multiplica la complejidad por un factor dependiente del tamaño del propio parche, respecto a la del algoritmo anterior. 50 5.2.1. Sum of Absolute Differences Sum of Absolute Differences [3] es la primera de las variaciones del Patch-wise Matching comprendidas en el alcance de este proyecto. Implica que para la comparación de dos parches se calcula la diferencia absoluta entre pares de píxeles en la misma posición (en coordenadas relativas dentro del rectángulo) y se toma la suma como coste de emparejamiento para el candidato. Además, se restringe el valor máximo de esta disparidad a una constante prefijada, de modo que dos píxeles claramente pertenecientes a zonas diferentes tengan siempre la misma diferencia entre sí. Esto supone que por cada comparación con un candidato, se han de realizar 𝑊∗𝐻+1 operaciones aritméticas básicas, donde 𝑊 es el ancho de la imagen, y 𝐻, el alto. Por otra parte existe un efecto de distorsión al seleccionar parches demasiado grandes con este método, debido a que se pueden estar incluyendo píxeles de diferentes objetos, con lo que los bordes se verán deformados en el mapa de profundidad. Es necesario, por lo tanto, buscar un balance adecuado en el tamaño de los parches, atendiendo a que:  Si son demasiado pequeños, no se aportará mucha información adicional al considerar un candidato por parte de su vecindario, por ser este muy reducido, con lo que la ambigüedad del criterio aumenta.  Si son demasiado grandes, los bordes estarán difuminados por el efecto antes mencionado. Además, el tiempo de procesamiento depende del tamaño del parche, con lo que al algoritmo se volverá más lento. También se puede utilizar este método en combinación con algoritmos de detección de bordes para reducir el efecto mencionado, aunque esto está fuera del alcance de este proyecto y no se ha probado. En la figura 5.4 se incluye un ejemplo de resultado obtenido por medio de este método para la vista izquierda de un par de imágenes dadas, junto al mapa de profundidad utilizado como ground truth para un tamaño de ventana de 11x11: 57 𝑃2 las penalizaciones pequeña y grande por discontinuidad de la profundidad, respectivamente. Esta ecuación favorece que píxeles vecinos tengan profundidades similares, ya que para para disparidades similares a la mejor candidata del píxel anterior en la dirección actual se sumará menos coste adicional. La substracción del último término se explica como un controlador para evitar que el coste se vaya acumulando a lo largo de la dirección hasta valores extremos. No afecta a los cálculos sobre el píxel actual, ya que se resta el mismo valor para todas las disparidades. b. Para los píxeles que no tengan ningún predecesor en la dirección elegida, se toma directamente el coste pre-calculado en la fase inicial como coste de la restricción de suavidad de la dirección actual. Esto se aplica para todas las disparidades posibles del píxel. c. El cálculo realizado para cada disparidad de cada píxel se agrega a la matriz de resultados en la posición correspondiente. 5. Con la matriz de reducción resultante de haber aplicado la restricción de suavidad en todas las direcciones y sentidos elegidos, para cada píxel se elige como mejor candidata la disparidad que tenga un menor coste acumulado, agregándola a la matriz de resultados. 6. Para cada píxel de la matriz de resultados: a. Se multiplica su valor de disparidad por un factor de escala para cubrir el mayor rango de valores posibles teniendo en cuenta que este resultado será almacenado como una imagen con 256 tonos de gris. En base a lo expuesto, podemos observar que la cantidad de cálculos necesarios por candidato no es muy elevada, con un coste computacional para los valores iniciales despreciable y muy liviano para la aplicación de la constante de suavidad a lo largo de las direcciones elegidas, dependiente de estas últimas. Por otra parte, el tener en cuenta los diferentes objetos de la escena como superficies con la misma profundidad, dejando un ligero margen para superficies curvas (la penalización para la diferencia unitaria de profundidad entre píxeles vecinos es mucho menor que para disparidades mayores), garantiza un buen grado de 58 coherencia en la asignación de profundidades a los distintos puntos de la imagen, especialmente en escenarios con pocos objetos que estén bien definidos. En la Figura 5.8 se incluye un ejemplo de resultado obtenido por medio de este algoritmo para la vista izquierda de un par de imágenes dadas, junto al mapa de profundidad utilizado como ground truth: FIGURA 5.8: RESULTADOS PARA SEMI-GLOBAL MATCHING: (A) IMAGEN IZQUIERDA, (B) IMAGEN DERECHA, (C) MAPA DE PROFUNDIDAD CALCULADO, (D) GROUND TRUTH Se puede observar que se han respetado las superficies de los objetos, cuyos valores de profundidad son muy homogéneos. También es reseñable que, a pesar de haber partido del resultado de la aplicación del algoritmo Pixel-wise Matching como solución inicial, que ofrecía un resultado de 82.4556% de píxeles mal calculados para este mismo par de imágenes, se ha obtenido un 7.95965% de píxeles incorrectos por medio de la aplicación de la restricción de suavidad, menos de un 10% de los del resultado original. 59 6. ARQUITECTURAS HARDWARE CONSIDERADAS En este capítulo se tratarán en profundidad las arquitecturas paralelas consideradas para la realización de este estudio. Como ya se ha dicho en la Introducción, estas son:  Intel Xeon E5-2630Lv2 [5]  Intel Xeon Phi 7120P [6]  Placa Parallella [7] Como ya se ha mencionado previamente, no se han podido realizar mediciones sobre el microprocesador portátil, debido a la falta de documentación sobre su uso y a dificultades técnicas siguiendo la guía de instalación. Se ha conseguido que corra el sistema operativo diseñado ad hoc para ella a pesar de desconocer la versión exacta del hardware, tanto la versión para uso con monitor como la más básica, que proporciona únicamente la posibilidad de acceso mediante SSH en LAN. No obstante, en la primera no se ha conseguido generar un output de vídeo a un monitor, mientras que la segunda, a pesar de responder a las peticiones SSH, no admite el usuario por defecto según la documentación. Dada la estimación hecha de los recursos que necesitaría resolver estos problemas técnicos, se ha decidido prescindir de este estudio. Por los motivos anteriores, desde este punto centraremos la atención del trabajo en los otros dos sistemas. Ambas arquitecturas han sido puestas a disposición del alumno a través de una estación de trabajo con las siguientes características:  Servidor Dell PowerEdge R720  Dos procesadores Intel Xeon E5-2630Lv2  32 GB de memoria RAM  Una tarjeta Intel Xeon Phi 7120P  Sistema operativo Centos 6.6  Intel® Many-core Platform Software Stack (MPSS) 3.5.1.  Intel Parallel Studio XE 2015 update2 A continuación explicamos en detalle ambas arquitecturas y cómo se ha enfocado el trabajo con cada una. 6.1. Intel Xeon E5-2630Lv2 Esta arquitectura cumple la función de procesador principal del servidor y, como tal, el modo de trabajo empleado para realizar las mediciones sobre ella es el mismo que sobre cualquier otra plataforma estándar: se compila el código en la propia 60 máquina y se ejecuta. Para esto, se ha utilizado el compilador de Intel ICC, ya que favorece el rendimiento al utilizar sus procesadores de servidor. Cada procesador de este tipo tiene seis núcleos físicos. Como podemos ver, el nivel de paralelismo es ligeramente más alto que el habitual para ordenadores personales contemporáneos, pero aun así está lejos de los estándares de supercomputación paralela. No obstante, como ya se ha mencionado, se trabaja con un cluster que agrupa dos de estos procesadores, con lo que el número de núcleos físicos utilizables por el software es de 12. Hay que tener en cuenta que a la hora del reparto de hilos entre ambos procesadores ya se encarga el sistema operativo (scheduling) de forma automática, de modo que el programador no interviene en esta distribución. Cabe esperar que cada uno de los núcleos sea más potente que aquellos de un ordenador personal de la misma generación y que, por lo tanto, esta arquitectura funcione bien para un número de hilos limitado, del orden del número de núcleos físicos. Como ya se ha comentado, el alumno no dispone de acceso directo al servidor físico, de modo que el trabajo con este cluster se realiza a través de un cliente SSH sobre una red VPN o desde la estación de trabajo que tiene asignada en el CITIUS. Además, las restricciones sobre la conexión a Internet de este servidor obligan a copiar manualmente los archivos del proyecto a través de la herramienta SCP. 6.2. Intel Xeon Phi 7120P Esta arquitectura many-core supone un cambio de paradigma frente a la anterior, pues su función es la de coprocesador de un servidor. Es decir, este sistema está pensado para que el procesador principal descargue en él el trabajo que sea altamente paralelizable para aprovechar el elevado número de núcleos físicos de que dispone (61). Estos núcleos, además, cuentan con tecnología Intel Hyper-Threading [17], que permite la ejecución paralela de varios hilos (en este caso, 4) en un solo núcleo, consiguiendo un aumento de la eficiencia a través de una planificación de los cambios de contexto que trata de evitar la espera prolongada de algunas instrucciones. Por esto, el número de núcleos lógicos asciende a la cifra de 244, valor que ya representa un nivel de paralelismo dentro del ámbito de la supercomputación. Por otra parte, esta máquina corre una versión reducida de Linux que permite el acceso a ella a través de SSH desde el procesador principal. De este modo, para utilizar este coprocesador, el alumno accede por medio de un cliente SSH sobre una red VPN al cluster de Xeon, y desde ahí, utilizando otra vez esta herramienta de trabajo remoto se autentica en el Xeon Phi. 61 En cualquier caso, la versión reducida de Linux que corre este coprocesador no incluye software para la compilación, ya que la ejecución de código en esta arquitectura está diseñada para hacerse de uno de los dos siguientes modos:  Ejecución nativa: Como ya se ha dicho, el coprocesador carece de herramientas de compilación propias, por lo que para realizar una ejecución nativa, es necesario realizar una compilación cruzada del código, desde el procesador principal, por ejemplo. Esto significa que se correrá en la otra arquitectura un programa que generará código máquina adaptado para esta. El compilador de Intel ICC facilita enormemente esta labor, ya que permite llevar a cabo la compilación cruzada con la simple adición de un flag extra. Una vez compilado, el ejecutable debe transferirse al sistema de archivos manejado por el coprocesador a través de SCP, y el usuario debe autenticarse en este sistema con una cuenta propia para ejecutar el programa.  Ejecución parcial como offload [18]: Otra modalidad, pensada para la cooperación directa entre procesador principal y coprocesador, pasa por la compilación del programa de forma directa para el procesador principal, con la declaración de secciones de offload que se descargan sobre el coprocesador (muy similar a la forma de trabajar con GPUs). Esta forma de ejecución está pensada para software con partes altamente paralelas bien definidas, que puedan aprovechar mejor la arquitectura many-core del Xeon Phi, sin renunciar a la ejecución más eficiente de las partes secuenciales o con paralelismo reducido sobre el Xeon principal. Para este proyecto, se ha decidido que el segundo modo de ejecución no forma parte de su alcance, de modo que todas las pruebas que se realicen sobre esta arquitectura se harán en base a una compilación cruzada del código. Otra característica importante de esta máquina es que permite definir la distribución por parte del usuario de forma manual de los hilos a la hora de correr un software. Existen tres opciones principales [19]:  Compact: La distribución de hilos se realiza rellenando cada núcleo antes de pasar al siguiente. Teniendo en cuenta que la tecnología Intel Hyper-Threading permite el lanzamiento de cuatro hilos de forma semisimultánea en el mismo núcleo, la distribución sería: 62 FIGURA 6.1: INTEL THREAD AFFINITY: MODO COMPACT  Scattered: En este caso, los hilos se distribuyen asignando uno a cada núcleo hasta completar la primera capa en todos, en cuyo caso se volvería a comenzar desde el primero para la siguiente. Esto se puede ver en la Figura 6.2: FIGURA 6.2: INTEL THREAD AFFINITY: MODO SCATTERED  Balanced: Este modo es muy similar al anterior, con la diferencia de que se agrupan en el mismo núcleo hilos con números consecutivos. Esto se ilustra en la figura 6.3: FIGURA 6.3: INTEL THREAD AFFINITY: MODO BALANCED 63 El modo de reparto de hilos se puede elegir en tiempo de compilación, ya sea mediante una instrucción explícita para ello en el código fuente o bien utilizando una variable de entorno de la consola, siguiendo el estilo de las preferencias en OpenMP. Estas opciones abren nuevas posibilidades a la hora de analizar el rendimiento del software en esta arquitectura, que serán revisadas en el apartado correspondiente al análisis de resultados. 64 7. IMPLEMENTACIÓN PARALELA Y OPTIMIZACIÓN En este capítulo trataremos la implementación de los algoritmos de Stereo Matching considerados y, más en profundidad, las mejoras de rendimiento que se han aplicado a cada uno a través de técnicas de paralelización y optimización. Como ya se ha dicho en el capítulo dedicado a la arquitectura del software desarrollado, cada uno de estos algoritmos ha sido implementado usando el lenguaje C++ como una función, y son llamados por el programa principal en función de los parámetros recibidos por línea de comandos. Esto se aplica también a las versiones paralelas, incluidas en otras funciones como si de algoritmos distintos se tratase. Las versiones básicas de los algoritmos se corresponden con la implementación directa de los pseudo-códigos mostrados en el apartado anterior. El proceso de desarrollo de las versiones paralelas se explica a continuación. 7.1. Pixel-wise Matching y Patch-wise Matching Se ha creado un único apartado para estos dos algoritmos debido a que su paralelización es similar y se puede establecer una analogía muy directa entre ambas. Como ya hemos visto en el capítulo anterior, el Pixel-wise Matching recorre píxel a pixel la imagen buscando un candidato para el emparejamiento en las líneas correspondientes de la otra imagen. No existen, pues, dependencias entre el cálculo de profundidad para dos píxeles diferentes. Lo mismo sucede con el Patch-wise Matching, cuya única diferencia es que utiliza una ventana de vecinos para reducir la ambigüedad en la elección del mejor candidato. De este modo, se pueden paralelizar los dos algoritmos asignando a cada hilo una cantidad determinada de filas o columnas de la imagen para que las procese independientemente del resto. Así, se almacenarán los resultados en una matriz de píxeles común, en cuya reducción no se darán condiciones de carrera debido al hecho de que el resultado para cada píxel se almacena en posiciones diferentes de dicha matriz. Con la cantidad de filas y columnas que tiene una imagen, está garantizado un reparto balanceado para cantidades de hilos incluso elevadas, con lo que no sería necesario recurrir a un refinamiento mediante paralelización anidada u otras estrategias. 7.2. Semi-Global Matching La paralelización del algoritmo Semi-Global Matching tiene una mayor complejidad que la de los algoritmos anteriores. A efectos de su paralelización, este algoritmo puede dividirse en tres bloques claramente definidos, ya que las estrategias 65 para abordarlos serán diferentes entre sí. Dichos bloques son los que se listan a continuación:  Cálculo de la solución inicial (Bloque 1): Como ya hemos explicado, este se realiza mediante un método basado en el Pixel-wise Matching, con la diferencia de que, en este caso, en lugar de almacenar directamente el mapa de profundidad, se mantienen los costes de emparejamiento para cada candidato respecto a cada píxel base. En cualquier caso, la metodología de paralelización es la misma que en el algoritmo original.  Ejecución del núcleo del algoritmo (Bloque 2): Esta fase engloba el cálculo de las soluciones parciales derivadas de la extensión de la restricción de suavidad en cada uno de los pares dirección-sentido elegidos, así como su reducción en una matriz común. Es la parte con mayor complejidad a nivel de posibilidades de paralelismo y, por lo tanto, se tratará de forma separada más adelante, desglosada por metodologías en los correspondientes sub-apartados.  Selección de la profundidad para cada píxel (Bloque 3): Dada la matriz de salida del bloque anterior, en este se recorrerá buscando para cada píxel la disparidad que menor coste acumulativo tenga. Simplemente se trata de recorrer una matriz tridimensional sin ningún tipo de dependencias en la consideración de distintos píxeles. De este modo, la paralelización más directa consiste en repartir una de las dimensiones de la matriz entre el número de hilos. Las dimensiones correspondientes al ancho y al alto de la imagen parecen las más adecuadas, pues sus valores son más elevados y permiten un reparto equitativo de la carga de trabajo entre un mayor número de hilos. La complejidad de paralelización del segundo bloque se debe a las dependencias de datos que presenta. Por un lado, la extensión de la restricción de suavidad a lo largo de cada par dirección-sentido obtiene un resultado que debe combinarse con el resto de soluciones parciales para la consecución de solución total. Esto supone una dependencia básica de reducción. Por otra parte, el cálculo del coste de emparejamiento de una determinada disparidad para un determinado píxel para cada par dirección sentido depende del anterior, de modo que la división de la imagen para el reparto de la carga de trabajo entre los hilos no es inmediata, y depende de la dirección y sentido que estén siendo considerados. A continuación se explicarán las distintas estrategias seguidas para la paralelización de este algoritmo, diferenciadas entre sí por la aproximación utilizada para el tratamiento del bloque central. Para los otros dos bloques, en todas ellas se utilizan los métodos descritos en los puntos anteriores. 66 7.2.1. Direcciones La aproximación más natural para abordar este problema podría ser el cálculo independiente de cada solución parcial vinculada a una dirección y un sentido. Para ello habría que crear una matriz por cada una de estas soluciones parciales (en la versión secuencial solamente hacía falta una en total). Estas matrices serán luego reducidas en una con la solución definitiva. Resulta evidente que no se pueden reducir a la par de la realización de los cálculos parciales, como permite la versión secuencial ya que, en este caso, varios hilos estarán accediendo a las mismas posiciones de memoria de forma simultánea, lo que podría provocar condiciones de carrera. Como solución para el problema de la citada reducción, se ha considerado la división de la matriz en franjas, tantas como pares dirección-sentido. De este modo, se crea un mutex para cada una de estas franjas y cada uno de los hilos comienza la reducción de sus soluciones parciales asociadas en una franja diferente, bloqueándola para evitar que el resto acceda a ella mientras tanto, evitando así carreras críticas. Una vez completada la franja, se pasa a la siguiente en un modelo circular de modo que, debido al balanceo en el reparto de la matriz, se espera que el tiempo perdido respecto a una reducción completamente paralela sea muy reducido. De lo anterior se puede deducir que este método funcionará bien para cantidades de hilos reducidas pues, como se ha dicho en el capítulo anterior, se ha elegido arbitrariamente ocho como el número de pares dirección-sentido que serán consideradas, de modo que un número de hilos mayor no mejorará el resultado para este bloque (aunque sí podría mejorar los otros dos). Un número elevado de hilos podría incluso reducir el rendimiento, dado que el coste de lanzarlos podría no verse compensado por las ganancias de rendimiento obtenidas en la ejecución de los otros bloques. 7.2.2. Franjas Otro modo de abordar la paralelización del núcleo del algoritmo es la división de la solución utilizada como punto de partida en lo que denominamos franjas. Como ya hemos dicho, existen dependencias en los cálculos realizados para cada píxel de una solución parcial con el anterior en la dirección y sentido correspondientes. Es necesario en este caso, por lo tanto, especificar una estrategia de paralelización diferente para la obtención de cada resultado parcial. Estas se dividen en dos tipos principales:  Direcciones horizontales o verticales respecto a las coordenadas de la imagen: En este caso el reparto de la matriz es muy directo. Para las direcciones horizontales se reparten las filas en franjas del mismo grosor y para las verticales, las columnas. De este modo, cada uno de los hilos puede avanzar independientemente del resto, con dependencias reducidas al interior de su franja 73 GRÁFICA 8.3: TIEMPOS DE EJECUCIÓN PARA SUM OF ABSOLUTE DIFFERENCES, XEON GRÁFICA 8.4: SPEEDUP PARA SUM OF ABSOLUTE DIFFERENCES, XEON 0 1 2 3 4 5 6 1 2 4 8 16 32 64 Tiempo (s) Hilos Tiempos de ejecución Versión paralela Secuencial 0,5 1 2 4 8 16 32 64 1 2 4 8 16 32 64 Speedup Hilos Speedup Versión paralela Óptimo 74 GRÁFICA 8.5: TIEMPOS DE EJECUCIÓN PARA ADAPTIVE SUPPORT-WEIGHT, XEON GRÁFICA 8.6: SPEEDUP PARA ADAPTIVE SUPPORT-WEIGHT, XEON Como se puede observar, la escalada de rendimiento en estos casos es casi lineal, acercándose mucho al óptimo. De hecho, se mantiene un aumento de la 0 5 10 15 20 25 30 35 1 2 4 8 16 32 64 Tiempo (s) Hilos Tiempos de ejecución Versión paralela Secuencial 0,5 1 2 4 8 16 32 64 124816 32 64 Speedup Hilos Speedup Versión paralela Óptimo 75 ganancia incluso más allá del límite razonable, que es la ocupación de todos los núcleos lógicos. Esto podría deberse a que, con un mayor nivel de reparto, las franjas asignadas a cada hilo son más estrechas, con lo que las probabilidades de que uno cargue en memoria caché un dato que el otro necesita aumentan. Esto es posible debido a que, para la consideración de un candidato, se toma un parche a su alrededor que podría abarcar píxeles dentro de otra franja. Con franjas más estrechas, la proporción de elementos comunes entre ellas respecto a los que no lo son será mayor. Por otra parte, podemos ver que para cantidades de hilos próximas al número de núcleos físicos de cada procesador, la ganancia se degrada un poco más para el primer método. Esto podría tener que ver con el hecho que se ha comentado ya en el subapartado anterior respecto al uso del segundo procesador del cluster, y tienen que organizarse para el reparto del trabajo y la puesta en común de resultados, lo cual no tendría un efecto tan importante proporcionalmente sobre el segundo método debido a que el tiempo consumido para los cálculos por este es mucho mayor, del orden de cinco veces más para las versiones secuenciales de ambos. En cualquier caso, podemos ver que para los dos métodos se llega a obtener un factor de speedup de alrededor de 10 en el servidor de 12 núcleos compuesto por dos procesadores diferentes, lo cual se puede considerar como un valor razonablemente elevado, acorde a la hipótesis realizada al respecto en el capítulo en el que se describían los algoritmos considerados. 8.1.3. Semi-Global Matching En este subapartado se analiza el algoritmo más interesante, en lo que a estrategias de paralelización se refiere, de entre los considerados. Como ya se ha explicado, su paralelización resulta significativamente más compleja que la de los otros dos algoritmos. Esto lleva a la separación en los tres bloques mencionados en la Sección 7.2, para los cuales se han realizado medidas por separado, en adición a la del total de tiempo consumido. Por los motivos anteriores, este subapartado no seguirá la misma estructuración que los que le preceden. Se comenzará por el mismo análisis que el realizado para los otros algoritmos, pero además, a continuación se añadirán las gráficas de rendimiento para cada uno de los tres bloques definidos y se comentarán los resultados correspondientes. Además, para cada uno de los bloques existen tres estrategias de paralelización diferentes, de modo que estas también serán comentadas y comparadas entre sí. También se añadirá un breve análisis sobre la posibilidad de cambiar el reparto de los hilos en la tercera estrategia de paralelización, variando las cantidades de ellos que se asignan al bucle externo y al interno. 76 A continuación se muestran en las Gráficas 8.7 y 8.8 los tiempos de ejecución y speedup obtenidos para el total de la ejecución: GRÁFICA 8.7: TIEMPOS DE EJECUCIÓN PARA SEMI-GLOBAL MATCHING (TOTAL), XEON GRÁFICA 8.8: SPEEDUP PARA SEMI-GLOBAL MATCHING (TOTAL), XEON Como se puede observar, entre los resultados obtenidos de las diferentes estrategias de paralelización hay un patrón común: todas ofrecen un rendimiento sensiblemente peor que la versión secuencial para ejecuciones con un hilo y, 0 0,2 0,4 0,6 0,8 1 1,2 1,4 1 2 4 8 16 32 64 Tiempo (s) Hilos Tiempos de ejecución Paralelismo direcciones Paralelismo franjas Paralelismo D+F Secuencial 0,5 1 2 4 8 16 32 64 1 2 4 8 16 32 64 Speedup Hilos Speedup Paralelismo direcciones Paralelismo franjas Óptimo Paralelismo D+F 77 ligeramente también para aquéllas con dos hilos. Esto es algo que cabía esperar, como se ha comentado ya en el capítulo anterior, debido a que todas incluyen overheads de cálculo, y el tiempo total de ejecución es muy pequeño, lo que convierte a estos en más significativos. Para la paralelización por franjas, los cálculos añadidos provienen del reparto inicial de las diagonales y las franjas horizontales y verticales. Para la estrategia basada únicamente en la simultaneidad de cálculo de las soluciones parciales, el origen es la reducción basada en mutex necesaria para calcular la solución agregada sin carreras críticas. Para el último método, existen ambos tipos de overhead, lo que lo posiciona desfavorablemente para ejecuciones con pocos hilos. Además de lo ya comentado, se puede observar que, en general para las tres estrategias, la pendiente de ganancia respecto al número de hilos utilizados es claramente inferior a los resultados ideales, y que se degrada considerablemente al superar la cantidad de hilos el número de núcleos físicos de un procesador. Este fenómeno afecta, sobre todo, a la paralelización por direcciones, ya que el núcleo de los cálculos no aumenta su rendimiento en proporción al número de threads utilizados a partir de 8 (no hay más soluciones parciales que requieran ser calculadas de forma simultánea). Los otros bloques sí tendrían ligeras mejorías, pero el aporte de estos al total del tiempo de ejecución es limitado, con lo que este método, que comienza para un único hilo como el mejor de los tres, es alcanzado en las últimas ejecuciones con muchos hilos por la paralelización combinada, que comienza como el peor. Se puede ver, por lo tanto, que para una ejecución por defecto en esta arquitectura, la mejor alternativa es utilizar el sistema de franjas. A continuación se desglosan estos tiempos en los tres bloques ya mencionados. Esto se ve ilustrado en las Gráficas 8.9, 8.10, 8.11, 8.12, 8.13 y 8.14. 78 GRÁFICA 8.9: TIEMPOS DE EJECUCIÓN PARA SEMI-GLOBAL MATCHING (BLOQUE 1), XEON GRÁFICA 8.10: SPEEDUP PARA SEMI-GLOBAL MATCHING (BLOQUE 1), XEON 0 0,05 0,1 0,15 0,2 0,25 1 2 4 8 16 32 64 Tiempo (s) Hilos Tiempos de ejecución Paralelismo direcciones Paralelismo franjas Paralelismo D+F Secuencial 0,5 1 2 4 8 16 32 64 1 2 4 8 16 32 64 Speedup Hilos Speedup Paralelismo direcciones Paralelismo franjas Óptimo Paralelismo D+F 79 GRÁFICA 8.11: TIEMPOS DE EJECUCIÓN PARA SEMI-GLOBAL MATCHING (BLOQUE 2), XEON GRÁFICA 8.12: SPEEDUP PARA SEMI-GLOBAL MATCHING (BLOQUE 2), XEON 0 0,2 0,4 0,6 0,8 1 1,2 1 2 4 8 16 32 64 Tiempo (s) Hilos Tiempos de ejecución Paralelismo direcciones Paralelismo franjas Paralelismo D+F Secuencial 0,5 1 2 4 8 16 32 64 1 2 4 8 16 32 64 Speedup Hilos Speedup Paralelismo direcciones Paralelismo franjas Óptimo Paralelismo D+F 80 GRÁFICA 8.13: TIEMPOS DE EJECUCIÓN PARA SEMI-GLOBAL MATCHING (BLOQUE 3), XEON GRÁFICA 8.14: SPEEDUP PARA SEMI-GLOBAL MATCHING (BLOQUE 3), XEON Respecto al primer bloque (Figuras 8.9 y 8.10), podemos observar que los rendimientos de las diferentes versiones escalan parejos entre sí, debido a que la paralelización de esta parte es idéntica para todos. Se observa una ligera degradación del rendimiento para cantidades de hilos bajas, que puede deberse al esfuerzo que 0 0,005 0,01 0,015 0,02 0,025 0,03 0,035 1 2 4 8 16 32 64 Tiempo (s) Hilos Tiempos de ejecución Paralelismo direcciones Paralelismo franjas Paralelismo D+F Secuencial 0,5 1 2 4 8 16 32 64 1 2 4 8 16 32 64 Speedup Hilos Speedup Paralelismo direcciones Paralelismo franjas Óptimo Paralelismo D+F 81 supone crear los hilos y que no se ve compensado por el ahorro en una zona donde los cálculos realizados son tan poco costosos. En el tercero (Figuras 8.13 y 8.14) debería suceder algo análogo, ya que la paralelización tiene las mismas características. No obstante, ya se ha realizado la ejecución de todo el resto del programa con anterioridad, de modo que se presentan algunas diferencias. Primeramente, no se aprecia el despunte de tiempo consumido para cantidades bajas de hilos que se ve en el primer bloque, probablemente debido a que los hilos ya han sido creados con anterioridad y se aprovecha para lanzarlos con menos esfuerzo en esta ocasión, con lo que el overhead correspondiente es mínimo. Unido a esto, se espera que haya datos disponibles en las memorias caché desde el principio. Por otra parte, se puede observar que la ejecución de la estrategia basada en el sistema de franjas arroja peores resultados que las otras dos. Esto podría deberse a que en estas últimas la reducción de la solución definitiva se realiza al final y no durante todo el proceso, con lo que tiene más probabilidades de encontrarse en caché todavía al comenzar la ejecución de este bloque o, al menos, de que gran parte de sus elementos lo estén. Además, puede afectar el posible desbalanceo de la carga propio de esta versión. Por último, el segundo bloque (Figuras 8.11 y 8.12) es decisivo para el tiempo de ejecución total, ya que es el que contiene el núcleo de los cálculos del algoritmo y, por lo tanto, el que más tiempo consume. Podemos ver que las tendencias de las gráficas correspondientes son análogas a las que provienen de la ejecución conjunta de los tres bloques. Dichas tendencias se explican, por lo tanto, con los mismos argumentos ofrecidos en el comentario de las dos primeras gráficas de este subapartado. Como conclusión de este apartado, podemos ver los resultados de un pequeño experimento secundario que consiste en la modificación del reparto de los hilos entre el lazo externo y el interno en la paralelización combinada. Se ha decidido realizar la comparación para la ejecución con 8 hilos. Utilizamos primero la distribución habitual, que toma todos los hilos posibles hasta 8 para el lazo externo y luego reparte equitativamente los restantes para cada una de las soluciones parciales, tomando por lo tanto, en este caso, los ocho para el exterior y 1 para cada solución parcial (se computarán de forma secuencial). Luego se ha probado con las variantes en las que el lazo externo utiliza 4 hilos y el interno 2, y viceversa. Los resultados de rendimiento son los que se ven en el siguiente gráfico de barras: 82 GRÁFICA 8.15: COMPARATIVA DE DIFERENTES REPARTOS ENTRE LAZOS EXTERNO E INTERNO, XEON Podemos observar que existen pequeñas diferencias de rendimiento, pero que en proporción al tiempo de ejecución son mínimas. No parece, por lo tanto, que la selección de una estrategia u otra vaya a suponer diferencias notorias en la ejecución del algoritmo. 8.2. Intel Xeon Phi 7120P Para esta arquitectura se han realizado unas pruebas análogas a las descritas anteriormente, teniendo en cuenta que ahora el número de núcleos es mucho mayor: 61. También cambia la cantidad de hilos que puede manejar cada núcleo físico por medio de la tecnología Hyper-Threading, que ascienden a 4. Por ello, se ha decidido realizar las mediciones para ejecuciones con 1, 2, 4, 8, 16, 32, 48, 56, 64, 96, 128, 192 y 240 hilos. Por otra parte, también se añadirá respecto al apartado anterior una breve sección en la que se compararán los diferentes modos de afinidad disponibles para este procesador. Como recordatorio previo al análisis de resultados, hay que tener en cuenta respecto a la arquitectura anterior que los núcleos de este sistema ofrecen un rendimiento bastante limitado, y que la ganancia respecto al uso de un procesador se obtiene para ejecuciones altamente paralelas. Se espera, por lo tanto, que una ejecución con pocos hilos desemboque en resultados peores que en el cluster anterior. 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 Tiempo (s) Tiempo de ejecución 8x1 4x2 2x4 89 GRÁFICA 8.24: TIEMPOS DE EJECUCIÓN PARA SEMI-GLOBAL MATCHING (BLOQUE 1), PHI GRÁFICA 8.25: SPEEDUP PARA SEMI-GLOBAL MATCHING (BLOQUE 1), PHI 0 0,5 1 1,5 2 2,5 3 3,5 1 4 16 64 256 Tiempo (s) Hilos Tiempos de ejecución Paralelismo direcciones Paralelismo franjas Paralelismo D+F Secuencial 0,5 1 2 4 8 16 32 64 128 256 1 4 16 64 256 Speedup Hilos Speedup Paralelismo direcciones Paralelismo franjas Paralelismo D+F Óptimo 90 GRÁFICA 8.26: TIEMPOS DE EJECUCIÓN PARA SEMI-GLOBAL MATCHING (BLOQUE 2), PHI GRÁFICA 8.27: SPEEDUP PARA SEMI-GLOBAL MATCHING (BLOQUE 2), PHI 0 2 4 6 8 10 12 1 4 16 64 256 Tiempo (s) Hilos Tiempos de ejecución Paralelismo direcciones Paralelismo franjas Paralelismo D+F Secuencial 0,5 1 2 4 8 16 32 64 128 256 1 4 16 64 256 Speedup Hilos Speedup Paralelismo direcciones Paralelismo franjas Paralelismo D+F Óptimo 91 GRÁFICA 8.28: TIEMPOS DE EJECUCIÓN PARA SEMI-GLOBAL MATCHING (BLOQUE 3), PHI GRÁFICA 8.29: SPEEDUP PARA SEMI-GLOBAL MATCHING (BLOQUE 3), PHI Como se puede observar, en los bloques primero y tercero escala mejor el rendimiento que en la arquitectura anterior, lo que probablemente sea debido al hecho ya mencionado de que el procesamiento secuencial en esta es más costoso y, 0 0,05 0,1 0,15 0,2 0,25 1 4 16 64 256 Tiempo (s) Hilos Tiempos de ejecución Paralelismo direcciones Paralelismo franjas Paralelismo D+F Secuencial 0,5 1 2 4 8 16 32 64 128 256 1 4 16 64 256 Speedup Hilos Speedup Paralelismo direcciones Paralelismo franjas Paralelismo D+F Óptimo 92 por lo tanto, es más probable que se compense el coste de creación de los hilos con la ganancia que aportan. Se ve, también, que el comportamiento en estos bloques se ve afectado por la ejecución del resto del programa en un grado claramente inferior, ya que el comportamiento es el esperado para estas regiones: que las diferentes estrategias tengan rendimientos parejos debido a que la paralelización de estas secciones es la misma para todas, y que la escalada de rendimiento se acerque razonablemente al óptimo, mucho más en el tercer bloque porque los hilos ya están creados y las cachés con datos útiles, y no hay que compensar este coste. Respecto al segundo bloque, como cabía esperar, marca las tendencias que hemos visto en los tiempos de ejecución de la totalidad del algoritmo, de modo que la justificación para estas ya se ha propuesto al comienzo de este subapartado. Profundizando en el comportamiento de este algoritmo, volvemos a realizar sobre esta arquitectura el mismo experimento visto en la anterior: lanzar la estrategia de paralelización combinada con diferentes repartos de hilos de ejecución entre el lazo externo y el interno. En este caso se prueba para 32 threads con la versión genérica, que usa 8 para el exterior y 4 para el interior; y con otras dos con 4 para el exterior y 8 para el interior, y 2 para el exterior y 16 para el interior, respectivamente. Los resultados se pueden ver en la siguiente gráfica de barras: GRÁFICA 8.30: COMPARATIVA DE DIFERENTES REPARTOS ENTRE LAZOS EXTERNO E INTERNO, PHI Una vez más, se observa que las diferencias entre las diferentes aproximaciones al reparto de la carga de trabajo son poco significativas respecto al tiempo de ejecución del programa, por lo que parece un aspecto menor su elección a la hora de optimizar el rendimiento del algoritmo. 0 0,2 0,4 0,6 0,8 1 1,2 1,4 1,6 1,8 2 Tiempo (s) Tiempo de ejecución 8x4 4x8 2x16 93 Por último, en este subapartado también se hará un análisis comparativo, como ya se había anunciado anteriormente, sobre el uso de los diferentes tipos de afinidades para la distribución de hilos en los núcleos. Recordamos que las opciones que nos brinda el compilador de Intel son scattered (la utilizada por defecto), compact y balanced. A estos efectos, incluimos a continuación las Gráficas 8.31, 8.32, 8.33 y 8.34 con el rendimiento de la ejecución del total del algoritmo para las dos aproximaciones restantes. GRÁFICA 8.31: TIEMPOS DE EJECUCIÓN PARA SEMI-GLOBAL MATCHING, COMPACT 0 2 4 6 8 10 12 14 16 1 4 16 64 256 Tiempo (s) Hilos Tiempos de ejecución Paralelismo direcciones Paralelismo franjas Paralelismo D+F Secuencial 94 GRÁFICA 8.32: SPEEDUP PARA SEMI-GLOBAL MATCHING, COMPACT GRÁFICA 8.33: TIEMPOS DE EJECUCIÓN PARA SEMI-GLOBAL MATCHING, BALANCED 0,5 1 2 4 8 16 32 64 128 256 1 4 16 64 256 Speedup Hilos Speedup Paralelismo direcciones Paralelismo franjas Paralelismo D+F Óptimo 0 2 4 6 8 10 12 14 16 1 4 16 64 256 Tiempo (s) Hilos Tiempos de ejecución Paralelismo direcciones Paralelismo franjas Paralelismo D+F Secuencial 95 GRÁFICA 8.34: SPEEDUP PARA SEMI-GLOBAL MATCHING, BALANCED Respecto al modo compact, podemos ver que se comporta de forma similar a la medida hasta ahora, con dos diferencias principales: la ganancia es, en general, peor; y existen pequeños saltos en la pendiente de esta frente al número de hilos de ejecución utilizados. Ambas diferencias se deben al hecho de que se rellenan todos los hilos de un núcleo antes de pasar al siguiente, como habíamos visto ya en el capítulo que describía las arquitecturas consideradas. De este modo, se fuerza el uso del paralelismo de hilos mediante la tecnología Hyper-Threading mientras sea posible, en lugar de repartir los hilos entre los distintos núcleos físicos. Como es natural, este pseudo-paralelismo, a pesar de ser más eficiente que una ejecución secuencial en la mayoría de los casos, no lo es tanto como el paralelismo real que ofrecen los núcleos independientes. Por ello, el rendimiento es peor, en general, que el obtenido mediante la estrategia de reparto scattered, y se producen estos pequeños saltos coincidentes con la utilización de un núcleo adicional cuando se llena el actual. Respecto al esquema balanced, podemos ver que el comportamiento de los resultados de rendimiento del algoritmo cuando se aplica son prácticamente idénticos a los analizados a lo largo de este capítulo para el modo scattered. Por lo tanto, parece que el hecho de que hilos con números contiguos se asignen al mismo núcleo no tiene un efecto relevante para la ejecución de este algoritmo. 0,5 1 2 4 8 16 32 64 128 256 1 2 4 8 16 32 64 128 256 Speedup Hilos Speedup Paralelismo direcciones Paralelismo franjas Paralelismo D+F Óptimo 96 8.3. Comparación de los resultados para ambas arquitecturas En este apartado, se realizará una breve comparación de los resultados obtenidos por cada arquitectura, que complementará todo lo que ya se ha dicho al respecto a lo largo de este capítulo. Servirá, pues, como conclusión de este. En primer lugar, lo más evidente es que para ejecuciones con números de hilos reducidos, el cluster ofrece resultados claramente superiores, como cabe esperar dado que sus núcleos tienen prestaciones sensiblemente mejores que los del coprocesador. Dejando esto a un lado, nos adentraremos en los comportamientos de cada uno de los algoritmos en términos de escalabilidad a medida que se aumenta el número de hilos. En el Pixel-wise Matching, podemos ver que la escalada de rendimiento es mejor en el servidor, sin llegar a decaer tanto como en el coprocesador, y alcanzando un tiempo mínimo de ejecución de orden diez veces inferior al obtenido en la otra arquitectura. En este caso, para un procesamiento tan breve, podemos ver que el alto nivel de paralelismo del Xeon Phi resulta fútil. En el caso del Patch-wise Matching, podemos ver que ambas versiones (Sum of Absolute Differences y Adaptive Support-Weight) escalan mejor en el coprocesador, debido a su prolongado tiempo de cálculo y a lo sencillo y equitativo que es el reparto de las cargas de trabajo, acercándose mucho a la ganancia ideal hasta cantidades de hilos elevadas. No obstante, solamente en la segunda variación se obtiene un mínimo para el tiempo total de cómputo inferior al obtenido por el cluster, al alcanzar un factor de ganancia mayor que 84. Los mínimos en este caso son 2,06s y 3,17s, respectivamente, lo que significa que en el Phi se obtiene una ventaja de aproximadamente el 35% para la mejor ejecución de esta versión. Para la otra, los mejores resultados son 0,99s y 0,56s, respectivamente, es decir, la mejor ejecución del coprocesador consume de forma aproximada un 177% del tiempo utilizado por la mejor ejecución en el servidor. Con esto, podemos ver que el paralelismo que ofrece el Xeon Phi solamente resulta útil con cargas de trabajo muy elevadas, como la que supone la segunda variación de este algoritmo. Por último, respecto al Semi-Global Matching, volviendo a un algoritmo con una carga de cómputo reducida, podemos ver que, a pesar de que la escalada de rendimiento es mucho mejor en el coprocesador, llegando a factores de ganancia superiores a ocho para el método por franjas frente a máximos inferiores a dos en el servidor, en el primero no se alcanzan tiempos de ejecución tan buenos como aquéllos obtenidos en el segundo. Esto se debe, como ya se ha explicado, a que para cargas de trabajo tan reducidas, el alto nivel de paralelismo no compensa el hecho de que las prestaciones de los núcleos del coprocesador sean acusadamente inferiores a las que tienen los del cluster. De este modo, las mejores ejecuciones con la estrategia que ofrece el mayor rendimiento en el Xeon Phi solamente consiguen aproximarse a tiempos del orden de 1s, sin llegar a alcanzar este, mientras que el procesador 97 principal logra un mínimo de casi 0,4s, aproximadamente un 60% menos. Estos mínimos se obtienen, en ambos casos, por medio de la estrategia de franjas. Como conclusión a este apartado cabe decir que, como sugiere su diseño, el uso del coprocesador solamente es aconsejable frente al del procesador principal para cargas de trabajo muy elevadas y con alta escalabilidad respecto al número de hilos utilizados. Hay que tener en cuenta también, que en este caso la comparación se realiza entre un cluster con dos procesadores principales frente a solamente un coprocesador, de modo que para el caso con un solo procesador principal, la carga de trabajo necesaria para que compense la utilización del Xeon Phi debería ser considerablemente inferior. 98 9. CONCLUSIONES Las potenciales utilidades del Stereo Matching requieren cada vez un rendimiento de ejecución más elevado, ya que se tiene a aplicaciones portátiles con requerimientos de respuestas en tiempo real, como puede ser la robótica; o incluso otras destinadas a manejar grandes cantidades de datos, como la reconstrucción tridimensional de escenarios. Por todo esto, resulta muy importante la optimización de los algoritmos de este campo. En este trabajo de fin de grado se ha planteado el estudio de algunos de los algoritmos de los que conforman el estado del arte en esta disciplina, llevando a cabo su implementación secuencial y añadiendo mejoras basadas en la paralelización, cuyo rendimiento ha sido testeado en dos arquitecturas muy diferentes, sobre las que se han realizado mediciones. Las mediciones realizadas han sido analizadas desde diferentes enfoques comparativos: la escalabilidad de rendimiento de cada algoritmo en sus versiones paralelas respecto a la secuencial, la ejecución de estos en ambas arquitecturas o el estudio de parámetros que afectan a la paralelización, como las afinidades en la distribución de hilos entre los núcleos, o el reparto de estos entre dos niveles de anidamiento de la paralelización. Estos resultados arrojan algunos datos de interés científico, como el hecho de que la ganancia de rendimiento basada en el incremento de hilos de ejecución es muy pobre para cargas de trabajo reducidas en estas arquitecturas. Otro ejemplo es el hecho de que la utilidad del coprocesador frente al servidor utilizado se limita a tareas con cargas computacionales muy elevadas y altamente escalables respecto al rendimiento frente al número de hilos utilizados (una vez más, hay que tener en cuenta que el servidor incluye dos procesadores CPUs). Además del aprendizaje que han facilitado los resultados, se han conseguido tasas de mejora de rendimiento muy importantes en algunos casos llegando, como dato reseñable, a obtener en una paralelización un factor de speedup superior a 84 respecto a la versión secuencial. En las variantes de Patch-wise Matching es donde se ha obtenido los efectos más positivos con las ejecuciones paralelas, con ganancias más moderadas para el Pixel-wise Matching por su bajo coste computacional base, que hace que no sea rentable un nivel elevado de paralelización; y el Semi-Global Matching, cuya compleja paralelización obliga, para su implementación, a alejarse de las tasas de ganancia ideales en base al número de threads utilizados. El alcance de este proyecto, no obstante, está limitado por el plazo de entrega, con lo que se ha decidido dejar fuera de éste algunas actividades que podrían plantearse como una ampliación del estudio de cara al futuro.