王 结 臣，王 豹，胡 玮，张 辉

并行空间分析算法研究进展及评述

王 结 臣，王 豹，胡 玮，张 辉

（南京大学地理信息科学系，江苏 南京 210093）

作为GIS的核心功能之一，空间分析逐步向处理数据海量化及分析过程复杂化方向发展，以往的串行算法渐渐不能满足人们对空间分析在计算效率、性能等方面的需求，并行空间分析算法作为解决目前问题的有效途径受到越来越多的关注。该文在简要介绍空间分析方法和并行计算技术的基础上，着重从矢量算法与栅格算法两方面阐述了目前并行空间分析算法的研究进展，评述了在空间数据自身特殊性的影响下并行空间分析算法的发展方向及存在的问题，探讨了在计算机软硬件技术高速发展的新背景下并行空间分析算法设计面临的机遇与挑战。

并行计算;空间分析;并行GIS

空间分析是GIS的核心功能之一，也是GIS区别于一般信息管理系统的显著特征之一。作为衔接空间数据处理与应用模型的重要部分，空间分析通过对原始数据的特征观察、分析和处理，获得更多的经验和知识，并以此作为空间行为的决策依据［1］。在GIS应用迅猛发展的今天，GIS空间分析已成为处理地理科学领域中各种地理对象分析的重要方法。然而，随着应用的深入，数据海量化、构架网络化、处理实时化等要求日益提高，对空间分析功能在计算效率、性能、处理能力等方面的要求也越来越高。

并行计算是将一项大的数据处理与数值计算任务（或任务的局部）分解为多个可相互独立、同时进行的子任务，并通过这些子任务相互协调的运行，实现快速、高效的问题求解［2］。近年来网络、高性能计算机、多核计算机等的推广应用为其提供了硬件支撑，并行算法等理论技术的发展为其提供了软件、理论支撑，这些技术已开始应用于包括GIS应用在内的诸多领域。然而，由于并行技术发展时间不长，因此GIS核心空间分析功能的并行化也处在发展初期。为了较好地认识并行计算技术对改进空间分析算法的作用，本文在简单介绍并行计算方法的基础上对并行空间分析算法作了综合性的回顾与探讨。

1 并行计算方法

并行计算是计算数学与新一代计算机相结合的产物，其主要研究内容包括并行计算机、并行算法、并行程序设计和并行应用等。相比于串行计算，并行计算有其明显的特点：多个处理器执行部件（执行核）协作，共同完成某一项任务，各个执行部件的处理工作可分布在相同的计算机上（MPP/SMP/多核处理器），也可分布在不同的计算机上。理论上，并行计算具有将计算能力从单个处理器无缝扩展到无限多个处理器的潜力［3］。大量计算任务被分配到多个分处理器上将获得更快的处理速度，其巨大的数据计算和处理能力优势使并行计算成为计算机领域的研究热点之一。在并行计算方面，并行体系结构、并行软件和并行算法三者缺一不可，其中并行算法是并行计算的核心和瓶颈技术。

并行算法是指在各种并行机上求解问题和处理数据，其本质是把多任务映射到分处理机中执行，或将现实的多维问题映射到具有拓扑结构的多处理机上求解。为了尽可能实现计算的高效率，并行算法需通过增加单位时间的算法复杂性来减少整体的时间复杂性，达到将时间复杂性转化为空间复杂性的目的。并行算法经过多年的发展，目前已形成一些基本设计方法，常见的并行计算策略有分治策略、平衡树方法、倍增技术、流水线技术及加速级联策略［4］。此外，为便于并行算法的设计与理论分析以及为并行计算提供软硬件系统设计的简易界面，近30年来，针对不同类型的并行计算机提出了多种并行计算模型，如PRAM及其改进模型、VLSI和BSP模型等，以及与网络并行计算密切相关的C3和LogP模型。其中，PRAM是广泛使用的抽象并行计算模型，BSP模型提供了简单和可定量分析程序运行时间的成本函数，C3和LogP模型考虑了通信和同步等因素，形成了更贴合实际的并行计算模型［5］。

2 并行空间分析方法

