Implementación paralela de algoritmos de agrupación jerárquica en GPU

Abstract

La clasificación a través del análisis de datos es frecuentemente utilizada para la inferencia de modelos. Sin embargo, los algoritmos de agrupación jerárquica acumulativa son poco utilizados debido a su gran costo computacional. Estos tienen la ventaja de agregar menor distorsión a los resultados, pues no requieren información que restrinja la cantidad o la forma en que se establecen los grupos. Un algoritmo de agrupación jerárquica en particular es hoy utilizado en la inferencia de modelos de tractos neuronales. Grandes cantidades de datos son procesados y el algoritmo se aplica en numerosas ocasiones, esto lo transforma en un factor limitante para la investigación de los modelos. En este trabajo se desarrolla una implementación paralela del algoritmo utilizado en la investigación señalada. Para esto se utiliza CUDA, una plataforma diseñada para utilizar un procesador gráfico en el cómputo algoritmos de propósito general. Los resultados que se han conseguido muestran aceleraciones de hasta 50 veces por sobre la implementación original. Se programó en C una versión secuencial del algoritmo, ésta que consigue acelerar más de 4 veces al algoritmo inicial. La implementación paralela, desarrollada en CUDA, consigue un tiempo de ejecución 13 veces mayor que la versión secuencial.                                                                             