基于GPU的并行矢量数据分析与索引技术研究

发布时间：2018-09-17 12:15

【摘要】：矢量数据作为GIS的基础数据结构之一，与栅格数据相比具有存储量小、图形显示精度高、有利于拓扑关系分析等优点。但由于其数据结构较为复杂，导致面向矢量数据并行化存取与处理的相关操作方法研究较为困难。特别是矢量数据的无结构化特点，与GPU利用数组结构存储数据之间存在较大差异，难以充分发挥GPU众核高度并行执行的优势。因此，本文将系统地研究基于GPU的矢量数据存取操作方法、程序设计架构、数据结构、高效并行空间分析算法以及空间索引等内容。为适应GPU不能利用内核程序动态分配存储空间，只能依赖有限的总线带宽从CPU端发送和接收数据的编程特点，本文以CSV格式文件为例，，设计与实现了面向矢量数据的并行计算框架。主要思想是首先在CPU端对空间数据进行预处理操作，然后根据空间对象的几何坐标大小分配GPU端存储空间，最后以空间对象为单位逐个拷贝至GPU端。本文采用分层设计思想构建基于GPU的空间分析方法，共包含存储、空间算子、存取策略、空间分析操作四部分。该方法具有较好的可扩展性，当某一层发生变化时，其它层仅需较小的修改即可实现，从而降低了各功能模块间耦合度。本文针对空间分析中的空间数据排序、空间关系分析等常见技术，在分析其并行性特点的基础上，结合面向GPU流处理器进行空间数据并行处理问题，以典型的叠加分析、静态R-树空间索引算法为例，提出了新的数据结构以及相关算法。并采用最大化并行执行、优化存储器使用等策略提高空间数据分析性能，力图为其它并行空间分析方法的优化提供借鉴。实验结果表明，与传统的基于CPU的算法相比，在一般的计算环境下基于GPU的算法能够获得较好的加速比。
[Abstract]:Vector data is one of the basic data structures of GIS. Compared with raster data, vector data has the advantages of less storage, higher precision of graphic display and more favorable to the analysis of topological relations. However, due to the complexity of its data structure, it is difficult to study the related operation methods for parallel access and processing of vector data. Especially, the unstructured feature of vector data is different from that of GPU using array structure to store data, so it is difficult to give full play to the advantage of high parallel execution of GPU multi-kernel. Therefore, this paper will systematically study the vector data access operation method based on GPU, programming architecture, data structure, efficient parallel spatial analysis algorithm and spatial index, and so on. In order to adapt to the programming characteristics that GPU can not dynamically allocate storage space by using kernel program, it can only rely on limited bus bandwidth to send and receive data from CPU. This paper takes the CSV format file as an example. A parallel computing framework for vector data is designed and implemented. The main idea is to preprocess the spatial data at the CPU end, then allocate the storage space of the GPU terminal according to the geometric coordinate size of the spatial object, and copy to the GPU terminal one by one with the spatial object as the unit. In this paper, a spatial analysis method based on GPU is constructed with the idea of hierarchical design. It includes four parts: storage, spatial operator, access strategy and spatial analysis operation. The method has good scalability. When one layer changes, other layers can be implemented only with small modifications, thus reducing the degree of coupling among the functional modules. In this paper, based on the analysis of the parallelism of spatial data sequencing and spatial relation analysis, the parallel processing problem of spatial data for GPU stream processor is analyzed, and the typical superposition analysis is used. Static R- tree spatial indexing algorithm is used as an example, and a new data structure and related algorithms are proposed. Strategies such as maximizing parallel execution and optimizing memory usage are adopted to improve the performance of spatial data analysis and to provide reference for the optimization of other parallel spatial analysis methods. The experimental results show that compared with the traditional algorithm based on CPU, the algorithm based on GPU can get a better speedup in general computing environment.
【学位授予单位】：中国科学院研究生院（东北地理与农业生态研究所）
【学位级别】：博士
【学位授予年份】：2014
【分类号】：TP391.41;P208

【参考文献】