DEM与地形分析的并行计算

宋效东，刘学军，汤国安＊，王永君，田 剑，2，窦万峰

（1.南京师范大学虚拟地理环境教育部重点实验室，江苏南京210046；2.合肥工业大学资源与环境工程学院，安徽合肥230009；3.南京师范大学计算机科学学院，江苏南京210046）

DEM与地形分析的并行计算

宋效东1，刘学军1，汤国安1＊，王永君1，田 剑1，2，窦万峰3

（1.南京师范大学虚拟地理环境教育部重点实验室，江苏南京210046；2.合肥工业大学资源与环境工程学院，安徽合肥230009；3.南京师范大学计算机科学学院，江苏南京210046）

总结了数字高程模型构建、特征提取等并行算法的研究进展，概述了不同并行算法的主要内容；探讨了DTA并行技术在海量地形数据可视化和高性能地学计算的应用，随着DEM的需求日益增大，高精度、高分辨率DEM产品及其附加服务也逐步产品化。最后，通过分析并行计算发展的关键问题，提出DTA并行技术的研究趋势及研究意义，合适的数据划分和结果融合策略、通用并行算法、容错机制和负载均衡策略的设计是今后研究的重要内容，尤其是如何在多种计算模式共同发展的背景下利用并行计算解决地学难题，从而得到更接近现实世界地理环境的模拟，并扩大数字地形分析的应用范围。

数字高程模型；数字地形分析；并行计算；进展

0 引言

数字地形分析（Digital Terrain Analysis，DTA）是在数字高程模型（Digital Elevation Model，DEM）上进行地形属性计算和特征提取的数字信息处理技术［1］，理论研究主要集中在空间数据获取、DEM预处理、地形分析算法的研究和误差分析等方面［2］。各种新型传感器获取DEM技术的出现，使DEM数据量呈几何级数增长，DEM基础数据呈现多比例尺、多分辨率的系列化特征，网络通讯技术的发展促进了各类DEM强烈的共享需求。尽管现有基于DEM的地形分析理论与方法趋于成熟，但如何使用传统的串行算法实现海量数据的高效处理，是DEM广泛应用亟待解决的关键问题，也是国内外相关领域研究的重要课题。

随着硬件技术和新型应用的不断发展，并行计算系统得到快速发展，如多核体系结构的发展［3，4］、云计算模式出现、GPU软硬技术的延伸［5，6］，为并行计算的广泛应用提供不可或缺的支持。近年来，海量空间数据分析不断增长的计算需求以及高性能地学应用需求的推动，使得并行地形分析成为高性能地学计算发展的重要趋势［7，8］。

纵观40余年数字地形分析的发展，尽管其理论与技术都有了一定的突破，但随着其应用领域的推广，仍存在很多有待于深入研究的问题，如并行计算模式与数字地形分析的融合问题、如何根据不同的地形分析算法设计适合具体硬件环境的算法体系以及如何适应计算机硬件发展环境等。本文总结了近年来一些具有代表性的数字地形分析并行算法，结合高性能地学计算的最新研究进展，着重分析了目前仍然存在的问题及解决问题的关键技术，并展望了前沿的进展情况和未来的研究方向。

1 并行构建DEM技术研究进展

DEM的建立是一种地形数据的建模过程。DEM数据组织方式有规则格网结构（grid）、不规则三角网结构（TIN）和等高（值）线结构，其中规则格网DEM和不规则三角网TIN是目前数字高程模型的两个主要数据模型。尽管众多学者对各种DEM构建技术做了不同方面（算法、I／O接口）的改进［9－12］，但在单机环境下对海量的空间数据进行快速处理仍十分困难，而借助并行计算技术可提高数据处理效率［13－17］。并行构建DEM的研究主要集中在：并行构建规则格网DEM、并行提取等高线［16］、并行生成不规则三角网等。

1.1 并行构建格网DEM

由于空间数据源的多样性与数据量巨大，空间数据内插算法的计算量也随之增大。内插算法的并行化是构建规则格网DEM的重要研究内容［13－19］，如按块进行分布式管理［20，21］、基于对象的存储方式［22，23］，采用并行计算策略能有效提升其处理效率［24，25］。鉴于DEM数据密集的特点，内插算法的并行化研究主要采用数据并行策略与主从的计算模式［26］。其中，反距离加权插值算法（IDW）在不同并行环境中的研究较多［17，18，25］，Armstrong等研究了IDW内插算法在MIMD环境下的并行化［13］，采用SIMD架构并对比不同的计算模式，给出IDW算法的不同实现方法和空间自适应并行化方法［14，15］；其他算法有逐行内插的并行IDW算法［18］、自适应方差图拟合算法［26］、基于四叉树的域分割算法［17］等。在异构网格计算环境下，针对分布式的数据集，四叉树的域分解算法和任务管理算法可以有效管理不规则的数据集合［17］。

