Next Article in Journal
Analyzing Refugee Migration Patterns Using Geo-tagged Tweets
Previous Article in Journal
On Metrics for Location-Aware Games
Article

A Hybrid Process/Thread Parallel Algorithm for Generating DEM from LiDAR Points

by 1,2, 3, 1,2, 1,2,* and 1,2
1
Qingdao Collaborative Innovation Center of Marine Science and Technology, College of Information Science and Engineering, Ocean University of China, No. 238, Songling Road, Qingdao 266100, China
2
Laboratory for Regional Oceanography and Numerical Modeling, Qingdao National Laboratory for Marine Science and Technology, No. 1, Wenhai Road, Qingdao 266237, China
3
Jiangsu Provincial Key Laboratory of Geographic Information Science and Technology, Nanjing University, No. 163, Xianlin Avenue, Nanjing 210023, China
*
Author to whom correspondence should be addressed.
ISPRS Int. J. Geo-Inf. 2017, 6(10), 300; https://0-doi-org.brum.beds.ac.uk/10.3390/ijgi6100300
Received: 10 August 2017 / Revised: 21 September 2017 / Accepted: 24 September 2017 / Published: 28 September 2017
Airborne Light Detection and Ranging (LiDAR) is widely used in digital elevation model (DEM) generation. However, the very large volume of LiDAR datasets brings a great challenge for the traditional serial algorithm. Using parallel computing to accelerate the efficiency of DEM generation from LiDAR points has been a hot topic in parallel geo-computing. Generally, most of the existing parallel algorithms running on high-performance clusters (HPC) were in process-paralleling mode, with a static scheduling strategy. The static strategy would not respond dynamically according to the computation progress, leading to load unbalancing. Additionally, because each process has independent memory space, the cost of dealing with boundary problems increases obviously with the increase in the number of processes. Actually, these two problems can have a significant influence on the efficiency of DEM generation for larger datasets, especially for those of irregular shapes. Thus, to solve these problems, we combined the advantages of process-paralleling with the advantages of thread-paralleling, forming a new idea: using process-paralleling to achieve a flexible schedule and scalable computation, using thread-paralleling inside the process to reduce boundary problems. Therefore, we proposed a hybrid process/thread parallel algorithm for generating DEM from LiDAR points. Firstly, at the process level, we designed a parallel method (PPDB) to accelerate the partitioning of LiDAR points. We also proposed a new dynamic scheduling strategy to achieve better load balancing. Secondly, at the thread level, we designed an asynchronous parallel strategy to hide the cost of LiDAR points’ reading. Lastly, we tested our algorithm with three LiDAR datasets. Experiments showed that our parallel algorithm had no influence on the accuracy of the resultant DEM. At the same time, our algorithm reduced the conversion time from 112,486 s to 2342 s when we used the largest dataset (150 GB). The PPDB was parallelizable and the new dynamic scheduling strategy achieved a better load balancing. Furthermore, the asynchronous parallel strategy reduced the impact of LiDAR points reading. When compared with the traditional process-paralleling algorithm, the hybrid process/thread parallel algorithm improved the conversion efficiency by 30%. View Full-Text
Keywords: parallel geo-computing; hybrid process/thread paralleling; DEM generation; LiDAR points parallel geo-computing; hybrid process/thread paralleling; DEM generation; LiDAR points
Show Figures

Figure 1

MDPI and ACS Style

Ren, Y.; Chen, Z.; Chen, G.; Han, Y.; Wang, Y. A Hybrid Process/Thread Parallel Algorithm for Generating DEM from LiDAR Points. ISPRS Int. J. Geo-Inf. 2017, 6, 300. https://0-doi-org.brum.beds.ac.uk/10.3390/ijgi6100300

AMA Style

Ren Y, Chen Z, Chen G, Han Y, Wang Y. A Hybrid Process/Thread Parallel Algorithm for Generating DEM from LiDAR Points. ISPRS International Journal of Geo-Information. 2017; 6(10):300. https://0-doi-org.brum.beds.ac.uk/10.3390/ijgi6100300

Chicago/Turabian Style

Ren, Yibin, Zhenjie Chen, Ge Chen, Yong Han, and Yanjie Wang. 2017. "A Hybrid Process/Thread Parallel Algorithm for Generating DEM from LiDAR Points" ISPRS International Journal of Geo-Information 6, no. 10: 300. https://0-doi-org.brum.beds.ac.uk/10.3390/ijgi6100300

Find Other Styles
Note that from the first issue of 2016, MDPI journals use article numbers instead of page numbers. See further details here.

Article Access Map by Country/Region

1
Back to TopTop