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

摘要

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