Full Text:   <4423>

CLC number: TP391

On-line Access: 2011-11-30

Received: 2011-03-02

Revision Accepted: 2011-06-30

Crosschecked: 2011-11-04

Cited: 24

Clicked: 6726

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE C 2011 Vol.12 No.12 P.990-999

http://doi.org/10.1631/jzus.C1100051


Accelerating geospatial analysis on GPUs using CUDA


Author(s):  Ying-jie Xia, Li Kuang, Xiu-mei Li

Affiliation(s):  Hangzhou Institute of Service Engineering, Hangzhou Normal University, Hangzhou 310012, China, Department of Automation, School of Electronic Information and Electrical Engineering, Shanghai Jiao Tong University, Shanghai 200240, China, Provincial Key Laboratory for Computer Information Processing Technology, Soochow University, Soochow 215006, China

Corresponding email(s):   xiayingjie@zju.edu.cn

Key Words:  General purpose GPU, CUDA, Geospatial analysis, Parallelization


Ying-jie Xia, Li Kuang, Xiu-mei Li. Accelerating geospatial analysis on GPUs using CUDA[J]. Journal of Zhejiang University Science C, 2011, 12(12): 990-999.

@article{title="Accelerating geospatial analysis on GPUs using CUDA",
author="Ying-jie Xia, Li Kuang, Xiu-mei Li",
journal="Journal of Zhejiang University Science C",
volume="12",
number="12",
pages="990-999",
year="2011",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.C1100051"
}

%0 Journal Article
%T Accelerating geospatial analysis on GPUs using CUDA
%A Ying-jie Xia
%A Li Kuang
%A Xiu-mei Li
%J Journal of Zhejiang University SCIENCE C
%V 12
%N 12
%P 990-999
%@ 1869-1951
%D 2011
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.C1100051

TY - JOUR
T1 - Accelerating geospatial analysis on GPUs using CUDA
A1 - Ying-jie Xia
A1 - Li Kuang
A1 - Xiu-mei Li
J0 - Journal of Zhejiang University Science C
VL - 12
IS - 12
SP - 990
EP - 999
%@ 1869-1951
Y1 - 2011
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.C1100051


Abstract: 
Inverse distance weighting (IDW) interpolation and viewshed are two popular algorithms for geospatial analysis. IDW interpolation assigns geographical values to unknown spatial points using values from a usually scattered set of known points, and viewshed identifies the cells in a spatial raster that can be seen by observers. Although the implementations of both algorithms are available for different scales of input data, the computation for a large-scale domain requires a mass amount of cycles, which limits their usage. Due to the growing popularity of the graphics processing unit (GPU) for general purpose applications, we aim to accelerate geospatial analysis via a GPU based parallel computing approach. In this paper, we propose a generic methodological framework for geospatial analysis based on GPU and its programming model Compute Unified Device Architecture (CUDA), and explore how to map the inherent parallelism degrees of IDW interpolation and viewshed to the framework, which gives rise to a high computational throughput. The CUDA-based implementations of IDW interpolation and viewshed indicate that the architecture of GPU is suitable for parallelizing the algorithms of geospatial analysis. Experimental results show that the CUDA-based implementations running on GPU can lead to dataset dependent speedups in the range of 13–33-fold for IDW interpolation and 28–925-fold for viewshed analysis. Their computation time can be reduced by an order of magnitude compared to classical sequential versions, without losing the accuracy of interpolation and visibility judgment.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

[1]AMD, 2010. ATI Stream Computing OpenCL Programming Guide. Available from http://developer.amd.com/gpu_assets/ATI_Stream_SDK_OpenCL_Programming_Guide.pdf [Accessed on Feb. 18, 2011].

[2]Blelloch, G., 1990. Vector Models for Data-Parallel Computing. MIT Press, Cambridge, MA.

[3]Clarke, K.C., 1995. Analytical and Computer Cartography (2nd Ed.). Prentice-Hall, Englewood Cliffs, NJ.

