周琛、李满春 等：破解有限算力约束下的地理大数据计算性能提升难题

近年来，地理大数据在数据维度、区域尺度、时空粒度及场景深度等方面持续深化发展，利用动态密集、连续大量产生的地理大数据开展复杂时空场景分析已成为地理信息领域的重要研究内容。复杂时空场景分析呈现出高精度、多尺度、广区域的发展态势，其蕴含的地理大数据实时采集、时空场景高并发计算请求、“云”“端”数据传输延迟等地理计算发展新特性，常引发信息丢失、算力不足、响应迟滞等问题，使得当前以云计算为主体的地理计算架构逐渐陷入中心化计算模式性能提升的困境，难以满足急速更迭的海量数据计算、复杂场景响应、实时请求处理等现实需求。面对复杂时空场景，地理大数据的实时计算响应效能的不足已成为制约其深入发展的首要因素。在此背景下，发展新型高性能地理计算体系、突破地理大数据实时计算响应效能瓶颈刻不容缓。

关于大规模、多尺度地理空间分析并行技术与方法的科学研究日益增多，越来越多的学者通过引入并行技术来突破传统单机平台对计算能力的约束，寻求对复杂地理空间分析过程的快速、准确求解，在矢量数据空间分析、栅格数据空间分析的并行技术研究方面均有不同程度的发展。研究合理、高效的负载均衡并行技术对大数据时代下的海量地理空间分析有着重要的推动意义。

目前存在的问题与不足，主要表现在以下几个方面：

①现有的并行方法对地理空间分析负载均衡并行策略的考虑较为粗略、单一，未能深入研究地理空间分析的数据特征、算法特征及计算粒度特征，因而取得的并行加速效果有限。

②在利用CPU、GPU对地理空间分析算法进行并行加速时，对适应 CPU/GPU 混合异构的负载均衡并行方法考虑较少。因此，提出一种能适用于海量地理空间数据的有效处理方法十分重要。

③CPU和GPU具有不同的计算模型和硬件架构特征，且CPU/GPU混合异构环境包含的节点计算能力差别可能较大。因此，设计一种合理的数据分配方法，根据并行计算节点包含的不同计算能力进行数据分配，才能有效保证混合异构环境中的负载均衡。

本书针对具有代表性的典型地理空间分析应用，从细粒度、多层次并行的角度分析算法特征及并行潜力，研究具有较强适应性和较高扩展性的负载均衡并行技术，从而实现高效的并行地理空间分析。具体而言，本书将根据空间数据的结构特征、地理空间分析类型的算法特征及并行计算环境的架构特征分别设计相适应的负载均衡并行方法。首先，通过研究空间数据特征，并根据算法原理进行数据复杂度分析，从而将空间数据分解成与不同计算阶段相适应的数据粒度，以实现数据层次的并行化。其次，深入研究地理空间分析算法原理，并将其分步骤进行分解；从而对各步骤分别设计包含不同计算粒度的并行策略，以实现算法层次的并行化。最后，通过研究不同并行计算硬件环境的架构特征，分别设计适用于多核 CPU 集群及众核 GPU 集群的并行策略，以实现计算环境层次的并行化。

具体包含以下研究内容：

(1)研究基于计算复杂度的矢量多边形空间分析负载均衡并行方法。研究矢量数据空间分析中的典型应用——矢量多边形空间分析包含的数据密集型和计算密集型空间分析的算法特征及其并行潜力，并结合矢量多边形的数据结构特征，针对不同并行计算过程分别设计多边形复杂度计算模型，以指导并行计算中的矢量多边形数据均衡分配。此外，设计复杂多边形粒度分解方法，根据不同多边形空间分析算法类型，将计算复杂的多边形对象进一步分解，从而进一步缓解数据倾斜引起的负载不均。
(2)研究顾及有效计算量的多粒度栅格空间分析负载均衡并行方法。研究局部型和全局型栅格数据空间分析算法特征，分别设计顾及有效计算量的栅格数据划分方法及动态任务并行调度策略。针对局部型空间分析类型，设计包含弯曲接缝线的不规则栅格数据划分方法及多粒度动态并行调度策略。针对全局型空间分析类型，首先设计考虑有效计算量的两阶段数据划分方法，使得节点内部的并行处理和节点之间的并行调度包含相适应的不同数据粒度，从而实现数据划分阶段的负载均衡；在并行执行过程中，设计抓取式的并行任务调度策略，进一步缓解并行计算中的负载失衡；在结果融合阶段，设计高效的结果融合策略以保证并行计算结果对象的完整。

(3)研究面向 CPU/GPU 混合架构的自适应负载均衡并行计算模型。通过深入讨并总结地理空间分析负载均衡并行技术的设计与实现涉及的不同层面，利用其代表性要素构建一种自适应的负载均衡并行计算模型，主要包含数据、算子、并行化方法、粒度和并行计算环境五个要素。为了使模型能够良好地适应于CPU/GPU 混合异构的并行计算环境， 分别研究多核 CPU 和众核 GPU 计算环境下的并行方法，以有效利用计算资源、处理地理大数据。分别设计串行算法快速并行化方法和自适应负载均衡方法，以实现对多数具有相同数据特征和计算特征的地理空间分析串行算法的快速并行化，并实现对 CPU/GPU 混合异构计算环境中不同算法类型和不同数据类型的良好适应性。采用面向对象和插件式开发的设计思想，进一步研发面向 CPU/GPU 混合架构的自适应负载均衡并行计算平台，实现模型从抽象的逻辑描述到具体应用的转化。

△ 研究技术路线图

本文摘编自《地理大数据并行计算负载均衡技术》一书，有删减，图片来源于该书，标题为编者所加。

《地理大数据并行计算负载均衡技术》

ISBN 978-7-03-077773-7

周 琛 李满春 陈振杰 余治欣 著

责任编辑：许 蕾

本书是在面向国家大数据与高质量发展等国家战略实施基础上，根据作者多年主持研究国家 863 计划项目、国家自然科学基金等重要科研项目的探索与实践总结而成。书中阐述了地理大数据并行计算的国内外研究进展， 着重介绍了基于计算复杂度的矢量多边形空间分析负载均衡并行方法、顾 及 有 效 计 算 量 的 多 粒 度 栅 格 空 间 分 析 负 载 均 衡 并 行 方 法 和 面 向CPU/GPU 混合架构的自适应负载均衡并行计算模型， 实现了混合算力协同负载均衡并行计算平台，破解了有限算力约束下的地理大数据计算性能提升难题。

本书可作为高等院校地理信息科学专业及相关专业本科生或研究生的参考用书，也可供科研机构和企事业单位从事地理大数据研究、开发、应用和管理工作的人员参考。

（本文编辑：洪弘）

地球为你而转！

欢迎关注：赛杰奥（sci_geo）

科学出版社地球科学订阅号