空间数据采集技术的迅速发展为规则格网DEM快速构建提出了新的挑战。在处理大量高密度和高精度的激光点云数据过程中，I／O处理成为系统性能提升的瓶颈。虽然众多学者对I／O处理算法［11］进行了改进，然而由于串行算法的局限性，处理时间仍不能满足具体的应用要求，并行I／O的设计仍是热点研究问题。尽管单核CPU的计算能力已有大幅度的提升，但其处理能力几乎达到了物理极限，很难有较大的提升空间，多核技术则为此提供了新的计算模式。有学者研究如何利用多核技术将点云数据分割为部分重叠的块状区域，各数据块采用流水线技术并行内插［25］，这些问题将是未来DEM构建的重要研究内容。

1.2 并行生成不规则三角网

常规构建散点域三角网的较为广泛算法是Delaunay直接三角剖分算法。根据Delaunay三角网构建过程的不同，生成Delaunay三角网的思想主要有分割合并、三角网增长和逐点插入［27］。

不规则三角网的计算较复杂，许多研究者希望利用并行计算提高三角剖分的效率。传统的解决策略是采用共享内存数据的方式［28，29］，对串行的三角网生成算法进行并行化改造。Huang等［30］提出了重排序算法以减少三角剖分过程中的操作，该算法可以推断计算问题的最长时间下限，并利用同等调度算法实施调度操作，对实时性要求较高；为解决不同处理器对共享内存的访问冲突问题，该算法采用了缓冲区存储数据策略，导致其不适宜处理海量的空间数据。考虑到这一问题，Merks［31］采用同时读／排斥写模型（CREW PRAM），以解决计算结点对共享内存数据的读写问题，通过分割合并将计算数据分解为各子块进行并行计算，其时间复杂度和空间复杂度分别为O（log n）和O（n）。

Delaunay三角剖分并行算法的实现主要集中在集群计算环境下［32－35］，该类并行算法关注三角网生成、分割等问题，如四点共圆的不唯一性及并行处理边界的任意性问题［33］；当合并两个子块三角形时，提取被修改的三角划分区域可以减少处理器之间的通信次数［34］。Kohout［35］等针对随机增量插入点的Delaunay串行算法进行了并行化改造，并从2维、3维角度分析了乐观算法、悲观算法等的计算效率。

提高凸壳计算速度是很多学者进行三角剖分算法设计的预期目标［36，37］，Amato算法［36］将凸壳计算的复杂度降至O（log n）。Lee等［37］提出改进的Delaunay并行剖分算法，通过增量构建的方法，在每个区域中使用Delaunay边界和生成的Delaunay三角形，对凸壳边界区域进行剖分；由于每个计算结点的边界线均已确定，计算结果的融合简单易行，且计算效率较高。面对多计算结点，还需进一步考虑所产生的负载均衡问题。

2 并行地形分析算法研究进展

数字地形分析并行计算具有数据密集和计算密集的特征，需要考虑任务并行、算法并行、数据并行等问题。针对海量高分辨率DEM数据，如何快速提取地形属性信息和地形特征并将其转化为能直接应用的信息，已成为数字地形分析研究迫切需要解决的问题。目前，这方面的研究主要集中在算法复杂度较高或全局性算法方面，在可视性分析和流域提取中的研究较多。

2.1 并行可视性分析

