Optimización paralela basada en CUDA del proceso de cálculo de intersecciones en el algoritmo de Greiner-Hormann
Autores: Zuo, Jiwei; Fan, Junfu; Li, Kuan; Liu, Qingyun; Zhou, Yuke; Zhang, Yi
Idioma: Inglés
Editor: MDPI
Año: 2025
Acceso abierto
Artículo científico
2025
Optimización paralela basada en CUDA del proceso de cálculo de intersecciones en el algoritmo de Greiner-Hormann
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Algoritmo
Intersección
Paralelo
Greiner-Hormann
Polígono
Eficiencia
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 70
Citaciones: Sin citaciones
El algoritmo de superposición de polígonos de Greiner-Hormann es un algoritmo comúnmente utilizado para análisis de superposición. Utiliza una estructura de lista doblemente enlazada para almacenar datos de vértices, y su paso de cálculo de intersección tiene un efecto significativo en la eficiencia operativa general del algoritmo. Para abordar el proceso de cálculo de intersección que consume tiempo en el algoritmo de Greiner-Hormann, este artículo presenta dos funciones núcleo que implementan un algoritmo de mejora paralela basado en CUDA multi-hilos. Este método asigna un hilo a cada borde del polígono sujeto, determina de manera paralela si se intersecta con cada borde del polígono de recorte, transfiere el número de puntos de intersección de vuelta a la CPU para el cálculo, y abre espacio de almacenamiento correspondiente en el lado de la GPU en base al número total de puntos de intersección; luego, la información como las coordenadas de intersección se calcula de forma paralela. Además, se realizan experimentos en los datos de ocho polígonos con diferentes complejidades, y se analizan estadísticamente el modo de hilo óptimo, el tiempo de ejecución y la relación de aceleración del algoritmo paralelo. Los resultados experimentales muestran que cuando un solo bloque de hilo de CUDA contiene 64 hilos o 128 hilos, el paso de transformación paralela del algoritmo de Greiner-Hormann tiene la mayor eficiencia computacional. Cuando la complejidad del polígono sujeto supera los 53,000, el algoritmo de mejora paralela puede obtener una relación de aceleración de aproximadamente tres veces la del algoritmo en serie. Esto muestra que el método de diseño en este artículo puede mejorar efectivamente la eficiencia operativa del algoritmo de análisis de superposición de polígonos en el contexto actual de datos a gran escala.
Descripción
El algoritmo de superposición de polígonos de Greiner-Hormann es un algoritmo comúnmente utilizado para análisis de superposición. Utiliza una estructura de lista doblemente enlazada para almacenar datos de vértices, y su paso de cálculo de intersección tiene un efecto significativo en la eficiencia operativa general del algoritmo. Para abordar el proceso de cálculo de intersección que consume tiempo en el algoritmo de Greiner-Hormann, este artículo presenta dos funciones núcleo que implementan un algoritmo de mejora paralela basado en CUDA multi-hilos. Este método asigna un hilo a cada borde del polígono sujeto, determina de manera paralela si se intersecta con cada borde del polígono de recorte, transfiere el número de puntos de intersección de vuelta a la CPU para el cálculo, y abre espacio de almacenamiento correspondiente en el lado de la GPU en base al número total de puntos de intersección; luego, la información como las coordenadas de intersección se calcula de forma paralela. Además, se realizan experimentos en los datos de ocho polígonos con diferentes complejidades, y se analizan estadísticamente el modo de hilo óptimo, el tiempo de ejecución y la relación de aceleración del algoritmo paralelo. Los resultados experimentales muestran que cuando un solo bloque de hilo de CUDA contiene 64 hilos o 128 hilos, el paso de transformación paralela del algoritmo de Greiner-Hormann tiene la mayor eficiencia computacional. Cuando la complejidad del polígono sujeto supera los 53,000, el algoritmo de mejora paralela puede obtener una relación de aceleración de aproximadamente tres veces la del algoritmo en serie. Esto muestra que el método de diseño en este artículo puede mejorar efectivamente la eficiencia operativa del algoritmo de análisis de superposición de polígonos en el contexto actual de datos a gran escala.