Research On GPU-based Parallel Vector Data Analysis And Index Technology

Vector data is one of the basic data structures in GIS and has severaladvantages compared to raster data, such as small-scale storage,high-resolution graphics display, being conducive to topological relationshipanalysis etc. However, because the data structure is more complex, themethods of parallel operations for accessing and processing are more difficultto study. Particularly there is a big difference between unstructured vector dataand array data structure used in GPU. It may be difficult to utilize the highparallelism of the many-core GPU. Therefore, in this paper we systematicallystudy the GPU-based vector operation methods for accessing data,programming architecture, data structures, effective parallel spatial analysisalgorithms, spatial indexes etc.In order to adapt to GPUs that do not allow dynamic memory allocationfrom kernels, relying on a bus of limited bandwidth to transfer data from andto the CPU, in this paper we present our design and implementation of aframework for parallel vector computing for CSV files. Themain steps include pre-processing for spatial data on CPU, allocating the GPUmemory based on the size of spatial geometry object, and coping to the GPUmemory one by one.The system is designed with four layers from bottom up, including thestorage, spatial primitives, accessing methods and spatial relationshipoperators. This layered design has high exibility. When a layer is modiêed,the implementation of the other layers requires little modiêcation. The degreeof coupling between modules is low. Based on the analysis of the parallelism on spatial data sort, spatialrelationship analysis etc., we give novel data structures and relative algorithms.The classical algorithms of overlay analysis and static R-tree index will beused as illustrations. In order to improve the performance of the new methodsand to offer reference for other parallel analysis methods, strategies formaximizing parallel execution and optimizing memory utilization are adopted.Experiment results show that our GPU-based algorithms are faster than theirCPU-based counterparts in general computing environment.