并行空间分析方法是GIS空间分析方法与并行计算的结合，致力于通过空间分析算法的并行化解决空间数据处理的速度与质量问题。GIS数据具备空间信息容量大、地理分布广、时效性强、多源异构等特征，为了有效组织多源的相关数据进行综合分析，以建立响应速度快、计算能力强和空间数据高效组织与管理的新机制来认知、模拟、预测和调控自然地理环境和社会经济过程，客观上要求大力发展空间分析并行计算方法。另外，大力发展并行空间分析方法也有主观上的可行性。其一，网络并行、多核处理器、可视化并行编程及分布式GIS等技术的发展，为空间分析的并行计算提供了条件;其二，以往对空间分析算法的改进多通过建立空间索引、数据分组、高速缓冲技术、数据结构优化及其他组合优化技术来提高算法性能，这些方案中大多渗透着并行计算中常用的分组、分治等思想，利于算法的并行化。

此外，并行空间分析还要考虑GIS的特殊性，其影响主要包括：1）算法因素：GIS中并非所有的空间应用及其关键算法均可实现并行化，这受限于空间应用算法本身的特征。2）数据因素：包括空间数据的复杂程度、相关性程度和数据量大小等。3）实现因素：已有的并行化算法设计与实现大多是基于MIMD并行计算机系统，使用PVM或MPI并行计算软件，而空间数据模型的并行特征将着眼于空间数据模型本身及空间数据的组织结构和存储方式［6］。为评估并行空间分析算法的研究进展，本文根据数据处理类型的不同，将并行GIS空间分析应用大体分为两类：基于矢量数据的并行存取与空间分析应用;基于栅格图像数据的并行空间分析应用。

2.1 并行矢量算法

矢量空间数据可较为精细地表达地物实体及详细属性信息，但实体间存在着多种复杂的空间关系（如相邻、相接等拓扑关系等），并行处理过程中须考虑地物实体的排序、联合、数据条带化以及拓扑关系维护等因素。因此，面向矢量空间数据的并行化存取与处理的相关算法和机制研究有较大难度。并不是所有的空间分析都适合并行化，这里主要从平面扫描算法、空间数据查询、空间连接操作、凸包算法、Delaunay三角网构建、空间网络分析等方面阐述空间矢量数据并行算法的研究进展。

平面扫描算法是支持矢量数据空间分析的有效算法，通过该算法对空间对象进行逐一扫描可判断其间的顺序及拓扑关系，是空间拓扑分析的基础。目前，并行平面扫描算法主要有分解归并方法和平面扫描树方法。分解归并方法应用较普遍，即主处理机通过将事件点平均分配给分处理机，各分处理机处理完各自的任务后将结果发送给主处理机，最后主处理机将各事件点合并，得到问题的解。平面扫描树技术是平面扫描算法并行化的一个重要手段，在具体的空间分析之前，首先进行预处理，通过并行归并等技术构建平面扫描树，然后遍历和搜索这棵扫描树，最终确定空间对象的拓扑邻近关系。平面扫描树技术可用于梯形分解、三角剖分及平面点定位等具体的空间问题中，因为采用并行方法，平面扫描树技术可以给每个元素分配处理器，极大地减小了处理问题的时间复杂度［7］。

空间数据查询通常被归类为空间数据库中空间操作的范畴。面对海量的空间数据，使用并行服务器实现多个并发用户同时参与数据查询，可以充分发挥并行计算的优势并大幅提高空间数据库的数据存取与处理能力。空间数据的并行查询效率与数据划分策略及空间索引结构密切相关。数据划分强调数据在多个磁盘系统上较均匀分布，每个磁盘上的数据保持相对平衡的状态。面向并行空间数据库系统，贾婷等提出了一种基于Hilbert空间填充曲线的适于矢量空间数据的划分方法和K－平均聚类算法，较好地实现了空间数据的均衡划分［8，9］。空间索引结构的构建要尽可能减小索引的重叠区域和空白区域，R树索引得到了广泛应用。刘润涛等结合改进的K－均值算法，给出了基于R树和四叉树的空间索引结构，具有更紧凑的结构和更高的查询效率［10］。

空间连接操作是GIS和空间数据库的重要操作。已有的并行空间连接算法可归纳为基于空间数据划分策略的并行空间连接和基于并行R树索引的并行空间连接。对于参与连接操作的两个空间关系，前者采用相同的数据划分策略将空间区域划分至并行计算机环境中的各节点上分别处理;后者充分利用了并行R树索引结构的优势，将计算负载分担到并行计算环境中的计算节点上，在并行R树构建过程中已完成海量空间数据的划分和排序［11］。

