【作者】 江岭；

【导师】 汤国安；

【作者基本信息】 南京师范大学 ， 地图学与地理信息系统， 2014， 博士

【摘要】 基于DEM的流域地形分析是数字地形分析的重要组成部分,也是GIS空间分析不可或缺的内容,在地貌、土壤、水文和生态学等科学研究及生成建设中发挥着重要的作用。目前,随着空间数据获取技术的发展,大区域高精度地形数据的快速获取成为现实,为流域地形分析提供了丰富的数据源。在这种大数据背景下,如何对海量规模的地形数据进行快速有效地处理和分析,使之转化为所需的地学知识,成为目前GIS遇到的一大难题。并行计算技术为解决这一难题带来了机遇。本论文以数字地形分析理论与方法为基础,从流域地形分析高性能计算出发,系统研究了流域地形分析并行计算的关键技术及流域地形分析算法并行化方法,以期丰富数字地形分析理论与方法体系,完善地学知识挖掘和知识转化平台,推动大区域高精度地形分析技术在数字流域等领域的有效应用。研究成果可望为大数据时代高性能GIS空间分析提供理论、方法上的借鉴。本论文的主要内容和研究成果如下：(1)综合流域地形分析问题所涉及的数据、任务、结构三大元素,研究提出了流域地形分析并行算法设计的量化模型——并行粒度模型,并从数据的属性和数据体、任务的参数和负载、及计算平台的有效内存等方面对并行粒度模型三大元素进行了有效的量化统一,为流域地形分析并行算法设计中任务分解提供了量化依据。(2)从数据划分策略、结果融合策略及数据通信策略等方面,研究了流域地形分析并行策略。根据数据冗余复制思想和并行粒度模型,构建了基于并行粒度模型的行划分策略和流域式划分策略——以并行粒度为控制参数将全局数据划分为多个并行子块,同时,每个并行子块包含与进程数相同的进程子域。以此为基础,研究了相应的结果融合策略：对于行划分策略,可采用进程子域的数据锚点进行融合,而流域式划分策略则采用三元组机制进行融合。分别从通信方式和数据压缩两方面,研究了流域地形分析并行计算的数据通信策略。分析了MPI中点对点通信和组通信的效率,并从转换压缩和编码压缩两方面,设计了DEM数据内存压缩方法。(3)基于流域地形分析并行策略,系统研究了顾及并行粒度控制的流域地形分割并行算法。面向基于并行粒度模型的行划分策略,提出了两阶段并行方法。以此两阶段并行方法为基础,研究了流域地形分割并行算法：设计了流域边界生成方法并行算法；分析了基于坡面径流模拟的子流域划分方法所存在的问题,针对该问题提出了子流域划分并行算法；提出了一种顾及子流域拓扑关系和面积的改进流域编码方法,并实现了流域编码并行算法。实验结果表明,在并行粒度控制条件下,流域地形分割并行算法能够有效提高计算效率和处理数据规模。(4)利用流域结构特征,研究了顾及并行粒度控制的流域地形特征提取并行算法。基于流域式划分策略的两阶段并行方法,以构建的无DEM预处理过程水流方向生成方法为基础,设计了流域河流网络提取并行算法,并详细研究了并行计算过程中子流域合并、负载平衡与任务分配,及子流域间的信息传递等关键问题；在此基础上,研究了基于子流域的流域河网密度计算方法,设计了河网密度计算并行算法,并重点分析了并行计算过程中“双层”子流域间的信息传递方法。通过实验证明,基于流域式划分策略的并行算法充分利用了子流域可作为独立计算单元的特征,大幅度缩短了算法执行总时间,同时,并行算法可顾及并行粒度控制并具有较好地并行性能。更多还原

【Abstract】 Watershed topographic analysis based on DEMs, an indispensable tool of spatial analysis in GIS applications, is a core part of digital terrain analysis. It plays an important role in many research fields such as landform, soil, hydrology and ecology. At present, with the development of spatial data acquisition technology, the quick acquisition of terrain data with large areas and fine scales becomes a solid reality; it provides rich data sources for watershed topographic analysis. Under the background of big data, it becomes a great difficulty in GIS that how to process and analyze these massive datasets quickly and efficiently to turn it into the required geological knowledge. Parallel computing brings an opportunitie to meet this challenge with the development of computer technology. In this paper, aiming at high performance computation in watershed topographic analysis, the key techniques of parallel computing in watershed topographic analysis have been deeply researched on the basis of the theories and methods of digital terrain analysis. This study has the practical significance for us to enrich the theoretical and methodological system of digital terrain analysis, to improve the platforms of geological knowledge mining and knowledge conversion, and to promote the effective application of terrain analysis techonology with large scopes and fine scales into many research fields such as digital watershed. The research findings can be as the theoretical and methodological references to high-performance computation in GIS spatial analysis under the age of big data.The mainly contents and research achievements of this paper are as follows:(1) A quantitative model for parallelizing algorithms of watershed topographic analysis, namely, parallel granularity model, is presented. The model integrates the elements of data, task and structure. These elements are involved by a problem of watershed topographic analysis. From the data attributes and data volume, parameters and load in a task, and the effective memory of a computing platform, the model carries on the effective quantitative unification to these three elements. The parallel granularity model provides a quantitative foundation to task decomposition in the design of parallel algorithm for watershed topographic analysis.(2) From the aspects of data decomposition, resulting fusion and data communication, the strategies of parallel computing for watershed topographic ananlysis are presented. According to the thought of data redundancy replication and parallel granularity model, the row-decomposition strategy and subwatershed-decomposition strategy based on parallel granularity model are designed. Using the parallel granularity as a control parameter, the global data is divided into multiple parallel blocks, and each parallel block contains multiple process subdomains as the same as the number of processes. On this basis, the corresponding resulting fusion strategy is studied. For the row-decomposition strategy, the resulting fusion is processed by the data anchor point of the process subdomain and a triple approach is adopted to merge the subresult of each process subdomain for subwatershed-decomposition strategy. The strategy of data communication is also presented in the view of communication mode and data compression. The efficiencies of point-to-point communication and group communication in MPI are analized, and the method of memory compression for DEM dataseets is designed from the aspects of transform compression and coding compression.(3) Based on the parallel strategies of watershed topographic analysis, parallel algorithms with parallel granularity control of watershed topographic partition are proposed. Facing to the row-decomposition strategy based on parallel granularity model, a two-phase parallelizing strategy is put forward. Based on the two-phase parallelizing strategy, parallel algorithms are respectively designed to calculate a basin with an outlet, subwatersheds with a watershed-area threshold, and watershed coding with an improved coding method considering topological relations and areas of subwatersheds. The experiment reulsts show that, with parallel granularity control, the parallel algorithms of watershed topographic partition can effectively improve the computaional efficiency and the processing-data scale.(4) According to the watershed structure, patallel algorithms with parallel granularity control of watershed topographic characteristics extraction are studied. On the basis of the two-phase parallelizing approach of the subwatershed-decomposition strategy, parallel algorithms are designed to extracte the stream network of a watershed and calculate drainage densities based on subwatersheds in a watershed. In the process of parallel computing, the key issues are researched in detail, such as subwatershed merger, load balancing and task allocation, and information transmission between subwatersheds. Experimental results prove that, the parallel algorithms based on the subwatershed-decomposition strategy can make full use of the characteristic that subwatershed can be considered as an independent computing unit, which makes the totoal execution time greately decrease; meanwhile, the parallel algorithms are under the condition of parallel granularity control and achieve a good parallel performance.更多还原