Método de Dividir y Conquistar Basado en Grafos para Paralelizar Operaciones Espaciales en Datos Vectoriales
Autores: Kang, Xiaochen; Lin, Xiangguo
Idioma: Inglés
Editor: MDPI
Año: 2014
Acceso abierto
Artículo científico
Categoría
Ciencias Medioambientales
Subcategoría
Ciencia y tecnología de los recursos naturales
Palabras clave
Ciencia de la computación
Análisis de dependencia
Paralelización de operaciones espaciales
Método basado en grafos
Datos vectoriales
Eficiencia computacional
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 7
Citaciones: Sin citaciones
En informática, el análisis de dependencias determina si es seguro o no paralelizar declaraciones en programas. Al tratar con operaciones espaciales intensivas en datos y computacionales en el procesamiento de grandes volúmenes de características geométricas, esta dependencia puede ser bien utilizada para explotar el paralelismo. En este artículo, proponemos un método basado en grafos de dividir y conquistar para paralelizar operaciones espaciales (GDCMPSO) en datos vectoriales. Puede representar las dependencias de datos espaciales en operaciones espaciales al representar las características vectoriales como vértices de un grafo y sus dependencias computacionales como aristas del grafo. De esta manera, las operaciones espaciales pueden ser paralelizadas en tres pasos: particionando el grafo en componentes de grafo con aristas inter-componentes primero, procesando simultáneamente múltiples subtareas indicadas por las componentes del grafo en segundo lugar y finalmente manejando las tareas restantes denotadas por las aristas inter-componentes. Para demostrar cómo funciona, se realizan operaciones de búfer y operaciones de intersección bajo este paradigma. En un entorno de 12 núcleos, ambas operaciones espaciales obtienen mejoras de rendimiento obvias, y las aceleraciones son superiores a ocho. Los resultados de las pruebas sugieren que GDCMPSO contribuye a un método para paralelizar operaciones espaciales y puede mejorar significativamente la eficiencia computacional en arquitecturas de múltiples núcleos.
Descripción
En informática, el análisis de dependencias determina si es seguro o no paralelizar declaraciones en programas. Al tratar con operaciones espaciales intensivas en datos y computacionales en el procesamiento de grandes volúmenes de características geométricas, esta dependencia puede ser bien utilizada para explotar el paralelismo. En este artículo, proponemos un método basado en grafos de dividir y conquistar para paralelizar operaciones espaciales (GDCMPSO) en datos vectoriales. Puede representar las dependencias de datos espaciales en operaciones espaciales al representar las características vectoriales como vértices de un grafo y sus dependencias computacionales como aristas del grafo. De esta manera, las operaciones espaciales pueden ser paralelizadas en tres pasos: particionando el grafo en componentes de grafo con aristas inter-componentes primero, procesando simultáneamente múltiples subtareas indicadas por las componentes del grafo en segundo lugar y finalmente manejando las tareas restantes denotadas por las aristas inter-componentes. Para demostrar cómo funciona, se realizan operaciones de búfer y operaciones de intersección bajo este paradigma. En un entorno de 12 núcleos, ambas operaciones espaciales obtienen mejoras de rendimiento obvias, y las aceleraciones son superiores a ocho. Los resultados de las pruebas sugieren que GDCMPSO contribuye a un método para paralelizar operaciones espaciales y puede mejorar significativamente la eficiencia computacional en arquitecturas de múltiples núcleos.