Magíster en Ciencias, Mención Computación / Ingeniero Civil Matemático / Las bases de datos de grafos son un modelo que ha ganado terreno en los últimos años, dada la necesidad de modelar situaciones complejas en donde el modelo relacional no es suficiente. En este trabajo introducimos el tema haciendo una revisión del estado del arte de las bases de datos de grafos, explicando algunas de sus aplicaciones reales, definiendo algunos de los diferentes modelos teóricos y analizando las implementaciones más importantes que existen en la realidad. De nuestro análisis concluimos que la gran falencia en el tema es la ausencia de un lenguaje de consulta formal, con una sintaxis y semántica clara, y que tenga un buen equilibrio entre expresividad y complejidad. Nuestra propuesta para solucionar este problema es utilizar Converse-PDL como lenguaje de consulta de bases de datos de grafos, definiéndolo formalmente, y demostrando que su complejidad teórica es óptima. Además, mostramos que la expresividad de este lenguaje es suficiente para una gran cantidad de aplicaciones. Una vez definido nuestro lenguaje, procedemos a diseñar una implementación eficiente, definiendo los algoritmos y las estructuras de datos necesarias, cuidando de cumplir todas las restricciones que están presentes en nuestro modelo computacional. Luego, procedemos a realizar la implementación en sí, describiendo en detalle las representaciones internas de los distintos elementos, respaldando con resultados experimentales las decisiones tomadas. Además, explicamos las distintas mejoras y optimizaciones que realizamos, con el fin de obtener la mayor eficiencia posible. Una vez terminada la implementación, procedemos a explicar todos los archivos programados y la interfaz de usuario implementada, con el fin de facilitar los futuros desarrollos. Con el fin de validar nuestra implementación, procedemos a diseñar un experimento para evaluar cuantitativamente el desempeño de nuestra implementación. El experimento diseñado se ejecuta en nuestra implementación, así como en otras tres implementaciones existentes, escogiendo los proyectos más competitivos, para así realizar una comparación objetiva. Finalizamos nuestro trabajo con las conclusiones obtenidas a partir de los experimentos, destacando los aspectos más importantes de nuestra implementación, y exponiendo algunas ideas a desarrollar en el futuro.

Magíster en Ciencias, Mención Computación / Ingeniera Civil en Computación / Una red tipo darknet es una porción de direcciones IPs asignado y ruteado en el cual no existen servicios activos ni servidores. Actualmente no existe un sistema, públicamente disponible, que permita la visualizar de forma gráfica los datos entregados por una red de estas características. El objetivo principal de esta tesis es la creación de un sistema dedicado a la visualización y análisis de datos de una darknet. El desarrollo de éste involucra la integración y evaluación de herramientas existentes además de la creación de un software enfocado en la creación de variados gráficos ad-hoc. Éstos permiten estudiar el comportamiento de la red con el fin de monitorearla para detectar posibles ataques. La metodología se basó principalmente en la investigación de herramientas, análisis sobre sus resultados y el diseño e implementación de un software dedicado a la creación de gráficos. Para conseguir lo descrito, se realizó un estudio de representaciones gráficas útiles para un analista. Se estudiaron distintos formatos con que la darknet puede entregar la información sobre el tráfico que recibe. Se evaluaron herramientas ya existentes con el fin de determinar si éstas entregan información relevante en términos de seguridad, y se estudió si satisfacen las necesidades planteadas para así utilizarlas o, en caso contrario, modificarlas. Se diseñaron e implementaron nuevas soluciones para contar con información valiosa referente a la toma de decisiones a partir de gráficos. Para esto se estudió cómo manipular los datos fuente para extraerles la información relevante. Para el caso de que éstos crezcan mucho en el tiempo, se realizó un estudio consistente en cómo extender el sistema de gráficos para manejar grandes volúmenes de datos. Se utilizaron 4 software de monitoreo de tráfico ya desarrollados: Moncube, TCPstat, EtherApe y Moncube, para generar imágenes sobre la actividad en la red. Estos gráficos son producidos diariamente a través de scripts que corren automáticamente cada día. El software diseñado y desarrollado para la creación de nuevas imágenes permite tener una visión completa de la red a través de 10 gráficos diarios diferentes. A través de un sitio web el analista podrá solicitar nuevos gráficos con los datos que él necesite, obteniendo una respuesta en tiempo razonable. En caso de que los datos arrojados por la darknet aumenten considerablemente se estudió el caso de bigdata, realizando un ejemplo gráfico cuyos datos fueron procesados en un ambiente cloud obteniendo respuestas valiosas y en corto tiempo. Finalmente se obtuvo un sistema completo que, en opinión de los autores, otorga información variada e interesante para un analista en seguridad. El software fue diseñado para ser extensible sin grandes dificultades, paralelizable y aplicable a otras variantes de redes de tipo darknet lo que permitirá monitorearlas y reaccionar ante eventos de seguridad. En un futuro, y a la luz de la experiencia del gráfico procesado en la nube, todos los gráficos creados para este trabajo podrían ser procesados en la nube para conseguir respuestas aún más rápidas que las ya obtenidas y permitir el procesamiento de grandes volúmenes de información.

