图表达与划分支持下的高性能矢量地理计算方法研究

High performance computing provides an effective way to deal with the growing spatial data and the high computational cost. When to efficiently process the vector geographic data in parallel, spatial decomposition plays a key role in dividing and solving the task evenly, and largely determines the task scheduling. Traditional decomposing methods, such as quad-tree partition, grid partition, etc., often use the horizontal or vertical lines to constrain the decomposing chunks, and fail to tackle some difficult issues, including the arbitrary distribution of vector objects, the diversity of the spatial associations, and the heterogeneity of the computation. With the pre-experiment, the present study will investigate the definitions of the computing elements, i.e., a new family of functions for processing the vector objects, the dependency relations, and the strength assessment of the computation. This will create a graph representation for describing the geocomputational process quantitatively. Then, a graph approach will be formed by combining the graph partitioning towards the heterogeneous environment, the sub-task computing scheme and the subsequent reduction. A further step is to design and develop a middleware prototype by way of parallel computing models. Finally, some typical algorithms will be parallelized and tested against the large scale vector data produced in the Geographic Conditions Monitoring project.

高性能计算为应对空间数据量及模型计算量的快速增长提供了有效手段。在矢量地理数据的并行处理中，空间划分是实现任务均衡分治的关键，并在很大程度上决定了任务调度的成功实施。传统的四叉树划分、规则网格划分等方法多采用水平或垂直界线来约束划分范围，缺乏对矢量对象的分布随机性、计算关联的多样性以及计算强度的非均匀性进行综合考虑。在预实验基础上，本项目将定义一组计算映射元素，包括对象操作函数、依赖关系操作函数、计算强度评估函数等，形成一种图式化表达以定量描述矢量数据的地理计算过程。然后，通过设计面向异构环境的图划分算法、子任务计算及子结果规约算法，构建高性能矢量地理计算的理论方法。进而，选取相应的并行计算模式，设计与实现中间件原型。最后，针对典型分析算法进行并行优化，并基于全国地理国情监测中的大规模矢量数据开展应用测试。

大数据时代，高性能计算已成为应对海量空间数据资源与复杂地理算法的必要手段。不同于易并行处理的栅格数据，矢量要素本身的数据分布偏斜特征成为决定均衡空间划分和高效任务调度的关键。传统的四叉树划分、规则格网划分等方法，由于缺乏对矢量对象的分布随机性、计算依赖关系及计算强度的综合表达，难以有效支撑各类矢量地理算法的分治优化。本项目主要从矢量地理计算任务的图式表达理论构建、多粒度均衡划分和异步重叠调度三个方面展开系统研究，研发了相应的方法和模型，实现了大规模地表覆盖转移矩阵计算系统。图式表达理论构建分别从拓扑依赖关系和距离依赖关系展开试验研究，验证了亿级规模图斑空间叠加分析和百万级规模点要素缓冲分析的可表达性。多粒度均衡划分研究主要涉及图斑级粒度（粗粒度）和节点粒度（细粒度）两方面内容，分别验证了多核CPU和众核GPU环境下不同算法的可并行性。图斑级粒度划分侧重于选用高效的分治方法，降低划分成本，进而利用多核CPU解决后续的高负载计算问题；细粒度划分则侧重于对全路径算法（All Pairs Shortest Paths，APSP）、地理加权回归算法（Geographically weighted regression，GWR）的高密集、轻量级代码片段进行识别、改造与并行调度，以显著提高整体性能。异步重叠调度以高耗时的封闭区域表面面积算法为研究对象，通过对规则划分、并行处理与属性汇总过程进行重叠，验证了该模型对百万以上规模图斑的I/O密集处理逻辑的显著优化效果。同时，项目的研究方法均基于地理国情监测中的大规模矢量数据开展应用测试，转移矩阵计算、APSP算法、表面面积算法等已在全国多个省区的推广软件中得到集成应用，取得了较为满意的成果转化效果。项目发表论文9篇，其中SCI检索6篇、EI检索2篇、中文核心1篇；项目提交发明专利4项；获得软件著作权3项；在GitHub上发布了Matrix的计算框架代码；资助赴加拿大学术交流1次，培养研究生2名，圆满完成了既定的各项考核指标。

内容获取失败，请点击重试