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

摘要

数字地形分析是地理信息系统软件的重要支撑功能之一。目前众多应用领域对大规模、高效率数字地形分析的需求日益增长,而其与计算资源低利用率之间的矛盾却日益突出。现有的数字地形分析方法很难甚至无法快速、高效地处理海量DEM数据,而并行计算为解决这一难题提供了新的思路。虽然传统的高性能计算技术使得DEM的处理效率得到了有效提升,但是随着并行计算集群技术、多核处理器技术以及并行计算模型等新型并行技术的出现,面向新型架构的数字地形分析并行算法亟需发展与完善。
　　首先,本文针对数字地形分析的数据密集、任务密集的特征,并结合当前并行计算平台的特点,提出了数据、任务与结构统一的,面向数字地形分析的可量化的粒度模型概念和定义,并从数据和任务拆分的角度构建了粒度关系依赖图。其次,在粒度模型的基础上,针对格网DEM的数据特征,构建了并行环境下可有效支撑DEM数据规则拆分的数据粒度模型,详细定义了数据粒度的属性以及数据粒度之间的关系。利用数据粒度的各维属性对数据粒度进行量化,提出了基于内存页调度机制的最小数据粒度和基于四叉树管理存储策略的组合数据粒度的概念,给出了便于DEM数据接边处理的冗余行列的计算和划分方法。综合考虑最小数据粒度和组合数据粒度,以及结构粒度,给出了面向并行数字地形分析的数据分发方法。再次,为了充分利用多核集群系统的硬件优势,任务并行能够更好地提高并行处理效率。
　　本文对数字地形分析中的63个地形因子进行分析,构建了任务分解的任务粒度模型,从任务粒度的属性和关系来对其进行量化研究。为了厘清可并行性,引入Petri网理论,提出了基于数据并行和任务并行的关系依赖图及其构建方法,并给出了相应的调度算法,为任务并行调度提供了理论依据。最后,为保证大规模并行系统的可靠运行和结果的正确性,本文在数据分发和任务调度的基础上,提出了两级调度机制,并给出基于冗余的并行容错调度算法,提高系统的可靠性。

目录

摘要

ABSTRACT

第一章 绪论

1.1 并行数字地形分析的发展与意义

1.2 关于并行数字分析的国内外研究现状

1.2.1 并行数字地形分析的平台

1.2.2 DEM数据并行化处理与存储

1.2.3 数字地形分析的并行化策略

1.3 课题的提出

1.4 论文的主要工作及创新

1.4.1 主要工作

1.4.2 创新之处

1.5 论文的结构

第二章 并行数字地形分析与容错调度研究

2.1 数字地形分析

2.2 并行计算

2.2.1 并行计算的软硬件平台

2.2.2 并行计算的模型

2.2.3 并行算法的设计

2.3 并行数字地形分析

2.3.1 数字高程模型构建的并行化

2.3.2 数字地形分析算法的并行化

2.3.3 DEM数据拆分及管理策略

2.4 容错机制及负载调度策略

2.4.1 容错机制

2.4.2 负载均衡策略

2.5 本章小结

第三章 并行数字地形分析的数据粒度模型及分发方法

3.1 粒度模型

3.2 数据粒度模型及量化方法

3.2.1 数据粒度的属性

3.2.2 数据粒度的关系

3.2.3 数据关系依赖图实例

3.3 数据分发方法

3.4 实验与分析

3.4.1 实验环境与实验数据

3.4.2 实验结果与分析

3.5 本章小结

第四章 并行数字地形分析的任务粒度模型及任务调度方法

4.1 任务并行概述

4.2 Petri网理论

4.2.1 国内外研究现状

4.2.2 基本概念

4.2.3 形式化定义

4.2.4 Petri网的性质

4.3 任务粒度模型

4.3.1 基本模型

4.3.2 任务粒度模型的属性

4.3.3 任务粒度的依赖关系

4.4 基于Petri网的并行关系依赖图

4.4.1 并行关系依赖图的构建流程

4.4.2 基于数据并行的构建分析

4.4.3 基于流域网络提取算法的实例分析

4.5 任务并行调度机制

4.5.1 相关概念介绍

4.5.2 基于Petri网的任务并行调度方法

4.6 本章小结

第五章 基于并行数字地形分析的容错机制

5.1 容错机制概述

5.2 容错粒度模型

5.3 两级调度机制

5.4 容错策略

5.4.1 冗余度计算

5.4.2 基于粒度模型的容错调度算法

5.5 本章小结

第六章 总结

6.1 论文总结

6.2 工作展望

参考文献

在读期间参加的科研项目与科研成果

致谢