The Parallel Computing Research On High-performance Spatial Analysis Under Cpu/Gpu Heterogeneous Environment

Spatial analysis is the core content of the geographic information system (GIS). As spatial analysis is applied to solve a variety of practical problems with time span and spatial span, its computational complexity is on the increase, the traditional computing model and algorithms which rely solely on the CPU have been difficult to meet the needs of rapid spatial data processing.The modern GPU have strong parallel computing power, how to use the powerful GPU parallel processing capability to solve the complex scientific computing problem has become a hot research topic. Aiming at the needs of real-time processing of spatial analysis, in this paper, a solution of taking use of the GPU’s large parallel computing capabilities and programmable to accelerate spatial analysis processing was proposed, and a synergistic parallel computing model was designed which uses CPU as the main processor and GPU as the coprocessor. Then, based on this computational model, several GPU parallel algorithms such as shortest path analysis algorithms, topological analysis algorithms, and spatial interpolation algorithms were designed and realized. Hence, the universal laws of spatial analysis processing based CPU/GPU hybrid computing environments were got, including data organization, data decomposition, task scheduling and thread mapping, etc. Finally, the ways of parallel algorithm performance optimization based on GPU architecture were discussed. Based on the completion of this study, there will be a useful computational technical support for the new high-performance GIS which take computing as core and spatial analysis and decision support as target. The main work of this paper can be summarized as the following:(1)We studied the theory and technology of general purpose parallel computing based on GPU, and discussed the related issue such as the basic mode of the parallel computing task decomposition, the theory and method of parallel programming, and to achieve a form of the hardware platforms of parallel computing implementation, the GPU-based general-purpose computing and CUDA programming mode, especially focus on the technology, methods of CPU/GPU heterogeneous parallel computing. (2)We studied the research situation of the shortest path problem and its description of graph theory. Aiming at the traditional serial algorithm can’t meet the need of the shortest path analysis’s real-time processing, we proposed a GPU-accelerated Floyd parallel algorithms for the shortest path problem and gave the design and implementation process. The experimental results show that the algorithm has a better Computational efficiency, and can greatly improve the processing of the shortest path analysis, and can significantly reduce the computation time.(3)We studied the research status and its main technical analysis of spatial interpolation. In view of the traditional bilinear interpolation algorithm can’t meet the need of the massive data real-time processing, we proposed to use the powerful GPU parallel processing capabilities to speed up its processing, and give the parallel algorithm process flow. The experimental results show that the parallel algorithm can effectively use of the powerful GPU parallel computing power, and it is able to meet the needs of real-time processing of large-scale data spatial interpolation.(4)We discussed the research status, development trends and the major type of topological relations. Through the studied, we conclude that the calculation of the relationship between the line/line topology is the key to the entire spatial topological relations. Then, according to the characteristics of the line/line topology relationship, we proposed a GPU-accelerated detection algorithm for the line/line topological relationships based on the line segment intersection. Applying the parallel detection algorithm to a space conflict detection experiment between the water lines, the result show that this parallel algorithm can meet the requirements of the line/line topology relationship detection, and can effectively accelerate the topology relationship calculation process.(5)In view of the computing power’s limited of the single node, and it is unable to meet the demand of the real-time processing of data-massive, model-complicated spatial analysis, We proposed to use CPU/GPU heterogeneous computer cluster to accelerate, and gave a distributed parallel computing model which combines the MPI and CUDA programming model. Based on this hybrid programming model, we designed and realized the shortest path analysis parallel algorithm and the bilinear spatial interpolation parallel algorithm. The experimental results show that the hybrid programming model can provide cluster-level and node-level two parallel strategies, and it can make full use of the advantages of MPI and CUDA model. It can improve the overall computing performance of the system and has a good speedup, reliability and scalability, and can provide a useful computing technology support for distributed spatial analysis applications.