Optimización de software de visualización y detección de patrones de drenaje y terrazas fluviales en superficies de terreno

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.