The Ordinary Kriging (OK) algorithm is an important method used in geostatistics applications for data interpolation usually based on field measurements of a variable of interest. The OK algorithm is used to estimate the value of a variable based on the variance of previous measurements. The OK algorithm has applications in areas such as environmental science, hydrogeology, mining, weather prediction and remote sensing. However, the OK algorithm is many times not suitable for large volumes of data due to its computational cost. In this work we present a study of a parallel implementation of the OK algorithm that takes advantage of heterogeneous computing environments through the usage of the Open Computing Language (OpenCL) framework. We use the OK algorithm to estimate a Digital Terrain Model (DTM) from a point cloud of a mangrove forest obtained via a terrestrial laser 3D scanning device. A downsampling procedure is applied to the raw data in order to extract the points that belong to the ground and then the OK algorithm is applied to obtain the DTM. The objective of our implementation is to effectively use all the computational resources available to accelerate the OK procedure. We show that our implementation can scale across multiple CPUs and GPUs devices and it is able to handle volumes of data that are typically produced by real world field measurements. The interpolation is a crucial step to make predictions of a variable at unknown locations, it is important to use the maximum amount of measurements possible in order to increase the performance of the prediction algorithm. Reducing the time to generate the interpolation model is, therefore, extremely important. We also compare the run times of a reference sequential implementation with our parallel one to show that the usage of parallel programming techniques can accelerate the fundamental steps of many important scientific researches.

kriging, geostatistics, interpolation, GPGPU, parallelization, heterogeneous computing

[1] M. A. Oliver and R. Webster. A tutorial guide to geostatistics: Computing and modelling variograms and kriging. Catena, 113:56–69, 2014.

2] Shengli Tao, Fangfang Wu, Qinghua Guo, Yongcai Wang, Wenkai Li, Baolin Xue, Xueyang Hu, Peng Li, Di Tian, Chao Li, Hui Yao, Yumei Li, Guangcai Xu, and Jingyun Fang. Segmenting tree crowns from terrestrial and mobile LiDAR data by exploring ecological theories. ISPRS Journal of Photogrammetry and Remote Sensing, 110(March 2016):66–76, 2015.

[3] Lluís Pesquer, Ana Cortés, and Xavier Pons. Parallel ordinary kriging interpolation incorporating automatic variogram fitting. Computers and Geosciences, 37(4):464–473, 2011.

[4] A. J Rossini, Luke Tierney, and Na Li. Simple Parallel Statistical Computing in R. Journal of Computational and Graphical Statistics, 16(2):399–420, 2007.

[5] Accelerating geostatistical simulations using graphics processing units (GPU). Computers & Geosciences, 46:51–59, 2012.

[6] Tangpei Cheng. Accelerating universal Kriging interpolation algorithm using CUDA-enabled GPU. Computers and Geosciences, 54:178–183, 2013.

[7] John E Stone, David Gohara, and Guochun Shi. OpenCL: A parallel programming standard for heterogeneous computing systems. Computing in Science and Engineering, 12(3):66–72, 2010.

[8] Bryan Catanzaro. Opencl optimization case study: Simple reductions. http://developer.amd.com/resources/articles-whitepapers/opencloptimization-case-study-simple-reductions, 2010.

[9] Gaël Guennebaud, Benoît Jacob, et al. Eigen v3. http://eigen.tuxfamily.org, 2010.