A Collaborative Parallel Spatial Interpolation Algorithmon Oriented Towards the Heterogeneous CPU/GPU System

Nowadays the heterogeneous CPU/GPU systems become ubiquitous, but most of current parallel spatial interpolation algorithms exploit only one type of computation units to speedup the calculation and thus it results in parallel resources wasted. To address this problem, a collaborative parallel thin plate spline interpolation algorithm is proposed in this paper to accelerate DEM generation from massive LiDAR point clouds. In this collaborative parallel algorithm, the input point clouds are firstly decomposed into a collection of discrete blocks and encapsulated as general task objects to shield the heterogeneous execution models of different processing units. And then a special scheduling algorithm, named Greedy-SET, is also proposed to achieve better load balance based on the computing capabilities of CPU and GPU. Experimental results demonstrate that the proposed collaborative parallel algorithm can achieve the highest speedup times of approximately 19.6. The performance improvement ratios compared with pure CPU and GPU parallel algorithms are 54% and 44% respectively.