可视性分析也称通视分析，实质上是对地形进行最优化处理的范畴。可视性分析的基本因子有两点之间的通视性和可视域计算。基于规则格网DEM的可视域算法在GIS分析中应用较广，研究以规则格网DEM为主，基于TIN的可视域分析稍有涉及［38］。在规则格网DEM中，可视域经常是以离散的形式表示，将每个格网点表示为可视或不可视，即可视矩阵。一种简单的计算基于规则格网DEM可视域的方法就是沿着视线的方向，从视点开始到目标格网点，计算与视线相交的格网单元并判断该单元是否可视，从而确定视点与目标视点之间是否可视。学者们利用SIMD并行架构对通视分析和可视域算法的并行化设计进行了深入研究［39－41］，对点到区域、点到点的视线进行并行处理。典型的并行可视域算法是分别计算观察点到目标区域内每个高程点的可视性，高程矩阵每个点的计算被分配给一个计算单元，每个计算单元将计算结果返回到格网单元内，同时，采用互斥机制避免了共享内存中同时读写问题［39］。由于高分辨率大尺度DEM数据的可视性分析算法计算量巨大，Mills等对串行的点到点的通视算法进行并行化，对源区域的每个视点的视线进行并行处理，减少了不同处理器之间的全局通信［40］。

MIMD并行架构下的可视性分析也有大量研究［42－44］，可视性算法在并行工作站集群中的数据并行策略及性能也有研究［42，43］。完整可视性数据库（CID）［44］存储了DEM中每个点的可视域，并采用任务重提交进行容错处理。并行可视性分析也涉及其他应用［45，46］，如处理基于TIN的最短路径寻找问题［46］、最优选址问题［45］。Kidner等［46］提出一种反向的并行可视性分析算法，在各计算结点采用传统的通视算法，计算区域－区域的可视性，有效利用了各计算结点的计算能力并取得较优的加速比。

2.2 并行流域提取

DEM在水文分析中的应用一直是研究的热点，尤其是基于DEM提取流域河网算法的并行化设计。由于DEM数据量的剧增和水文算法全局依赖的计算复杂性，串行计算模式难以解决高计算量和高复杂性并存的难题。

流域网络提取工作主要包括：DEM数据预处理（伪洼地填充）、生成流向、提取水流累积矩阵、设置临界集水面积阈值提取河网水系。由于流域提取涉及任务间的约束关系、节点间负载均衡与流域网络的拓扑关系等问题，并行流域提取成为研究热点。早期的并行流域网络提取主要是基于SIMD并行架构［47，48］，对流域提取算法并行化问题提出不同的解决方案。Mower［47］选取流域提取建模的性能统计量，比较了功能并行策略和数据并行策略的性能，验证了并行算法的可行性。尽管基于行分割的数据并行策略取得较好的负载均衡，但通信代价过高，相比通过文件和顺序切割DEM数据的并行策略其总体性能不理想。内存共享的并行架构下处理流域提取中的全局迭代，需要合理地处理结点间的任务依赖关系，否则，异步操作成为并行算法性能提升的瓶颈［48］。部分学者利用图理论，并行生成最小流向树［49］，避免DEM预处理时大量的填洼运算。

近年来，分布式并行计算模式推动了高性能水文分析的发展［50－53］，如径流模拟［54］、湍流模拟［55，56］和洪水预测［57］等。不同于共享内存架构，分布式并行计算中需要解决数据分发、低通信效率、计算进程调度与结果融合等问题。例如，汇流累积量的计算需要确保每个格网单元至少被访问一次［51］；对各进程实时监控以减少进程间通信消耗，也是提升大尺度流域水文并行计算效率的有效途径［58］。尽管传统的并行算法在计算能力方面有了一定的改进，但负载均衡问题一直未得到较好的解决。在新型高性能计算系统中，高通量计算有望取得更高的吞吐能力和效能。基于分水岭边界对DEM进行数据划分，以小流域为并行计算的基本单位，可有效地保证流域拓扑关系的提取［52］。成熟的机群作业系统Condor软件可用来控制任务队列的调度，有效地避免不同数据分割粒度造成的计算异步问题。GPU在计算能力和存储器访问带宽上具有优势［59，60］，基于CUDA的并行流域网络提取算法，可以执行计算量更大的矩阵相乘运算，采用优化的归并排序算法及内存分配策略，从而提供了适合现代计算机基于GPU的水文分析解决方案。

3 并行数字地形分析的应用

3.1 海量数据的地形可视化

数字地形分析中可视化分析的重点在于地形特征的可视化表达和信息增强，从而表达地形曲面参数、地表形态特征和复合地形属性的信息。目前主要基于TIN模型实现地形可视化，这类算法通常比较复杂，剖分的粒度较小。地形可视化的主要研究内容有：自适应地表模型建立方法、地形简化模型的误差标准、空间连续性、数据压缩与离核绘制［61，62］。传统的桌面系统难以满足对与日俱增的DEM数据实时可视化分析的需求，有效方法是并行处理［63，65］。并行计算在地形可视化算法领域中研究较多［66］，如并行绘制、高分辨率显示墙系统等［64］。

