基于并行数字地形分析的粒度模型与容错调度研究

发布时间：2019-06-01 17:38

【摘要】：数字地形分析是地理信息系统软件的重要支撑功能之一。目前众多应用领域对大规模、高效率数字地形分析的需求日益增长,而其与计算资源低利用率之间的矛盾却日益突出。现有的数字地形分析方法很难甚至无法快速、高效地处理海量DEM数据,而并行计算为解决这一难题提供了新的思路。虽然传统的高性能计算技术使得DEM的处理效率得到了有效提升,但是随着并行计算集群技术、多核处理器技术以及并行计算模型等新型并行技术的出现,面向新型架构的数字地形分析并行算法亟需发展与完善。首先,本文针对数字地形分析的数据密集、任务密集的特征,并结合当前并行计算平台的特点,提出了数据、任务与结构统一的,面向数字地形分析的可量化的粒度模型概念和定义,并从数据和任务拆分的角度构建了粒度关系依赖图。其次,在粒度模型的基础上,针对格网DEM的数据特征,构建了并行环境下可有效支撑DEM数据规则拆分的数据粒度模型,详细定义了数据粒度的属性以及数据粒度之间的关系。利用数据粒度的各维属性对数据粒度进行量化,提出了基于内存页调度机制的最小数据粒度和基于四叉树管理存储策略的组合数据粒度的概念,给出了便于DEM数据接边处理的冗余行列的计算和划分方法。综合考虑最小数据粒度和组合数据粒度,以及结构粒度,给出了面向并行数字地形分析的数据分发方法。再次,为了充分利用多核集群系统的硬件优势,任务并行能够更好地提高并行处理效率。本文对数字地形分析中的63个地形因子进行分析,构建了任务分解的任务粒度模型,从任务粒度的属性和关系来对其进行量化研究。为了厘清可并行性,引入Petri网理论,提出了基于数据并行和任务并行的关系依赖图及其构建方法,并给出了相应的调度算法,为任务并行调度提供了理论依据。最后,为保证大规模并行系统的可靠运行和结果的正确性,本文在数据分发和任务调度的基础上,提出了两级调度机制,并给出基于冗余的并行容错调度算法,提高系统的可靠性。
[Abstract]:Digital terrain analysis is one of the important supporting functions of GIS software. At present, the demand for large-scale and efficient digital terrain analysis is increasing in many application fields, but the contradiction between it and the low utilization rate of computing resources is becoming more and more prominent. The existing digital terrain analysis methods are difficult or even unable to deal with massive DEM data quickly and efficiently, and parallel computing provides a new way to solve this problem. Although the traditional high performance computing technology has effectively improved the processing efficiency of DEM, with the emergence of parallel computing cluster technology, multi-core processor technology and parallel computing model and other new parallel technologies, The parallel algorithm of digital terrain analysis for new architecture needs to be developed and improved. First of all, according to the data-intensive and task-intensive characteristics of digital terrain analysis, and combined with the characteristics of the current parallel computing platform, this paper proposes a unified data, task and structure. The concept and definition of quantitative granularity model for digital terrain analysis are constructed, and the dependency graph of granularity relation is constructed from the point of view of data and task resolution. Secondly, on the basis of granularity model, according to the data characteristics of grid DEM, a data granularity model which can effectively support DEM data rule resolution in parallel environment is constructed, and the attributes of data granularity and the relationship between data granularity are defined in detail. The data granularity is quantified by using the attributes of each dimension of data granularity, and the concepts of minimum data granularity based on memory page scheduling mechanism and combined data granularity based on quadtree management storage strategy are proposed. The calculation and partition method of redundant rows and rows which is convenient for DEM data edge processing is given. Considering the minimum data granularity, the combined data granularity and the structure granularity, a data distribution method for parallel digital terrain analysis is presented. Thirdly, in order to make full use of the hardware advantages of multi-core cluster system, task parallelism can improve the efficiency of parallel processing. In this paper, 63 terrain factors in digital terrain analysis are analyzed, and the task granularity model of task decomposition is constructed, and the quantitative research is carried out from the attributes and relations of task granularity. In order to clarify the parallelism, the Petri net theory is introduced, and the relational dependency graph based on data parallelism and task parallelism and its construction method are proposed, and the corresponding scheduling algorithms are given, which provides a theoretical basis for task parallel scheduling. Finally, in order to ensure the reliable operation of large-scale parallel systems and the correctness of the results, a two-level scheduling mechanism is proposed on the basis of data distribution and task scheduling, and a parallel fault-tolerant scheduling algorithm based on redundancy is proposed. Improve the reliability of the system.
【学位授予单位】：南京师范大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：TP338.6;TP301.1

【参考文献】