A Hybrid Parallel Spatial Interpolation Algorithm for Massive LiDAR Point Clouds on Heterogeneous CPU-GPU Systems
Nowadays, heterogeneous CPU-GPU systems have become ubiquitous, but current parallel spatial interpolation (SI) algorithms exploit only one type of processing unit, and thus result in a waste of parallel resources. To address this problem, a hybrid parallel SI algorithm based on a thin plate spline...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2017-11-01
|
| Series: | ISPRS International Journal of Geo-Information |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2220-9964/6/11/363 |
| _version_ | 1828731894439608320 |
|---|---|
| author | Hongyan Wang Xuefeng Guan Huayi Wu |
| author_facet | Hongyan Wang Xuefeng Guan Huayi Wu |
| author_sort | Hongyan Wang |
| collection | DOAJ |
| description | Nowadays, heterogeneous CPU-GPU systems have become ubiquitous, but current parallel spatial interpolation (SI) algorithms exploit only one type of processing unit, and thus result in a waste of parallel resources. To address this problem, a hybrid parallel SI algorithm based on a thin plate spline is proposed to integrate both the CPU and GPU to further accelerate the processing of massive LiDAR point clouds. A simple yet powerful parallel framework is designed to enable simultaneous CPU-GPU interpolation, and a fast online training method is then presented to estimate the optimal decomposition granularity so that both types of processing units can run at maximum speed. Based on the optimal granularity, massive point clouds are continuously partitioned into a collection of discrete blocks in a data processing flow. A heterogeneous dynamic scheduler based on the greedy policy is also proposed to achieve better workload balancing. Experimental results demonstrate that the computing power of the CPU and GPU is fully utilized under conditions of optimal granularity, and the hybrid parallel SI algorithm achieves a significant performance boost when compared with the CPU-only and GPU-only algorithms. For example, the hybrid algorithm achieved a speedup of 20.2 on one of the experimental point clouds, while the corresponding speedups of using a CPU or a GPU alone were 8.7 and 12.6, respectively. The interpolation time was reduced by about 12% when using the proposed scheduler, in comparison with other common scheduling strategies. |
| first_indexed | 2024-04-12T17:53:02Z |
| format | Article |
| id | doaj.art-b2331ff2225f42e88ed8a59bc52076c7 |
| institution | Directory Open Access Journal |
| issn | 2220-9964 |
| language | English |
| last_indexed | 2024-04-12T17:53:02Z |
| publishDate | 2017-11-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | ISPRS International Journal of Geo-Information |
| spelling | doaj.art-b2331ff2225f42e88ed8a59bc52076c72022-12-22T03:22:27ZengMDPI AGISPRS International Journal of Geo-Information2220-99642017-11-0161136310.3390/ijgi6110363ijgi6110363A Hybrid Parallel Spatial Interpolation Algorithm for Massive LiDAR Point Clouds on Heterogeneous CPU-GPU SystemsHongyan Wang0Xuefeng Guan1Huayi Wu2The State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, 129 Luoyu Road, Wuhan 430079, ChinaThe State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, 129 Luoyu Road, Wuhan 430079, ChinaThe State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, 129 Luoyu Road, Wuhan 430079, ChinaNowadays, heterogeneous CPU-GPU systems have become ubiquitous, but current parallel spatial interpolation (SI) algorithms exploit only one type of processing unit, and thus result in a waste of parallel resources. To address this problem, a hybrid parallel SI algorithm based on a thin plate spline is proposed to integrate both the CPU and GPU to further accelerate the processing of massive LiDAR point clouds. A simple yet powerful parallel framework is designed to enable simultaneous CPU-GPU interpolation, and a fast online training method is then presented to estimate the optimal decomposition granularity so that both types of processing units can run at maximum speed. Based on the optimal granularity, massive point clouds are continuously partitioned into a collection of discrete blocks in a data processing flow. A heterogeneous dynamic scheduler based on the greedy policy is also proposed to achieve better workload balancing. Experimental results demonstrate that the computing power of the CPU and GPU is fully utilized under conditions of optimal granularity, and the hybrid parallel SI algorithm achieves a significant performance boost when compared with the CPU-only and GPU-only algorithms. For example, the hybrid algorithm achieved a speedup of 20.2 on one of the experimental point clouds, while the corresponding speedups of using a CPU or a GPU alone were 8.7 and 12.6, respectively. The interpolation time was reduced by about 12% when using the proposed scheduler, in comparison with other common scheduling strategies.https://www.mdpi.com/2220-9964/6/11/363CPU-GPUhybrid parallel algorithmspatial interpolationthin plate splineLiDAR point clouds |
| spellingShingle | Hongyan Wang Xuefeng Guan Huayi Wu A Hybrid Parallel Spatial Interpolation Algorithm for Massive LiDAR Point Clouds on Heterogeneous CPU-GPU Systems ISPRS International Journal of Geo-Information CPU-GPU hybrid parallel algorithm spatial interpolation thin plate spline LiDAR point clouds |
| title | A Hybrid Parallel Spatial Interpolation Algorithm for Massive LiDAR Point Clouds on Heterogeneous CPU-GPU Systems |
| title_full | A Hybrid Parallel Spatial Interpolation Algorithm for Massive LiDAR Point Clouds on Heterogeneous CPU-GPU Systems |
| title_fullStr | A Hybrid Parallel Spatial Interpolation Algorithm for Massive LiDAR Point Clouds on Heterogeneous CPU-GPU Systems |
| title_full_unstemmed | A Hybrid Parallel Spatial Interpolation Algorithm for Massive LiDAR Point Clouds on Heterogeneous CPU-GPU Systems |
| title_short | A Hybrid Parallel Spatial Interpolation Algorithm for Massive LiDAR Point Clouds on Heterogeneous CPU-GPU Systems |
| title_sort | hybrid parallel spatial interpolation algorithm for massive lidar point clouds on heterogeneous cpu gpu systems |
| topic | CPU-GPU hybrid parallel algorithm spatial interpolation thin plate spline LiDAR point clouds |
| url | https://www.mdpi.com/2220-9964/6/11/363 |
| work_keys_str_mv | AT hongyanwang ahybridparallelspatialinterpolationalgorithmformassivelidarpointcloudsonheterogeneouscpugpusystems AT xuefengguan ahybridparallelspatialinterpolationalgorithmformassivelidarpointcloudsonheterogeneouscpugpusystems AT huayiwu ahybridparallelspatialinterpolationalgorithmformassivelidarpointcloudsonheterogeneouscpugpusystems AT hongyanwang hybridparallelspatialinterpolationalgorithmformassivelidarpointcloudsonheterogeneouscpugpusystems AT xuefengguan hybridparallelspatialinterpolationalgorithmformassivelidarpointcloudsonheterogeneouscpugpusystems AT huayiwu hybridparallelspatialinterpolationalgorithmformassivelidarpointcloudsonheterogeneouscpugpusystems |