海量数据的并行可视化技术在地学分析中的应用可以较好地满足数据分析的要求，高分辨的并行显示技术有助于深入观察试验结果的细节。图形硬件技术的发展要求基于大规模地形数据的可视化算法重新设计，以期充分发挥CPU与GPU的宽带通信优势。另外，如何利用硬件可编程语言将部分算法高效地移植到GPU上顺利执行，仍需进一步研究，实时动态的大规模地形可视化技术也将是今后研究的重要内容之一。

3.2 高性能地学计算

高性能地学计算实现了地理环境中全球性或大区域性以时空演变为特征的地理现象（如数值天气预报、全球气候变化、地理信息系统等）模拟。地学领域中的并行算法研究和应用层出不穷，在面向大尺度地形研究方面，如天气预测［67，68］①enviroGRIDS项目：http：／／www.envirogrids.net.②ALADIN，高分辨率数值天气预报项目：http：／／www.cnrm.meteo.fr／aladin.、石油勘探［69，70］、灾害预测［71，72］③天气研究预测模型：http：／／www.wrf－model.org／index.php.大地震动模拟［73］、海洋波浪模拟［74］等。

随着高精度、高分辨率的DEM产品逐步产业化，除提供常规的DEM产品外，还需要提供DEM数据增值服务。数字地形分析并行技术所提供的高性能计算能力可以很好地实现DEM服务的增值［23，45］和灾害预报［57，72］等功能。然而，目前大多数的实际应用仍停留在“数据”层面，忽视了对数据内容的挖掘与信息的提取，难以实现较高的数据应用效益和空间数据增值。因此，亟须利用地形分析并行技术，从DEM数据中提取实际应用的地形参数和地形特征信息，提升高性能地学计算中空间数据增值服务的质量。

4 讨论与展望

数字地形分析并行技术的发展与并行计算密切相关，各种分析算法必须适应复杂的计算环境。随着数字地形分析内涵的不断深化和应用的日趋广泛，高性能计算技术的发展与普及将把数字地形分析推向一个全新的应用水平。另外，数字地形分析的发展也为高性能地学应用提供了新的驱动力和应用背景。其可能的发展趋势和需要探索的方向包括：

（1）数据划分策略。不同的数据划分策略对数字地形分析并行算法的设计具有不同的影响，这需要选择最优的划分策略来解决地形特征的影响，以适应不同的并行计算环境。针对以数据密集为特征的并行计算，准确处理具有依赖关系的数据和数据之间的操作，解决全局性算法的分布式并行实现和不规则对象的规则划分，实现简单高效地管理数据将是研究的重点。地形数据的串行预处理和后处理也是性能提高的重要制约因素。

（2）计算结果的并行融合处理。分析单元间的区域相关是数字地形分析的基本特征。对于具有确定相关半径的数据并行单元，结果融合主要是接边操作；对于相关半径强烈依赖于相邻单元内地形特征的并行分析单元［53］或算法之间存在相互依赖，需要设计高耦合度的结果融合策略，但设计过程应避免频繁的融合操作。

（3）通用并行算法设计问题。理论上，并行程序在不同体系结构的平台上应可移植，但可移植性通常伴随着性能的降低。只有考虑到体系结构特征，并行算法的性能才能达到最优。不同的并行计算模型以及处理器个数、带宽、存储性能的不同，造成了算法在不同平台上使用时不能达到期望值。更严峻的是，在转向不同的体系结构时，不仅程序员需要移植现有的应用程序，研究人员也需要选择或设计相应的算法及子过程。

（4）负载均衡策略。为了提高系统资源利用率和并行计算的性能，尤其是在异构集群环境中，各结点的性能有所不同，应选择适当的计算结果集合的级别以充分利用系统资源。如何兼顾负载均衡度和同步开销以提高整体的计算性能，尚需进一步研究。

（5）容错问题。并行算法的设计还应考虑合适的容错机制，在高效加速故障恢复的同时降低容错开销，保证计算性能的同时尽可能提高系统可靠性，以满足应用的需要。容错技术的引入不可避免地带来一定程度的冗余计算。为了避免重构计算资源并重启计算的故障恢复，大规模并行系统需要在检测到故障之后，恢复故障进程上的计算状态。

［1］ 周启鸣，刘学军.数字地形分析［M］.北京：科学出版社，2007.

