Similar articles

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.

[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.