凸包是平面点集的最小外接凸多边形。目前，串行求取凸包的经典解法有包绕法、内外法、扫描法、分治法和分层次方法等。在凸包算法并行化方面，最初采用分治方法，即通过对散乱点集的分类，在不同处理器上分别求取分凸包，最后构造各分凸包的公共凸包［12］。采用此方法在一定程度上提高了计算效率，但由于凸包往往只是由点集中小部分点构成，绝大多数点参与计算浪费了大量时间，而删除内点在串行计算中也是一项规模很大的工作。郝小柱等采用并行的方法删除内点，对保留点排序形成简单有序多边形，最后对该多边形求取凸包，大大减小了时间复杂度［13］。Delaunay三角网的并行构建也可建立在凸包分组基础上，采用分治方法，首先按照一定间隔把凸包的边传给各处理机，并建立相应的边表和总边表;然后，各处理机按照Delaunay三角网规则找到点集中符合要求的点，直至找不到时算法终止［14］。因为凸包的构建是一个重要计算环节，其计算效率对Delaunay三角网的生成效率影响较大。

空间网络分析是矢量数据空间分析的重要组成部分，因其涉及空间要素间复杂的拓扑关系而使得大规模网络分析计算耗时过长。最短路径分析是网络分析中的经典问题，也是资源分配、路线设计与分析等优化问题的基础，目前实现并行化的方法主要有网络复制及网络分割［15，16］。网络复制最短路径并行算法是主处理器将整个网络复制到各分处理器中，同时将网络中的所有源点分配到各分处理器上;然后，各处理器调用单源最短路径串行算法求解各自负责源点的最短路径，并将结果汇总到主处理器中。网络分割并行算法则不同，它是在分布式网络上求解单源最短路径：首先将整个网络分割成若干子网并分配到各分处理器上，每个分处理器负责一个子网中的最短路径求解。为得到全局的最短路径，网络分割方法需要各处理器间不断进行信息交换，需要一些额外的时间开销，但在大规模网络路径分析中，网络分割策略比网络复制性能更好。

除以上并行算法外，其他的一些并行矢量算法研究也取得了阶段性的成果，大多体现了分而治之的思想。如在缓冲区分析的并行算法中，为避免数据结构复杂、数据量大带来的计算效率低下问题，结合矢量数据的自身特征和区域特征，采用图层式和图幅式并行算法，将计算数据分解到各分处理器中，组合计算的结果即得到所求缓冲区［17］。与此类似，叠置分析的并行算法也大多是采用图幅分割的方法，只是图幅划分的方式不同［18］。

2.2 并行栅格算法

栅格数据结构是以规则的阵列表示空间地物或现象分布的数据组织，其基本的空间分析方法包括局部运算、邻域运算、分带运算、距离与体积量测及空间自相关分析等。由于栅格数据具有计算量大、每个数据点上的计算形式相同及数据比较独立、关联性小等特点，使栅格数据能够很好地利用分布式并行技术来处理。并行计算在栅格图像分析处理方面的应用相对较早。20世纪80年代初研制的Goodyear Massively Parallel Processor（MPP）并行机，其初衷就是为了NASA进行Landsat影像处理［19］。目前在空间信息处理方面，并行计算理论与方法也多应用于遥感栅格影像数据的并行处理［20］。面向栅格数据的空间分析方法中，局部运算、邻域运算及距离量测等问题在大数据量的情况下有一定难度，其算法的并行化方面目前已有一些初步研究成果。局部运算和邻域并行运算主要应用于遥感图像的并行几何校正、并行图像分类和并行图像融合等方面，而距离量测并行运算主要应用在基于欧几里得距离和成本距离的距离分析方面。

与矢量数据相比，栅格数据结构简单，没有复杂的拓扑关系，空间分析算法也相对简单，但栅格数据一直存在数据量大、计算量大等缺点［21］。因此，栅格数据空间分析的并行模式多采用数据并行模式。数据并行策略的基础是数据划分，最直观的栅格数据划分方式有行、列划分和棋盘式划分。