［2］ WILSON J P.Digital terrain modeling［J］.Geomorphology，2012，137（1）：107－121.

［3］ ASANOVIC K，BODIK R，CATANZARO B C，et al.The Landscape of Parallel Computing Research：A View from Berkeley［R］.Tech.Report UCB／EECS－2006－183，USA，2006.

［4］ 陈国良，孙广中，徐云，等.并行计算的一体化研究现状与发展趋势［J］.科学通报，2009，54（8）：1043－1049.

［5］ XIA Y，LI Y，SHI X.Parallel Viewshed Analysis on GPU using CUDA［A］.Third International Joint Conference on Computational Science and Optimization［C］，Huangshan（Yellow）Mountain，Anhui，China，2010.373－374.

［6］ CERVENANSKY M，TOTH Z，STARINSKY J et al.Parallel GPU－based data－dependent triangulations［J］.Computers ＆Graphics，2010，34（2）：125－135.

［7］ BUYYA R，ABRAMSON D，GIDDY J.An economy driven resource management architecture for global computational power grids［A］.The 2000 International Conference on Parallel and Distributed Processing Techniques and Applications（PDPTA 2000）［C］.Las Vegas，USA，2000.

［8］ LECCA G，PDTITDIDIER M，HLUCHY L，et al.Grid computing technology for hydrological applications［J］.Hydrology，2011，403（1－2）：186－199.

［9］ WEGMULLER U，SANTORO M，WERNER C，et al.DEMgeneration using ERS－ENVISAT interferometry［J］.Applied Geophysics，2009，69（1）：51－58.

［10］ ARDIANSYAH P O D，YOKOYAMA R.DEM generation method from contour lines based on the steepest slope segment chain and a monotone interpolation function［J］.ISPRS Journal of Photogrammetry and Remote Sensing，2002，57（1－2）：86－101.

［11］ AGARWAL P，ARGE L，DANNER A.From point cloud to grid DEM：A scalable approach［A］.Proceedings of the 12th International Symposium on Spatial Data Handling［C］.Vienna，Austria，2006.771－788.

［12］ 胡金星，吴焕萍，潘懋，等.基于格网划分的海量DEM数据生成［J］.计算机辅助设计与图形学学报，2004，16（1）：41－44.

［13］ ARMSTRONG M P，MARCIANO R.Parallel spatial interpolation［A］.Proceedings of the Eleventh International Symposium on Computer－Assisted Cartography（Auto－Carto 11）［C］.Minneapolis，USA，1993.414－423.

［14］ ARMSTRONG M P，MARCIANO R.Massively parallel strategies for local spatial interpolation［J］.Computers ＆Geosciences，1997，23（8）：859－867.

［15］ ARMSTRONG M P，MARCIANO R.Local interpolation using a distributed parallel supercomputer［J］.International Journal of Geographical Information Systems，1996，10（6）：713－729.

［16］ DEPAK P，KUMAR K P，VARADAN G.A service oriented utility grid for data parallel remote sensing applications［A］.HPCS 2009（International Conference on High Performance Computing ＆Simulation）［C］.Leipzig，Germany，2009.131－137.

［17］ WANG S，ARMSTRONG M P.A quadtree approach to domain decomposition for spatial interpolation in Grid computing environments［J］.Parallel Computing，2003，29（10）：1481－1504.

［18］ HUANG F，LIU D，TAN X，et al.Explorations of the implementation of a parallel IDW interpolation algorithm in a Linux cluster－based parallel GIS［J］.Computers ＆Geosciences，2010，37（4）：426－434.

［19］ MA H，WANG Z.Distributed data organization and parallel data retrieval methods for huge laser scanner point clouds［J］.Computers ＆Geosciences，2011，37（2）：193－201.

［20］ 刘家宏，王光谦，王开.大流域数字高程模型数据管理系统［J］.清华大学学报（自然科学版），2004，44（12）：1646－1649.

［21］ 温菊屏.大规模地形漫游系统关键技术的研究［J］.计算机与数字工程，2009，37（1）：47－50.

［22］ 王晨，周颖，张德富.一种并行分布对象的互操作模型［J］.软件学报，1999，10（8）：861－867.

［23］ 郑胜，喻占武，李忠民.基于OBS的分布并行海量地形数据服务系统［J］.计算机工程，2008，34（5）：71－73.

