Desarrollo de una aplicación paralela para construcción de grafos de vecindad relativa en GPUs y OpenMP

Abstract

[Resumen]: En este trabajo se aborda la construcción eficiente del Grafo de Vecindad Relativa (RNG, por sus siglas en inglés) a partir de un conjunto de puntos en el plano, aprovechando la propiedad geométrica que establece que el RNG es un subgrafo de la Triangulación de Delaunay. A partir de esta relación, se diseña una canalización híbrida CPU–GPU en la que la triangulación se calcula en la CPU, mientras que la fase de validación de aristas se acelera en la GPU mediante código CUDA. El objetivo principal es reducir el coste computacional asociado a la construcción directa del RNG y analizar el impacto del paralelismo heterogéneo en términos de rendimiento, escalabilidad y uso de recursos. Para ello, se implementan distintas estrategias de paralelización y gestión de memoria y se evalúa su comportamiento sobre diferentes tamaños de problema. Los resultados experimentales muestran mejoras significativas de tiempo de ejecución frente a la ejecución puramente en CPU, especialmente en escenarios de alta densidad de puntos. Asimismo, se identifican los principales cuellos de botella del proceso y se discuten posibles líneas de optimización futura.[Abstract]: This work addresses the efficient construction of the Relative Neighborhood Graph (RNG) from a set of planar points by exploiting the geometric property that the RNG is a subgraph of the Delaunay Triangulation. Based on this relationship, we design a hybrid CPU–GPU pipeline in which the triangulation is computed on the CPU, while the edge-validation stage is accelerated on the GPU using CUDA. The main goal is to reduce the computational cost of direct RNG construction and to analyze the impact of heterogeneous parallelism in terms of performance, scalability, and resource utilization. Several parallelization and memory-management strategies are implemented and evaluated across different problem sizes. Experimental results demonstrate significant execution-time improvements compared to CPU-only execution, particularly for large and dense point sets. In addition, the main bottlenecks of the pipeline are identified, and potential directions for further optimization are discussed.