地理大数据并行计算空间划分与任务调度方法研究

Parallel geocomputation is an important technique in the research field of geographical information systems (GIS). The existing studies are still needed to be improved when dealing with large-scale geographical data, complicated geocomputation, and hybrid parallel computing environment. In this project, we aim to first design a parallel spatial decomposition method based on computational complexity for vector-based geocomputation algorithms. The complexity models are developed according to the characteristics of vector data structure, vector-based geocomputation algorithm, and parallelism, in order to optimize the process of decomposition and assignment for massive vector data. This will greatly improve the parallel efficiency of vector-based geocomputation. Second, we present parallel spatial decomposition and task scheduling approaches based on actual calculations and hierarchical task dependency for raster-based geocomputation algorithms. Through applying these approaches that are with multi-granularity, the strong task dependency during parallel processing can be reduced and consequently the parallel efficiency can be significantly increased. Third, we plan to propose an adaptive dynamic task scheduling approach, which can be well adopted to large-scale geographical data, complicated computational processes, and hybrid parallel computing environment. By using the above parallel computing models and approaches, the massive geographical data can be rapidly processed and timely analyzed. It will therefore provide significant theories and techniques for lots of geographical application fields such as monitoring and emergency response of natural resources.

并行地理计算是地理信息科学研究领域的重要技术手段。当前研究在处理地理大数据、复杂地理计算过程和混合异构计算环境时的并行性能需进一步提升。基于此，本项目拟（1）设计基于计算复杂度评价模型的矢量地理计算并行空间划分方法，通过研究矢量空间数据结构特征、算法特征和并行潜力，构建相适应的计算复杂度模型，来实现矢量空间数据的均衡划分，从而提高矢量地理计算的并行效率。（2）提出顾及有效计算量和层次任务依赖的栅格地理计算并行方法，通过融合多粒度的分层次空间划分及任务调度过程，来缓解并行任务依赖严重的问题，从而有效提升并行计算性能。（3）研发自适应动态任务调度方法，以有效协同地理大数据、复杂地理计算过程及混合异构并行计算环境，实现自适应的并行优化处理。通过构建的并行计算模型与技术方法体系，实现大规模地理空间数据的快速处理与实时分析，进而为国土资源动态监测与应急响应等地理学应用领域提供理论与技术支撑。

随着对地观测技术的快速发展，地理计算面临着数据量庞大、计算过程复杂密集和计算类型多样的难题；采用高性能计算技术以提高地理大数据的计算效率十分迫切和必需。本项目聚焦地理大数据并行计算中的空间划分与任务调度难题，开展了三方面的研究内容。1）设计了基于计算复杂度的矢量多边形空间分析并行方法。研究分别针对数据密集型和计算密集型多边形空间分析类型构建多边形复杂度估算模型，用以指导矢量数据的均衡划分。通过分析不同算法类型的原理与特征，筛选可能影响算法计算效率的影响指数；构建多边形模拟数据集，通过模拟实验确定对算法效率实际有影响的指数及对应的影响程度顺序，并以此构建多边形复杂度估算模型。实验结果表明，基于多边形计算复杂度的并行方法较传统并行方法可大大缩短算法的运行时间，并取得良好的加速比和稳定的负载均衡性能。2）提出了顾及有效计算量的多粒度栅格空间分析并行方法。研究针对局部型栅格空间分析类型，研究提出考虑栅格有效计算量的不规则数据划分方法和多粒度动态并行调度方法。针对全局型栅格数据空间分析类型，研究设计双层空间划分方法、抓取式并行调度方法以及基于二叉树的计算结果融合策略。实验结果表明，研究提出的数据划分方法和并行调度方法较传统方法均能大大缩短算法的并行时间、取得更好的并行加速比和稳定的负载均衡性能。3）研发CPU/GPU协同的动态任务调度方法。研究设计自适应负载均衡方法，可根据待处理数据类型、算法类型和并行计算环境自适应地选择任务调度方法和计算粒度，实现不同串行算法和自定义计算规则的快速并行化，并实现并行计算过程中的有效动态负载均衡。实验结果表明，研究提出的方法对CPU/GPU混合异构计算环境中不同的算法类型和不同的数据量均具有良好的适应性。本项目研究成果可实现大规模地理空间数据的快速处理与实时分析，进而为国土空间优化、自然资源监测等地理学领域提供重要理论基础与技术支撑。