［24］ STOOKEY J，XIE Z，CUTLER B，et al.Parallel ODETLAP for Terrain compression and reconstruction［A］.16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems（ACM GIS 2008）［C］.Irvine，USA，2008.

［25］ GUAN X，WU H.Leveraging the power of multi－core platforms for large－scale geospatial data processing：Exemplified by generating DEM from massive LiDAR point clouds［J］.Computers＆Geosciences，2010，36（10）：1276－1282.

［26］ PESQUER L，CORTES A，PONS X.Parallel ordinary kriging interpolation incorporating automatic variogram fitting［J］.Computers ＆Geosciences，2010，37（4）：464－473.

［27］ 余杰，吕品，郑昌文.Delaunay三角网构建方法比较研究［J］.中国图象图形学报，2010，15（8）：1158－1167.

［28］ 张明敏，潘志庚，郑文庭，等.散乱点集Delaunay三角剖分的分布并行算法［J］.计算机辅助设计与图形学学报，2000，12（7）：484－487.

［29］ KOHOUT J，KOLINGEROVA I，ZARA J.Practically oriented parallel Delaunay triangulation in E2 for computers with shared memory［J］.Computers ＆Graphics，2004，28（5）：703－718.

［30］ HUANG J，WING O.Optimal parallel triangulation of a sparse matrix［J］.IEEE Transactions on Circuits and Systems，1979，26（9）：726－732.

［31］ MERKS E.An optimal parallel algorithm for triangulating a set of points in the plane［J］.International Journal of Parallel Programming，1986，15（5）：399－411.

［32］ WU H，GUAN X，GONG J.ParaStream：A parallel streaming Delaunay triangulation algorithm for LiDAR points on multicore architectures［J］.Computers ＆Geosciences，2011，37（9）：1355－1363.

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

［34］ CHEN M B，CHUANG T R，WU J J.A parallel divide－andconquer scheme for Delaunay triangulation［A］.Ninth International Conference on Parallel and Distributed Systems［C］.Taiwan，China，2002.571－576.

［35］ KOHOUT J，KOLINGEROVA I，ZRAR J.Parallel Delaunay triangulation in E2 and E3 for computers with shared memory［J］.Parallel Computing，2005，31（5）：491－522.

［36］ AMATO N M，PREPARATA F P.An NC parallel 3Dconvex hull algorithm［A］.Proceedings of the Ninth Annual Symposium on Computational Geometry［C］.San Diego，USA，1993.289－297.

［37］ LEE S，PARK C I，PARK C M.An Improved parallel algorithm for Delaunay triangulation on distributed memory parallel computers［A］.Proceedings of Advances in Parallel and Distributed Computing（APDC）［C］.Shanghai，China，1997.131－138.

［38］ FLORIANI L D，MONTANI C，SCOPIGNO R.Parallelizing visibility computations on triangulated terrains［J］.International Journal of Geographical Information Systems，1994，8（6）：515－531.

［39］ TENG Y A，DEMENTHON D，DAVIS L S.Stealth terrain navigation［J］.IEEE Transactions on Systems，Man，and Cybernetics，1993，23（1）：96－110.

［40］ MILLS K，FOX G，HEIMBACH R.Implementing an intervisibility analysis model on a parallel computing system［J］.Computers ＆Geosciences，1992，18（8）：1047－1054.

［41］ GERMAIN D，LAURENDEAU D，VEZINA G.Visibility analysis on a massively data－parallel computer［J］.Concurrency：Practice and Experience，1996，8（6）：475－487.

［42］ RALLINGS P J，WARE J A，KIDNER D B.Parallel distributed processing for digital terrain analysis［A］.Proceedings of the 3rd International Conference on GeoComputation［C］.Bristol，United Kingdom，1998.

［43］ WARE J A，KIDNER D B，RALLINGS P J.Parallel distributed viewshed analysis［A］.Proceedings of the 6th ACM International Symposium on Advances in Geographic Information Systems［C］.Washington，USA，1998.151－156.

［44］ MINETER M J，DOWERS S，CALDWELL D R，et al.Highthroughput computing to enhance intervisibility analysis［A］.Proceedings of the 7th International Conference on GeoComputation［C］.Southampton，United Kingdom，2003.

［45］ LANTHIER M，NUSSBAUM D，SACK J R.Parallel implementation of geometric shortest path algorithms［J］.Parallel Computing，2003，29（10）：1445－1479.