并行几何校正较适合采用数据并行的处理方式，但以往采用简单的数据划分方法易导致频繁的处理器间通信，全局计算量较大。为减少通信的时间开销，蒋艳凰等提出一种基于局部输出区域计算的校正方法，数据被划分为不规则的子图像块，且各处理器在其子图像的边界处冗余存储若干行像元，这样避免了并行重采样过程中的通讯，加快了处理速度［22］。然而，此种方法中的数据划分不是基于重采样数据的像元数目均等划分，可能导致算法负载不平衡，浪费计算资源。综合考虑算法的负载平衡能力和全局计算量，欧新良等提出一种基于动态分界点计算的PIWA-DDC算法，通过对输入图像的一维划分，并估算变换后目标子图像的像元数目，不仅保持了上述算法的优点，还保证了算法的负载平衡［23］。

并行图像分类的典型算法通常也采用数据并行的方式。由于并行图像分类时在边界像元附近存在信息交换，其数据划分通常采用棋盘式划分方式，各处理器对相应的分块分别计算。但如果划分后某识别目标被分配到不同的子图像中，可能会导致此目标丢失，一般采用边界覆盖的方法解决［24］，相邻的子图像通过一定宽度的图像相互覆盖，确保了识别结果的完整性。并行计算加快了数据分析的速度，但各计算节点之间需要密集的通讯，恶化了并行效率。蒋利顺等在遥感图像K-Means非监督分类中，充分考虑了图像的平滑特性及并行中通信的有效程度，选择在多次计算后再通信并更新均值的方法，消除了无效的通信，取得了较好的聚类速度和精度［25］。

图像融合是国内外遥感领域研究的热点，但与图像融合串行算法发展相比，并行算法的研究相对滞后。目前，无论是经典的IHS、PCA及DWT等像素级融合算法的并行化，还是后来提出的PACWT算法［26，27］，其并行模式基本是数据并行的方式，区别在于有的采用了水平数据划分方法，有的采用了可避免无效数据通信的冗余数据划分方法。理想的并行算法要做到各进程间尽可能少甚至没有通信，图像融合的并行计算还应从图像融合的基本原理上进行并行化，这样才能使并行算法的效率更理想。

虽然栅格数据的并行化适合采用数据并行的模式，但并不意味着其他并行模式没有引起关注。在并行图像分类算法中，Gursory提出了一种算法并行的计算模式［28］，获得了良好的加速比，只是在分类精度上有所损失。此外，GPU计算也被引入栅格数据的空间分析中。GPU可以看作SIMD并行流式处理器，并行性和灵活的可编程性使它可以完成图形绘制以外的计算任务。而且，与CPU相比，GPU更适合并行流处理，很多栅格分析算法已利用GPU进行了并行化。杨靖宇等基于GPU以流水线并行模式实现了影像SAM分类算法的并行化［29］;卢俊等利用GPU的可编程渲染器和其处理数据的并行性，将影像融合的IHS算法映射到GPU中进行计算［30］;在距离量测方面，Majdandzic等设计了一种基于GPU生成离散点Voronoi图的栅格算法，首先根据特定的分辨率确定像元的数目，然后对每个生成元指定一个颜色，通过大量的处理单元并行量测每个像元到生成元的距离，赋予每个像元距其最近生成元的颜色［31］;采用类似思路，Rong等设计了一种基于GPU的Delaunay三角网生成算法［32］。

3 评述与讨论

受空间数据自身特殊性的影响，目前并行GIS空间分析方法的探索方向主要有两个。其一是对现有的计算密集型空间操作实现并行化处理，关注的人相对较多。目前，空间分析算法的并行化大多采用数据并行的方式，通过将划分后的数据发送到并行计算环境中的各个计算节点参与并行运算，将计算结果组合得到最终结果。其他并行模式的应用相对较少，但一些学者的研究为其发展奠定了基础。第二个方向致力于利用额外的计算能力开创新型空间分析算法，如利用GPU的并行特性研究地图渲染与显示技术等。沿着这两个方向，并行空间分析算法的研究已取得一些成果，也暴露出一些新的问题：1）地理空间数据作为大规模数据集上的复杂变量，在很大程度上影响了处理器间的负载平衡，大量数据的I/O操作仍是难以克服的瓶颈;2）目前的并行算法研究大多集中在数据并行的模式，需要对空间数据进行处理前的划分与处理后的合并，但是当前对数据划分算法的研究较多，而数据合并同样也是一个难题（尤其是对矢量拓扑数据的合并），需要进行更深入的研究;3）由于以往数据存储与管理方式及空间索引机制等方面的限制，使算法的并行设计容易破坏空间实体的完整性和一致性，导致空间数据存取与处理操作的不精确与不完整;4）基于GPU的并行计算在细粒度的像素级数据并行问题中有明显优势，但在进行一些复杂的栅格空间分析操作时受到限制，而且采用GPU计算时，数据加载与结果反馈需额外耗费一定时间，制约了它的处理速度。

