Procesamiento de consultas kNN en espacios métricos utilizando GPUs

Abstract

El presente trabajo pretende abordar el análisis, diseño e implementación paralela de algoritmos de búsquedas en espacios métricos. Más concretamente, se analizaron varios índices métricos relevantes en la literatura y se escogieron los que mejor se adaptaban a la tarjetas gráficas actuales (GPUs), plataforma paralela sobre la que se llevó a cabo su implementación. Dadas, por un lado las altas prestaciones de las modernas GPUs y, por otro, las numerosas restricciones sobre la regularidad del código para conseguir un buen rendimiento, se optó por implementar, con carácter comparativo, una versión exhaustiva de la búsqueda, mejorando propuestas previas. La regularidad del método exhaustivo en los accesos a memoria, clave para explotar correctamente el alto potencial de las GPUs, hace que, en determinados contextos, sea preferible a técnicas algorítmicamente más complejas pero con mayores asimetrías en su paralelización. Los resultados obtenidos permiten afirmar que las GPUs son una plataforma adecuada para la búsqueda en espacios métricos, incluso en contextos de poca carga (es decir, baja frecuencia de llegada de solicitudes). También se realizó un análisis del efecto de la dimensionalidad del espacio en la eficacia de los métodos. Como cabía esperar, a mayor dimensionalidad, más complicado es reducir el número de comparaciones y, por consiguiente, el método exhaustivo se postula como una buena alternativa en términos de rendimiento. [ABSTRACT] This work was devoted to propose and implement algorithms using GPUs to solve queries in metric spaces. We have selected several well known indexes from the literature that solve queries efficiently in metric spaces in a sequential way. We compared the implementations of those index-based algorithms on GPU against exhaustive search methods. The latter is based in previous work of the area, but we have significantly improved its performance. Performance results are analyzed and discussed to show the paramount importance of bandwidth optimization while coding for GPUs-like parallel platforms. The influence of the space dimensionality leads to the an interesting finding: on lowdimensional spaces, the indexing methods perform better, while in high-dimensional spaces the exhaustive search method takes advantage. Finally, we can conclude that GPUs are a very good target platform for metric space searching algorithms.