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

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

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

With the development of high performance computing, parallel processing has been widely used in an- alyzing LiDAR point clouds. Aiming at the loading unbalancing problem that exists in current parallel algo- rithms 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 mas- ter 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 balanc- ing. 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 re- sult 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.