基于 OpenMP 的并行化水文分析算法研究与实现

0 引 言

地理信息系统( Geographic Information System，以下简称 GIS) 中的空间分析服务具有算法逻辑复杂、数据规模庞大的特点，属于一种计算密集型服务。随着数据采集、传输、处理技术的不断发展，大范围、高分辨率的地理空间数据使得传统串行算法难以满足性能要求。与此同时 64 位系统和多核计算技术不断发展，如何充分利用 64位系统和多核环境下的计算资源成为 GIS 研究人员必须面对的问题。而高性能地学计算概念的提出，正是希望将 IT 技术发展成果与地理信息理论相结合，解决 GIS 中大规模地理空间数据的并行存储、查询、分析等关键技术问题，提高 GIS 的空间数据处理、管理与分析能力。

1 空间分析并行化

作为衔接空间数据处理与应用模型的重要部分，空间分析通过对原始数据的特征观察分析和处理获得更多的经验和知识，并以此作为空间行为的决策依据[1]。GIS空间数据规模不断膨胀，导致传统串行空间分析方法很容易成为系统性能瓶颈。而并行计算技术凭借其对于多核计算能力的充分利用，以及可扩展的计算模式为大规模空间数据的分析提供了一种解决方案。

并行算法经过多年的发展，目前已形成一些基本设计方法，常见的并行计算策略有分治策略，平衡树方法，倍增技术，流水线技术及加速级联策略[2]。由于 GIS 数据具有空间信息量大、地理分布广、时效性强、多源异构等特征，为了有效组织多源的相关数据进行综合分析，以建立响应速度快、计算能力强和空间数据高效组织与管理的新机制来认知、模拟、预测和调控自然地理环境和社会经济过程，客观上要求大力发展空间分析并行计算方法[3]。而在空间分析功能并行化的具体实施过程中，可以划分为基于数据的并行化、基于算法的并行化和基于硬件技术的并行化几种模式。

1. 1 基于数据的并行化

该模式主要是指那些不需要对空间分析算法进行整体调整，即主要通过对待分析数据的均匀划分，从而将原始计算任务均匀的分配到多个计算单元中。较为典型的应用场景为空间分析中面向栅格数据的分析，如水文分析、插值计算、等值线提取、地形计算等分析功能。与矢量数据相比，栅格数据结构简单，没有复杂的拓扑关系，空间分析算法逻辑也相对简单[4]。但另一方面，栅格数据一般数据量较大，导致整体计算量较大，因此栅格数据空间分析的并行模式多采用数据并行模式。

1. 2 基于算法的并行化

该模式主要指那些不能完全通过数据划分达到分析过程并行化的功能，举例来说，空间分析中的矢量数据之间一般存在较为复杂的空间关系，如线与面的边界覆盖关系，面与面的邻接关系，面与点的包含关系等。使得基于矢量数据的空间分析操作较难通过简单的数据划分来并行化。即在对分析数据进行划分的基础上，还需要分析算法针对数据特点，对划分和合并过程进行特殊处理。如矢量数据处理较多使用平面扫描算法，在进行该算法的并行化改进时，主处理单元通过将事件点平均分配给从处理单元，各从处理单元处理完各自的任务后将结果发送给主处理单元，最后主处理单元将各事件点合并，才能得到最终解。

更多内容请查看pdf