Ingeniero Civil en Computación / La visualización científica es un área que apoya el análisis de datos generados por simulaciones de fenómenos físicos e ingenieriles, entre otros. Junto a los datos geometrícos del modelo que describen el dominio se requiere visualizar datos escalares y vectoriales asociados a los vértices, arcos y/o caras del modelo. Existen diversas técnicas para visualizar dichos campos tales como coloreado superficial, volume rendering, isolíneas, isosuperficies y otros. Camarón es una herramienta gráfica de estudio de mallas mixtas que permite conocer propiedades de los elementos que las constituyen. Para hacer más fácil el estudio cuenta con coloreado de vértices, polígonos y poliedros según el valor del criterio de evaluación a elección, además de presentar un histograma con la propiedad en estudio. Camarón además cuenta con múltiples renderers, métodos de selección de elementos, criterios de evaluación y archivos de entrada/salida junto con una arquitectura que lo hace fácilmente extensible. Ocupa la GPU de una máquina en forma activa para permitir una interacción fluida. Las GPU son unidades de procesamiento altamente paralelo que permiten paralelizar la mayoría de los algoritmos de visualización científica. Existen varias herramientas desarrolladas para aprovechar los recursos de una GPU tales como CUDA, OpenCl o OpenGL. La última es usada principalmente para fines gráficos. El objetivo de esta memoria consitió en introducir la visualización de campos escalares en Camarón principalmente con el uso de isolíneas para modelos superficiales e isosuperficies para volumétricos. La implementación ocupa el lenguaje C++ y aprovecha las capacidades de procesamiento de una GPU moderna con el uso de la biblioteca OpenGL. La arquitectura implementada es extensible y permite el manejo de valores escalares y vectoriales asociados a los vértices de una malla. Los algoritmos de generación de isosuperficies e isolíneas fueron implementados ocupando las capacidades de paralelismo de una GPU. Más aún el uso de la funcionalidad Transform Feedback en OpenGL permitió que la interacción con la malla fuese fluída. Se mejoró Dado que existen varios visualizadores en 3D para apoyar el análisis de datos científicos, se comparó el software Camarón con uno de los más usados ParaView. Los resultados muestran un desempeño entre 4 y 6 veces mejor para Camarón en términos de rapidez, aunque con sobrecostos en uso de memoria de hasta 6 veces lo usado por ParaView.