[4]Densham, P.J., Armstrong, M.P., 1998. Spatial Analysis. In: Healey, R.G., Dowers, S., Gittings, B.M., et al. (Eds.), Parallel Processing Algorithms for GIS. Taylor and Francis, London, p.387-413.

[5]ESRI, 2009. ArcGIS Desktop Help. Available from http://webhelp.esri.com/arcgisdesktop/9.3/index.cfmTopicName=Performing_a_ viewshed_analysis [Accessed on Feb. 18, 2011].

[6]Finkel, R., Bentley, J.L., 1974. Quad Trees: a data structure for retrieval on composite keys. Acta Inform., 4(1):1-9.

[7]Gaede, V., Guenther, O., 1998. Multidimensional access methods. ACM Comput. Surv., 30(2):170-231.

[8]Guan, X., Wu, H., 2009. Parallel optimization of IDW interpolation algorithm on multicore platform. SPIE, 7146:71461Y-71461Y-9.

[9]Kidner, D.B., Sparkes, A.J., Dorey, M.I., Mark Ware, J., Jones, C.B., 2002. Visibility analysis with the multiscale implicit TIN. Trans. GIS, 5(1):19-37.

[10]Micikevicius, P., 2009. 3D Finite Difference Computation on GPUs Using CUDA. Proc. 2nd Workshop on General Purpose Processing on Graphics Processing Units, p.79-84.

[11]Mineter, M., Dowers, S., Caldwell, D., Gittings, B., 2003. High-Throughput Computing to Enhance Intervisibility Analysis. 7th Int. Conf. on GeoComputation, p.1-10.

[12]Nickolls, J., Buck, I., Garland, M., Skadron, K., 2008. Scalable parallel programming with CUDA. Queue, 6(2):40-53.

[13]NVIDIA, 2010. NVIDIA CUDA C Programming Guide, Version 3.1. Available from http://developer.download.nvidia.com/compute/cuda/3_1/toolkit/docs/NVIDIA_CUDA_C_ ProgrammingGuide_3.1.pdf [Accessed on Feb. 18, 2011].

[14]Papari, G., Petkov, N., 2009. Reduced Inverse Distance Weighting Interpolation for Painterly Rendering. 13th Int. Conf. on Computer Analysis of Images and Patterns, p.509-516.

[15]Pratas, F., Mata, R., Sousa, L., 2010. Iterative Induced Dipoles Computation for Molecular Mechanics on GPUs. Third ACM Workshop on General Purpose Processing on Graphics Processing Units, p.111-120.

[16]Samet, H., 2006. Foundations of Multidimensional and Metric Data Structures. Morgan-Kaufmann, San Francisco, CA.

[17]Shepard, D., 1968. A Two-Dimensional Interpolation Function for Irregularly-Spaced Data. Proc. 23rd ACM National Conf., p.517.

[18]Tournier, J.C., Naef, M., 2010. Influences of SIMD Architectures for Scattered Data Interpolation Algorithm. 10th IEEE Int. Symp. on Performance Analysis of Systems and Software, p.109-110.

[19]Wang, S., Armstrong, M.P., 2009. A theoretical approach to the use of cyberinfrastructure in geographical analysis. Int. J. Geograph. Inform. Sci., 23(2):169-193.

[20]Ware, J.A., Kidner, D.B., Rallings, P.J., 1998. Parallel Distributed Viewshed Analysis. Proc. 6th ACM Int. Symp. on Advances in Geographic Information Systems, p.151-156.

[21]Xia, Y., Li, Y., Shi, X., 2010a. Parallel Viewshed Analysis on GPU Using CUDA. 3rd IEEE Int. Joint Conf. on Computational Sciences and Optimization, p.373-374.

[22]Xia, Y., Zhu, M., Shi, X., 2010b. A workflow-serialized parallel spatial IDW interpolation on Windows HPC. Appl. Mech. Mater., 20-23:370-375.

[23]Zhou, K., Hou, Q., Wang, R., Guo, B., 2008. Real-time KD-tree construction on graphics hardware. ACM Trans. Graph., 27(5):126.

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - 2022 Journal of Zhejiang University-SCIENCE