采用动态负载均衡的LiDAR数据生成DEM并行算法
收稿日期: 2014-12-10
修回日期: 2015-01-09
网络出版日期: 2015-05-10
基金资助
国家"863"计划项目(2011AA120301);地理空间信息工程国家测绘地理信息局重点实验室开放课题(200712)。
Parallel Algorithm of Generating DEM from LiDAR Point Clouds Based on Dynamic Load Balancing Strategy
Received date: 2014-12-10
Revised date: 2015-01-09
Online published: 2015-05-10
随着高性能计算的发展,并行技术已经广泛应用于LiDAR数据的分析处理。本文针对现有LiDAR数据生成DEM并行算法所存在的负载不均衡问题,设计并实现了动态负载均衡的LiDAR数据生成DEM并行算法。该算法采用主从式并行策略,管理进程负责LiDAR点云的高效自适应条带划分,计算进程负责LiDAR点云生成DEM的计算。本文设计了任务量的动态调度策略:首先,由所有进程并行创建任务量由大到小排列的待处理任务队列;然后,管理进程根据计算进程的反馈对待处理任务进行动态分配,以达到负载均衡。在24 核集群环境下,用30 GB(约12 亿点)LiDAR数据对本文算法进行测试,生成分辨率为1 m的格网DEM,算法加速比峰值达到15.16;同时,与静态调度策略进行对比实验,结果显示本文的动态负载均衡策略可更好地保证进程间的负载均衡,有效地提高了LiDAR生成DEM并行算法的整体效率。
任沂斌, 陈振杰, 程亮, 李满春, 骈宇哲 . 采用动态负载均衡的LiDAR数据生成DEM并行算法[J]. 地球信息科学学报, 2015 , 17(5) : 531 -537 . DOI: 10.3724/SP.J.1047.2015.00531
With the development of high performance computing, parallel processing has been widely used in analyzing LiDAR point clouds. Aiming at the loading unbalancing problem that exists in current parallel algorithms for generating DEM from LiDAR point clouds, this research implements a parallel algorithm which uses dynamic load balancing strategy to generate DEM from massive LiDAR points. The parallel algorithm is based on the master- slave scheduling strategy. The master processor adaptively partitions LiDAR data and generates several strips afterwards. The data strip may be horizontal or vertical based on the characteristic of LiDAR data. The slave processors generate raster DEM from discrete LiDAR points using spatial interpolation. Furthermore, we propose a dynamic scheduling strategy based on the quantity of tasks. The quantity of each task is measured by the number of points in data strip. Firstly, all processors count the point number for all data strips and the master processor creates a task queue. The task queue is arranged according to the point number of those data strips in a descending order from the largest to the smallest. Secondly, the master processor communicates with the slave processors to distribute these tasks dynamically, thus to help the slave processors achieve the load balancing. In this way, all of the data strips are processed from the largest to the smallest based on the computational complexity. Finally, we test the proposed parallel algorithm in a cluster. The cluster is composed of 24 cores. The volume of the LiDAR point clouds for testing is 30 GB, which contains about 1.2 billion points. The resolution of the target DEM is 1 meter, and the biggest speedup ratio of the parallel algorithm is 15.16. At the same time, we compare the dynamic scheduling strategy proposed in this paper with the static scheduling strategy. The result shows that the dynamic scheduling strategy proposed in this research achieves a better load balancing among all processors. Therefore, we can come to a conclusion that the parallel algorithm proposed in this research can significantly improve the efficiency of generating DEM from massive LiDAR point clouds.
Key words： dynamic load balancing; LiDAR; DEM; parallel computation
[1] Lloyd C D, Atkinson P M. Deriving ground surface digital elevation models from LiDAR data with geostatistics[J]. International Journal of Geographical Information Science, 2006,20(5):535-563.
[2] White S A, Wang Y. Utilizing DEMs derived from LIDAR data to analyze morphologic change in the North Carolina coastline[J]. Remote sensing of environment, 2003,85(1):39-47.
[3] Ma R. DEM generation and building detection from lidar data[J]. Photogrammetric Engineering & Remote Sensing, 2005,71(7):847-854.
[4] Hu X, Li X, Zhang Y. Fast filtering of LiDAR point cloud in urban areas based on scan line segmentation and GPU acceleration[J]. Geoscience and Remote Sensing Letters, IEEE, 2013,10(2):308-312.
[5] Hongchao M, Wang Z. Distributed data organization and parallel data retrieval methods for huge laser scanner point clouds[J]. Computers & Geosciences, 2011,37(2): 193-201.
[6] Wang Y, Chen Z, Cheng L, et al. Parallel scanline algorithm for rapid rasterization of vector geographic data[J]. Computers & Geosciences, 2013,59:31-40.
[7] Bernabé S, Plaza A, Marpu P R, et al. A new parallel tool for classification of remotely sensed imagery[J]. Computers & Geosciences, 2012,46:208-218.
[8] Liu J, Zhu A X, Liu Y, et al. A layered approach to parallel computing for spatially distributed hydrological modeling[J]. Environmental Modelling & Software, 2014,51: 221-227.
[9] Chen C, Chen Z, Li M, et al. Parallel relative radiometric normalisation for remote sensing image mosaics[J]. Computers & Geosciences, 2014,73:28-36.
[10] Khaitan S K, McCalley J D, Somani A. Proactive task scheduling and stealing in master-slave based load balancing for parallel contingency analysis[J]. Electric Power Systems Research, 2013,103:9-15.
[11] Dong B, Li X, Wu Q, et al. A dynamic and adaptive load balancing strategy for parallel file system with large-scale I/O servers[J]. Journal of Parallel and Distributed Computing, 2012,72(10):1254-1268.
[12] Guan X, Wu H. Leveraging the power of multi-core platforms for large-scale geospatial data processing: Exemplified by generating DEM from massive LiDAR point clouds[J]. Computers & Geosciences, 2010,36(10):1276-1282.
[13] Huang F, Liu D, Tan X, et al. Explorations of the implementation of a parallel IDW interpolation algorithm in a Linux cluster-based parallel GIS[J]. Computers & Geosciences, 2011,37(4):426-434.
[14] Han S H, Heo J, Sohn H G, et al. Parallel processing method for airborne laser scanning data using a PC cluster and a virtual grid[J]. Sensors, 2009,9(4):2555-2573.
[15] Bater C W, Coops N C. Evaluating error associated with lidar-derived DEM interpolation[J]. Computers & Geosciences, 2009,35(2):289-300.
[16] Yang C T, Cheng K W, Shih W C. On development of an efficient parallel loop self-scheduling for grid computing environments[J]. Parallel Computing, 2007,33(7):467-487.
[17] Parsopoulos K E. Parallel cooperative micro-particle swarm optimization: A master-slave model[J]. Applied Soft Computing, 2012,12(11):3552-3579.
[18] 钱辰,窦万峰,杨坤,等.基于时间均衡的并行插值数据划 分方法研究[J].地理与地理信息科学,2013,29(4): 86-90.
[19] 齐琳,沈婕,郭立帅,等.面向D-TIN 并行构建的动态条带 数据划分方法与实验分析[J].地球信息科学学报,2012, 14(1):55-61.
[20] 张靖,高伟.LAS 格式解析及其扩展域的应用[J].测绘科 学,2008,33(3):154-155.
[21] Yero E J H, Henriques M A A. Speedup and scalability analysis of Master-Slave applications on large heterogeneous clusters[J]. Journal of Parallel and Distributed Computing, 2007,67(11):1155-1167.
/
| 〈 |
|
〉 |