并行数字地形分析算法模式与数据拆分方法

发布时间：2018-06-20 23:19

本文选题：数字地形分析 + 并行计算　；参考：《南京师范大学》2013年硕士论文

【摘要】：海量数字高程模型(DEM)数据和复杂的地理空间处理算法模式等,使得传统的基于单核计算机的串行数字地形分析算法在效率上的不足日益凸显。而面向海量DEM数据,在并行平台上开发新的并行数字地形分析算法,是解决数字地形分析算法效率问题的关键。设计并行算法时须考虑并行相关性、粒度、局部性、负载均衡等问题。本文首先分析了数据并行、任务并行、递归拆分并行、流水线并行等常用模式在并行数字地形分析算法中的应用方法。得出了并行数字地形分析算法适合采用数据并行模式的结论。在此基础上,设计了一个适用于数字地形分析算法的并行架构。采用主从模式和数据并行方法,将拆分后的每块数据的计算作为独立的任务,采用工作队列动态在进程之间进行计算分配,减少了进程之间的通信量,并取得较好的负载均衡效果。数据并行的一个关键是消除或减少由于数据拆分所导致的不同节点之间的数据相关性。本文根据各种数字地形分析算法的计算特征将其分为邻域相关算法与全局相关算法两大类。针对邻域相关算法,设计了与上述算法模式和算法特征相适应的数据规则拆分方法,包括行、列、块拆分等,提出块拆分可以较小的数据冗余代价来消除节点之间的数据相关性；针对全局相关算法,设计了顾及算法计算特征的、基于多次重采样的不规则数据拆分方法,以低分辨率重采样数据上的初步地形分析结果指导高分辨率的数据拆分,消除了不同计算节点之间的数据相关性。为了验证上述并行架构和数据拆分方法的合理性,搭建了一个由八台PC机组成的机群和OpenMP+MPI为软件的实验系统,采用本文设计的并行数字地形分析算法模式和数据拆分方法,分别以并行坡度计算为邻域相关算法的例子,和并行洼地填平计算为全局相关算法的例子,进行了串行算法与并行算法正确性的对比实验,以及并行算法效率实验。实验结果并行计算和串行计算结果一致,并行加速比理想且符合预期。实验结果表明,本文给出的主从结构和数据并行的数字地形分析算法模式,结合对邻域相关算法与全局相关算法采用的规则拆分以及多次重采样拆分方法,在保持了计算节点之间动态负载平衡的同时,较好的解决了并行数字地形分析的数据相关性问题,适合于大部分的数字地形分析算法的并行化改造,具有一定的普适性,本研究为基于大范围高分辨率DEM数据进行精细化的并行数字地形分析应用提供了有益的理论和技术支撑。
[Abstract]:Mass digital elevation model (DEM) data and complex geospatial processing algorithms make the traditional serial digital terrain analysis algorithm based on single core computer more and more inefficient. The key to solve the problem of efficiency of digital terrain analysis algorithm is to develop a new parallel digital terrain analysis algorithm based on parallel platform for massive Dem data. Parallel correlation, granularity, locality and load balance should be considered in designing parallel algorithms. In this paper, the application methods of data parallelism, task parallelism, recursive split parallelism and pipeline parallelism in parallel digital terrain analysis algorithms are analyzed. It is concluded that the parallel digital terrain analysis algorithm is suitable for data parallel mode. On this basis, a parallel architecture for digital terrain analysis algorithm is designed. By using master-slave mode and data parallel method, the computation of each block of data after splitting is regarded as an independent task, and the work queue is used to dynamically calculate and distribute between processes, thus reducing the communication between processes. And achieved better load balancing effect. One of the keys of data parallelism is to eliminate or reduce the data correlation between different nodes caused by data splitting. According to the computational characteristics of various digital terrain analysis algorithms, this paper divides them into two categories: neighborhood correlation algorithm and global correlation algorithm. Aiming at the neighborhood correlation algorithm, this paper designs a method of data rule splitting, including row, column, block partition and so on, which adapts to the above algorithm pattern and algorithm features. It is proposed that block splitting can reduce the cost of data redundancy in order to eliminate the data correlation between nodes. For the global correlation algorithm, an irregular data splitting method based on multiple resampling is designed, which takes into account the computational characteristics of the algorithm. The preliminary terrain analysis results on the low-resolution resampling data are used to guide the high-resolution data splitting, and the data correlation between different computing nodes is eliminated. In order to verify the rationality of the parallel architecture and the method of data splitting, an experimental system composed of eight PCs and OpenMP MPI is built. The parallel digital terrain analysis algorithm and the method of data splitting are adopted in this paper. Taking the parallel slope calculation as an example of neighborhood correlation algorithm and the parallel low-fill calculation as a global correlation algorithm, the comparison between the correctness of the serial algorithm and the parallel algorithm and the experiment of the efficiency of the parallel algorithm are carried out. The experimental results are consistent with those of serial computation, and the parallel speedup is ideal and in line with the expectation. The experimental results show that the master-slave structure and the data parallel digital terrain analysis algorithm model, combined with the neighborhood correlation algorithm and the global correlation algorithm of the rule split and multiple resampling split method, At the same time, it can solve the data correlation problem of parallel digital terrain analysis, which is suitable for the parallel transformation of most digital terrain analysis algorithms, and has certain universality. This study provides useful theoretical and technical support for the application of fine parallel digital terrain analysis based on large range and high resolution Dem data.
【学位授予单位】：南京师范大学
【学位级别】：硕士
【学位授予年份】：2013
【分类号】：P208

【参考文献】