［46］ KIDNER D B，RAILINGS P J，WARE J A.Parallel processing for terrain analysis in GIS：visibility as a case study［J］.Geoinformatica，1997，1（2）：183－207.

［47］ MOWER J E.Data－parallel procedures for drainage basin analysis［J］.Computers ＆Geosciences，1994，20（9）：1365－1378.

［48］ CLEMATIS A，CODA A，SPAGNUOLO M.Developing Non－Local Iterative Parallel Algorithms for GIS on a Workstation Network［A］.Proceedings of the Sixth Euromicro Workshop on Parallel and Distributed Processing［C］.Madrid，Spain，1998.250－256.

［49］ DO H T，LIMET S，MELIN E.Parallel Computing of Catchment Basins of Rivers in Large Digital Elevation Models［A］.2010 International Conference on High Performance Computing and Simulation（HPCS）［C］.Caen，France，2010.39－47.

［50］ WALLIS C，WALLACE R，TARBOTON D G，et al.Hydrologic Terrain Processing Using Parallel Computing［A］.18th World IMACS／MODSIM Congress［C］.Cairns，Australia，2009.

［51］ WALLIS C，WATSON D，TARBOTON D G，et al.Parallel Flow－Direction and Contributing Area Calculation for Hydrology A－nalysis in Digital Elevation Models［A］.PDPTA2009（The 2009 International Conference on Parallel and Distributed Processing Techniques and Applications）［C］.Las Vegas，USA，2009.

［52］ GONG J，XIE J.Extraction of drainage networks from large terrain datasets using high throughout computing［J］.Computers ＆Geosciences，2009，35（2）：337－346.

［53］ MUSTAPHA H，GHORAYEB A，MUSTAPHA K A.Underground flow simulations using parallel finite element method［J］.Computers ＆Geosciences，2010，36（2）：161－166.

［54］ TANG G，D＇AZEVEDO E F，ZHANG F，et al.Application of a hybrid MPI／Open MP approach for parallel groundwater model calibration using multi－core computers［J］.Computers ＆Geosciences，2010，36（11）：1451－1460.

［55］ WOODWARD P R，PORTER D H，ANDERSON S E，et al.Parallel computation of turbulent fluid flows with the piecewise－parabolic method［A］.Proceedings of the Parallel CFD 2006 Conference［C］.Busan，Korea，2006.

［56］ WOODWARD P R，PORTER D H，SYTINE I，et al.Very High Resolution Simulations of Compressible，Turbulent Flows［A］.Proceedings of the Fourth UNAM Supercomputing Conference［C］.Mexico City，Mexico，2000.

［57］ KUSSUL N，SHELESTOV A，SKAKUN S.Grid system for flood extent extraction from satellite images［J］.Earth Science Informatics，2008，1（3）：105－117.

［58］ SHANG Y，WU B，LI T，et al.Fault－Tolerant Technique in the Cluster Computation of the Digital Watershed Model［J］.Tsinghua Science and Technology，2007，12（z1）：162－168.

［59］ ORTEGA L，RUEDA A.Parallel drainage network computation on CUDA［J］.Computers ＆Geosciences，2010，36（2）：171－178.

［60］ 赵向辉，苗青，付忠良.基于CUDA的汇流分析并行算法的研究与实现［J］.计算机应用研究，2010，27（7）：2445－2447，2451.

［61］ 孙敏，薛勇，马霭乃.基于格网划分的大数据集DEM三维可视化［J］.计算机辅助设计与图形学学报，2002，14（6）：566－570.

［62］ 张慧杰，孙吉贵，刘雪沽，等.大规模三维地形可视化算法研究进展［J］.计算机科学，2007，34（3）：10－16.

［63］ PORTER D H，WOODWARD P R，IYER A.Initial experiences with grid－based volume visualization of fluid flow simulations on PC clusters［A］.Proceedings of Visualization and Data Analysis 2005（VDA2005）［C］.San Jose，USA，2005.

［64］ 陈绍林，张怀，石耀霖.地学中海量数据的并行可视化研究进展［J］.中国科学院研究生院学报，2008，25（5）：577－584.

［65］ 石教英，金哲凡.并行多边形绘制技术综述［J］.计算机辅助设计与图形学学报，2003，15（6）：637－642.

［66］ VROLIJK B，POST F H.Interactive out－of－core isosurface visualization in time－varying data sets［J］.Computers ＆Graphics，2006，30（2）：265－276.

