论文部分内容阅读
DEM是地理信息科学领域的重要数据之一，在数字地形分析、数字流域分析和三维地表显示等领域有着广泛的应用。随着数据获取技术和DEM应用领域的不断发展，对大区域、高分辨率DEM数据的需求日益迫切。LiDAR技术能迅速获取地理空间物体的高精度三维信息，被较多的用于DEM数据的生产。然而，较高的点云密度往往使得LiDAR点云的数据量较大，给传统计算平台下LiDAR数据到DEM的快速转换提出了挑战。并行计算为LiDAR数据到DEM的快速转换提供了可能。LiDAR数据并行处理具有计算密集和I/O密集双重属性。然而，现有研究多基于单机多核或PC机群环境，并行环境相对落后，并行算法扩展性不强，而且，未给出减少I/O代价的有效策略。另一方面，现有并行算法的负载均衡策略（数据划分、任务调度）在处理大规模LiDAR数据时，也易引起划分时间长、负载不均衡等问题。 本文面向高性能集群，以设计高效、易扩展的LiDAR数据生成DEM并行算法为目标，分析LiDAR数据并行处理过程中的关键问题，将进程与线程混合并行策略应用到LiDAR数据到DEM的并行转换中。重点研究了混合并行策略下的LiDAR数据划分方法、并行调度策略和并行I/O等关键问题，形成了进程与线程结合的LiDAR数据生成DEM并行算法，并对并行算法进行了测试。论文主要研究内容如下: (1)进程与线程混合并行策略研究。分析LiDAR数据生成DEM并行处理过程中的关键问题，结合高性能集群下进程与线程混合编程模型的优势，提出进程与线程混合并行的LiDAR数据到DEM数据的并行转换过程。研究进程与线程的协同过程，充分发挥进程、线程优势，提高I/O效率，减少边界问题，保证并行算法扩展性。满足LiDAR数据并行处理计算密集与I/O密集的双重需求。 (2)双层LiDAR数据划分方法。针对进程与线程的特点，分别设计LiDAR数据划分方法，进程层粗粒度条带划分，线程层顾及负载均衡的细粒度划分。同时，设计双层空间索引策略，进程层设计顾及数据缓冲区的粗粒度索引，用以加快进程的数据读取，重点研究了粗粒度索引的并行构建方法;线程层设计基于内存优化的格网索引，用以加快空间插值计算时邻域点搜索速度。 (3)进程和线程混合的动态任务调度策略。研究了进程层与线程层的并行模式与调度策略。发挥进程跨节点调度的优势，采用数据并行模式，研究了数据并行模式下基于计算量的动态调度策略，以保证进程负载均衡。发挥线程共享内存的优势，设计异步任务并行策略，进一步隐藏LiDAR数据I/O时间。 (4)进程与线程结合的LiDAR数据生成DEM并行算法实现与测试。编程实现进程与线程结合的LiDAR数据生成DEM并行算法。在高性能集群下，选择不同规模的数据对算法进行测试。测试本文提出的混合并行策略、数据划分方法和并行调度策略的有效性，并与现有并行策略进行对比分析。 综上所述，本文面向高性能集群环境，提出了进程与线程结合的LiDAR数据生成DEM混合并行算法;重点突破了大规模LiDAR数据到DEM并行转换过程中的负载均衡（数据划分、调度策略）和并行I/O等问题;并在集群环境下对算法进行了测试。研究结果表明:在高性能集群下，本文提出的进程与线程混合并行策略相对于纯并行策略可更高效的实现大区域LiDAR数据到高分辨率DEM的快速转换;混合并行策略可以提高LiDAR数据并行I/O效率，线程层异步并行策略可以有效隐藏LiDAR数据读取时间;本文的双层LiDAR数据划分方法与进程和线程混合的动态任务调度策略能有效的保证算法负载均衡。