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

摘要

海量数字高程模型(DEM)数据和复杂的地理空间处理算法模式等，使得传统的基于单核计算机的串行数字地形分析算法在效率上的不足日益凸显。而面向海量DEM数据，在并行平台上开发新的并行数字地形分析算法，是解决数字地形分析算法效率问题的关键。
　　设计并行算法时须考虑并行相关性、粒度、局部性、负载均衡等问题。本文首先分析了数据并行、任务并行、递归拆分并行、流水线并行等常用模式在并行数字地形分析算法中的应用方法。得出了并行数字地形分析算法适合采用数据并行模式的结论。在此基础上，设计了一个适用于数字地形分析算法的并行架构。采用主从模式和数据并行方法，将拆分后的每块数据的计算作为独立的任务，采用工作队列动态在进程之间进行计算分配，减少了进程之间的通信量，并取得较好的负载均衡效果。
　　数据并行的一个关键是消除或减少由于数据拆分所导致的不同节点之间的数据相关性。本文根据各种数字地形分析算法的计算特征将其分为邻域相关算法与全局相关算法两大类。针对邻域相关算法，设计了与上述算法模式和算法特征相适应的数据规则拆分方法，包括行、列、块拆分等，提出块拆分可以较小的数据冗余代价来消除节点之间的数据相关性;针对全局相关算法，设计了顾及算法计算特征的、基于多次重采样的不规则数据拆分方法，以低分辨率重采样数据上的初步地形分析结果指导高分辨率的数据拆分，消除了不同计算节点之间的数据相关性。
　　为了验证上述并行架构和数据拆分方法的合理性，搭建了一个由八台PC机组成的机群和OpenMP+MPI为软件的实验系统，采用本文设计的并行数字地形分析算法模式和数据拆分方法，分别以并行坡度计算为邻域相关算法的例子，和并行洼地填平计算为全局相关算法的例子，进行了串行算法与并行算法正确性的对比实验，以及并行算法效率实验。实验结果并行计算和串行计算结果一致，并行加速比理想且符合预期。
　　实验结果表明，本文给出的主从结构和数据并行的数字地形分析算法模式，结合对邻域相关算法与全局相关算法采用的规则拆分以及多次重采样拆分方法，在保持了计算节点之间动态负载平衡的同时，较好的解决了并行数字地形分析的数据相关性问题，适合于大部分的数字地形分析算法的并行化改造，具有一定的普适性，本研究为基于大范围高分辨率DEM数据进行精细化的并行数字地形分析应用提供了有益的理论和技术支撑。

目录

声明

论文说明

摘要

图目录

表目录

第1章 绪论

1．1 研究背景与意义

1．1．1 研究背景

1．1．2 研究意义

1．2 国内外研究现状分析

1．2．1 GIS并行化的相关研究

1．2．2 数字地形分析研究

1．2．3 并行数字地形分析相关研究

1．2．4 并行数字地形分析算法存在的问题

1．3 研究目标、研究内容与技术路线

1．3．1 研究目标

1．3．2 研究内容

1．3．3 技术路线

1．4 论文的组织结构

第2章 并行数字地形分析的相关理论基础

2．1 并行计算性能分析

2．1．1 性能损失

2．1．2 相关性、粒度和局部性

2．1．3 性能度量

2．2 负载均衡、可扩展性与可移植性

2．2．1 负载均衡

2．2．2 可扩展性

2．2．3 可移植性

2．3 数字地形分析算法设计与实现

2．3．1 DEM数据拆分方法分类

2．3．2 数字地形分析算法分类

2．4 本章小结

第3章 并行数字地形分析算法模式

3．1 常用并行编程计算模式

3．1．1 数据并行模式

3．1．2 任务并行模式

3．1．3 递归拆分并行模式

3．1．4 流水线并行模式

3．2 并行数字地形分析算法架构

3．2．1 常用并行编程模式在并行数字地形分析算法中的应用

3．2．2 进程间任务分配与负载均衡

3．2．3 并行数字地形分析算法流程

3．3 本章小结

第4章 DEM数据拆分策略

4．1 概述

4．2 邻域相关算法的DEM数据拆分策略

4．2．1 块拆分

4．2．2 重叠区域

4．2．3 拆分方案

4．3 全局相关算法的DEM数据拆分策略

4．3．1 拆分方案

4．3．2 算法正确性验证

4．4 本章小结

第5章 典型并行数字地形分析算法实现

5．1 并行环境介绍

5．1．1 硬件环境

5．1．2 软件环境

5．2 邻域范围相关算法的实验

5．2．1 串行坡度算法介绍

5．2．2 并行坡度计算

5．2．3 实验结果

5．3 全局范围算法的实验

5．3．1 串行洼地填平算法介绍

5．3．2 数据拆分过程

5．3．3 并行洼地填平计算

5．3．4 实验结果

5．4 实验分析

5．4．1 邻域相关算法实验分析

5．4．2 全局相关算法实验分析

5．5 本章小结

第6章 结论与展望

6．1 主要研究工作

6．2 研究结论

6．3 问题与展望

6．3．1 问题

6．3．2 展望

参考文献

致谢