Ingeniera Civil en Computación / El Centro de Estudios Isla de Pascua y Oceanía, dependiente del Departamento de Antropología en la Facultad de Ciencias Sociales, se dedica a realizar proyectos relacionados con el patrimonio arqueológico de la Isla de Pascua. Uno de estos proyectos corresponde al proyecto Estatuaria de la Isla de Pascua, el cual, ha recopilado información significativa referente a los Moai y los atributos de estos tales como largo total, largo cabeza, material y localización. De acuerdo a la información recolectada, se ha determinado que existe una tipología de la estatuaria de la Isla de Pascua definida a partir de un conjunto de atributos. Debido a la enorme cantidad de información que existe actualmente y a que los investigadores responsables del proyecto no cuentan con herramientas apropiadas ni poseen la especialización necesaria, no ha habido un avance significativo en un análisis estilístico más detallado de los Moai, de los patrones recurrentes de diseño, proporciones, medidas, ni se ha abordado a la fecha la visualización y/o modelamiento de la data recopilada con respecto a estos. El objetivo de la memoria es desarrollar una herramienta que permita un análisis más riguroso de la información disponible por medio de la visualización científica de datos, la computación gráfica y de algoritmos apropiados para extraer información valiosa. Para cumplir el objetivo de la memoria, primero se realizó una toma de requerimientos y se describieron los casos de uso del sistema. Luego se desarrollaron prototipos basados en los casos de uso lo que involucró la investigación de variadas tecnologías. Posteriormente se creó una base de datos que contiene datos ficticios y una base de datos que contiene un subconjunto de Moai. Finalmente, se diseñó la arquitectura del sistema basándose en los prototipos creados, se implementó la administración de las bases de datos, la búsqueda entre intervalos de atributos, la búsqueda basada en la relación de dos atributos, la clasificación de Moai según su tipo, mapas interactivos con distintos modos de visualización y el modelamiento en 3D de un Moai. La validación de la herramienta se realizó evaluando su funcionalidad sobre los datos ficticios y para ver si efectivamente la herramienta visualizaba de forma correcta la información del catastro. El resultado final es una herramienta de escritorio gráfica e interactiva que permite difundir y analizar el registro arqueológico que se tiene hasta ahora de los Moai ya sea para fines educativos o de investigación.

El cálculo de la trayectoria de partículas en la atmósfera es una actividad abordada desde hace mucho tiempo, tomando en cuenta un enfoque clásico del uso de los computadores, en el cual se utilizan sus recursos como Procesador Central (CPU) y Memoria RAM. Este enfoque, que ha servido para alcanzar los logros actuales, con predicciones bastante acertadas, aún adolece de problemas claves y en cierta medida irresolubles, que se ven acentuados cuando los procesos se hacen más complejos, ya sea incorporando muchas partículas, o tomando en cuenta modelos de desplazamiento más realistas. El presente trabajo aborda un enfoque totalmente nuevo, el cual hace uso de una componente física de los computadores llamada “Tarjeta Gráfica”, la cual cuenta con su propia unidad de procesamiento gráfico llamada GPU por sus siglas en inglés. Esta componente, gracias a su gran cantidad de núcleos, ofrece la posibilidad de realizar paralelamente entre sí todos, o una parte de los cálculos que le son asignados, de una manera mucho más potente que lo conseguido en la actualidad al hacer uso solamente de CPU. Este problema es abordado mediante la implementación de un programa en dos versiones: una para funcionar exclusivamente en CPU y la otra para hacer uso de GPU en los cálculos. De esta manera se puede contar con un método directo para comparar el desempeño de estos dos enfoques, contrastarlos entre sí, y deducir los casos en que uno supera al otro. El principal insumo en la comparación de estos cálculos es la información del pronóstico del viento. El programa fue aplicado a una situación real: la erupción del Volcán Chaitén, para un día cuyos datos se poseían de antemano. Los resultados obtenidos fueron graficados y comparados con una imagen satelital correspondiente al mismo día simulado, siendo posible comprobar la alta similitud entre ellas. El tiempo de cálculo empleado por la versión que funciona en GPU supera en algunos casos en más de doscientas veces lo que tarda su contraparte CPU, sin afectar en gran medida la exactitud de los cálculos. Esto permite comprobar efectivamente que las GPU superan ampliamente el desempeño de las CPU, cuando el problema abordado es altamente paralelizable. Este es un tema que no está en absoluto cerrado, por cuanto son muchos los caminos donde seguir explorando las ventajas y desventajas del uso de GPU para estos cálculos. Por ejemplo se puede ver cómo funcionan las GPU incorporando procesos físicos más complejos para el cálculo de los desplazamientos de las partículas, o se puede considerar algunas propiedades físicas de estas partículas, como lo es la masa por ejemplo.