Búsqueda por Similitud en Espacios Métricos Sobre Plataformas Multi-Core (CPU y GPU)

Abstract

Este trabajo de tesis está dedicado al estudio de la gestión eficiente de threads en el procesamiento de consultas sobre índices para espacios métricos. Se proponen algoritmos multi-thread eficientes para procesadores multi-core convencionales y para procesadores gráficos GPU. Para procesadores multi-core se concluye que la mejor estrategia es mantener un sólo índice compartido por todos los threads y se propone aplicar una estrategia híbrida de procesamiento de consultas, la cual aplica una estrategia distinta dependiendo del nivel de tráfico de consultas que llegan al procesador. La estrategia propuesta alcanza buen rendimiento para diversos tipos de índices métricos. Para tráfico alto de consultas, la estrategia híbrida aplica un método estándar en el que cada thread se hace cargo de procesar completamente una consulta por vez. Para tráfico bajo de consultas, la estrategia híbrida utiliza varios threads para procesar cada consulta utilizando paralelismo sincrónico por lotes. También se concluye que la estrategia intuitiva de particionar el índice en tantos threads como núcleos tenga el procesador, y asignar un thread a cada partición para ejecutar en ella el algoritmo secuencial, no entrega buenos resultados en comparación a la estrategia híbrida propuesta en este trabajo de tesis. Para procesadores gráficos GPU, fue necesario diseñar tanto una estrategia de distribución del índice en los núcleos como estrategias de procesamiento de consultas que tengan en cuenta el modelo de programación de las GPUs. En este caso, los algoritmos propuestos resultan ser bastante más complejos que los diseñados para procesadores convencionales, pero estos muestran de que es posible alcanzar un rendimiento eficiente y escalable en este hardware. Se observó que sólo los índices métricos que pueden ser representados como matrices permiten alcanzar un buen rendimiento. En particular, un índice basado en clustering de objetos es el que alcanza el mejor rendimiento tanto para consultas por rango como para consultas de vecinos más cercanos.