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 并行可視性分析

可視性分析也稱通視分析，實質上是對地形進行最優化處理的范疇?？梢曅苑治龅幕疽蜃佑袃牲c之間的通視性和可視域計算?；谝巹t格網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］。盡管傳統的并行算法在計算能力方面有了一定的改進，但負載均衡問題一直未得到較好的解決。在新型高性能計算系統中，高通量計算有望取得更高的吞吐能力和效能?；诜炙畮X邊界對DEM進行數據劃分，以小流域為并行計算的基本單位，可有效地保證流域拓撲關系的提?。?2］。成熟的機群作業系統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