［67］ BARROS S R M，KAURANNE T.On the parallelization of global spectral weather models［J］.Parallel Computing，1994，20（9）：1335－1356.

［68］ MICHALAKES J，DUDHIA J，GILL D，et al.The weather research and forecasting model：Software architecture and performance［A］.ZWIEFHOFER W，MOZDZYNSKI G.World Scientific，Proceedings of the Eleventh ECMWF Workshop on the Use of High Performance Computing in Meteorology［C］.Reading，UK，2005.156－168.

［69］ COUMOU D，MATTHAI S，GEIGER S，et al.A parallel FEFV scheme to solve fluid flow in complex geologic media［J］.Computers ＆Geosciences，2008，34（12）：1697－1707.

［70］ BUCKER H M，KAUERAUF A I，RASCH A.A smooth transition from serial to parallel processing in the industrial petroleum system modeling package Petro Mod［J］.Computers ＆Geosciences，2008，34（11）：1473－1479.

［71］ XIE J，YANG C，ZHOU B，et al.High－performance computing for the simulation of dust storms［J］.Computers，Environment and Urban Systems，2010，34（4）：278－290.

［72］ SHELESTOV A Y，KUSSUL N N，SKAKUN S V.Grid technologies in monitoring systems based on satellite data［J］.Journal of Automation and Information Sciences，2006，38（3）：69－80.

［73］ FU H，CLAPP R G，LINDTJORN O，et al.Revisiting finite difference and spectral migration methods on diverse parallel architectures.Computers ＆Geosciences，In Press，Corrected Proof，Available online 25 October 2011.doi：10.1016／j.cageo.2011.09.17.

［74］ KASHIYAMA K，SAITOH K，BEHR M，et al.Parallel finite element methods for large－scale computation of storm surges and tidal flows［J］.International Journal for Numerical Methods in Fluids，1997，24（12）：1371－1389.

Abstract：Theory and methodology of Digital Terrain Analysis（DTA）have played key roles in GIS in recent years，and the appearance of parallel computing provides new propositions for DTA.After a detailed analysis of previous researches of many scholars，this paper reviews the evolvement of some major parallel algorithms such as the generalization of Digital Elevation Models（DEMs），calculation of land surface parameters.Meanwhile，the main contents of each parallel algorithm have been summarized.Secondly，the applications of parallel technology of DTA in large－scale data visualization and High Performance Geo－Computation（HPGC）are discussed.With more and more demand of DEM in each area，high－precision and high－resolution DEM productions are becoming industrial.Besides the support of ordinary DEM productions，the added value of DEM service is also needed.At the end，by analyzing the focused issues of the development of parallel computing，this paper proposes the tendency and the significance of future researches：1）Make DTA conform to different computing environment by selecting and devising proper partition strategy of spatial data，and parallelism is restricted to pre－processing and post－processing of large－scale terrain data in serial mode；2）Merge the distributed computing results；3）Design universal parallel algorithm so that it can adapt to various architecture.Furthermore，appropriate fault－tolerant scheme should be considered，which can accelerate the recovery of faults efficiently and reduce the cost of fault－tolerant.To a great extent，dynamic load balancing（DLB）can enhance the efficiency of dynamic and irregular issues in order to resolve a series of problems of terrain analysis；4）Appropriate fault－tolerance and load balancing strategies will be another research topics of this domain.

Key words：Digital Elevation Model；Digital Terrain Analysis；parallel computing；evolvement

Parallel Computing of the Digital Elevation Model and Digital Terrain Analysis

SONG Xiao－dong1，LIU Xue－jun1，TANG Guo－an1，WANG Yong－jun1，TIAN Jian1，2，DOU Wan－feng3
（1.Key Laboratory of Virtual Geographic Environment，Ministry of Education，Nanjing Normal University，Nanjing 210046；2.School of Resources and Environment Engineering，Hefei University of Technology，Hefei 230009；3.School of Computer Science and Technology，Nanjing Normal University，Nanjing 210046，China）

P208

A

1672－0504（2012）04－0001－07

2012－02－22；

2012－03－10

国家863计划资助项目（2011AA120303）；国家自然科学基金项目（41171298、41071244）；资源与环境信息系统国家重点实验室开放基金项目（2010KF0002SA）

宋效东（1986－），男，博士研究生，从事并行计算及高性能GIS研究。＊通讯作者E－mail：tangguoan＠njnu.edu.cn