地球信息科学学报

地球信息科学学报 ›› 2015, Vol. 17 ›› Issue (5): 531-537.doi: 10.3724/SP.J.1047.2015.00531

• 地理计算并行化 • 上一篇    下一篇

采用动态负载均衡的LiDAR数据生成DEM并行算法

任沂斌, 陈振杰, 程亮, 李满春, 骈宇哲   

  1. 江苏省地理信息技术重点实验室, 南京210023
  • 收稿日期:2014-12-10 修回日期:2015-01-09 出版日期:2015-05-10 发布日期:2015-05-10
  • 通讯作者: 陈振杰(1974-),男,博士,副教授,研究方向为GIS算法、高性能地理计算。E-mail:chenzj@nju.edu.cn E-mail:chenzj@nju.edu.cn
  • 作者简介:任沂斌(1990-),男,硕士生,研究方向为高性能地理计算。E-mail:ryb0911@163.com
  • 基金资助:

    国家"863"计划项目(2011AA120301);地理空间信息工程国家测绘地理信息局重点实验室开放课题(200712)。

Parallel Algorithm of Generating DEM from LiDAR Point Clouds Based on Dynamic Load Balancing Strategy

REN Yibin, CHEN Zhenjie, CHENG Liang, LI Manchun, PIAN Yuzhe   

  1. Jiangsu Provincial Key Laboratory of Geographic Information Sciences and Technology, Nanjing 210023, China
  • Received:2014-12-10 Revised:2015-01-09 Online:2015-05-10 Published:2015-05-10

PDF (PC)

赞

被引次数

5 | 3

摘要：

随着高性能计算的发展,并行技术已经广泛应用于LiDAR数据的分析处理。本文针对现有LiDAR数据生成DEM并行算法所存在的负载不均衡问题,设计并实现了动态负载均衡的LiDAR数据生成DEM并行算法。该算法采用主从式并行策略,管理进程负责LiDAR点云的高效自适应条带划分,计算进程负责LiDAR点云生成DEM的计算。本文设计了任务量的动态调度策略:首先,由所有进程并行创建任务量由大到小排列的待处理任务队列;然后,管理进程根据计算进程的反馈对待处理任务进行动态分配,以达到负载均衡。在24 核集群环境下,用30 GB(约12 亿点)LiDAR数据对本文算法进行测试,生成分辨率为1 m的格网DEM,算法加速比峰值达到15.16;同时,与静态调度策略进行对比实验,结果显示本文的动态负载均衡策略可更好地保证进程间的负载均衡,有效地提高了LiDAR生成DEM并行算法的整体效率。

关键词: 并行计算, LiDAR, DEM, 动态负载均衡

Abstract:

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