GPU/CUDA-Based parallelization of the ECSAGO evolutionary algorithm

Abstract

El crecimiento exponencial de los volúmenes de datos y de la complejidad computacional ha generado grandes desafíos para los algoritmos de clustering tradicionales al procesar conjuntos de datos de gran escala y alta dimensionalidad. Este trabajo presenta el diseño e implementación de una versión paralela del algoritmo Evolutionary Clustering with Self-Adaptive Genetic Operators (ECSAGO), acelerada con GPU mediante CUDA, con el objetivo de superar las limitaciones de escalabilidad sin perder las capacidades de autoadaptación del algoritmo. La implementación se basa en un modelo maestro–esclavo que distribuye las tareas entre la CPU y la GPU: la CPU gestiona la lógica evolutiva, mientras que la GPU se encarga de la evaluación de aptitud, altamente demandante en cómputo, mediante kernels CUDA especializados. Los experimentos, realizados con conjuntos de datos sintéticos y reales, muestran que la aceleración con GPU depende en gran medida de la densidad computacional, alcanzando mejoras de hasta 9.6× en problemas de alta dimensionalidad y estableciendo un umbral práctico cercano a 500.000 para obtener beneficios claros. La versión paralela mantiene la calidad del agrupamiento en todas las pruebas, con puntuaciones de silueta comparables a las de la versión secuencial y, en algunos casos, con una exploración mejorada en escenarios complejos. En conjunto, este trabajo convierte a ECSAGO en una alternativa viable para aplicaciones de agrupamiento a gran escala en entornos intensivos en datos y ofrece orientaciones prácticas para profesionales que buscan aprovechar la aceleración con GPU. (Texto tomado de la fuente)

The exponential growth of data volumes and computational complexity has created substantial challenges for traditional clustering algorithms when processing large-scale, high-dimensional datasets. This work presents the design and implementation of a GPU-accelerated parallel version of the Evolutionary Clustering with Self-Adaptive Genetic Operators (ECSAGO) algorithm using CUDA, addressing fundamental scalability limitations while preserving the algorithm's sophisticated self-adaptive capabilities. The implementation employs a master-slave architectural model that strategically distributes computational responsibilities between CPU and GPU components, with the CPU managing evolutionary control logic and the GPU executing computationally intensive fitness evaluation through specialized CUDA kernels. Comprehensive experimental evaluation across synthetic and real-world datasets demonstrates that GPU acceleration effectiveness correlates strongly with computational density, achieving substantial speedup improvements of up to 9.6× for high-dimensional problems while establishing a clear computational density threshold of approximately 500.000 for beneficial acceleration. The parallel implementation successfully preserves clustering quality across all experimental conditions, with silhouette scores remaining within acceptable bounds of sequential counterparts and evidence of enhanced exploration capabilities in complex datasets. This work transforms ECSAGO into a viable solution for large-scale, high-dimensional clustering applications in contemporary data-intensive domains while providing practical guidelines for practitioners regarding GPU acceleration deployment decisions.