除了GIS数据本身特殊性外，并行GIS空间分析算法的研究还受到计算机硬件和软件等具体环境的影响。20世纪90年代以前，由于并行机的成本过高，并行计算在GIS领域的应用研究进展较缓慢。随着众核和多核计算机、分布式计算机及并行数据库、空间分析并行库等的发展，大大推动了并行空间分析算法的研究，且它们与GIS的结合还出现了若干新的发展，如并行空间数据库及并行空间索引技术、多核体系下的并行GIS计算、网格GIS与云计算等，这对于并行GIS空间分析算法研究既是一个机遇，也是一个挑战。一方面，优越的空间数据存储方式和计算环境能够在很大程度上增加并行计算所能处理的地理空间数据量，提高并行空间数据处理的效率。另一方面，如何充分利用高效的计算资源以构建良好的并行GIS设计环境、开发配套的并行GIS算法、应用库和工具包又是一项艰巨任务。面对机遇与挑战，并行GIS空间分析算法的发展应致力于充分利用并行计算环境提供的强大的计算能力，设计高效率的空间数据库，开发高性能并行算法，实现矢量和栅格数据的并行处理，以期最终能够形成可部署于并行计算环境中的并行GIS软件包。

4 结语

并行空间分析算法是GIS空间分析算法与并行计算技术的结合，空间数据区别于一般数据的复杂性使空间分析算法的并行化具有一定的难度，经过近几十年发展，针对矢量数据和栅格数据的并行算法研究都取得了较大的成就。本文在回顾前人研究的基础上，重点阐述了并行空间分析算法的研究进展，探讨了GIS数据特殊性和计算机软硬件对算法研究的影响及研究中存在的问题。随着计算机硬件水平的发展以及空间分析算法和并行计算理论与实践的不断完善，并行空间分析算法的研究将得到更广泛的重视，并极大地推动GIS技术与应用的发展。

［1］刘湘南，黄方.GIS空间分析原理与方法［M］.北京：科学出版社，2005.32－35.

［2］张波林，迟学斌.并行计算导论［M］.北京：清华大学出版社，2006.3－6.

［3］陈国良.并行计算：结构·算法·编程［M］.北京：高等教育出版社，2003.4－7.

［4］戴波.并行算法及其应用［D］.电子科技大学，2002.16－19.

［5］王欢，都志辉.并行计算模型对比分析［J］.计算机科学，2005，32（12）：142－145.

［6］张丽丽.支持空间分析的并行算法的研究与实现［D］.南京航空航天大学，2008.2－4.

［7］赵春宇.高性能并行GIS中矢量空间数据存取与处理关键技术研究［D］.武汉大学，2006.70－76.

［8］贾婷，魏祖宽，唐曙光，等.一种面向并行空间查询的数据划分方法［J］.计算机科学，2010，37（8）：198－200.

［9］MENG L K，HUANG C Q，ZHAO C Y，et al.An improved Hilbert curve for parallel spatial data partitioning［J］.Geo-spatial Information Science，2007，10（4）：282－286.

［10］刘润涛，安晓华，高晓爽.一种基于R－树的空间索引结构［J］.计算机工程，2009，35（23）：32－34.

［11］KAMEL I，FALOUTSOS C.Hilbert R-tree：An improved rtree using fractals［A］.Proceedings of the 20th VLDB Conference Santago，Chile［C］.1994.

［12］张三元，马利庄.平面散乱点集凸包并行算法［J］.浙江大学学报（工学版），1999，33（4）：432－435.

［13］郝小柱，胡祥云，戴光明，等.平面点集凸包的并行算法研究［J］.计算机应用，2005，25（10）：2462－2464.

