Triangularización de espacios de datos a través de la librería Hitmap

Universidad de Valladolid ESCUELA DE INGENIER´ IA INFORM ´ ATICA GRADO EN INGENIER´ IA INFORM ´ ATICA MENCI ´ ON EN TECNOLOG´ IAS DE LA INFORMACI ´ ON Triangularizaci´on de espacios de datos a trav´es de la librer´ıa Hitmap Curso acad´emico: 2020-2021 Alumno: Hugo Prieto T´arrega Tutores acad´emicos: Yuri Torres de la Sierra Mar´ıa Inmaculada Santamar´ıa Valenzuela A Imaz. 3 4 AGRADECIMIENTOS Agradecimientos Quiero agradecer a mis padres el apoyo que me han dado durante todo mi periodo como estudiante en la universidad, sobretodo durante este ´ultimo curso acad´emico, pues sin ellos no podr´ıa haberme centrado tanto en mi desarrollo acad´emico. Por otro lado quiero agradecer a Yuri Torres de la Sierra y a Arturo Gonz´alez Escribano por sus esfuerzos por guiarme y ense˜narme durante el desarrollo de este proyecto y en especial a Mar´ıa Inmaculada Santamar´ıa Valenzela, por su paciencia y su buen hacer. 5 AGRADECIMIENTOS 6 RESUMEN Resumen Actualmente, el paradigma de la computaci´on paralela es ampliamente utilizado por cient´ıficos e investigadores para la resoluci´on de problemas de c´alculo con gran carga computacional. En la lista de TOP 500 se refleja el ranking con los 500 supercomputadores m´as potentes del mundo que existen en la actualidad. Estos sistemas son empleados para realizar c´alculos con grandes vol´umenes de datos en diferentes ´areas de conocimiento tales como las matem´aticas, la astronom´ıa, la biolog´ıa o la medicina. Dentro del paradigma de la computaci´on paralela destacamos la t´ecnica denominada como “Tiling”. Esta t´ecnica consiste en el reparto de la carga computacional entre diferentes unidades computaciones. Este reparto de carga se consigue a trav´es del particionado del espacio de memoria donde se alojan los datos. Se realiza una divisi´on del dominio de datos del problema en bloques asignados a cada procesador. Hitmap es una librer´ıa dise˜nada por el grupo de investigaci´on Trasgo que a´una mecanismos de comunicaci´on as´ı como mecanismos del particionado de datos. Este particionado se realiza con bloques de forma rectangular modelados a trav´es de la estructura de datos Shape, que permite la creaci´on de pol´ıgonos rectangulares de n-dimensiones. En este trabajo se desarrolla una extensi´on de la librer´ıa Hitmap para la triangularizaci´on del espacio de datos. Esta t´ecnica se implementa a trav´es de particiones triangulares de memoria permitiendo al sistema de computo paralelo aprovechar mejor la geometr´ıa del espacio de datos en ciertos tipos de problema, para reducir, en la medida de lo posible, las operaciones de comunicaci´on y sincronizaci´on. Para realizar este particionado en pol´ıgonos triangulares se desarrollan los algoritmos de intersecci´on, diferencia y uni´on. 7 RESUMEN 8 ABSTRACT Abstract Nowadays, the paradigm of parallel computing is widely used by scientists and researchers for solving computational problems with high computational load. The TOP 500 list reflects the ranking of the 500 most powerful supercomputers in the world that currently exist. These systems are used to perform calculations with large volumes of data in different areas of knowledge such as mathematics, astronomy, biology or medicine. Within the paradigm of parallel computing we highlight the technique known as “Tiling”. This technique consists of the distribution of the computational load between different computational units. This load sharing is achieved through the partitioning of the memory space where the data is stored. The data domain of the problem is divided into blocks assigned to each processor. Hitmap is a library designed by the Trasgo research group that combines communication mechanisms as well as data partitioning mechanisms. This partitioning is done with rectangular shaped blocks modeled through the Shape data structure, which allows the creation of n-dimensional rectangular polygons. In this project an extension of the Hitmap library is developed for the triangularization of the data space. This technique is implemented through triangular memory partitions, allowing the parallel computing system to take better advantage of the geometry of the data space in certain types of problems, to reduce, as far as possible, the communication and synchronization operations. To carry out this partitioning in triangular polygons, the intersection, difference and union algorithms are developed. 9 ´ INDICE DE FIGURAS 3.12. Representaci´on de triangulos a trav´es de la estructura HitSigExtShape. . . . 57 3.13. Diagrama de flujo de la b´usqueda horizontal. . . . . . . . . . . . . . . . . . . 59 3.14. Diagrama de flujo de la b´usqueda vertical. . . . . . . . . . . . . . . . . . . . . 60 3.15.Intersecci´ondeAyB. ............................... 61 3.16. Diferencia de A menos B. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 3.17. Diferencia de B menos A. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 3.18.Uni´ondeAyB. .................................. 61 3.19. Equivalencia entre la uni´on y la suma de la intersecci´on y las diferencias. . . . 61 5.1. Casodeprueba1. ................................. 88 5.2. Salida del caso de prueba 1 para el algoritmo de intersecci´on. . . . . . . . . . 89 5.3. Salida del caso de prueba 1 para el algoritmo de la diferencia. . . . . . . . . . 90 5.4. Salida esperada del caso de prueba 1 para el algoritmo de uni´on. . . . . . . . 91 5.5. Casodeprueba2. ................................. 92 5.6. Salida del caso de prueba 2 para el algoritmo de intersecci´on. . . . . . . . . . 92 5.7. Salida del caso de prueba 2 para el algoritmo de la diferencia. . . . . . . . . . 93 5.8. Salida del caso de prueba 2 para el algoritmo de uni´on. . . . . . . . . . . . . . 94 5.9. Casodeprueba3. ................................. 95 5.10. Salida del caso de prueba 3 para el algoritmo de intersecci´on. . . . . . . . . . 96 5.11. Salida del caso de prueba 3 para el algoritmo de la diferencia. . . . . . . . . . 96 5.12. Salida del caso de prueba 3 para el algoritmo de uni´on. . . . . . . . . . . . . . 97 5.13.Casodeprueba4. ................................. 97 5.14. Salida del caso de prueba 4 para el algoritmo de intersecci´on. . . . . . . . . . 98 5.15. Salida del caso de prueba 4 para el algoritmo de la diferencia. . . . . . . . . . 99 5.16. Salida del caso de prueba 4 para el algoritmo de uni´on. . . . . . . . . . . . . . 100 5.17.Casodeprueba5. ................................. 100 5.18. Salida del caso de prueba 5 para el algoritmo de intersecci´on. . . . . . . . . . 101 16 ´ INDICE DE FIGURAS 5.19. Salida del caso de prueba 1 para el algoritmo de la diferencia. . . . . . . . . . 102 5.20. Salida esperada del caso de prueba 1 para el algoritmo de uni´on. . . . . . . . 102 5.21. Salida esperada del caso de prueba 1 para el algoritmo de uni´on. . . . . . . . 104 5.22. Salida obtenida del caso de prueba 1 para el algoritmo de uni´on. . . . . . . . 104 17 ´ INDICE DE FIGURAS 18 ´ INDICE DE CUADROS ´ Indice de cuadros 2.1. Fases del desarrollo de proyecto. . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.2. Tabla de riesgos del proyecto. . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.3. Plan de contingencia del proyecto. . . . . . . . . . . . . . . . . . . . . . . . . 39 2.4. Coste de trabajo de personal del proyecto. . . . . . . . . . . . . . . . . . . . . 40 2.5. Coste de uso de las m´aquinas en el proyecto. . . . . . . . . . . . . . . . . . . 40 2.6. Coste total del proyecto. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 19 ´ INDICE DE CUADROS 20 LISTINGS Listings 4.1. EstructuraPoint................................... 64 4.2. EstructuraSegment. ................................ 64 4.3. Estructura PointLookUp. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4.4. Estructura TriangleReal. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 4.5. Macros de gesti´on de memoria alocada. . . . . . . . . . . . . . . . . . . . . . 66 4.6. Macros de gesti´on de error de punto flotante. . . . . . . . . . . . . . . . . . . 66 4.7. Macros que calculan el m´aximo y el m´ınimo. . . . . . . . . . . . . . . . . . . 67 4.8. Funci´on principal del algoritmo de intersecci´on. . . . . . . . . . . . . . . . . . 67 4.9. Funci´on principal del algoritmo de la diferencia. . . . . . . . . . . . . . . . . . 68 4.10. Funci´on principal del algoritmo de uni´on. . . . . . . . . . . . . . . . . . . . . 69 4.11. Funci´on principal de construcci´on del pol´ıgono de intersecci´on. . . . . . . . . 71 4.12. Funci´on principal de la partici´on del pol´ıgono de intersecci´on. . . . . . . . . . 76 5.1. Salidas esperadas y obtenidas por la intersecci´on para el caso 1. . . . . . . . . 88 5.2. Salidas esperadas y obtenidas por la diferencia para el caso 1. . . . . . . . . . 89 5.3. Salidas esperadas y obtenidas por la uni´on para el caso 1. . . . . . . . . . . . 89 5.4. Salidas esperadas y obtenidas por la interescci´on para el caso 2. . . . . . . . . 92 5.5. Salidas esperadas y obtenidas por la diferencia para el caso 2. . . . . . . . . . 92 5.6. Salidas esperadas y obtenidas por la uni´on para el caso 2. . . . . . . . . . . . 93 5.7. Salidas esperadas y obtenidas por la intersecci´on para el caso 3. . . . . . . . . 95 21 LISTINGS 5.8. Salidas esperadas y obtenidas por la diferencia para el caso 3. . . . . . . . . . 95 5.9. Salidas esperadas y obtenidas por la uni´on para el caso 3. . . . . . . . . . . . 96 5.10. Salidas esperadas y obtenidas por la intersecci´on para el caso 4. . . . . . . . . 98 5.11. Salidas esperadas y obtenidas por la diferencia para el caso 4. . . . . . . . . . 98 5.12. Salidas esperadas y obtenidas por la uni´on para el caso 4. . . . . . . . . . . . 99 5.13. Salidas esperadas y obtenidas por la intersecci´on para el caso 5. . . . . . . . . 101 5.14. Salidas esperadas y obtenidas por la diferencia para el caso 5. . . . . . . . . . 101 5.15. Salidas esperadas y obtenidas por la uni´on para el caso 1. . . . . . . . . . . . 101 5.16. Salida obtenida por la uni´on para el caso 1. . . . . . . . . . . . . . . . . . . . 103 5.17. Salidas obtenidas por la uni´on para el caso 1. . . . . . . . . . . . . . . . . . . 103 22 CAP´ ITULO 1. INTRODUCCI ´ ON Cap´ıtulo 1 Introducci´on En este cap´ıtulo se introducen los siguientes aspectos: El contexto y la motivaci´on del proyecto. El planteamiento del problema y los objetivos del proyecto. La organizaci´on de los contenidos del documento. 1.1. Contexto En esta secci´on se describe el contexto en el que se desarrolla este proyecto, introduciendo los principales fundamentos de la computaci´on paralela, de los sistemas paralelos, de los sistemas heterog´eneos y del particionado del espacio de datos. 1.1.1. Computaci´on paralela Actualmente, existe una gran cantidad de problemas de car´acter cient´ıfico cuya resoluci´on es muy costosa en tiempo de ejecuci´on con los m´etodos de computaci´on cl´asicos. Entre los ejemplos de estos problemas encontramos simulaciones que involucran c´alculos complejos y/o grandes vol´umenes de datos en diferentes ´areas de conocimiento [1] tales como las matem´aticas, astronom´ıa, biolog´ıa o medicina, que sin el paradigma de la computaci´on paralela tardar´ıan una cantidad significativa de tiempo de procesamiento continuado para finalizar. Existen otras aplicaciones como el deep learning [2], basadas en el uso de redes neuronales, que sin la mejora de rendimiento que supone el uso de sistemas de computo paralelos ser´ıa pr´acticamente inabordables. Estas redes neuronales aprovechan todos los recursos hardware existentes en dispositivos aceleradores, como GPUs (unidades de Procesamiento Gr´afico [3]) 23 1.1. CONTEXTO y FGPAs (matriz de puertas l´ogicas programable [4]). La miner´ıa de monedas criptogr´aficas, como los BitCoins, es otro ejemplo basada en la resoluci´on de problemas matem´aticos, soportada en gran medida por las tarjetas gr´aficas. Para conseguir estas optimizaciones, la computaci´on paralela se basa en el uso de muchas unidades computacionales que llevan a cabo c´alculos de forma simult´anea [5]. De esta forma, grandes problemas computacionales son divididos en otros problemas m´as peque˜nos, resueltos individualmente por cada una de estas unidades de procesamiento. Un ejemplo t´ıpico de estos problemas es una multiplicaci´on de matrices con un gran n´umero de elementos. Los espacios de datos son repartidos entre los nodos de computo, reduciendo de forma te´orica los tiempos proporcionalmente al n´umero de nodos. Actualmente, los ordenadores con mayor capacidad computacional del mundo emplean el paradigma de la computaci´on paralela y se invierten millones de euros en el desarrollo y mejora de estas supercomputadoras, as´ı como en el alquiler de las mismas para la realizaci´on de c´alculos cient´ıficos. En la lista de TOP 500 [6] se publica cada medio a˜no la lista actualizada de los 500 superordenadores m´as potentes del mundo. Adem´as, tambi´en se publica la lista de los Green500, con los 500 supercomputadores energ´eticamente m´as eficientes. 1.1.2. Sistemas paralelos Una aplicaci´on secuencial puede escalar su rendimiento de manera proporcional al n´umero de unidades computacionales del sistema. En este caso ideal, con dos o cuatro unidades funcionales el tiempo se ve dividido a la mitad o la cuarta parte, respectivamente. El tiempo necesario para ejecutar una aplicaci´on de forma secuencial puede optimizarse mejorando su rendimiento de manera lineal, es decir, si se duplican sus elementos de c´omputo el tiempo se reduce a la mitad del tiempo obtenido secuencialmente, si se triplican este tiempo se reduce a una tercera parte, y as´ı sucesivamente. Esa mejora del rendimiento es ideal, ya que en la pr´actica no se alcanzan estos escenarios, debido a problemas como el tiempo de encaminamiento, en concreto con los mecanismos de de comunicaci´on y sincronizaci´on, asociados al coste temporal que supone la divisi´on del problema entre subtareas concurrentes y el paso de datos entre procesadores debido a dependencias; la necesidad de disipar el calor generado por estos grandes supercomputadores o secciones de c´odigo que solo pueden ser ejecutadas de forma estrictamente secuencial. A pesar de los problemas anteriormente mencionados, la computaci´on paralela presenta una serie de ventajas [7] tal y como se observan en los siguientes items: La resoluci´on de problemas que no se podr´ıan ser ejecutados secuencialmente con una sola CPU en un tiempo razonable. Ejecuci´on de una mayor carga computacional en menos tiempo a trav´es de aceleradoras hardware como GPUs y FGPAs. Posibilidad de ejecuci´on de problemas de complejidad y orden mayor en un tiempo razonable. 24 CAP´ ITULO 1. INTRODUCCI ´ ON Permite la ejecuci´on simult´anea de varias instrucciones y/o tareas. Se obtiene un mejor balance entre productividad y coste que en la computaci´on secuencial tradicional. Se obtiene un mejor balance entre productividad y coste energ´etico que en la computaci´on secuencial tradicional. Gran capacidad expansi´on, es decir, posibilidad de a˜nadir nuevos nodos y dispositivos hardware. Gran capacidad de escalabilidad, es decir, que la mejora del sistema aumente de forma proporcional a la expansi´on en nodos. Actualmente, el supercomputador m´as potente del mundo est´a localizado en Jap´on. Se trata de Fugaku [8], que cuenta con un total de 7.600.848 cores y una potencia de c´alculo de 415.599 Teraflops, lo que equivale a 230.833 PlayStation 4 trabajando simult´aneamente [9]. 1.1.3. Sistemas heterog´eneos Un sistema de computaci´on heterog´eneo es aquel que est´a compuesto por unidades computacionales y/o nodos con arquitecturas distintas, conectados a trav´es de un sistema de red. MareNostrum 5 [10] es un ejemplo de sistema heterog´eneo, siendo ´este uno de los supercomputadores m´as avanzados de Europa, localizado en Espa˜na, cuyas optimizaciones m´as recientes consisten en la integraci´on de una mayor variedad de procesadores, cada unos orientados a aplicaciones m´as espec´ıficas. Los sistemas heterog´eneos presentan una serie de ventajas [11] frente a los sistemas homog´eneos, entre las que se encuentran: La diversidad de procesadores permite diferentes opciones de ejecuci´on, empleando aquellos recursos mejor optimizados para las distintas tareas que conforman un problema. El gasto energ´etico asociado a los c´alculos puede ser regulado eligiendo qu´e nodos van a llevar a cabos los c´alculos. Ante la posibilidad de presentar diferentes potencias de c´alculo en cada nodo, se puede llevar a cabo repartos de carga adaptados a las velocidades de los distintos procesadores, para alcanzar un nivel superior de optimizaci´on. 1.1.4. Particionado de datos Una de las caracter´ısticas principales de la computaci´on paralela es la posibilidad de repartir de carga entre los distintos procesadores o nodos de computo, de forma que las distintas tareas y conjuntos de datos son asignados a cada unidad de c´omputo teniendo en 25 1.4. ESTRUCTURA DEL DOCUMENTO El cap´ıtulo cuatro explica la implementaci´on final de los algoritmos mencionados, a trav´es de sus cabeceras, includes y funciones principales. El cap´ıtulo cinco presenta las pruebas realizadas para validar los resultados obtenidos por los tres algoritmos. El cap´ıtulo seis describe las conclusiones, incluyendo objetivos cumplidos y trabajo futuro. 32 CAP´ ITULO 2. PLANIFICACI ´ ON Cap´ıtulo 2 Planificaci´on En este cap´ıtulo se introducen los siguientes aspectos: El modelo de desarrollo empleado para llevar a cabo el proyecto. Los riesgos del proyecto, junto al camino cr´ıtico y el plan de contingencia para los distintos riesgos. El coste estimado del desarrollo del proyecto. 2.1. Modelo de desarrollo Para el desarrollo de este proyecto se ha escogido como m´etodo un System Development Life Cycle [22] (a partir de ahora referenciado como SDLC) lineal en cascada. En este SDLC el proyecto es divido en una serie de fases secuenciales, en las que se enfatiza el dise˜no y cumplimiento de un plan, con unas fechas objetivo y donde se realiza un control riguroso durante el ciclo de desarrollo sobre el avance y estado del proyecto mediante documentaci´on y reuniones peri´odicas con los “project managers”. En este proyecto, los encargados de la supervisi´on del desarrollo son los tutores acad´emicos, Yuri Torres de la Sierra y Mar´ıa Inmaculada Santamar´ıa Valenzuela. Este modelo de desarrollo ha sido seleccionado por ser un buen candidato para proyectos donde el equipo de desarrollo no cuenta con mucha experiencia, debido a la rigurosidad con la que se comprueba el alcance de los objetivos establecidos, as´ı como la correcci´on de la documentaci´on y el software desarrollado, adem´as de que permite medir con facilidad el avance del desarrollo. Adem´as, es f´acilmente integrable con las mec´anicas de trabajo del grupo de investigaci´on de Trasgo, con reuniones de trabajo semanales y diversos canales de comunicaci´on directa, que permiten realizar reportes con facilidad. 33 2.1. MODELO DE DESARROLLO 2.1.1. Fases del desarrollo Inicialmente, el desarrollo del proyecto se planifica para llevarse a cabo en ocho fases principales. Estas ocho etapas son secuenciales, como consecuencia de la metodolog´ıa de trabajo seleccionada, y la suma de las duraciones de cada una de ellas da como resultado una duraci´on estimada de 300 horas, correspondientes con los 12 cr´editos ECTS asociados a la asignatura del TFG. Las fases en las que se ha dividido el proyecto vienen reflejadas en la siguiente tabla: ID Descripci´on F1 Estudio de la librer´ıa Hitmap. F2 Estudio de los algoritmos. F3 Toma de decisiones de dise˜no relacionadas con el trabajo previo del Technical Report [21]. F4 Implementaci´on del algoritmo de intersecci´on. F4.1 Implementaci´on del algoritmo de construcci´on del pol´ıgono de intersecci´on. F4.2 Implementaci´on del algoritmo de partici´on del pol´ıgono de intersecci´on. F5 Implementaci´on del algoritmo de la diferencia. F6 Implementaci´on del algoritmo de la uni´on. F7 Experimentaci´on. F8 Elaboraci´on de la memoria. Cuadro 2.1: Fases del desarrollo de proyecto. Las fases F1, F2 y F3 est´an relacionadas con el estado del arte del proyecto, aprendizaje de las tecnolog´ıas y lectura del trabajo relacionado previo. Estas son proyectadas para la segunda mitad del primer cuatrimestre, invirtiendo una cantidad de horas semanales menor que el dedicado durante el segundo cuatrimestre debido a la necesidad de compaginar el trabajo con otras cinco asignaturas. Por su parte, la tareas F4, F5, F6, F7 y F8 se proyectan para el segundo cuatrimestre, con un carga semanal aproximada de trabajo de 20 horas. Las fases F4, F5 y F6 se corresponden con la implementaci´on de la extensi´on de la librer´ıa Hitmap, desarrollando los algoritmos de intersecci´on, uni´on y diferencia. La fase F4, es la de mayor duraci´on del proyecto porque engloba aproximadamente un 80 % de la programaci´on total del trabajo, puesto que, como se mencionar´a en el cap´ıtulo 3, los algoritmos de uni´on y diferencia est´an basados en el de intersecci´on. Dentro de la etapa F4 existen dos subfases, correspondientes a la descomposici´on principal del flujo del algoritmo de intersecci´on, la construcci´on del pol´ıgono de intersecci´on y la partici´on del pol´ıgono de intersecci´on. Tras las fases del estado del arte, desarrollo e implementaci´on, se proyectan las dos ´ultimas etapas del proyecto, relacionadas con la experimentaci´on y la documentaci´on. La fase F7 se corresponde con la realizaci´on de la experimentaci´on para validar la correcci´on de los 34 CAP´ ITULO 2. PLANIFICACI ´ ON algoritmos, y la F8 con la elaboraci´on de este documento. Para estas tareas se estima el ´ultimo de mes de trabajo. A continuaci´on, se muestra el diagrama de Gantt [23], que modela el reparto temporal de cada una de las etapas: Figura 2.1: Diagrama de Gantt del proyecto. El n´umero que figura en la columna de la izquierda en el diagrama de Gantt 2.1 se corresponde con el ID de la etapa de desarrollo. Para la primera etapa, iniciada en la segunda mitad de noviembre se planifica para ser llevada a cabo en una semana. Tras esta, siguen la etapa 2 y 3, realizadas de forma secuencial, con una duraci´on una y dos semanas, respectivamente. Tras estas tres primeras fases, relacionadas con el estado del arte del proyecto, se produce una parada en el desarrollo hasta mediados de enero, con la finalizaci´on del per´ıodo de ex´amenes del primer cuatrimestre. Con la finalizaci´on del primer cuatrimestre del curso acad´emico 2020/21, se reanuda el desarrollo del proyecto con las fases relacionadas con la implementaci´on y experimentaci´on. Desde este momento y hasta que se realicen todas la tareas de implementaci´on de los tres algoritmos, etapas con ID 4, 5 y 6, la realizaci´on de la experimentaci´on para validar la correcci´on del c´odigo, etapa con ID 7, y el desarrollo se la librer´ıa se har´an en paralelo. La implementaci´on del algoritmo de intersecci´on se planifica para tener una duraci´on de unos 60 d´ıas lectivos, finalizando a mediados de abril, seguida por la implementaci´on del algoritmo de diferencia, con dos semanas de plazo, y por ´ultimo por la implementaci´on de la uni´on, con una semana de plazo. Estas tres fases son estrictamente secuenciales pues la uni´on se basa en la intersecci´on y la diferencia, y la diferencia en la intersecci´on. Una vez finalizada la programaci´on y la experimentaci´on en la primera semana de mayo, comienza la ´ultima fase del desarrollo, la elaboraci´on de la memoria (ID 8), cuya fecha l´ımite se fija el 14 de junio del 2021 para entregar el proyecto en la primera convocatoria de este mismo curso. 35 2.2. AN ´ ALISIS DE RIESGOS 2.1.2. Seguimiento La duraci´on real de las tareas, en l´ıneas generales, se ha correspondido con la planificaci´on inicial del proyecto. Esto se debe sobretodo a las mec´anicas de trabajo y de seguimiento del grupo de investigaci´on Trasgo. Todos los jueves se han realizado reuniones de trabajo donde todos los investigadores informaban de su progreso semanal. En estas reuniones, se entregaba el trabajo asignado en la reuni´on anterior y se recib´ıan nuevas tareas para la semana siguiente. De esta forma, se controla el progreso del proyecto, adem´as de recibir un feedback constante sobre el ritmo y la calidad del trabajo. A mayores, a partir de mayo se realizan reuniones los martes para revisar el estado de esta memoria. Adem´as de las reuniones realizadas de forma telem´atica v´ıa Discord (una plataforma de videoconferencias [24]), se cuenta con una canal de texto donde se deja por escrito las tareas del proyecto que van siendo asignadas por el tutor, as´ı como el estado de las mismas (terminadas, en proceso o inacabadas). De esta forma, las etapas 1, 2 y 3 se realizaron en los tiempos que fueron estimados, realizando todas las tareas relacionadas con el estado del arte antes de terminar el primer cuatrimestre. Con la finalizaci´on del per´ıodo ordinario de ex´amenes se retoma el trabajo, con el inicio de la etapa 4. Esta es la ´unica fase del proyecto que experimenta ciertos atrasos con las entregas, debido a problemas en el c´odigo y a la aparici´on de errores en las salidas de los casos de prueba nuevos que se˜nalaban a errores de validez en secciones de c´odigo realizadas tiempo atr´as. Estos atrasos surgieron en concreto en la etapa 4.2. que se corresponde con la implementaci´on del algoritmo de partici´on del pol´ıgono de intersecci´on, con una demora de entre 1 y 2 semanas. Para solventar esto, se aumento el ritmo de trabajo en la semana posterior a la entrega de la tarea asociada y se logr´o recuperar el avance correcto de las tareas seg´un la planificaci´on inicial y no atrasar las posteriores etapas. Por su parte, las etapas 5, 6, 7 y 8 fueron completadas en los tiempos proyectados sin ning´un tipo de percance. 2.2. An´alisis de riesgos En esta secci´on se van a enumerar los principales riesgos que amenazan el avance del proyecto, se va a describir el camino cr´ıtico del mismo y cu´ales son las principales medidas del plan de contingencia para paliar los efectos adversos asociados a cada uno de los riesgos. 2.2.1. Riesgos Los autores Bob Hughes y Mike Cotterell [25] definen un riesgo como “Una condici´on o evento incierto que, si ocurre tiene efectos positivos o negativos en los objetivos del proyecto”. Empleando la metodolog´ıa de Barry Boehm [25] se han enumerado los principales riesgos que pueden afectar al proyecto en la siguiente. En la tabla 2.2, se muestra el ´ındice denominado como exposici´on al riesgo [25]. ´ Este es empleado para medir el da˜no potencial de un riesgo y es calculado como el producto de la 36 CAP´ ITULO 2. PLANIFICACI ´ ON Descripci´on del riesgo Probabilidad Impacto Riesgo Desarrollo t´ecnicamente demasiado complejo 5 4 20 Estimaci´on no realista de los tiempos de desarrollo 6 4 24 Aver´ıa de la m´aquina de trabajo personal usada para el desarrollo 1 2 2 Enfermedad del programador 2 6 12 Enfermedad del tutor 2 3 6 Retrasos en el desarrollo debido a confinamientos del programador o tutores por el Covid-19 4 3 12 Resultados de la experimentaci´on err´oneos 5 3 15 Cambio en los requisitos durante el desarrollo del proyecto 1 7 7 Cuadro 2.2: Tabla de riesgos del proyecto. probabilidad de que un riesgo se materialice por el impacto que este produce. Este valor es empleado para priorizar el uso de recurso a la hora de dise˜nar planes de contingencia frente a los distintos riesgos. Los valores que pueden tomar tanto la probabilidad como el impacto van de 0 a 10 y por tanto, el riesgo puede ir de 0 a 100. Como es l´ogico aquellos riesgos con valores m´as alto deber´an ser los primeros en ser atendidos. Para el caso de este proyecto son el desarrollo t´ecnico demasiado complejo y una estimaci´on no realista de los tiempos de desarrollo. 2.2.2. Camino cr´ıtico El camino cr´ıtico de un proyecto [26] se define como la cadena de actividades que define la duraci´on de un proyecto y que, por ende si se experimenta un retraso en alguna de las actividades se producir´a un retraso en la duraci´on total del proyecto. Este camino cr´ıtico esta marcado en rojo en el diagrama de Gantt de la figura 2.2. Figura 2.2: Camino cr´ıtico del proyecto. 37 2.3. PRESUPUESTO DEL PROYECTO Como se puede apreciar en el diagrama de Gantt, el camino cr´ıtico esta formado por las etapas 4 a 8 del proyecto. Esto se debe a dos razones principales: La secuencialidad de las tareas de implementaci´on, en paralelo a su correspondiente experimentaci´on, seguidas de la elaboraci´on de este documento. La presencia de una per´ıodo de tiempo de pausa para el proyecto entre las etapas 3 y 4, debido a la presencia de los ex´amenes del primer cuatrimestre. Las tres primeras etapas, relacionadas con el estado del arte, est´an proyectadas para ser acabadas a mediados de diciembre y al no retomarse la actividad del proyecto hasta el segundo cuatrimestre, se cuenta con un per´ıodo de un mes por el cual si se produce alg´un retraso en las primeras fases, este no afectar´a a la duraci´on del proyecto. Por otro lado, las etapas 4, 5, 6, 7 y 8 conforman el anteriormente definido como camino cr´ıtico, pues un retraso en cualquiera de ellas retrasar´ıa la fecha de finalizaci´on global. La implementaci´on de cada uno de los tres algoritmos se hace de forma secuencial, mientras la experimentaci´on para validar su correcci´on se hace en paralelo. Por ´ultimo, solo cuando se haya terminado tanto la implementaci´on como la experimentaci´on se podr´a iniciar la elaboraci´on de esta memoria. Esta secuencialidad es inherente a un proyecto de estas caracter´ısticas donde se cuenta con un ´unico programador. 2.2.3. Plan de contingencia El libro “Software Project Manager” [25] define el plan de contigencia como un conjunto de acciones que se llevan a cabo para mitigar el impacto de la materializaci´on de uno o m´as riesgos. En la tabla 2.3 se muestra las principales medidas propuestas para hacer frente a los riesgos descritos en la secci´on 2.2.1. 2.3. Presupuesto del proyecto En esta secci´on se realiza un an´alisis del presupuesto del proyecto. El coste asociado a todo el ciclo de desarrollo se puede desglosar en dos grupos principales; la amortizaci´on de las maquinas de trabajo empleadas y las horas de trabajo del desarrollador y de los tutores. Esto es as´ı pues no ha sido necesario la adquisici´on de licencias de software ni emplear m´aquinas del cluster del grupo de investigaci´on Trasgo. De esta forma el presupuesto del proyecto se distribuye de la siguiente manera: Sueldo del desarrollador: se estima el sueldo de un ingeniero inform´atico junior en unos 20.000 ebrutos anuales. Trabajando a jornada completa (8 horas diarias) y suponiendo unos 250 d´ıas laborales al a˜no aproximadamente, se obtiene un coste del desarrollador de 10 ela hora. 38 CAP´ ITULO 2. PLANIFICACI ´ ON Descripci´on del riesgo Plan de Contingencia Desarrollo t´ecnicamente demasiado complejo. Se acotan los objetivos del proyecto. Estimaci´on no realista de los tiempos de desarrollo. Se realiza la entrega del proyecto en la segunda convocatoria. Aver´ıa de la m´aquina de trabajo personal usada para el desarrollo. Se recupera el trabajo del repositorio remoto y se continua el desarrollo en las m´aquinas de Trasgo. Enfermedad del programador Se realiza el trabajo de forma telem´atica y entrega del proyecto en segunda convocatoria. Enfermedad del tutor. Se realizan las consultas sobre el desarrollo del proyecto al resto de tutores u otros investigadores del grupo Trasgo. Retrasos en el desarrollo debido a confinamientos del programador o tutores por el Covid-19. Se realiza trabajo y seguimiento telem´atico v´ıa discord y con repositorios remotos. Resultados de la experimentaci´on err´oneos. Se realiza la b´usqueda del origen de los errores mediante las herramientas valgrind y GDB. En caso de no solucionarlos declararlos como trabajo futuro. Cambio en los requisitos durante el desarrollo del proyecto. Se aumentan las horas de trabajo semanales para alcanzar los nuevos objetivos. Cuadro 2.3: Plan de contingencia del proyecto. Sueldo del tutor personal docente investigador predoctoral: se estima el sueldo de un investigador doctorando en unos 14000 ebrutos anuales. Trabajando a jornada completa (8 horas diarias) y suponiendo unos 250 d´ıas laborales al a˜no aproximadamente, se obtiene un coste del desarrollador de 7 ela hora. Sueldo del tutor personal docente investigador: se estima el sueldo de un investigador doctorando en unos 28000 ebrutos anuales. Trabajando a jornada completa (8 horas diarias) y suponiendo unos 250 d´ıas laborales al a˜no aproximadamente, se obtiene un coste del desarrollador de 14 ela hora. Coste de la m´aquina de desarrollado: la m´aquina utilizada se trata de un Lenovo Thinkpad de 16 GB de RAM, un procesador Intel Core i7 y una memoria gr´afica GeForce MX250. Tuvo un coste de 1400 ey con estimaci´on de vida ´util de 5 a˜nos. El coste asociado a la amortizaci´on es de 0,31 e/hora. Las horas de utilizaci´on de cada recurso se proyectan de la siguiente forma: Desarrollador: 300 horas asociadas a los 12 cr´editos de la asignatura del Trabajo de Fin de Grado. Tutora personal docente investigador predoctoral: el desarrollo de este proyecto se enmarca dentro de uno de los proyectos de investigaci´on del grupo Trasgo y la tutora 39 2.3. PRESUPUESTO DEL PROYECTO acad´emica Mar´ıa Inmaculada Santamar´ıa es la principal investigadora en el mismo. Se estima que invertir´a unas 100 horas totales. Tutor personal docente investigador: con el tutor acad´emico Yuri Torres se realizan 8 reuniones de una hora a partir del 4 de mayo con motivo de revisi´on de esta memoria. A mayores, todos los jueves desde el inicio del proyecto se realizan reuniones de seguimiento de una duraci´on aproximada de media hora en las que participan Yuri Torres y Arturo Gonz´alez. El total de horas empleadas por el personal docente investigador en este proyecto se estima en 23h. M´aquina del desarrollador: se utiliza durante la totalidad del proyecto, por ende, 300 horas. Bajo estas condiciones, el coste de trabajo del personal y de uso de las m´aquinas en el proyecto viene descrito en las tablas 2.4 y 2.5. Personal Coste/hora (e) Horas Total Alumno 10 300 3000 Tutora PDI predoctoral 7 100 700 Tutor PDI 1 14 15 210 Tutor PDI 2 14 8 112 Total 4022 Cuadro 2.4: Coste de trabajo de personal del proyecto. M´aquina Precio (e) Amortizaci´on (a˜nos) Coste/hora (e) Horas Total (e) Del desarrollador 14000 5 0.31 300 93 Total 93 Cuadro 2.5: Coste de uso de las m´aquinas en el proyecto. En la tabla 2.6 se indica cual es el coste total del proyecto, calculado a partir del coste de las m´aquinas y de las horas de trabajo del personal. Actividad Coste (e) Horas de trabajo del personal 4022 Uso de las m´aquinas 93 Total 4115 Cuadro 2.6: Coste total del proyecto. 40 CAP´ ITULO 3. AN ´ ALISIS Y DISE ˜ NO Cap´ıtulo 3 An´alisis y dise˜no En este cap´ıtulo se introducen los siguientes aspectos: Un an´alisis sobre la funcionalidad de Hitmap que va a ser ampliada. La funcionalidad de los algoritmos selecccionados (intersecci´on, uni´on y diferencia); una descripci´on gen´erica. Los fundamentos matem´aticos de los diferentes algoritmos seleccionados. El dise˜no de cada uno de los tres algoritmos. 3.1. An´alisis El objetivo de este proyecto es es ampliar la funcionalidad de la librer´ıa Hitmap del grupo de investigaci´on de Trasgo, para permitir el particionado triangular del espacio de memoria, tambi´en denominado como la triangularizaci´on de espacio de datos. Tal y como se ha descrito en la secci´on 1.2.3., Hitmap es una librer´ıa dise˜nada para desacoplar el patr´on de comunicaci´on del particionado de datos, mediante el uso de expresiones abstractas que se adaptan autom´aticamente en tiempo de ejecuci´on dependiendo de la partici´on finalmente utilizada. Para lograr esto, la librer´ıa trabaja con las siguientes estructuras [14]: Signature: Una Signature S es una tupla de tres elementos enteros que representa un subespacio de ´ındices de una array un en dominio de una dimensi´on. De esta forma, la definici´on de una signature es la siguiente: S∈Signature = (begin :end :stride) Card(s∈Signature) = [(s.end −s.begin)/s.stride] 41 3.2. FUNCIONALIDAD DE LOS ALGORITMOS Figura 3.8: Salida del caso de prueba 1 para el algoritmo de la diferencia. Figura 3.9: Caso de prueba 1 de la uni´on. Salida: Un array de Shapes de 2 dimensiones, compuesto por los pol´ıgonos que conforman la partici´on de los pol´ıgonos de la uni´on. En la figura 3.7 se puede apreciar en rojo los Shapes que conforman dicha partici´on. Consideraciones: •La salida es una array de Shapes. Estos Shapes solo pueden ser de aquellos tipos 48 CAP´ ITULO 3. AN ´ ALISIS Y DISE ˜ NO Figura 3.10: Partici´on del pol´ıgono de la uni´on del caso de prueba 1. modelados por la librer´ıa Hitmap y su extensi´on, es decir, pol´ıgonos rectangulares o triangulares. •Las Signatures son tuplas de tres elementos enteros que representan un subconjunto de ´ındices pertencientes a Z2. •Las intersecciones entre los lados de los Shapes de entrada dan lugar a los v´ertices del pol´ıgono de intersecci´on con coordenadas en R2y no en Z2. Esto obliga al algoritmo a realizar un reajuste a coordenadas enteras de los pol´ıgonos para poder ser modelados mediante las estructuras Signature y Shape. •El reajuste de los pol´ıgonos de la partici´on de los pol´ıgonos de la diferencia da lugar a puntos aislados con coordenadas enteras que pertenecen a la diferencia pero que al reajustarse ya no se encuentran dentro de los Shapes reajustados. Estos puntos son denominados outsiders y hay que a˜nadirlos al array de Shapes de salida. •El conjunto de pol´ıgonos que conforman la partici´on del pol´ıgono de intersecci´on debe ser disjunto, es decir, un ´ındice no puede pertenecer a m´as de un pol´ıgono. Esto asegura que una posici´on de memoria o dato es procesada ´unica y exclusivamente por una unidad de computo concreta. •Los outsiders pueden ser modelados mediante Shapes en forma de tri´angulos o rect´angulos de dimensi´on 0. Para ello, los campos begin y end, de las signatures de los pol´ıgonos deben tener el mismo valor. •La salida del algoritmo de uni´on de dos Shapes, Sa y Sb, es equivalente a las salidas de la diferencia de Sa menos Sb, la salida de Sb menos Sa y la salida de la intersecci´on de Sa y Sb, almacenadas en un ´unico array. Como consecuencia de estas consideraciones obtenemos que la salida de la uni´on para el caso 49 3.3. REQUISITOS FUNCIONALES Y NO FUNCIONALES de prueba 1, indicado en la 3.9, es la siguiente: Figura 3.11: Salida del caso de prueba 1 para el algoritmo de uni´on. 3.3. Requisitos funcionales y no funcionales Resultado de las caracter´ısticas y funcionalidades ofrecidas por la librer´ıa Hitmap, as´ı como de los objetivos presentes en la extensi´on de la misma a desarrollar en este proyecto, se establecen un conjunto de requisitos que debe cumplir el nuevo software. Estos requisitos se categorizan en dos grupos principales, funcionales y no funcionales. Los requisitos funcionales [28] son declaraciones de los servicios y funcionalidades que ofrecer´a el software a desarrollar y de la forma en que ´este se comportar´a a entradas particulares. La extensi´on de la librer´ıa Hitmap a desarrollar durante este proyecto presenta los siguientes requisitos funcionales: RF01: La librer´ıa debe modelar particiones triangulares del espacio de memoria. Como se ha descrito en la secci´on 1.2.4, el principal objetivo de la extensi´on de la librer´ıa Hitmap que se va a desarrollar es la posibilidad de admitir tri´angulos como unidad de divisi´on del particionado del espacio de datos. Esto permite a la librer´ıa Hitmap adapatarse mejor a la geometr´ıa del problema de computo. RF02: La librer´ıa debe calcular la intersecci´on entre dos shapes. 50 CAP´ ITULO 3. AN ´ ALISIS Y DISE ˜ NO Para poder trabajar con las particiones triangulares de memoria es necesario poder obtener la intersecci´on entre dos shapes (estructura definida por Hitmap) y obtener su correspondiente partici´on en pol´ıgonos manejados por la librer´ıa y su correspondiente extensi´on. RF03: La librer´ıa debe calcular la diferencia entre dos shapes. Para poder trabajar con las particiones triangulares de memoria es necesario poder obtener la diferencia entre dos shapes y obtener su correspondiente partici´on en pol´ıgonos manejados por la librer´ıa y su correspondiente extensi´on. RF04: La librer´ıa debe calcular la uni´on entre dos shapes. Para poder trabajar con las particiones triangulares de memoria es necesario poder obtener la uni´on entre dos shapes y obtener su correspondiente partici´on en pol´ıgonos manejados por la librer´ıa y su correspondiente extensi´on. Los requisitos no funcionales [28] son aquellos requerimientos que no se refieren directamente a las funciones espec´ıficas que ofrece el software, sino a las propiedades emergentes de ´este como la fiabilidad, la respuesta en el tiempo y la capacidad de almacenamiento, as´ı como las restricciones del sistema. La extensi´on de la librer´ıa Hitmap a desarrollar durante este proyecto presenta los siguientes requisitos no funcionales: RNF01: Los shapes manejados por la librer´ıa podr´an representar rect´angulos, tri´angulos, segmentos o puntos. Como se describe en la secci´on 3.1, la estructuras de la librer´ıa Hitmap son capaces de modelar rect´angulos de lados paralelos a los ejes de coordenadas, as´ı como puntos y segmentos. Para lograr la triangularizaci´on del espacio de datos es necesario extender la estructura HitSigExtShape para que pueda modelar tambi´en tri´angulos. RNF02: Los c´alculos realizados por la librer´ıa para los algoritmos de intersecci´on, diferencia y uni´on deben ser correctos. Los c´alculos realizados por dichos algoritmos ser´an empleados para manejar el particionado de memoria de un espacio de datos. Si estas operaciones son realizadas de forma incorrecta o con salidas distintas a las esperadas puede degenerar en errores en la gesti´on de memoria y de procesos en las aplicaciones que utilicen la librer´ıa Hitmap en el ´ambito de la computaci´on paralela heterog´enea. 51 3.4. FUNDAMENTOS MATEM ´ ATICOS DE LOS ALGORITMOS RNF03: Las particiones realizadas para las salidas de los algoritmos deben ser disjuntas y todo ´ındice de memoria de la salida debe pertenecer a una partici´on. El objetivo del particionado es que todo ´ındice sea gestionado ´unicamente por un procesador, con el objetivo de evitar c´alculos redundantes, en caso de un´ındice que pertenece a m´as de un partici´on, y p´erdida de informaci´on, en caso de que un ´ındice no pertenezca a ninguna partici´on. Para ello, se debe asegurar que las salidas de los algoritmos sean disjuntas y recojan todos los ´ındices necesarios. RNF05: El software debe integrarse correctamente en la arquitectura de la librer´ıa Hitmap. La librer´ıa Hitmap cuenta con una estructura de directorios de cierta complejidad y que responde a unos criterios de dise˜no propuestos por el grupo de investigaci´on Trasgo. Es por ello que los ficheros creados para extender la librer´ıa deben ser incluidos correctamente en la arquitectura de la librer´ıa. RNF04: El lenguaje de programaci´on empleado para el desarrollo debe ser C. El lenguaje de programaci´on empleado debe ser el mismo que ha sido empleado por el grupo de Investigaci´on trasgo para la implementaci´on de la librer´ıa Hitmap. Es por ello que el desarrollo se realizar´a en C. 3.4. Fundamentos matem´aticos de los algoritmos En esta secci´on se enumeran los fundamentos y teoremas matem´aticos en los que se basan los algoritmos de intersecci´on, diferencia y uni´on. Existen una serie de fundamentos matem´aticos comunes a los tres algoritmo que son empleados como base para la construcci´on de sus respectivas operaciones. Son ejemplos de esto la teor´ıa de conjuntos y de partici´on. A lo largo de todo el proyecto se trabajan con conjuntos de ´ındices que representan posiciones de memoria con la particularidad de que su geometr´ıa viene definida por la estructura Shape de la librer´ıa Hitmap. Las operaciones de intersecci´on, diferencia y uni´on se realizar´an sobre dos conjuntos obteniendo un subconjunto o un nuevo conjunto, en funci´on del algoritmo. Es por ello que se procede a definir lo que es un conjunto: Conjunto [29] es una colecci´on bien definida de objetos, es decir, est´a definida de forma que para un objeto xcualquiera, podamos determinar si xpertenece o no al conjunto. Los objetos que pertenecen al conjunto se llaman elementos o miembros. Denotaremos los conjuntos por letras may´usculas, tales como A o X; si a es un elemento del conjunto A, escribimos a ∈A. Una particularidad de los algoritmos implementados en esta extensi´on de Hitmap es que los conjuntos de salida se almacenan en un array de Shapes. Estos Shapes son tri´angulos 52 CAP´ ITULO 3. AN ´ ALISIS Y DISE ˜ NO o rect´angulos que conforman la partici´on del conjunto inicial, habilitando la posibilidad de asignar cada partici´on a un procesador virtual. Es por ello que se procede a definir lo que es una partici´on: Partici´on P de un conjunto X, es una colecci´on de conjuntos no vac´ıos X1,X2, ... tales que XiTXj=∅para i 6= j y SkXk= X. Sea una relaci´on de equivalencia en un conjunto X y sea x∈X. Entonces [x] = {y∈X:y−x}se llama clase de equivalencia de x. 3.4.1. Intersecci´on Seg´un la teor´ıa de conjuntos, la intersecci´on de dos conjuntos A y B, no vac´ıos, se define como [29]: ATB={x:x∈Ayx∈B} Teorema: La intersecci´on de un pol´ıgono convexo de nlados con otro convexo de m lados es un pol´ıgono convexo de c´omo mucho n+mv´ertices [30]. Como consecuencia del teorema anterior, la intersecci´on calculada por la librer´ıa Hitmap obtiene como salida un pol´ıgono de intersecci´on con un m´aximo de 8 v´ertices (intersecci´on entre dos rect´angulos). El pol´ıgono de intersecci´on de dos Shapes, Sa y Sb, viene determinado por los siguientes v´ertices: Los puntos resultantes de la intersecci´on entre los lados de Sa y Sb. Los v´ertices de Sa que pertenecen a Sb. Los v´ertices de Sb que pertenecen a Sa. Para la determinaci´on de aquellos v´ertices obtenidos a trav´es de la intersecci´on de los lados de los Shapes Sa y Sb, se emplean las ecuaciones de las rectas que estos lados determinan [31]: a1x+b1y=c1a2x+b2y=c2 y se obtienen, a partir de la regla de Cramer o sustituyendo una variable, las coordenadas del punto de intersecci´on (xs, ys)(xs, ys) : xs=c1b2−c2b1 a1b2−a2b1 , ys=a1c2−a2c1 a1b2−a2b1 (Si a1b2−a2b1= 0 las l´ıneas son paralelas y estas f´ormulas no se pueden usar porque implican dividir por 0). A mayores es necesario tener en cuenta una serie de consideraciones: 53 3.4. FUNDAMENTOS MATEM ´ ATICOS DE LOS ALGORITMOS 1. La intersecci´on de las dos figuras puede ser un punto o una l´ınea. Esta salida puede ser modelada por las estructuras de Hitmap, a trav´es de Shapes de dimensi´on 0 y 1, respectivamente. 2. Los pol´ıgonos pueden simplemente no interseccionar y est´ar separados. El algoritmo devolver´a un conjunto vac´ıo. 3. Un pol´ıgono puede estar contenido dentro del otro. Como resultado de la intersecci´on de ambos pol´ıgonos se obtendr´a el pol´ıgono que est´a siendo contenido. 3.4.2. Diferencia Seg´un la teor´ıa de conjuntos, la diferencia para dos conjuntos, A y B, no vac´ıos, se define como [29]: A−B={x:x /∈Ayx∈B} Existen una serie de propiedades de la teor´ıa de conjuntos que debe cumplir el algoritmo de la diferencia para su correcto funcionamiento: La diferencia de dos pol´ıgonos, Sa y Sb, teniendo que Sb es un conjunto vac´ıo, tiene como resultado el propio Sa. Esto se debe a la propiedad del elemento neutro: A− ∅ =A La diferencia de un pol´ıgono Sa menos ´el mismo es el conjunto vac´ıo. A−A=∅ La diferencia de dos pol´ıgonos, Sa y Sb, teniendo que ning´un punto de Sb pertenece Sa, es decir, son dos conjuntos disjuntos, tiene como resultado Sa. A-B=A↔ATB=∅ La diferencia de dos pol´ıgonos, Sa y Sb, es el conjunto vac´ıo si Sa est´a contenido en Sb, es decir, Sa se trata de un subconjunto de Sb. A - B = ∅ ↔ A⊆B 3.4.3. Uni´on Seg´un la teor´ıa de conjuntos la uni´on [29] de dos conjuntos, A y B, no vac´ıos, se define como: 54 CAP´ ITULO 3. AN ´ ALISIS Y DISE ˜ NO ASB={x:x∈Aox∈B} Existen una serie de propiedades de la teor´ıa de conjuntos que debe cumplir el algoritmo de la diferencia para su correcto funcionamiento: La uni´on de un pol´ıgono, Sa, consigo mismo es el propio Sa. Esto se debe a la propiedad de Idempotencia: A∪A=A La uni´on de dos pol´ıgonos, Sa y Sb, siendo Sb un pol´ıgono contenido por Sa tiene como resultado el propio Sa. B⊆A→A∪B=A La uni´on de un pol´ıgono Sa con un conjunto vac´ıo es el propio Sa. Esto se debe a la propiedad del elemento neutro: A∪ ∅ =A 3.5. Dise˜no En esta secci´on se describen las principales decisiones de dise˜no tomadas para el desarrollo de la extensi´on de la librer´ıa Hitmap y en particular para cada uno de los tres algoritmos (intersecci´on, diferencia y uni´on). Previo a la realizaci´on y desarrollo de este proyecto, la librer´ıa contaba con las estructuras HitSig y HitSigShape para modelar las particiones rectangulares del espacio de datos. La estructura HitSigShape cuenta con un array con tantos elementos como dimensiones del espacio tenga el cuerpo modelado. Para el caso del rect´angulo, HitSigShape est´a compuesto por dos HitSig, que indican el ´ındice de inicio y de final para cada dimensi´on del espacio. La estructura HitSig debe construirse de forma que su campo begin sea menor que end. typedef struct { int begin ; /∗∗<The begin index of the dimension ∗/ int end ; /∗∗<The end index of the dimension ∗/ int s t r i d e ; /∗∗<The s t r i d e f or regular sparse domains ∗/ }HitSig ; typedef struct { /∗ ∗ @privatesection ∗/ int numDims ; /∗∗<Number of dimensions .∗ ∗/ HitSig s i g [HIT MAXDIMS ] ; /∗∗<H itSi g o b j e c t s to defin e each dimension .∗/ }HitSigShape ; 55 3.5. DISE ˜ NO Estas dos estructuras deber´an ser extendidas para poder modelar particiones triangulares. Como resultado, se crean las estructuras HitSigExt y HitSigExtShape. La primera cuenta con los mismos campos, pero con la diferencia de que el campo begin puede ser mayor que end. Como se explicar´a m´as adelante, esta caracter´ıstica permitir´a modelar los distintos tipos de tri´angulo que maneja la librer´ıa. typedef struct { int begin ; /∗∗<The begin index of the dimension ∗/ int end ; /∗∗<The end index of the dimension ∗/ int s t r i d e ; /∗∗<The s t r i d e f or regular sparse domains ∗/ }HitSigExt ; La estructura HitSigShape ha sido extendida con el campo entero type, que puede tomar el valor 0 o 1 dependiendo de si la Shape reprensenta un rect´angulo o un tri´angulo, respectivamente. typedef struct { /∗ ∗ @privatesection ∗ ∗/ int numDims ; /∗∗<Number of dimensions ∗/ int type ; /∗∗<0 i f r e ct a ngul a r shape , 1 i f t r i a n g u l a r shape ∗/ HitSigExt s i g [ HIT\MAXDIMS ] ; /∗∗<The s t r i d e for extended sparse domains ∗/ }HitSigExtShape ; Los tri´angulos modelados por la extensi´on propuesta en este proyecto presentan una serie de caracter´ısticas: Son tri´angulos rect´angulos de base y altura paralelos a los ejes de coordenadas. Esos tri´angulos pueden ser de cuatro tipos: T1, T2, T3 y T4. Este tipo viene determinado por la orientaci´on de la diagonal del rect´angulo con respecto a los ejes de coordenadas. El modelado de cada uno de los cuatro tipos de tri´angulos se realiza a trav´es de los campos begin y end de las estructuras HitSigExt. El uso de estos valores para modelar cada tri´angulo viene expresado en la figura 3.12. 3.5.1. Intersecci´on El algoritmo de intersecci´on se ha dise˜nado entorno a dos fases principales: la construcci´on del pol´ıgono de intersecci´on y la partici´on del pol´ıgono del intersecci´on. El objetivo final de estas dos fases es la determinaci´on del pol´ıgono de la intersecci´on de los Shapes de entrada a trav´es de sus v´ertices y representar este pol´ıgono a trav´es de un array de Shapes que conforman la partici´on del mismo. Como consecuencia, el esqueleto principal del algoritmo de intersecci´on para R2de dos figuras, (SaySb), pudiendo ser dos tri´angulos, dos rect´angulos o un tri´angulo y un rect´angulo, es de la forma: 56 CAP´ ITULO 3. AN ´ ALISIS Y DISE ˜ NO Figura 3.12: Representaci´on de triangulos a trav´es de la estructura HitSigExtShape (Figura extr´ıda de [21]). 1. Construcci´on del pol´ıgono de intersecci´on. Objetivo: Obtener un array con los v´ertices que conforman el pol´ıgono de intersecci´on. Estos v´ertices se obtienen a trav´es de las intersecciones entre los lados de los pol´ıgonos de entrada. a)Si ambas figuras son rect´angulos: 1. La intersecci´on ya est´a definida en la librer´ıa HitMap. Funci´on: HitShape hit shapeIntersect(HitShape sh1, HitShape sh2) en hit shape.c b)Si Sa es un tri´angulo y Sb es un rect´angulo: 1. Intersecci´on de la altura de Sbcon la base y diagonal de Sa 2. Intersecci´on de la base de Sbcon la altura y diagonal de Sa c)Si ambas figuras son tri´angulos: 1. Intersecci´on de la altura de Sacon la base y diagonal de Sb 2. Intersecci´on de la base de Sacon la altura y diagonal de Sb 3. Intersecci´on de la diagonal de Sacon la altura, base y diagonal de Sb A mayores ser´a necesario a˜nadir al pol´ıgono de intersecci´on: V´ertices de Saque pertenecen a Sb V´ertices de Sbque pertenecen a Sa 2. Partici´on del pol´ıgono de intersecci´on. Objetivo: Dado un array con los v´ertices del pol´ıgono de intersecci´on, obtener un array con los pol´ıgonos generados por la partici´on (HitSigExtShapes). 57 4.1. MECANISMOS DE ABSTRACCI ´ ON typedef struct { double x ; double y ; int notnull ; //0 es n ull , 1 no es n u l l }Point ; Listing 4.1: Estructura Point. Segment: Estructura de datos creada para modelar un segmento para un espacio de R2. Este segmento viene determinado por las coordenadas reales de sus extremos, x1-y1 y x2-y2 , y un campo que indica si el segmento es nulo o no (notnull). Surge por la necesidad de representar los segmentos que determinan los lados de los Shapes de entrada. A partir de estos segmentos se realizan las intersecciones entre los lados de los Shapes, mediante las ecuaciones de la rectas que contienen dichos segmentos y los rangos de R2en los que est´an comprendidos. R2. typedef struct { int type ; // 0 base , 1 altura , 2 diagonal double x1 ; double y1 ; double x2 ; double y2 ; int notnull ; //0 es n ull , 1 no es n u l l }Segment ; Listing 4.2: Estructura Segment. PointLookUp: Estructura da datos que extiende la estructura Point para almacenar la informaci´on generada durante la b´usquedas de los tri´angulos de la partici´on del pol´ıgono de intersecci´on. Esta estructura viene determinada por un punto del tipo Point, la direcci´on en la que ha sido alcanzado durante las b´usquedas, un entero que indica si el punto resulta de una colisi´on al avanzar durante las b´usquedas y en que direcci´on se ha producido dicha colisi´on y si es el resultado o no de la intersecci´on con una diagonal. Surge de la necesidad de detectar cierta casu´ıstica para modelar el flujo de las b´usquedas horizontal y verticales. En funci´on de si el punto es generado como resultado de una colisi´on o no y en caso de serlo con una diagonal o no, supone diferencias a la hora de segmentos que deben almacenarse para la formaci´on de tri´angulos de partici´on del pol´ıgono de intersecci´on. typedef struct { Point point ; int d i r e c t i o n ; //1 (up ) , 2 (down) , 3 ( l e f t ) or 4 ( r i g h t ) int collision ; //0 not r e s u l t of a c o l l i s i o n of segments , 1 , 2 , 3 , 4 r e s u l t of c o l l i s i o n and i n d i c a t e d i r e c t i o n o f th e collision int diagonal ; //0 no r e s u l t o f i n t e r s e c t i o n with dia go nal . Otherwise , r e s u l t of i n t e r s e c t i o n with d ia gonal }PointLookUp ; 64 CAP´ ITULO 4. IMPLEMENTACI ´ ON Listing 4.3: Estructura PointLookUp. TriangleReal: Estructura de datos que modela los tri´angulos que conforman la partici´on del pol´ıgono de intersecci´on con v´ertices definidos para R2resultante de las b´usquedas horizontal y vertical. Esta estructura tiene cuatro campos que representan los tres v´ertices que determinan el tri´angulo, del tipo PointLookUp, teniendo que el v´ertice situado en el ´angulo recto del tri´angulo se almacena dos veces. A mayores, se utiliza un campo para determinar si el triangulo es nulo o no. Surge de la necesidad de almacenar los tri´angulos determinados durante las b´usquedas de tri´angulos de partici´on, los cu´ales al manejar coordenadas reales no pueden ser modelados mediante shapes. Tras la fase de reajuste estos triangelreals son reajustados para almacenarse mediante shapes. typedef struct { PointLookUp A; PointLookUp B; PointLookUp Bortho ; PointLookUp C; int notnull ; }TriangleReal ; Listing 4.4: Estructura TriangleReal. 4.2. Macros Existen tres grupos de macros en la implementaci´on de la propuesta del m´odulo de Hitmap: •Macros de gesti´on de alocaci´on de memoria A lo largo de la extensi´on de la librer´ıa se realizan m´ultiples reservas de memoria con el objetivo de alocar all´ı los distintos arrays de estructuras necesarias para operar con las entradas, almacenar los resultados intermedios de los algoritmos y dar la salida final en un ´unico array de memoria. Con el objetivo de mejorar el rendimiento de los algoritmos y evitar la gesti´on de memoria de forma din´amica se han definido una serie de macros con valores enteros que representan el n´umero de estructuras de memoria que se van a almacenar en los distintos arrays para los que se reserva memoria en los distintos algoritmos. Estas reservas de memoria, con el fin de evitar errores de punteros debido a valores no definidos se han realizado mediante la funci´on calloc [33]. Para el ejemplo del array de salida del algoritmo de intersecci´on la reserva de memoria es de la forma: 65 4.2. MACROS HitSigExtShape ∗intersectionSaSb ; in t e rs ectio n Sa Sb = c a l l o c (ARRAY TAM, sizeof( Point ) ) ; Mediante el uso de estas macros, en caso de que a trav´es de la experimentaci´on se observe que el tama˜no de memoria reservada a lo largo del algoritmo es insuficiente, basta con sustituir el valor utilizado por las macros para la llamada a la funci´on calloc. #d e f i n e ARRAY TAM 16 #d e f i n e ARRAY TAM2 32 #d e f i n e ARRAY TAM3 64 #d e f i n e ARRAY TAM4 128 Listing 4.5: Macros de gesti´on de memoria alocada. •Macros de gesti´on de error de punto flotante En el lenguaje de programaci´on C, al realizar algunos c´alculos con n´umeros decimales, por ejemplo con variables de tipo double, existe una cierta imprecisi´on debido a la representaci´on binaria del n´umero decimal, que puede que no sea exacta, y a la falta de coincidencia de tipos entre los n´umeros usados [34]. Este tipo de errores se denominan errores de precisi´on en los c´alculos de punto flotante [35]. Para el caso de los algoritmos desarrollados durante este proyecto, los errores de punto flotante han surgido en los c´alculos de intersecciones entre los segmentos que determinan los lados de los shapes de entrada, generando bugs e incorrecciones en los c´alculos realizados por los algoritmos. Estos errores se manifestaron al realizar la comprobaci´on de si dos puntos ten´ıan las mismas coordenadas: dos puntos te´oricamente iguales en coordenadas resultaban ser diferentes por diferencias decimales de una precisi´on de 10−15. Para solventar esto, se ha creado la macro ERROR, que determina que la precisi´on con la que va a trabar la librer´ıa es de 11 cifras decimales. En caso de que a trav´es de la experimentaci´on se demostrase de que esta precisi´on sigue generando incorreciones debido a problemas de c´alculo de ounto flotante, dicho valor puede ser modificado. #d e f i n e ERROR 0.00000000001 Listing 4.6: Macros de gesti´on de error de punto flotante. •Macros que sustituyen funciones El ´ultimo grupo de macros implementadas son aquellas que sustituyen funciones. En concreto son dos, que realizan los c´alculos del m´aximo y el m´ınimo de dos n´umeros. Estas macros surgen de la necesidad de realizar comparaciones entre n´umeros de forma frecuente, pudiendo ser estos de tipos distintos, ya sean dobles o enteros. Con estas macros el m´aximo y el m´ınimo se puede calcular sin realizar gestiones entre tipos. 66 CAP´ ITULO 4. IMPLEMENTACI ´ ON #d e f i n e MAX( a , b ) ( ( a ) >= ( b) ? ( a ) : (b) ) #d e f i n e MIN( a , b ) ( ( a ) <= ( b) ? ( a ) : (b) ) Listing 4.7: Macros que calculan el m´aximo y el m´ınimo. 4.3. Funciones principales intersection: funci´on que lleva a cabo el algoritmo intersecci´on. Calcula el pol´ıgono de intersecci´on entre dos shapes y devuelve la partici´on triangular de dicho pol´ıgono. •Entradas: Dos HitSigExtShape, Sa y Sb, que representan los pol´ıgonos de entradas (rect´angulos o tri´angulos) para los cu´ales se realiza la intersecci´on. •Salidas: Un array de HitSigExtShape con los pol´ıgonos que conforman la partici´on del pol´ıgono de intersecci´on. •Funcionamiento: Presenta dos fases principales: la primera es la construcci´on del pol´ıgono de intersecci´on, donde se consiguen la lista de los puntos que representan los v´ertices que determinan el pol´ıgono de intersecci´on, y la segunda fase, que es la partici´on del pol´ıgono de intersecci´on, donde a partir de la lista de v´ertices se obtienen los tri´angulos que constituyen la partici´on y se devuelve como un array de HitSigExtShapes. 1HitSigExtShape ∗i n t e r s e c t i o n ( HitSigExtShape Sa , HitSigExtShape Sb) { 2 3// I ndica que e l a lgorit mo es de i n t e r s e c c i o n 4i n t difference = 0; 5 6// Array de s a l i d a d el algor itmo 7HitSigExtShape ∗intersection ; 8 9//Se obtienen l o s v e r t i c e s del poli gono de i n t e r s e c c i o n 10 Point ∗ver te x = i n t e r s e c t i o n p o l y g o n B u i l d i n g (Sa , Sb , d i f f e r e n c e ) ; 11 12 // Se obti en e l a p a r t i c i o n en t r i a n g u l o s d el p ol ig on o 13 //de interseccion 14 i n t e r s e c t i o n = i p p a r t i t i o n ( vertex , Sa , Sb , d i f f e r e n c e ) ; 15 16 //Se devuelve e l array de s a l i d a con l o s Shapes 17 // que conforman l a p a r t i c i o n t r i a n g u l a r d el pol ig on o 18 //de interseccion 19 return intersection ; 20 } 21 Listing 4.8: Funci´on principal del algoritmo de intersecci´on. 67 4.3. FUNCIONES PRINCIPALES difference: funci´on que lleva a cabo el algoritmo la diferencia. Calcula los pol´ıgonos resultantes de la diferencia entre dos shapes y devuelve la partici´on triangular de dichos pol´ıgonos. •Entradas: Dos HitSigExtShape, Sa y Sb, que representan los pol´ıgonos de entradas (rect´angulos o tri´angulos) para los cu´ales se realiza la diferencia. •Salidas: Un array de HitSigExtShape con los pol´ıgonos que conforman la partici´on de los pol´ıgonos resultantes de la diferencia entre los dos shapes. •Funcionamiento: Presenta tres fases principales: la primera es la construcci´on de los pol´ıgono resultantes de la diferencia, donde se consiguen la lista de los puntos que representan los v´ertices de dichos pol´ıgonos, la segunda fase, que es la partici´on de los pol´ıgonos resultantes de la diferencia, donde a partir de la lista de v´ertices se obtienen los tri´angulos que constituyen la partici´on y se devuelve como un array de HitSigExtShapes, y la tercera y ´ultima fase, donde los tri´angulos de la partici´on son separados del esqueleto de Sb para asegurar que la salida es disjunta entre s´ı y con Sb. 1 2HitSigExtShape ∗d i f f e r e n c e ( HitSigExtShape Sa , HitSigExtShape Sb ){ 3 4// I ndic a que es e l algoritmo de l a d i f e r e n c i a 5i n t differenceFlag = 1; 6 7// Array de s a l i d a d el algor itmo 8HitSigExtShape ∗difference ; 9 10 // Vert ices que terminan l o s p o l g o n o s r e s u l t a n t e s de l a d i f e r e n c i a 11 // entr e Sa y Sb 12 Point ∗ver te x = i n t e r s e c t i o n p o l y g o n B u i l d i n g (Sa , Sb , d i f f e r e n c e F l a g ) ; 13 14 // Se obti en e l a p a r t i c i o n en t r i a n g u l o s de l o s p o li g on o s r e s u l t a n t e s 15 //de l a d i f e r e n c i a de Sa menos Sb 16 d i f f e r e n c e = i p p a r t i t i o n ( vertex , Sa , Sb , d i ff er e n c eF la g ) ; 17 18 //Se separan l o s Shapes r e s u l t a n t e s d el e sq ue lo d el Shape Sb 19 // para as egu ra que l a s a l i d a y Sb son d i s j u n t o s 20 d i f f e r e n c e = s e p a r a t e s k e l e t o n s f r o m S b ( d i f f e r e n c e , Sb ) ; 21 22 //Se devuelve e l array de s a l i d a con l o s Shapes que conforman 23 // la p a r t i c i o n t r i a n g u l a r de l a d i f e r e n c i a d el p ol ig on o de 24 //interseccion 25 return difference ; 26 } 27 28 29 30 Listing 4.9: Funci´on principal del algoritmo de la diferencia. 68 CAP´ ITULO 4. IMPLEMENTACI ´ ON unionHitSig: funci´on que lleva a cabo el algoritmo de uni´on. Calcula los pol´ıgonos resultantes entre dos shapes y devuelve la partici´on triangular de dichos pol´ıgonos. •Entradas: Dos HitSigExtShape, Sa y Sb, que representan los pol´ıgonos de entradas (rect´angulos o tri´angulos) para los cu´ales se realiza la uni´on. •Salidas: Un array de HitSigExtShape con los pol´ıgonos que conforman la partici´on de los pol´ıgonos resultantes de la uni´on. •Funcionamiento: Presenta cuatro fases: 1. En la primera se calcula la diferencia de Sa menos Sb con la funci´on difference y se almacena en un array su correspondiente salida. 2. En la segunda se calcula la diferencia de Sb menos Sa con la funci´on difference y se almacena en un array su correspondiente salida. 3. En la tercera se calcula la intersecci´on entre Sa y Sb con la funci´on intersection y se almacena en un array su correspondiente salida. 4. En la cuarta y ´ultima fase se alamcenan las tres salidas anteriores en un ´unico array que se corresponde con la salidad del algoritmo de uni´on. 1HitSigExtShape ∗unionHitSig ( HitSigExtShape Sa , HitSigExtShape Sb ) { 2 3// Array donde se almacen l o s shapes que conforman 4// la d i f e r e n c i a de Sa menos Sb 5HitSigExtShape ∗differenceSaSb ; 6 7// Array donde se almacen l o s shapes que conforman 8// la d i f e r e n c i a de Sb menos Sa 9HitSigExtShape ∗differenceSbSa ; 10 11 // Array donde se almacen l o s shapes que conforman 12 // la i n t e r s e c c i o n de Sa y Sb 13 HitSigExtShape ∗intersectionSaSb ; 14 15 // Array de s a l i d a d el algor itmo 16 HitSigExtShape ∗unionSaSb ; 17 18 //Se c al cu la l a d i f e r e n c i a de Sa menos Sb 19 differenceS a S b = d i f f e r e n c e ( Sa , Sb) ; 20 21 //Se c al cu la l a d i f e r e n c i a de Sb menos Sa 22 differenceS b S a = d i f f e r e n c e (Sb , Sa ) ; 23 24 //Se c al c ul a l a i n t e r s e c c i o n de Sa y SB 25 in t e rs ectio n Sa Sb = i n t e r s e c t i o n (Sa , Sb ) ; 26 27 // Reserva de memoria del a array de s a l i d a 28 unionSaSb = c a l l o c (ARRAY TAM4, sizeof(HitSigExtShape)) ; 29 30 i n t z = 0 ; 69 4.3. FUNCIONES PRINCIPALES 31 32 //Se copian l o s Shapes de l a d i f e r e n c i a 33 //de Sa menos Sb en e l array de s a l i d a 34 f o r (i n t i =0; i<ARRAY TAM2; i++){ 35 i f ( ! d i f f e r e n c e S a S b [ i ] . type==0 | | ! d i f f e r e n c e S a Sb [ i ] . s i g [ 0 ] . begin == 0 36 | | ! differenceSaSb [ i ] . s i g [ 0 ] . end == 0 | | ! d i f f e r e n c e S a S b [ i ] . s i g [ 1 ] . begin==0 37 | | ! differenceSaSb [ i ] . s i g [ 1 ] . end ==0){ 38 unionSaSb [ z]= d i f f e r e n c e S a S b [ i ] ; 39 z++; 40 } 41 } 42 43 //Se copian l o s Shapes de l a d i f e r e n c i a 44 //de Sb menos Sa en e l array de s a l i d a 45 f o r (i n t i =0; i<ARRAY TAM2; i++){ 46 i f ( ! d i f f e r e n c e S b S a [ i ] . type==0 | | ! d i f f e r e n c e S b Sa [ i ] . s i g [ 0 ] . begin == 0 47 | | ! differenceSbSa [ i ] . s i g [ 0 ] . end == 0 | | ! d i f f e r e n c e S b S a [ i ] . s i g [ 1 ] . begin==0 48 | | ! differenceSbSa [ i ] . s i g [ 1 ] . end ==0){ 49 unionSaSb [ z]= d i f f e r e n c e S b S a [ i ] ; 50 z++; 51 } 52 } 53 54 //Se copian l o s Shapes de l a i n t e r s e c c i o n 55 //de Sa y Sb en e l array de s a l i d a 56 f o r (i n t i =0; i<ARRAY TAM2; i++){ 57 i f ( ! i n t ersec t i o n S a S b [ i ] . type==0 | | ! i nt er s ectionSa Sb [ i ] . s i g [ 0 ] . begin == 0 58 | | ! inters ec t ionSaSb [ i ] . s i g [ 0 ] . end == 0 | | ! in t ersectio nS a Sb [ i ] . s i g [ 1 ] . begin==0 59 | | ! inters ec t ionSaSb [ i ] . s i g [ 1 ] . end ==0){ 60 unionSaSb [ z]= i n t e rsect i o n S a S b [ i ] ; 61 z++; 62 } 63 } 64 65 //Se devuelve e l array de s a l i d a con 66 // l o s shapes que conforma l a p a r i t u c i o n 67 // de l a union de Sa y Sb 68 return unionSaSb ; 69 70 } 71 72 73 Listing 4.10: Funci´on principal del algoritmo de uni´on. intersection polygon building: funci´on cuyo comportamiento var´ıa en funci´on de si es llamada por el algoritmo de la diferencia o por el algoritmo de intersecci´on. Calcula los v´ertices que determinan el pol´ıgono de intersecci´on o los pol´ıgonos resultantes de la diferencia de los shapes de entrada. •Entradas: Dos HitSigExtShape, Sa y Sb, que representan los pol´ıgonos de entradas (rect´angu70 CAP´ ITULO 4. IMPLEMENTACI ´ ON los o tri´angulos) para los cu´ales se realizan la intersecci´on o diferencia y un entero, que act´ua como flag. Si toma el valor 0, el algoritmo que invoca a intersection polygon building es la intersecci´on y si toma el valor 1 es la diferencia. •Salidas: Un array de puntos que determinan el pol´ıgono de intersecci´on o los pol´ıgonos de la diferencia, en funci´on del algoritmo que invoca a intersection polygon building. Estos puntos son utilizados posteriormente en la funci´on ip partition durante las b´usquedas horizontal y vertical. •Funcionamiento: El funcionamiento depende de que algoritmo invoca esta funci´on: ◦Para el algoritmo de intersecci´on, se calculan las intersecciones entre los lados de los shapes de entrada, Sa y Sb, y se almacenan dichos puntos. Tras esto, se almacenan en el mismo array aquellos v´ertices de Sa que pertenecen a Sb y los v´ertices de Sb que pertenecen a Sa. ◦Para el algoritmo de la diferencia, se calculan las intersecciones entre los lados de los shapes de entrada, Sa y Sb, y se almacenan dichos puntos. Tras esto, se almacenan en el mismo array todos los v´ertices de Sa y aquellos v´ertices de Sb que pertenezcan a Sa. 1 2Point ∗i n t e r s e c t i o n p o l y g o n B u i l d i n g ( HitSigExtShape Sa , HitSigExtShape Sb , i n t difference){ 3 4// Array de s a l i d a que almacenara l o s v e r t i c e s d el 5// poligono de i n t e r s e c c i o n o l o s v e r t i c e s que determinan 6// l o s p ol ig on os de l a d i f e r e n c i a 7Point ∗puntosPoligonoInterseccion ; 8 9// Arrays que almacenan l o s v e r t i c e s de Sa y Sb 10 Point ∗vertexSa ; 11 Point ∗vertexSb ; 12 13 //Se r es erva memoria para e l array de v e r t i c e s 14 puntosPoligonoInterseccion = calloc(ARRAYTAM, sizeof( Point ) ) ; 15 16 //Punto donde se almacenara l a s i n t e r s e c c i o n e s 17 // c a l c u l a d a s en cada i t e r a c i o n 18 Point auxpoint ; 19 i n t z = 0 ; 20 21 // Arrays que almacenan l o s segmentos de Sa y Sb 22 Segment ∗segmentsSa ; 23 Segment ∗segmentsSb ; 24 25 //Shape a u x i l i a r para interc ambiar Sa con Sb 26 HitSigExtShape Sc ; 27 28 //En caso de que Sa sea un rec t angul o y Sb 29 //un t r ian g ul o , e s t o s se i nter cambian 30 i f ( Sa . type == 0 && Sb . type == 1) { 31 Sc = Sa ; 71 4.3. FUNCIONES PRINCIPALES 32 Sa = Sb ; 33 Sb = Sc ; 34 } 35 36 //Obtenemos l o s segmentos que determinan l o s 37 // l ad os de l o s shapes de entrada 38 segmentsSa = get s egments from Sh ape ( Sa ) ; 39 segmentsSb = get segments from Shape (Sb ) ; 40 41 //Obtenemos l o s v e r t i c e s de l o s shapes Sa y Sb 42 vertexSa = get p oi nts f ro m S ha pe ( Sa ) ; 43 vertexSb = get poin t s from Shape ( Sb ) ; 44 45 // I n t e r s e c c i o n e nt re 2 r e ctangulos 46 i f ( Sa . type == 0 && Sb . type == 0) { 47 48 // Inte rse cam os todos l o s l ad os no p a r a l e l o s entr e s i 49 f o r (i n t i =0; i <4; i++){ 50 f o r (i n t j =0; j <4; j++){ 51 52 i f ( segmentsSa [ i ] . type == 0 && segmentsSb [ j ] . type == 1) {// i n t e r s e c t i o n base Sa h eig ht Sb 53 54 auxpoint = o r t h o g o n a l i n t e r s e c t i o n ( segmentsSa [ i ] , segmentsSb [ j ] ) ; 55 56 // Si hay i n t e r s e c c i o n se almacena 57 i f ( auxpoint . notnull == 1) { 58 59 z++; 60 puntosPoligonoInterseccion [z−1] = auxpoint ; 61 62 } 63 64 }e l s e i f ( segmentsSb [ j ] . type == 0 && segmentsSa [ i ] . type == 1) {// i n t e r s e c t i o n base Sb h eig ht Sa 65 66 auxpoint = o r t h o g o n a l i n t e r s e c t i o n ( segmentsSb [ j ] , segmentsSa [ i ] ) ; 67 68 // Si hay i n t e r s e c c i o n se almacena 69 i f ( auxpoint . notnull == 1) { 70 71 z++; 72 puntosPoligonoInterseccion [z−1] = auxpoint ; 73 74 } 75 76 } 77 78 } 79 80 } 81 82 // i n t e r s e c c i o n entre un t ri ang ulo y un r ect an gu lo 83 }e l s e i f (Sa . type == 1 && Sb . type == 0) { 84 85 // Inte rse cam os todos l o s l ad os no p a r a l e l o s entr e s i 86 f o r (i n t i =0; i <3; i++){ 72 CAP´ ITULO 4. IMPLEMENTACI ´ ON 87 f o r (i n t j =0; j <4; j++){ 88 89 i f ( segmentsSa [ i ] . type == 0 && segmentsSb [ j ] . type == 1) {// i n t e r s e c t i o n base Sa h eig ht Sb 90 91 auxpoint = o r t h o g o n a l i n t e r s e c t i o n ( segmentsSa [ i ] , segmentsSb [ j ] ) ; 92 93 // Si hay i n t e r s e c c i o n se almacena 94 i f ( auxpoint . notnull == 1) {//hay i n t e s e c c i o n 95 96 z++; 97 puntosPoligonoInterseccion [z−1] = auxpoint ; 98 99 } 100 101 }e l s e i f ( segmentsSb [ j ] . type == 0 && segmentsSa [ i ] . type == 1) {// i n t e r s e c t i o n base Sb h eig ht Sa 102 103 auxpoint = o r t h o g o n a l i n t e r s e c t i o n ( segmentsSb [ j ] , segmentsSa [ i ] ) ; 104 105 // Si hay i n t e r s e c c i o n se almacena 106 i f ( auxpoint . notnull == 1) { 107 108 z++; 109 puntosPoligonoInterseccion [z−1] = auxpoint ; 110 111 } 112 113 }e l s e i f ( segmentsSa [ i ] . type == 2) {// i n t e r s e c t i o n diagonal Sa , height or base Sb 114 115 auxpoint = d i a g o n a l i n t e r s e c t i o n ( segmentsSa [ i ] , segmentsSb [ j ] ) ; 116 117 // Si hay i n t e r s e c c i o n se almacena 118 i f ( auxpoint . notnull == 1) { 119 120 z++; 121 puntosPoligonoInterseccion [z−1] = auxpoint ; 122 123 } 124 125 } 126 127 } 128 129 } 130 131 // i n t e r s e c c i o n entre dos t r i an g ul os 132 }e l s e { 133 134 // Inte rse cam os todos l o s l ad os no p a r a l e l o s entr e s i 135 f o r (i n t i =0; i <3; i++){ 136 f o r (i n t j =0; j <3; j++){ 137 138 i f ( segmentsSa [ i ] . type == 0 && segmentsSb [ j ] . type == 1) {// i n t e r s e c t i o n base Sa h eig ht Sb 139 73 4.4. FUNCIONES SECUNDARIAS almost equal: Comprueba si dos valores de tipo double tienen una diferencia menor a la indicada por la macro ERROR. Devuelve el valor 1 si la diferencia es menor que ERROR y 0 en el caso contrario. int almost equal(double a , double b) ; order Look Up points: Ordena los puntos extendidos introducidos en el array de entrada de forma que los puntos con menor coordenada Y y menor coordenada X vayan primero. PointLookUp ∗order Look Up points ( PointLookUp p oi nt s [ ] ) ; collision: Dado un punto extendido generado al colisionar con un segmento previamente visitado en el avance de alguna de las b´usquedas, obtiene el punto extendido de origen del avance que junta al punto de entrada determina el segmento a almacenar. PointLookUp c o l l i s i o n ( PointLookUp c o l l i d edPoint , int direction , PointLookUp v i s i t e d P o i n t s [ ] ) ; point belongs to skeleton: Comprueba si el punto introducido por par´ametro pertenece al per´ımetro del shape introducido por par´ametro. Devuelve el valor 1 si el punto pertenece y 0 en el caso contrario. int p o i n t b e l o n g s t o s k e l e t o n ( Point point , HitSigExtShape S ) ; segment is on border: Comprueba si el segmento introducido por par´ametro pertenece al per´ımetro del shape introducido por par´ametro. Devuelve el valor 1 si el segmento pertenece y 0 en el caso contrario. int segme n t i s on borde r ( Point point1 , Point point2 , HitSigExtShape Sa , HitSigExtShape Sb) ; point already visited: Comprueba si el punto introducido por par´ametro ya ha sido visitado durante las b´usquedas horizontal y v´ertical. Devuelve el valor 1 si el punto ya ha sido visitado y 0 en el caso contrario. int point already visited(Point point , int d i r e c t i o n , PointLookUp visitedPoints []) ; diagonal loop: Comprueba si existe un punto con coordenadas enteras (un ´ındice de memoria) entre los dos puntos introducidos por par´ametro. Devuelve el valor 1 si existe dicho punto y 0 en el caso contrario. int dia g o n a l l o op ( Point point , Point newPoint , int d i r e c t i o n ) ; try to advance: Dados un punto de partida, una direcci´on, los shapes de entrada de los algoritmos de intersecci´on, diferencia o uni´on, los lados de los mismos y un array con los segementos ya visitados calcula el siguiente punto alcanzado durante el avance en la fase de b´usquedas. 80 CAP´ ITULO 4. IMPLEMENTACI ´ ON PointLookUp try to a dvanc e ( Point point , int d i r e c t i o n , HitSigExtShape Sa , HitSigExtShape Sb , Segment segmentsSa [ ] , Segment segmentsSb [ ] , PointLookUp v i s i t e d P o i n t s [ ] , Segment v is it ed Segm en ts [ ] , int difference); horizontal lookup: Dados un punto de partida, una direcci´on, los shapes de entrada de los algoritmos de intersecci´on, diferencia o uni´on, los lados de los mismos, un array con los segmentos ya visitados y otro con los puntos ya visitados obtiene parte de los v´ertices que determinan los tri´angulos de la partici´on. PointLookUp ∗h o r i z o n t a l l o o k u p ( Point v er t ex [ ] , HitSigExtShape Sa , HitSigExtShape Sb , PointLookUp v i s i t e d P o i n t s [ ] , Segment visitedSegments [] , int difference); vertical lookup: Dados un punto de partida, una direcci´on, los shapes de entrada de los algoritmos de intersecci´on, diferencia o uni´on, los lados de los mismos, un array con los segmentos ya visitados y otro con los puntos ya visitados obtiene parte de los v´ertices que determinan los tri´angulos de la partici´on. PointLookUp ∗v e r t i c a l l o o k u p ( Point v ertex [ ] , HitSigExtShape Sa , HitSigExtShape Sb , PointLookUp v i s i t e d P o i n t s [ ] , Segment visitedSegments [] , int difference); point to Shape: Construye un shape que representa el punto introducido por par´ametro. HitSigExtShape poin t t o Shap e ( Point point ) ; segment to Shape: Construye un shape que representa el segmento introducido por par´ametro. HitSigExtShape segment to Shape ( Point point1 , Point point2 ) ; isolated vertices and segments: Dado el array de puntos alcanzados durante las b´usquedas horizontal y vertical, detecta aquellos puntos y segmentos aislados que no forman parte de un tri´angulo de la partici´on y se almacenan en el array de salida representados mediante shapes. HitSigExtShape ∗i s o l a t e d v e r t i c e s a n d s e g m e n t s ( HitSigExtShape i n t e r s e c t i o n [ ] , Point ver tex [ ] , PointLookUp v i s i t e d P o i n t s [ ] , HitSigExtShape Sa, HitSigExtShape Sb) ; find point: Dado el array de puntos visitados durante las b´usquedas y un punto introducido por par´ametro determina si dicho punto se encuentra entre los puntos visitados. PointLookUp f i n d p o i n t ( PointLookUp point , PointLookUp v i s i t e d P o i n t s [ ] , int s i z e ) ; 81 4.4. FUNCIONES SECUNDARIAS orthogonal point: Dado el array de puntos visitados durante las b´usquedas y un punto extendido, devuelve un punto de dicho array con las mismas coordenadas y direcci´on ortogonal que determina junto al primero el a´ngulo rect´angulo de uno de los tri´angulos de la partici´on. PointLookUp o rthog o na l p oi n t ( PointLookUp point , PointLookUp v i s i t e d P o i n t s [ ] , int s i z e ) ; two segments to triangle real: Dados los cuatro puntos que determinan los dos segmentos que representan la base y altura de un tri´angulo, se devuelve el tri´angulo de coordenadas reales determinado por estos. Triangl eReal t w o s e g m e n t s t o t r i a n g l e r e a l ( PointLookUp point1 , PointLookUp point2 , PointLookUp point3 , PointLookUp point4 ) ; ceil or add: Redondea una coordenada de un shape al entero superior. int c e i l o r a d d (double x ) ; floor or subs: Redondea una coordenada de un shape al entero inferior. int floor or subs(double x ) ; outsiders: Dados un tri´angulo de coordenadas reales y el shape resultante del reajuste del primero a coordenadas enteras, obtiene un array con los puntos que pertenec´ıan al tri´angulo inicial pero que se pierden al reajustar. HitSigExtShape ∗o u t s i d e r s ( T riangl eReal t r i a n g l e O r i g i n a l , HitSigExtShape triangleModified); adjust triangle: Dados los 3 v´ertices (uno duplicado pero con direcciones distintas) que conforman un tri´angulo con coordenadas reales, reajusta dicho tri´angulo a coordenadas enteras y es devuelto mediante la estructura shape. HitSigExtShape a d j u s t t r i a n g l e ( PointLookUp point1 , PointLookUp point2 , PointLookUp point3 , PointLookUp point4 ) ; point belongs to any Segment: Dado un array de segmentos y un punto, determina si dicho punto pertenece a alguno de los segmentos. En caso afirmativo se devuelve el valor 1 y en caso contrario el valor 0. int point b elongs t o any S egm ent ( Point point , Segment segments [ ] ) ; two points to segment: Dados dos puntos devuelve el segmento que estos determinan. Segment two p oin ts to seg men t ( Point point1 , Point point2 ) ; find and null: Dado el array de puntos visitados durante las b´usquedas, esta funci´on localiza los trs puntos introducidos por par´ametro en el array y los fija como nulos. 82 CAP´ ITULO 4. IMPLEMENTACI ´ ON PointLookUp ∗f i n d a n d n u l l ( PointLookUp point1 , PointLookUp point2 , PointLookUp point3 , PointLookUp ∗visitedPoints , int s i z e ) ; triangle overlaps triangle: Dados dos tri´angulos introducidos por par´ametro comprueba si presentan puntos comunes. En caso afirmativo se devuelve el valor 1 y en caso contrario el valor 0. int t r i a n g l e o v e r l a p s t r i a n g l e ( TriangleReal tr i a ngle 1 , TriangleReal t r i a n g l e 2 ) ; triangle overlaps any triangle: Dados un tri´angulo y un array de tri´angulos introducidos por par´ametros comprueba si el primero se solapa con alguno de los tri´angulos presentes en el array. En caso afirmativo se devuelve el valor 1 y en caso contrario el valor 0. int t r i a n g l e o v e r l a p s a n y t r i a n g l e ( TriangleReal t ria ngl e , TriangleReal t r i a n g l e s [ ] ) ; determine triangles: Dado el array de puntos obtenidos durante las b´usquedas, construye los tri´angulos de la partici´on del pol´ıgono de la intersecci´on o de los pol´ıgonos resultantes de la diferencia y los almacena en el array de salida de los algoritmos. HitSigExtShape ∗d e t e r m i n e t r i a n g l e s ( HitSigExtShape i n t e r s e c t i o n [ ] , PointLookUp v i s i t e d P o i n t s [ ] ) ; join rectangles: Dado el array con los shapes de salida de los algoritmos de intersecci´on, diferencia o uni´on, realiza la fusi´on de aquellos shapes que son rect´angulos contiguos y que van a generar como resultado un nuevo rect´angulo m´as grande. int j o i n r e c t a n g l e s ( HitSigExtShape ∗intersection , int ∗valid , int i , int j , HitSigExtShape Sb, int c h e c k c r o s s ) ; outsider is redundant: Comprueba si un outsider introducido por par´ametro pertenece a otro shape de entrada. En caso afirmativo se devuelve el valor 1 y 0 en caso contrario. int o u t s i d e r i s r e d u n d a n t ( HitSigExtShape o uts i de r , HitSigExtShape f i g u r e ) ; share interval: Dados dos HitSigExt comprueba si los intervalos que representan ambas estructuras comparten intervalos. En caso afirmativo se devuelve el valor 1 y 0 en caso contrario. int s h a r e i n t e r v a l ( HitSigExt Sa , HitSigExt Sb) ; separate skeletons rect rect: Dados dos rect´angulos introducidos por par´ametros, se realiza el reajuste de las coordenadas del primero para asegurar que estos sean disjuntos. 83 4.4. FUNCIONES SECUNDARIAS int s e p a r a t e s k e l e t o n s r e c t r e c t ( HitSigExtShape i n t e r s e c t i o n [ ] , int v a l i d [ ] , int i , int j , int ∗z ) ; separate skeletons rect triangle: Dados un rect´angulo y un tri´angulo introducidos por par´ametros, se realiza el reajuste de las coordenadas del primero para asegurar que estos sean disjuntos. int s e p a r a t e s k e l e t o n s r e c t t r i a n g l e ( HitSigExtShape i n t e r s e c t i o n [ ] , int v a l i d [ ] , int i , int j , int ∗z ) ; modify diagonal: Dado un tri´angulo introducido por par´ametro, modifica su lado diagonal reajustando su v´ertice A o C o ambos en funci´on de los flags de entrada. void modify diago nal ( HitSigExtShape ∗triangle , int modA, int modC) ; outsiders separate skeletons: Dados un triangulo de coordenadas reales y el shape resultante del reajuste del primero a coordenadas enteras, obtiene un array con los puntos que pertenec´ıan al tri´angulo inicial pero que se pierden al reajustar. HitSigExtShape ∗o u t s i d e r s s e p a r a t e s k e l e t o n s ( TriangleReal t r i a n g l e O r i g i n a l , HitSigExtShape t r iang l eMo d ifie d , int admitDiag , int x , int y ) ; separate skeletons triangle triangle: Dados dos tri´angulos introducidos por par´ametros, se realiza el reajuste de las coordenadas del primero para asegurar que estos sean disjuntos. int s e p a r a t e s k e l e t o n s t r i a n g l e t r i a n g l e ( HitSigExtShape i n t e r s e c t i o n [ ] , int v a l i d [ ] , int i , int j , int ∗z ) ; separate skeletons: Dados dos shapes introducidos por par´ametro se realiza el reajuste de las coordenadas de los mismos para asegurar que estos son disjuntos y no comparten puntos en su per´ımetro. HitSigExtShape ∗s e p a r a t e s k e l e t o n s ( HitSigExtShape i n t e r s e c t i o n [ ] , HitSigExtShape Sb) ; belonging condition difference: Comprueba si un punto alcanzado durante las b´usquedas desde otro punto inicial, ambos introducidos como entrada, pertenece a la diferencia de Sa menos Sb. int b e l o n g i n g c o n d i t i o n d i f f e r e n c e ( Point i n i t i a l P o i n t , Point reachedPoint , HitSigExtShape Sa, HitSigExtShape Sb) ; belonging condition: Comprueba si un punto alcanzado durante las b´usquedas desde otro punto inicial, ambos introducidos como entrada, pertenece a la intersecci´on entre Sa y Sb int b e l o n g i n g c o n d i t i o n ( Point i n i t i a l P o i n t , Point reac he dP oint , HitSigExtShape Sa, HitSigExtShape Sb, int difference); 84 CAP´ ITULO 4. IMPLEMENTACI ´ ON separate skeletons triangle rect: Dados un tri´angulo y un rect´angulo introducidos por par´ametros, se realiza el reajuste de las coordenadas del primero para asegurar que estos sean disjuntos. int s e p a r a t e s k e l e t o n s t r i a n g l e r e c t ( HitSigExtShape i n t e r s e c t i o n [ ] , int v a l i d [ ] , int i , int j , int ∗z ) ; separate skeletons from Sb: Dado un array de shapes y otro shape Sb, introducidos por par´ametros, se realiza el reajuste de las coordenadas de todos los shapes del array para asegurar que estos sean disjuntos con respecto a Sb. HitSigExtShape ∗s e p a r a t e s k e l e t o n s f r o m S b ( HitSigExtShape i n t e r s e c t i o n [] , HitSigExtShape Sb) ; readjust triangle separate: Realiza el reajuste de las coordenadas de un tri´angulo introducido por par´ametro, modificando los v´ertices A o B o C del mismo o cualquier combinaci´on de los mismos, en funci´on de los flags de entrada. HitSigExtShape r e a d j u s t t r i a n g l e s e p a r a t e ( HitSigExtShape t r ian gl e , int readjustA , int readjustB , int readjustC , double m, double t ) ; 85 4.4. FUNCIONES SECUNDARIAS 86 CAP´ ITULO 5. PRUEBAS Cap´ıtulo 5 Pruebas En este cap´ıtulo se introducen los siguientes aspectos: Se detallan los casos de prueba m´as significativos planteados para cada uno de los algoritmos implementados (intersecci´on, diferencia y uni´on), as´ı como sus salidas esperadas y las salidas obtenidas. Las figuras ilustradas durante este cap´ıtulo siguen la nomenclatura indicada en la secci´on 3.2. 5.1. Pruebas En esta secci´on se muestran los casos de prueba m´as significativos empleados en los algoritmos de intersecci´on, diferencia y uni´on para comprobar la validez de los mismos. Estos casos de prueba se dividen en dos tipos; los casos base y los casos l´ımite. Para aquellos casos en los que se obtenga una salida incorrecta se localiza la causa de dicho error, se realizan las modificaciones pertinentes y se documentan con el objetivo de obtener un software funcional y usable por el grupo de investigaci´on Trasgo. 5.1.1. Casos base Los casos base de un conjuntos de pruebas de validaci´on son aquellos que buscan comprobar la correcci´on del funcionamiento de un software para un conjunto de entradas est´andar, es decir, aquellas entradas que son esperables/deseables y que muestran si los c´alculos realizados por los algoritmos son correctos para la mayor´ıa de situaciones. 87 5.1. PRUEBAS Caso de prueba 1 Dos tri´angulos como entrada que determinan un pol´ıgono de intersecci´on cuyos v´ertices distan entre s´ı una distancia superior a una unidad en el plano de coordenadas para 2 dimensiones y entre los que est´a comprendido al menos un punto de coordenadas enteras. Figura 5.1: Caso de prueba 1. •Shapes de entrada Sa ={2,1,{0,12,1},{0,8,1}} Sb ={2,1,{5,10,1},{−2,12,1}} •Salida del caso de prueba 1 para el algoritmo de intersecci´on Caso 1 −intersection Entrada : Sa = {2 , 1 , {0 , 12 , 1},{0 , 8 , 1}} Sb = {2 , 1 , {5 , 10 , 1},{−2, 12 , 1}} Shapes esperad os : shapes [ 0 ] = {2 , 0 , {5 , 8 , 1},{0 , 2 , 1}} shapes [ 1 ] = {2 , 1 , {9 , 9 , 1},{0 , 0 , 1}} shapes [ 2 ] = {2 , 1 , {5 , 7 , 1},{3 , 4 , 1}} shapes [ 3 ] = {2 , 1 , {6 , 6 , 1},{4 , 4 , 1}} Shapes obtenidos : shapes [ 0 ] = {2 , 0 , {5 , 8 , 1},{0 , 2 , 1}} shapes [ 1 ] = {2 , 1 , {9 , 9 , 1},{0 , 0 , 1}} shapes [ 2 ] = {2 , 1 , {5 , 7 , 1},{3 , 4 , 1}} shapes [ 3 ] = {2 , 1 , {6 , 6 , 1},{4 , 4 , 1}} Resultado : Correcto Listing 5.1: Salidas esperadas y obtenidas por la intersecci´on para el caso 1. 88 CAP´ ITULO 5. PRUEBAS Figura 5.2: Salida del caso de prueba 1 para el algoritmo de intersecci´on. •Salida del caso de prueba 1 para el algoritmo de la diferencia Caso 1 −difference Entrada : Sa = {2 , 1 , {0 , 12 , 1},{0 , 8 , 1}} Sb = {2 , 1 , {5 , 10 , 1},{−2, 12 , 1}} Shapes esperad os : shapes [ 0 ] = {2 , 0 , {0 , 4 , 1},{0 , 4 , 1}} shapes [ 1 ] = {2 , 1 , {9 , 9 , 1},{1 , 1 , 1}} shapes [ 2 ] = {2 , 1 , {10 , 12 , 1},{0 , 1 , 1}} shapes [ 3 ] = {2 , 1 , {9 , 9 , 1},{2 , 2 , 1}} shapes [ 4 ] = {2 , 1 , {0 , 4 , 1},{5 , 8 , 1}} shapes [ 5 ] = {2 , 1 , {3 , 3 , 1},{6 , 6 , 1}} Shapes obtenidos : shapes [ 0 ] = {2 , 0 , {0 , 4 , 1},{0 , 4 , 1}} shapes [ 1 ] = {2 , 1 , {9 , 9 , 1},{1 , 1 , 1}} shapes [ 2 ] = {2 , 1 , {10 , 12 , 1},{0 , 1 , 1}} shapes [ 3 ] = {2 , 1 , {9 , 9 , 1},{2 , 2 , 1}} shapes [ 4 ] = {2 , 1 , {0 , 4 , 1},{5 , 8 , 1}} shapes [ 5 ] = {2 , 1 , {3 , 3 , 1},{6 , 6 , 1}} Resultado : Correcto Listing 5.2: Salidas esperadas y obtenidas por la diferencia para el caso 1. •Salida del caso de prueba 1 para el algoritmo de uni´on Caso 1 −unionHitSig 89 5.1. PRUEBAS Figura 5.10: Salida del caso de prueba 3 para el algoritmo de intersecci´on. shapes [ 1 ] = {2 , 1 , {9 , 12 , 1},{0 , 1 , 1}} shapes [ 2 ] = {2 , 1 , {1 , 9 , 1},{2 , 7 , 1}} shapes [ 3 ] = {2 , 1 , {10 , 10 , 1},{1 , 1 , 1}} shapes [ 4 ] = {2 , 0 , {0 , 0 , 1},{3 , 8 , 1}} shapes [ 5 ] = {2 , 1 , {3 , 3 , 1},{6 , 6 , 1}} shapes [ 6 ] = {2 , 1 , {6 , 6 , 1},{4 , 4 , 1}} Shapes obtenidos : shapes [ 0 ] = {2 , 0 , {0 , 8 , 1},{0 , 1 , 1}} shapes [ 1 ] = {2 , 1 , {9 , 12 , 1},{0 , 1 , 1}} shapes [ 2 ] = {2 , 1 , {1 , 9 , 1},{2 , 7 , 1}} shapes [ 3 ] = {2 , 1 , {10 , 10 , 1},{1 , 1 , 1}} shapes [ 4 ] = {2 , 0 , {0 , 0 , 1},{3 , 8 , 1}} shapes [ 5 ] = {2 , 1 , {3 , 3 , 1},{6 , 6 , 1}} shapes [ 6 ] = {2 , 1 , {6 , 6 , 1},{4 , 4 , 1}} Resultado : Correcto Listing 5.8: Salidas esperadas y obtenidas por la diferencia para el caso 3. Figura 5.11: Salida del caso de prueba 3 para el algoritmo de la diferencia. •Salida del caso de prueba 3 para el algoritmo de uni´on Caso 3 −unionHitSig Entrada : 96 CAP´ ITULO 5. PRUEBAS Sa = {2 , 1 , {0 , 12 , 1},{0 , 8 , 1}} Sb = {2 , 1 , {5 , 10 , 1},{−2, 12 , 1}} Shapes esperad os : shapes [ 0 ] = {2 , 1 , {0 , 12 , 1},{0 , 8 , 1}} shapes [ 1 ] = {2 , 1 , {−2, −1, 1},{2 , 4 , 1}} shapes [ 2 ] = {2 , 0 , {−1, −1, 1},{3 , 3 , 1}} Shapes obtenidos : shapes [ 0 ] = {2 , 1 , {0 , 12 , 1},{0 , 8 , 1}} shapes [ 1 ] = {2 , 1 , {−2, −1, 1},{2 , 4 , 1}} shapes [ 2 ] = {2 , 0 , {−1, −1, 1},{3 , 3 , 1}} Resultado : Correcto Listing 5.9: Salidas esperadas y obtenidas por la uni´on para el caso 3. Figura 5.12: Salida del caso de prueba 3 para el algoritmo de uni´on. Caso de prueba 4 Dos tri´angulos como entrada cuya intersecci´on es un segmento diagonal. Figura 5.13: Caso de prueba 4. •Shapes de entrada Sa ={2,1,{0,12,1},{0,8,1}} 97 5.1. PRUEBAS Sb ={2,1,{6,0,1},{8,4,1}} •Salida del caso de prueba 4 para el algoritmo de intersecci´on Caso 4 −intersection Entrada : Sa = {2 , 1 , {0 , 12 , 1},{0 , 8 , 1}} Sb = {2 , 1 , {6 , 0 , 1},{8 , 4 , 1}} Shapes esperad os : shapes [ 0 ] = {2 , 1 , {0 , 0 , 1},{8 , 8 , 1}} shapes [ 1 ] = {2 , 1 , {3 , 3 , 1},{6 , 6 , 1}} shapes [ 2 ] = {2 , 1 , {6 , 6 , 1},{4 , 4 , 1}} Shapes obtenidos : shapes [ 0 ] = {2 , 1 , {0 , 0 , 1},{8 , 8 , 1}} shapes [ 1 ] = {2 , 1 , {3 , 3 , 1},{6 , 6 , 1}} shapes [ 2 ] = {2 , 1 , {6 , 6 , 1},{4 , 4 , 1}} Resultado : Correcto Listing 5.10: Salidas esperadas y obtenidas por la intersecci´on para el caso 4. Figura 5.14: Salida del caso de prueba 4 para el algoritmo de intersecci´on. •Salida del caso de prueba 4 para el algoritmo de la diferencia Caso 4 −difference Entrada : Sa = {2 , 1 , {0 , 12 , 1},{0 , 8 , 1}} Sb = {2 , 1 , {6 , 0 , 1},{8 , 4 , 1}} Shapes esperad os : shapes [ 0 ] = {2 , 0 , {0 , 5 , 1},{0 , 3 , 1}} shapes [ 1 ] = {2 , 1 , {6 , 12 , 1},{0 , 3 , 1}} shapes [ 2 ] = {2 , 1 , {0 , 5 , 1},{4 , 7 , 1}} shapes [ 3 ] = {2 , 1 , {7 , 7 , 1},{3 , 3 , 1}} shapes [ 4 ] = {2 , 1 , {9 , 9 , 1},{2 , 2 , 1}} shapes [ 5 ] = {2 , 1 , {1 , 1 , 1},{7 , 7 , 1}} 98 CAP´ ITULO 5. PRUEBAS shapes [ 6 ] = {2 , 1 , {2 , 2 , 1},{6 , 6 , 1}} shapes [ 7 ] = {2 , 1 , {4 , 4 , 1},{5 , 5 , 1}} Shapes obtenidos : shapes [ 0 ] = {2 , 0 , {0 , 5 , 1},{0 , 3 , 1}} shapes [ 1 ] = {2 , 1 , {6 , 12 , 1},{0 , 3 , 1}} shapes [ 2 ] = {2 , 1 , {0 , 5 , 1},{4 , 7 , 1}} shapes [ 3 ] = {2 , 1 , {7 , 7 , 1},{3 , 3 , 1}} shapes [ 4 ] = {2 , 1 , {9 , 9 , 1},{2 , 2 , 1}} shapes [ 5 ] = {2 , 1 , {1 , 1 , 1},{7 , 7 , 1}} shapes [ 6 ] = {2 , 1 , {2 , 2 , 1},{6 , 6 , 1}} shapes [ 7 ] = {2 , 1 , {4 , 4 , 1},{5 , 5 , 1}} Resultado : Correcto Listing 5.11: Salidas esperadas y obtenidas por la diferencia para el caso 4. Figura 5.15: Salida del caso de prueba 4 para el algoritmo de la diferencia. •Salida del caso de prueba 4 para el algoritmo de uni´on Caso 4 −unionHitSig Entrada : Sa = {2 , 1 , {0 , 12 , 1},{0 , 8 , 1}} Sb = {2 , 1 , {6 , 0 , 1},{8 , 4 , 1}} Shapes esperad os : shapes [ 0 ] = {2 , 1 , {0 , 11 , 1},{0 , 7 , 1}} shapes [ 1 ] = {2 , 1 , {6 , 0 , 1},{8 , 4 , 1}} shapes [ 2 ] = {2 , 0 , {12 , 12 , 1},{0 , 0 , 1}} shapes [ 3 ] = {2 , 1 , {1 , 1 , 1},{7 , 7 , 1}} shapes [ 4 ] = {2 , 1 , {2 , 2 , 1},{6 , 6 , 1}} shapes [ 5 ] = {2 , 1 , {4 , 4 , 1},{5 , 5 , 1}} shapes [ 6 ] = {2 , 1 , {5 , 5 , 1},{4 , 4 , 1}} shapes [ 7 ] = {2 , 1 , {7 , 7 , 1},{3 , 3 , 1}} shapes [ 8 ] = {2 , 1 , {8 , 9 , 1},{2 , 2 , 1}} shapes [ 9 ] = {2 , 1 , {10 , 10 , 1},{1 , 1 , 1}} Shapes obtenidos : shapes [ 0 ] = {2 , 1 , {0 , 11 , 1},{0 , 7 , 1}} shapes [ 1 ] = {2 , 1 , {6 , 0 , 1},{8 , 4 , 1}} shapes [ 2 ] = {2 , 0 , {12 , 12 , 1},{0 , 0 , 1}} 99 5.1. PRUEBAS shapes [ 3 ] = {2 , 1 , {1 , 1 , 1},{7 , 7 , 1}} shapes [ 4 ] = {2 , 1 , {2 , 2 , 1},{6 , 6 , 1}} shapes [ 5 ] = {2 , 1 , {4 , 4 , 1},{5 , 5 , 1}} shapes [ 6 ] = {2 , 1 , {5 , 5 , 1},{4 , 4 , 1}} shapes [ 7 ] = {2 , 1 , {7 , 7 , 1},{3 , 3 , 1}} shapes [ 8 ] = {2 , 1 , {8 , 9 , 1},{2 , 2 , 1}} shapes [ 9 ] = {2 , 1 , {10 , 10 , 1},{1 , 1 , 1}} Resultado : Correcto Listing 5.12: Salidas esperadas y obtenidas por la uni´on para el caso 4. Figura 5.16: Salida del caso de prueba 4 para el algoritmo de uni´on. Caso de prueba 5 Dos tri´angulos como entrada que no presentan ning´un punto com´un. Figura 5.17: Caso de prueba 5. •Shapes de entrada Sa ={2,1,{0,12,1},{0,8,1}} Sb ={2,1,{5,10,1},{−2,12,1}} •Salida del caso de prueba 1 para el algoritmo de intersecci´on 100 CAP´ ITULO 5. PRUEBAS Caso 5 −intersection Entrada : Sa = {2 , 1 , {0 , 12 , 1},{0 , 8 , 1}} Sb = {2 , 1 , {6 , 8 , 1},{6 , 8 , 1}} Shapes esperad os : Shapes obtenidos : Resultado : Correcto Listing 5.13: Salidas esperadas y obtenidas por la intersecci´on para el caso 5. Figura 5.18: Salida del caso de prueba 5 para el algoritmo de intersecci´on. •Salida del caso de prueba 5 para el algoritmo de la diferencia Caso 5 −difference Entrada : Sa = {2 , 1 , {0 , 12 , 1},{0 , 8 , 1}} Sb = {2 , 1 , {6 , 8 , 1},{6 , 8 , 1}} Shapes esperad os : shapes [ 0 ] = {2 , 1 , {0 , 12 , 1},{0 , 8 , 1}} Shapes obtenidos : shapes [ 0 ] = {2 , 1 , {0 , 12 , 1},{0 , 8 , 1}} Resultado : Correcto Listing 5.14: Salidas esperadas y obtenidas por la diferencia para el caso 5. •Salida del caso de prueba 5 para el algoritmo de uni´on Caso 5 −unionHitSig Entrada : 101 5.1. PRUEBAS Figura 5.19: Salida del caso de prueba 1 para el algoritmo de la diferencia. Sa = {2 , 1 , {0 , 12 , 1},{0 , 8 , 1}} Sb = {2 , 1 , {5 , 10 , 1},{−2, 12 , 1}} Shapes esperad os : shapes [ 0 ] = {2 , 1 , {0 , 12 , 1},{0 , 8 , 1}} shapes [ 1 ] = {2 , 1 , {6 , 8 , 1},{6 , 8 , 1}} Shapes obtenidos : shapes [ 0 ] = {2 , 1 , {0 , 12 , 1},{0 , 8 , 1}} shapes [ 1 ] = {2 , 1 , {6 , 8 , 1},{6 , 8 , 1}} Resultado : Correcto Listing 5.15: Salidas esperadas y obtenidas por la uni´on para el caso 1. Figura 5.20: Salida esperada del caso de prueba 1 para el algoritmo de uni´on. 5.1.3. Correciones de los algoritmos Como se ha visto en la secci´on 5.1.1, el algoritmo de uni´on produce una salida incorrecta para el caso de prueba 1. Este caso de prueba consiste en las siguientes entradas: 102 CAP´ ITULO 5. PRUEBAS Shapes de entrada Sa ={2,1,{0,12,1},{0,8,1}} Sb ={2,1,{5,10,1},{−2,12,1}} Para estas entradas, la salida esperada para el algoritmo de uni´on es la siguiente: shapes [ 0 ] = {2 , 0 , {0 , 4 , 1},{0 , 4 , 1}} shapes [ 1 ] = {2 , 1 , {9 , 9 , 1},{1 , 2 , 1}} shapes [ 2 ] = {2 , 1 , {10 , 12 , 1},{0 , 1 , 1}} shapes [ 3 ] = {2 , 1 , {0 , 4 , 1},{5 , 8 , 1}} shapes [ 4 ] = {2 , 1 , {3 , 3 , 1},{6 , 6 , 1}} shapes [ 5 ] = {2 , 0 , {5 , 9 , 1},{−2, −1, 1}} shapes [ 6 ] = {2 , 1 , {10 , 10 , 1},{−2, −2, 1}} shapes [ 7 ] = {2 , 1 , {7 , 7 , 1},{4 , 4 , 1}} shapes [ 8 ] = {2 , 1 , {8 , 8 , 1},{3 , 3 , 1}} shapes [ 9 ] = {2 , 1 , {5 , 7 , 1},{5 , 12 , 1}} shapes [ 1 0 ] = {2 , 1 , {6 , 6 , 1},{9 , 9 , 1}} shapes [ 1 1 ] = {2 , 1 , {7 , 7 , 1},{6 , 6 , 1}} shapes [ 1 2 ] = {2 , 0 , {5 , 8 , 1},{0 , 2 , 1}} shapes [ 1 3 ] = {2 , 1 , {9 , 9 , 1},{0 , 0 , 1}} shapes [ 1 4 ] = {2 , 1 , {5 , 7 , 1},{3 , 4 , 1}} shapes [ 1 5 ] = {2 , 1 , {6 , 6 , 1},{4 , 4 , 1}} Listing 5.16: Salida obtenida por la uni´on para el caso 1. Que se corresponde con la siguiente figura: Sin embargo, la salida obtenida por el algoritmo de uni´on es la siguiente: shapes [ 0 ] = {2 , 0 , {0 , 4 , 1},{0 , 4 , 1}} shapes [ 1 ] = {2 , 1 , {9 , 9 , 1},{1 , 1 , 1}} shapes [ 2 ] = {2 , 1 , {10 , 12 , 1},{0 , 1 , 1}} shapes [ 3 ] = {2 , 1 , {9 , 9 , 1},{2 , 2 , 1}} shapes [ 4 ] = {2 , 1 , {0 , 4 , 1},{5 , 8 , 1}} shapes [ 5 ] = {2 , 1 , {3 , 3 , 1},{6 , 6 , 1}} shapes [ 6 ] = {2 , 0 , {5 , 9 , 1},{−2, −1, 1}} shapes [ 7 ] = {2 , 1 , {10 , 10 , 1},{−2, −2, 1}} shapes [ 8 ] = {2 , 1 , {8 , 8 , 1},{3 , 3 , 1}} shapes [ 9 ] = {2 , 1 , {5 , 7 , 1},{5 , 12 , 1}} shapes [ 1 0 ] = {2 , 0 , {5 , 8 , 1},{0 , 2 , 1}} shapes [ 1 1 ] = {2 , 1 , {9 , 9 , 1},{0 , 0 , 1}} shapes [ 1 2 ] = {2 , 1 , {5 , 7 , 1},{3 , 4 , 1}} shapes [ 1 3 ] = {2 , 1 , {6 , 6 , 1},{4 , 4 , 1}} Listing 5.17: Salidas obtenidas por la uni´on para el caso 1. Que se corresponde con la siguiente figura: Como se pueda apreciar en la figura 5.22, se produce la p´erdida de los puntos con coordenadas (7 , 4), (6 , 9) y (7 , 6), que se corresponden con los shapes 7, 10 y 11 del listing 5.16, respectivamente. 103 5.1. PRUEBAS Figura 5.21: Salida esperada del caso de prueba 1 para el algoritmo de uni´on. Figura 5.22: Salida obtenida del caso de prueba 1 para el algoritmo de uni´on. Observando las salidas se puede apreciar que todos los shapes perdidos pertenecen a la diferencia de Sb menos Sa. Como se ha descrito en la secci´on de 3.5.3, el algoritmo de intersecci´on realiza el c´alculo de la intersecci´on de Sa con Sb, la diferencia de Sa menos Sb y 104 CAP´ ITULO 5. PRUEBAS la diferencia de Sb menos Sa. Esto acota el error de los c´alculos al algoritmo de la diferencia, en concreto para una situaci´on generada para la diferencia de Sb menos Sa. Estos resultados chocan con los requisitos RF03, RF04, RNF02 y RNF03 descritos en la secci´on 3.3, por ende, es necesario realizar modificaciones en el algoritmo para lograr la correcci´on de los c´alculos y cumplir con todos los requisitos funcionales y no funcionales. Tras una fase de debug se localiza el punto concreto en el que se origina el error: el reajuste de un tri´angulo de coordenadas reales a enteras y su posterior generaci´on de puntos outsiders. Este tri´angulo se trata del shape 9 del array de salida, el cual se trata de un tri´angulo de tipo 1. La problem´atica surge al aplicar un reajuste que no se corresponde con el tipo de tri´angulo que se trata, por lo que se crea una funci´on denominada hit sig ext shape share side part que detecta ciertas condiciones particulares que distinguen el tipo de tri´angulo y coincidencias con shapes contiguos, de forma que se invoca a la funci´on de reajuste correcta. La b´usqueda del origen del error de las salidas en este caso de prueba y la posterior fase de modificaci´on del software para lograr la validez del algoritmo ha afectado ligeramente al camino cr´ıtico. Esta tarea de depuraci´on costo dos d´ıas completos de trabajo que obligaron a reducir el tiempo empleado para desarrollar esta memoria con el objetivo de alcanzar la fecha l´ımite de finalizaci´on del proyecto. 105 112 AP´ ENDICE A. CONTENIDOS DEL PROYECTO Ap´endice A Contenidos del proyecto La entrega de este Trabajo de Fin de Grado ha sido realizada a trav´es del fichero ZIP DatosTFGHugoPrietoTarrega, que contiene los siguientes archivos: intersecion.h: fichero de cabecera [38] que incluye la declaraci´on de las estructuras de datos, macros y funciones empleadas por los algoritmos que extienden la librer´ıa Hitmap. intersection.c: fichero que contiene el c´odigo fuente de la extensi´on la librer´ıa Hitmap desarrollada en este. 113 114 BIBLIOGRAF´ IA Bibliograf´ıa [1] G. Hager y G. Wellein. Introduction to high performance computing for scientists and engineers. CRC Press, 2010. [2] Yoshua Bengio, Aaron Courville, and Pascal Vincent. Representation learning: A review and new perspectives. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(8):1798–1828, 2013. [3] Ivan S. Ufimtsev and Todd J. Mart´ınez. Graphical processing units for quantum chemistry. Computing in Science Engineering, 10(6):26–34, 2008. [4] Sparsh Mittal. A Survey of FPGA-based Accelerators for Convolutional Neural Networks. Febrero 2020. https://www.researchgate.net/publication/327931012_A_ Survey_of_FPGA-based_Accelerators_for_Convolutional_Neural_Networks. [5] Jorge Ort´ız. La computaci´on paralela: alta capacidad de procesamiento, 2020. https: //www.teldat.com/blog/es/computacion-paralela-capacidad-procesamiento/, ´ Ultimo acceso: Junio, 2021. [6] TOP 500. TOP 500 - HomePage , 2021. https://www.top500.org/,´ Ultimo acceso: Junio, 2021. [7] Felipe Restrepo Calle. Ventajas y desventajas de la computaci´on paralela. http://ferestrepoca.github.io/paradigmas-de-programacion/paralela/ paralela_teoria/index.html#four,´ Ultimo acceso: Junio, 2021. [8] TOP 500. HIGHLIGHTS - NOVEMBER 2020, noviembre 2020. https://www.top500. org/,´ Ultimo acceso: Junio, 2021. [9] Juan Antonio Pascual Estap´e. Petaflops, la unidad de medida de los superordenadores, julio 2020. https://computerhoy.com/reportajes/tecnologia/ petaflops-unidad-medida-superordenadores-667982,´ Ultimo acceso: Junio, 2021. [10] Juan Carlos L´opez. Con MareNostrum 5 podr´ıamos quedar entre los tres supercomputadores m´as r´apidos del mundo, pero no es nuestro objetivo)), Mateo Valero, director del BSC, Febrero 2020. https://www.xataka.com/investigacion/ marenostrum-5-podriamos-quedar-tres-supercomputadores-rapidos-mundo-no-nuestro-objetivo-mateo-valero-director-bsc, ´ Ultimo acceso: Junio, 2021. 115 BIBLIOGRAF´ IA [11] Eloy Fustero. ¿Qu´e es la computaci´on heterog´enea? Parte II, Noviembre 2013. https: //blogthinkbig.com/computacion-heterogenea-2,´ Ultimo acceso: Junio, 2021. [12] Arturo Gonz´alez-Escribano. Grupo Trasgo, 2020. https://trasgo.infor.uva.es/, ´ Ultimo acceso: Junio, 2021. [13] UVa. Departamento de Inform´atica de la Universidad de Valladolid, 2021. https: //www.infor.uva.es/,´ Ultimo acceso: Junio, 2021. [14] Javier Fresno Diego R. Llanos Arturo Gonzalez-Escribano, Yuri Torres. An Extensible System for Multilevel Automatic Data Partition and Mapping. IEEE Transactions on Parallel and Distributed Systems, 25(5):1–2, 2014. [15] W. Stallings. Computer organization and architecture: Designing for performance. Upper Saddle River, NJ: Prentice Hall. 2010. [16] Jonathan Sterne. Plug-in. Encyclopedia Britannica, Octubre 2019. https://www. britannica.com/technology/plug-in.´ Ultimo acceso: junio 2021. [17] Tech Terms. Software Terms : Framework Definition, March 2013. shorturl.at/firFJ, ´ Ultimo acceso: Junio, 2021. [18] Yuri Torres, Arturo Gonzalez-Escribano, and Diego Ferraris. Encapsulated synchronization and load-balance in heterogeneous programming. pages 502–513, 08 2012. [19] Gu´ıa Docente Computaci´on Paralela Curso 2018-2019, 2018. [20] Diego R. Llanos Ana Moreton-Fernandez, Arturo Gonzalez-Escribano. A technique to automatically determine Ad-hoc communication patterns at runtime. Parallel Computing 69, pages 45 – 62, 2017. [21] Arturo Gonz´alez Escribano Mar´ıa Inmaculada Santamar´ıa Valenzuela, Yuri Torres de la Sierra. Triangular tiling. an extension for hitmap’s hitsigshape structure and its algebra, (pendiente de env´ıo). pages 1–6, 2021. [22] CMS. Selecting a development approach . pages 1 – 10, marzo 2008. [23] Bob Hughes and Mike Cotterel. Software project management. pages 49–71, May 2009. [24] Discord. Discord: Main Page , 2021. https://discord.com/brand-new,´ Ultimo acceso: Junio, 2021. [25] Bob Hughes and Mike Cotterel. Software project management. pages 162–188, May 2009. [26] Bob Hughes and Mike Cotterel. Software project management. pages 129–160, May 2009. [27] Encyclopedia of Mathematics. Parallelotope, 2020. https://encyclopediaofmath. org/wiki/Parallelotope,´ Ultimo acceso: Junio, 2021. [28] T´ecnicas para Identificar Requisitos Funcionales y No Funcionales, 2020. https://sites.google.com/site/metodologiareq/capitulo-ii/ tecnicas-para-identificar-requisitos-funcionales-y-no-funcionales. 116 BIBLIOGRAF´ IA [29] Robert A. Beezer Thomas W. Judson. ´ Algebra abstracta, teor´ıa y aplicaciones. pages 1–14, 2017. [30] Alberto M´arquez. Intersecci´on de pol´ıgonos convexos, 2020. https://n9.cl/lo8yu, ´ Ultimo acceso: Junio, 2021. [31] Erich Hartmann. Geometry and algorithms for computer aided design. page 17, 2003. [32] Arturo Gonz´alez Escribano Mar´ıa Inmaculada Santamar´ıa Valenzuela, Yuri Torres de la Sierra. Triangulartiling. an extension for hitmap’s hitsigshape structure and its algebra. pages 6–29, 2021. [33] tutorials point. C library function - calloc(), 2017. https://www.tutorialspoint.com/ c_standard_library/c_function_calloc.htm. [34] Microsoft. Por qu´e los n´umeros de punto flotante pierden precisi´on, 2016. https://docs.microsoft.com/es-es/cpp/build/ why-floating-point-numbers-may-lose-precision?view=msvc-160. [35] Microsoft. Precisi´on y precisi´on en los c´alculos de punto flotante, 2020. https://docs.microsoft.com/es-es/office/troubleshoot/access/ floating-calculations-info. [36] Educando con TIC. Valores l´ımite: Pruebas de caja negra, 2021. https:// educandocontic.com/valores-limite-pruebas/,´ Ultimo acceso: Junio, 2021. [37] Univeridad de Salamanca. 21 International Conference Computational and Mathematical Methods in Science and Engineering, 2021. https://cmmse.usal.es/cmmse2021/ welcome/. [38] Wikipedia. Archivo de cabecera, 2021. https://es.wikipedia.org/wiki/Archivo_ de_cabecera. 117