图形处理器空间插值并行算法的实现

空间插值是地理信息系统(GIS)空间分析中计算复杂且耗时的操作,因此无法满足实时性的要求。随着图形处理器(GPU)浮点计算能力的大幅提高,GPU通用计算已成为处理GIS领域内复杂计算的研究热点。为实时化一些传统低效的算法提供了良好的契机。利用GPU在并行计算上的优势,将反距离加权法插值算法映射到了统一计算设备架构(CUDA)并行编程架构。首先在GPU中建立二级索引使计算层次得到了合理的划分,然后利用多线程分块策略执行并行插值计算。最后通过实验表明,该方法的插值误差与CPU方法相比能控制在10-6数量级,并且在插值半径较大插值数据较多的情况下,该算法可达到40倍以上的加速比。充分证明了该方法的正确性及高效性。

Realization of GPU parallel spatial interpolation method

Interpolation is one computational complex and time-consuming operation in the fields of spatial analysis that can not meet the real time demand. With the rapid increase of GPU floating-point computing power, general-purpose computation on graphics processors (GPGPU) has became an evolving research field in spatial information processing, and it provides an opportunity to accelerate some traditional inefficient algorithms. In this paper, we map the inverse distance weighted (IDW) interpolation method to the compute unified device architecture (CUDA) parallel programming model. Taking the advantage of graphics processing unit (GPU) parallel computing, we build two-level indexes on GPU, then blocking schemes are used to assign computing task among different threads. After illustrating the parallel interpolation process, we conduct several experiments, The experiment result shows that the error of this new method can control under 10^-6 compared with CPU-based method. With larger influence radius and massive data, the performance can obtain above 40 times speedups over a very similar single-threaded CPU implementation. It is demonstrated the correctness and high efficiency of our optimized implementation.