论文部分内容阅读
随着GIS应用的越来越广泛和深化,空间分析与地理计算模型与方法也越来越复杂。同时,由于空间信息获取能力增强,GIS需要处理和分析的空间数据量也越来越大。但是,已有的高性能计算框架因为计算模式、对空间数据处理的支持及对硬件环境的适应性等方面的限制,无法满足面向海量空间数据的计算的需求。
本文从高性能计算出发,总结了已有计算框架的计算模式及其优缺点,结合空间分析与地理计算的特点,建立了一个高性能计算框架。在框架的基础上提出基于DAG模型的并行处理、基于空间数据分割的并行处理及GPU加速的地理计算等三种高性能地理计算模式。论文描述了框架的架构设计与结构组成,并着重分析了框架对于集群、多核、GPU等各类计算资源的资源管理和调度方法。
基于DAG模型的并行处理模式将由多个子任务构成的计算任务依照子任务间依赖关系构建为DAG模型,并通过发掘子任务之间潜在的并行性以实现高性能计算。论文首先分析了各种的任务依赖类型,并提出根据子任务输入输出特征识别子任务依赖关系建立DAG模型的方法。论文提出并实现了基于DAG模型的并行处理框架,叙述了它的结构和执行过程,为实现计算任务在计算资源上的有效分配,论文提出并实现了基于后继关键路径的调度算法。测试结果表明框架对于此类模型的计算具有较高的性能及较好的伸缩性。
基于数据分割的并行处理模式通过对海量空间数据进行分割,并将分割产生的数据分片在不同的计算节点中并行运算以达成高性能计算的目标。论文首先分析了空间数据的特征及空间分割的复杂性,探讨了格网分割、基于四叉树的空间分割和基于R树的空间分割这三种空间分割方式的特点。然后通过两类典型计算——空间探索和空间连接比较了三种空间分割方式的效率差异。针对R树的子空间交叠特性所带来的计算节点间额外通讯开销问题,论文提出了基于空间连接优化的解决方法。针对因数据偏斜造成的负载不均衡问题,论文提出了基于能力估算的贪心算法。论文提出并实现了基于空间数据分割的并行处理框架,分别叙述了空间扫描统计和空间叠加问题在框架中的处理模式和实现,测试结果表明它们具有良好的性能和较好的伸缩性。
GPU加速的空间分析与地理计算模式通过充分发挥GPU的通用计算能力实现高性能的地理计算。论文选取了地图投影、第k个最临近点、最短路径、叠加分析及空间扫描统计等五种典型计算,比较了这五种计算在计算密集型或数据密集型、数据访问模式、数据相关性、内在并行性等方面的特点。然后分别叙述了它们在GPU上高效的实现方式。最后,通过在各种硬件环境下的实验证明这些实现是高性能的。