［14］易法令，李庆华，杨薇薇.Delaunay三角剖分并行算法研究及实现［J］.小型微型计算机系统，2001，22（4）：450－452.

［15］卢照，师军.并行最短路径搜索算法的设计与实现［J］.计算机工程与应用，2010，46（3）：69－71.

［16］隽志才，倪安宁，贾洪飞，等.两种策略下的最短路径并行算法研究与实现［J］.系统工程理论方法应用，2006，15（2）：123－127.

［17］姚艺强，高劲松，孟令奎，等.网格环境下缓冲区分析的并行计算［J］.地理空间信息，2007，5（1）：98－101.

［18］李峙，陈朝晖.空间叠加分析中的分而治之算法研究与应用［J］.计算机工程与应用，2009，45（34）：230－232.

［19］BATCHER K.Design of a massively parallel processor［J］.IEEE Transaction on Computers，1980，29（9）：836－840.

［20］KAZHDAN M，HOPPE H.Streaming multigrid for gradientdomain operations on large images［J］.ACM Transactions on Graphics，2008，27（3）：1－10.

［21］黄杏元，马劲松.地理信息系统概论（第三版）［M］.北京：高等教育出版社，2008.80－89.

［22］蒋艳凰，杨学军，易会战.卫星遥感图像并行几何校正算法研究［J］.计算机学报，2004，27（7）：944－951.

［23］欧新良，陈松桥，常志明.基于动态分界点计算的并行几何校正算法［J］.计算机研究与发展，2006，43（6）：1115－1121.

［24］刘晓沐，岳丽华，陈博，等.遥感图像目标识别的并行处理方法［J］.计算机应用，2007，27（9）：2123－2125.

［25］蒋利顺，刘定生.遥感图像K-Means并行算法研究［J］.遥感信息，2008（1）：27－30.

［26］胡冰.遥感图像融合并行算法的研究及实现［D］.国防科技大学，2006.9－40.

［27］王攀峰，杜云飞，周海芳，等.基于复小波变换的遥感图像并行融合算法［J］.计算机工程与科学，2008，30（3）：35－39.

［28］GURSORY A.Data decomposition for parallel K-Means clustering［J］.Parallel Processing and Applied Mathematics，2004，14（4）：241－248.

［29］杨靖宇，张永生，董广军.基于GPU的遥感影像SAM分类算法并行化研究［J］.测绘科学，2010，35（3）：9－11.

［30］卢俊，张保明，黄薇，等.基于GPU的遥感影像数据融合HIS变换算法［J］.计算机工程，2009，35（7）：261－263.

［31］MAJDANDZIC I，TREFFZ C，WOLFFE G.Computation of Voronoi diagrams using a graphics processing unit［A］.IEEE International Conference on Electro/Information Technology［C］.2008.437－441.

［32］RONG G D，TAN T S，CAO T T.Computing two-dimensional Delaunay triangulation using graphics hardware［A］.Symposium on Interactive 3D Graphics and Games［C］.2008.89－97.

Review on Parallel Spatial Analysis Algorithms

WANG Jie－chen，WANG Bao，HU Wei，ZHANG Hui
（DepartmentofGeographicInformationScience，NanjingUniversity，Nanjing210093，China）

As one of the core functions of GIS，spatial analysis aims at processing massive data and analyzing more complicated phenomena.However，previous sequential algorithms couldn′t meet the needs of spatial analysis in terms of processing speed，computing efficiency and so on.So parallel spatial analysis algorithms，as an effective way to solve the current problems，have

more and more attention.On the basis of introducing spatial analysis and parallel computation，the main attention was focused on elaborating the progress of study on parallel spatial analysis algorithms from two major aspects：parallel vector algorithms and parallel raster algorithms.Further，under the influencing of the spatial data′s self particularities，the development of parallel spatial analysis algorithms and its remaining problems are concisely reviewed.Last，the opportunities and challenges of the study encountered in the context of the rapid development of computer hardware and software technology are also discussed.

parallel computation;spatial analysis;parallel GIS

P208

A

1672－0504（2011）06－0001－05

2011－05- 18;

2011－08－22

江苏高校优势学科建设工程资助项目;国家基础科学人才培养基金能力提高项目（J0830518）

王结臣（1973－），男，博士，教授，主要从事地理信息系统理论与应用研究。E－mail：hotmailwang＠yahoo.com.cn