ARTICLES

Parallel IDW Algorithm Based on CUDA and Experimental Analysis

Expand
  • School of Environment and Spatial Informatics, China University of Mining and Technology, Xuzhou 221116, China

Received date: 2011-04-19

  Revised date: 2011-09-22

  Online published: 2011-10-25

Abstract

In recent years, spatial data acquisition methods were significantly improved, such as LiDAR, which usually generated hundreds of millions of points. These amounts of datasets create great challenges to computation capacity of computers. In the past several years, the computing capacity of graphical processing unit (GPU) has improved significantly, too. General-purpose computing on GPUs has come into notice. GPUs are an aggregation of streaming processors. The amount of streaming processors in latest device exceeds 240. The peak floating-point operations per second of CPUs are ten times slower than that of GPUs now. A new software platform, called Computer Unified Device Architecture (CUDA), allows GPU programs to be developed in ANSI C. Parallel parts are worked on GPUs based on kernels, which are invoked by the CPU. Each kernel works on a grid of blocks, and each block is an array of threads. In the application process, each block is mapped to a multiprocessor, and each thread is mapped to a streaming processor. A typical CUDA program follows the flows as follow. First, the host function begins by locating one or more buffers in the GPU global memory and conveys the data to them. Then the CUDA program is started more times by appointing the number of threads per block. Finally, the results are transformed back to CPU memory. GPUs have been applied to solve many problems in signal processing, computational geometry and so forth. However, little has been used in spatial interpolation. CUDA Inverse-distance weighting (IDW) algorithm is the most frequently used model in spatial interpolation because it is relatively easy to compute. However, when dimensions increase, obtaining fast running time remains important. In this study, we explore the parallel algorithm for IDW, using the CUDA developed by NVIDIA. The main objective is to compare running times using CPUs versus GPUs under the same conditions. The numerical experiments show that processing speed of CUDA-based algorithm is 6 times faster than that of CPU-based method.

Cite this article

LIU Eryong, WANG Yunjia . Parallel IDW Algorithm Based on CUDA and Experimental Analysis[J]. Journal of Geo-information Science, 2011 , 13(5) : 707 -710 . DOI: 10.3724/SP.J.1047.2011.00709

References

[1] Lu G Y, Wong D W. An Adaptive Inverse-distance Weighting Spatial Interpolation Technique[J].Computer & Geoscience,2008,34:1044-1055.

[2] Ortega L, Rueda A. Parallel Drainage Network Computation on CUDA[J]. Computer & Geoscience, 2010,36:171-178.

[3] 肖汉,张祖勋.基于GPGPU的并行影像匹配算法[J].测绘学报,2010,39(1):46-51.

[4] 张舒,褚艳利.GPU高性能运算之CUDA[M].北京:中国水利水电出版社,2009.

[5] 赵元,张新长,康停军.并行蚁群算法及其在区位选址中的应用[J].测绘学报,2010,39(3):322-327.

[6] Guan Xuefeng, Wu Huayi. Leveraging the Power of Multi-core Platforms for Large-scale Geospatial Data Processing: Exemplified by Generating DEM from Massive LIDAR Point Clouds[J]. Computer & Geoscience,2010,36:1276-1282.

[7] NVIDIA. NVIDIA CUDA 编程指南 . http://www.nvidia.com/object/cuda_home_new.html.

[8] 黄先锋,程晓光,张帆,龚健雅.基于边长比约束的离散点准确边界追踪算法[J].武汉大学学报. 信息科学版,2009,34(6):688-691.

[9] 程林,王美玲,张毅. 一种基于SuperMap GIS的改进Dijkstra算法[J].地球信息科学学报, 2010,12(5): 649-654.

[10] 陈冬平,陈莹,陈兴伟. 以DEM提取流域水系河源的最小误差分析[J].地球信息科学学报,2011,13(2):240-244.

[11] 马建超,林广发,陈友飞,陈俊明. DEM栅格单元异质性对地形湿度指数提取的影响分析[J].地球信息科学学报,2011,13(2):157-163.
Outlines

/