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

发布时间：2018-06-27 12:46

本文选题：LiDAR + DEM　；参考：《地球信息科学学报》2015年05期

【摘要】：随着高性能计算的发展,并行技术已经广泛应用于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并行算法的整体效率。
[Abstract]:With the development of high performance computing, parallel technology has been widely used in the analysis and processing of Li Dar data. In this paper, we design and implement a dynamic load-balancing parallel algorithm for generating Dem data from Li Dar data, aiming at the problem of load imbalance existing in the existing parallel algorithms for generating Dem from Li Dar data. The algorithm adopts a master-slave parallel strategy, the management process is responsible for efficient adaptive strip partition of the Li Dar point cloud, and the computing process is responsible for the Dem generation of the Li Dar point cloud. In this paper, a dynamic scheduling strategy for task quantity is designed: firstly, all the processes parallel create the queue of tasks to be processed from large to small, and then the management process dynamically allocates processing tasks according to the feedback of the computing process. To achieve load balancing. In the 24-core cluster environment, the algorithm is tested with 30 GB (about 1.2 billion points) Li DAR data, and the grid DEM with a resolution of 1 m is generated, and the speedup peak of the algorithm reaches 15.16. At the same time, the algorithm is compared with the static scheduling strategy. The results show that the proposed dynamic load balancing strategy can better ensure the load balance between processes and effectively improve the overall efficiency of the parallel algorithm for the generation of Dem by Li DAR.
【作者单位】：江苏省地理信息技术重点实验室;
【基金】：国家“863”计划项目(2011AA120301) 地理空间信息工程国家测绘地理信息局重点实验室开放课题(200712)
【分类号】：TP338.6

【参考文献】