基于PVM网络并行计算技术的DEM建模研究

论文摘要

作为数字地面模型的一个分支,数字高程模型(DEM)被越来多地应用到人类生活和工作的各个方面,如桥梁道路勘测﹑建筑设计﹑地理信息系统(GIS)系统构建﹑及军事战争的地形分析中,如何快速准确的生成大区域的数字高程模型成为当前该领域的一个重要研究课题。大区域数字高程模型建模过程是一个将大量甚至海量的野外数据点进行复杂分析和计算的过程,在计算资源一定的条件下,该过程的时间复杂度随着数据点数目的增加而加大,甚至无法得到结果。本文提出了利用网络并行计算的思想加快数字高程模型的建模过程,具有重大意义。首先,介绍了数字高程模型的种类,在分析了传统建立三角网类型的数字高程模型后提出了新的建模算法:分治逐点插入算法,并详细分析和设计实现了该算法。该算法融合了分治算法的快速与逐点插入算法的良好空间复杂度,并使用真实数据进行测试,取得了良好的效果,更重要的是该算法能有效的分解为并行算法,易于并行计算的实现。然后,探讨了利用虚拟并行计算机(PVM)架构并行计算系统。该系统架设简单,能有效的将桌面小型微机或大型机连接起来组成一个虚拟并行计算机。在剖析了分治逐点插入算法的串行算法后,在任务级的并行粒度上设计并实现了该算法的并行算法,建立了该网络并行计算系统的主机和节点计算机的程序架构,成功的将分治逐点插入算法移植到该网络并行计算环境中。最后,在进程级的并行粒度上探讨了三角网建模的并行实现方法,将三角网建模过程中的凸壳寻找过程改编成并行算法。采用被广泛使用的加速比模型对该并行系统进行了加速比分析,给出了如何得到良好并行效率的方法。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 引言
• 1.2 数字地形模型与DEM 概述
• 1.3 网络并行计算与PVM 概述
• 1.4 本文研究目的与意义
• 1.5 研究内容与篇章结构
• 2 DEM 建模理论分析与实现
• 2.1 DEM 建模的方法
• 2.1.1 基于点的建模方法
• 2.1.2 基于三角形的建模方法
• 2.1.3 基于格网的建模方法
• 2.1.4 基于混合方法的DEM 建模
• 2.1.5 DEM 建模方法的选择
• 2.2 常规三角网生成算法分析
• 2.2.1 分治算法
• 2.2.2 逐点插入算法
• 2.2.3 生长算法
• 2.3 分治逐点插入算法分析与实现
• 2.3.1 算法步骤
• 2.3.2 算法之数据结构
• 2.3.3 算法之实现
• 3 利用PVM 并行能力加速DEM 建模
• 3.1 并行计算方法
• 3.1.1 并行计算的概念
• 3.1.2 PVM 优势分析
• 3.2 构建基于PVM 的虚拟并行计算系统
• 3.2.1 构建方式选择
• 3.2.2 启动和配置PVM 系统
• 3.3 利用PVM 技术加速三角网生成
• 3.3.1 三角网建模计算的并行性分析
• 3.3.2 PVM 主机和节点的程序结构设计
• 3.3.3 中粒度并行性分析
• 3.3.4 并行效率分析
• 3.3.5 并行计算与单机计算之性能比较
• 4 总结与展望
• 4.1 论文总结
• 4.2 工作展望
• 致谢
• 参考文献
• 附录 攻读硕士期间发表论文目录