Este trabajo presenta el diseño e implementación de una versión paralela del algoritmo DBSCAN dentro del paradigma SIMT, orientada a la identificación y clasificación de agregados en conjuntos de datos. El objetivo principal es acelerar las fases más costosas del algoritmo aprovechando el modelo de ejecución de GPU. En una primera fase se desarrolla una versión secuencial de referencia en Python, seguida de una versión optimizada (vectorizada) en CPU mediante Numba, y finalmente una versión paralela en GPU complementada con una optimización adicional en C para mejorar el rendimiento en la fase de propagación del agregado.
El código incluye además un módulo de extracción de características morfológicas que describe cada agregado identificado, proporcionando diversas métricas, tales como centros geométricos, tamaños y factores de forma elementales. La validación se realiza utilizando tanto datos e imágenes de agregados generados mediante simulaciones de dinámica molecular, así como tratando imágenes fotográficas de muestras biológicas. En ese proceso se evalúa la precisión en la detección de agregados y la coherencia de las propiedades extraídas. Los resultados muestran mejoras significativas en el tiempo de ejecución respecto al algoritmo secuencial de referencia, y a la versión mejorada con Numba.
Asimismo, se analiza el consumo energético de cada implementación, mostrando que la reducción del tiempo en GPU se traduce en un menor consumo compensando el mayor gasto energético de GPU frente a CPU. El trabajo concluye con un análisis de las limitaciones detectadas, así como con propuestas de mejora que incluyen la incorporación de técnicas de preprocesado de imágenes, el uso de modelos basados en redes neuronales para una identificación más robusta y la integración de estructuras espaciales como linked cells para mejorar la escalabilidad.
ABSTRACT
This paper presents the design and implementation of a parallel version of the DBSCAN algorithm within the SIMT paradigm, aimed at identifying and classifying clusters in datasets. The main objective is to accelerate the most costly phases of the algorithm by leveraging the GPU execution model. In the first phase, a sequential reference version is developed in Python, followed by an optimised (vectorised) version on CPU using Numba, and finally a parallel version on GPU complemented with additional optimisation in C to improve performance in the cluster propagation phase.
The code also includes a morphological feature extraction module that describes each identified aggregate, providing various metrics such as geometric centres, sizes, and elementary shape factors. Validation is performed using both data and images of aggregates generated by molecular dynamics simulations and by processing photographic images of biological samples. This process evaluates the accuracy of aggregate detection and the consistency of the extracted properties. The results show significant improvements in execution time compared to the sequential reference algorithm and the version enhanced with Numba.
The energy consumption of each implementation is also analysed, showing that the reduction in GPU time translates into lower consumption, offsetting the higher energy consumption of the GPU compared to the CPU. The work concludes with an analysis of the limitations detected, as well as proposals for improvement that include the incorporation of image pre-processing techniques, the use of neural network-based models for more robust identification, and the integration of spatial structures such as linked cells to improve scalability.
Este trabajo presenta el diseño e implementación de una versión paralela del algoritmo DBSCAN dentro del paradigma SIMT, orientada a la identificación y clasificación de agregados en conjuntos de datos. El objetivo principal es acelerar las fases más costosas del algoritmo aprovechando el modelo de ejecución de GPU. En una primera fase se desarrolla una versión secuencial de referencia en Python, seguida de una versión optimizada (vectorizada) en CPU mediante Numba, y finalmente una versión paralela en GPU complementada con una optimización adicional en C para mejorar el rendimiento en la fase de propagación del agregado.
El código incluye además un módulo de extracción de características morfológicas que describe cada agregado identificado, proporcionando diversas métricas, tales como centros geométricos, tamaños y factores de forma elementales. La validación se realiza utilizando tanto datos e imágenes de agregados generados mediante simulaciones de dinámica molecular, así como tratando imágenes fotográficas de muestras biológicas. En ese proceso se evalúa la precisión en la detección de agregados y la coherencia de las propiedades extraídas. Los resultados muestran mejoras significativas en el tiempo de ejecución respecto al algoritmo secuencial de referencia, y a la versión mejorada con Numba.
Asimismo, se analiza el consumo energético de cada implementación, mostrando que la reducción del tiempo en GPU se traduce en un menor consumo compensando el mayor gasto energético de GPU frente a CPU. El trabajo concluye con un análisis de las limitaciones detectadas, así como con propuestas de mejora que incluyen la incorporación de técnicas de preprocesado de imágenes, el uso de modelos basados en redes neuronales para una identificación más robusta y la integración de estructuras espaciales como linked cells para mejorar la escalabilidad.
ABSTRACT
This paper presents the design and implementation of a parallel version of the DBSCAN algorithm within the SIMT paradigm, aimed at identifying and classifying clusters in datasets. The main objective is to accelerate the most costly phases of the algorithm by leveraging the GPU execution model. In the first phase, a sequential reference version is developed in Python, followed by an optimised (vectorised) version on CPU using Numba, and finally a parallel version on GPU complemented with additional optimisation in C to improve performance in the cluster propagation phase.
The code also includes a morphological feature extraction module that describes each identified aggregate, providing various metrics such as geometric centres, sizes, and elementary shape factors. Validation is performed using both data and images of aggregates generated by molecular dynamics simulations and by processing photographic images of biological samples. This process evaluates the accuracy of aggregate detection and the consistency of the extracted properties. The results show significant improvements in execution time compared to the sequential reference algorithm and the version enhanced with Numba.
The energy consumption of each implementation is also analysed, showing that the reduction in GPU time translates into lower consumption, offsetting the higher energy consumption of the GPU compared to the CPU. The work concludes with an analysis of the limitations detected, as well as proposals for improvement that include the incorporation of image pre-processing techniques, the use of neural network-based models for more robust identification, and the integration of spatial structures such as linked cells to improve scalability. Read More
Related posts:
Plotting a path forward with VMware version 7
Algoritmos de Estimaciones de Distribuciones Aplicados al Algoritmo Iterative Proportional Fitting
Comparativa del rendimiento de una GPU usando OpenMP, OpenACC CUDA mediante un ejemplo de dinámica molecular
Sistema de detección y seguimiento de objetos con un dron basado en la red Yolo
Improving Converge Detection for Plasma Transport Simulations through Evolutionary Optimization
Recent version of Neptune RAT is spreading, stealing credentials