Optimización de software de visualización y detección de patrones de drenaje y terrazas fluviales en superficies de terreno
Professor Advisor
dc.contributor.advisor
Hitschfeld Kahler, Nancy
Author
dc.contributor.author
Pefaur Pumarino, José Tomás
Associate professor
dc.contributor.other
Bergel, Alexandre
Associate professor
dc.contributor.other
Ochoa Delorenzi, Sergio
Admission date
dc.date.accessioned
2017-01-31T20:59:30Z
Available date
dc.date.available
2017-01-31T20:59:30Z
Publication date
dc.date.issued
2016
Identifier
dc.identifier.uri
https://repositorio.uchile.cl/handle/2250/142813
General note
dc.description
Ingeniero Civil en Computación
es_ES
Abstract
dc.description.abstract
La Geomorfología fluvial corresponde al estudio de los procesos de formación y sedimentación de los ríos, y de su interacción con el entorno, lo que entrega información sobre la "historia de vida" de un terreno. En este contexto, existen dos elementos de estudio interesantes: las redes de drenaje y las terrazas fluviales.
Runnel es un software que tiene por objetivo visualizar y detectar patrones de drenaje y terrazas fluviales sobre terrenos representados por grillas o triangulaciones de éstas. Si bien el funcionamiento de Runnel es correcto, éste tiene un gran problema: el tiempo de ejecución de sus principales algoritmos. A medida que el tamaño del terreno crece, el tiempo de ejecución aumenta considerablemente. Con el fin de mejorar este problema, se decidió paralelizar los algoritmos de detección de redes de drenaje: Peucker, Callaghan, RWFlood y Ángulo Diedro. Al mismo tiempo, se decidió implementar una triangulación simplificada, la cual disminuye el número de triángulos, y en consecuencia, se disminuye el tiempo de ejecución de los algoritmos que usan la triangulación.
Para lograr la paralelización se utilizó OpenCL, herramienta que permite la ejecución de un código paralelo tanto en GPU como en CPU de forma indistinguible. Para la triangulación simplificada se utilizó un algoritmo basado en la eliminación de uno de los vértices de aquellos triángulos que cumplen una condición predeterminada.
Como resultado de la paralelización se obtuvieron mejoras significativas con los algoritmos de Peucker (speed-up mínimo: 1.19 y speed-up máximo: 13.63), Callaghan (speed-up mínimo: 5.87 y speed-up máximo: 19.82) y Ángulo Diedro (speed-up mínimo: 1.43 y speed-up máximo: 23.53). La triangulación simplificada también entregó mejoras en rendimiento, pero con menor impacto que la paralelización (speed-up mínimo: 1.14 y speed-up máximo: 1.94). El único algoritmo que no resultó en mejoras en su tiempo de ejecución (en la mayoría de los casos de prueba) fue el algoritmo RWFlood (speed-up mínimo: 0.16 y speed-up máximo: 2.93).
Junto con el desarrollo de los algoritmos paralelos se adquirió conocimiento sobre las diferencias de rendimiento de una CPU con una GPU. Se tuvo que ahondar en la arquitectura de cada una y reconocer el tipo de problema que cada una puede resolver de manera óptima.
Se propone como trabajo futuro solucionar el uso excesivo de la memoria en la triangulación, analizar del impacto de la triangulación simplificada en los terrenos, solucionar el problema del tiempo de ejecución de RWFlood y paralelizar otros algoritmos.