DEM與地形分析的并行計算

宋效東，劉學軍，湯國安＊，王永君，田 劍，2，竇萬峰

（1.南京師范大學虛擬地理環(huán)境教育部重點實驗室，江蘇南京210046；2.合肥工業(yè)大學資源與環(huán)境工程學院，安徽合肥230009；3.南京師范大學計算機科學學院，江蘇南京210046）

DEM與地形分析的并行計算

宋效東1，劉學軍1，湯國安1＊，王永君1，田 劍1，2，竇萬峰3

（1.南京師范大學虛擬地理環(huán)境教育部重點實驗室，江蘇南京210046；2.合肥工業(yè)大學資源與環(huán)境工程學院，安徽合肥230009；3.南京師范大學計算機科學學院，江蘇南京210046）

總結(jié)了數(shù)字高程模型構建、特征提取等并行算法的研究進展，概述了不同并行算法的主要內(nèi)容；探討了DTA并行技術在海量地形數(shù)據(jù)可視化和高性能地學計算的應用，隨著DEM的需求日益增大，高精度、高分辨率DEM產(chǎn)品及其附加服務也逐步產(chǎn)品化。最后，通過分析并行計算發(fā)展的關鍵問題，提出DTA并行技術的研究趨勢及研究意義，合適的數(shù)據(jù)劃分和結(jié)果融合策略、通用并行算法、容錯機制和負載均衡策略的設計是今后研究的重要內(nèi)容，尤其是如何在多種計算模式共同發(fā)展的背景下利用并行計算解決地學難題，從而得到更接近現(xiàn)實世界地理環(huán)境的模擬，并擴大數(shù)字地形分析的應用范圍。

數(shù)字高程模型；數(shù)字地形分析；并行計算；進展

0 引言

數(shù)字地形分析（Digital Terrain Analysis，DTA）是在數(shù)字高程模型（Digital Elevation Model，DEM）上進行地形屬性計算和特征提取的數(shù)字信息處理技術［1］，理論研究主要集中在空間數(shù)據(jù)獲取、DEM預處理、地形分析算法的研究和誤差分析等方面［2］。各種新型傳感器獲取DEM技術的出現(xiàn)，使DEM數(shù)據(jù)量呈幾何級數(shù)增長，DEM基礎數(shù)據(jù)呈現(xiàn)多比例尺、多分辨率的系列化特征，網(wǎng)絡通訊技術的發(fā)展促進了各類DEM強烈的共享需求。盡管現(xiàn)有基于DEM的地形分析理論與方法趨于成熟，但如何使用傳統(tǒng)的串行算法實現(xiàn)海量數(shù)據(jù)的高效處理，是DEM廣泛應用亟待解決的關鍵問題，也是國內(nèi)外相關領域研究的重要課題。

隨著硬件技術和新型應用的不斷發(fā)展，并行計算系統(tǒng)得到快速發(fā)展，如多核體系結(jié)構的發(fā)展［3，4］、云計算模式出現(xiàn)、GPU軟硬技術的延伸［5，6］，為并行計算的廣泛應用提供不可或缺的支持。近年來，海量空間數(shù)據(jù)分析不斷增長的計算需求以及高性能地學應用需求的推動，使得并行地形分析成為高性能地學計算發(fā)展的重要趨勢［7，8］。

縱觀40余年數(shù)字地形分析的發(fā)展，盡管其理論與技術都有了一定的突破，但隨著其應用領域的推廣，仍存在很多有待于深入研究的問題，如并行計算模式與數(shù)字地形分析的融合問題、如何根據(jù)不同的地形分析算法設計適合具體硬件環(huán)境的算法體系以及如何適應計算機硬件發(fā)展環(huán)境等。本文總結(jié)了近年來一些具有代表性的數(shù)字地形分析并行算法，結(jié)合高性能地學計算的最新研究進展，著重分析了目前仍然存在的問題及解決問題的關鍵技術，并展望了前沿的進展情況和未來的研究方向。

1 并行構建DEM技術研究進展

DEM的建立是一種地形數(shù)據(jù)的建模過程。DEM數(shù)據(jù)組織方式有規(guī)則格網(wǎng)結(jié)構（grid）、不規(guī)則三角網(wǎng)結(jié)構（TIN）和等高（值）線結(jié)構，其中規(guī)則格網(wǎng)DEM和不規(guī)則三角網(wǎng)TIN是目前數(shù)字高程模型的兩個主要數(shù)據(jù)模型。盡管眾多學者對各種DEM構建技術做了不同方面（算法、I／O接口）的改進［9－12］，但在單機環(huán)境下對海量的空間數(shù)據(jù)進行快速處理仍十分困難，而借助并行計算技術可提高數(shù)據(jù)處理效率［13－17］。并行構建DEM的研究主要集中在：并行構建規(guī)則格網(wǎng)DEM、并行提取等高線［16］、并行生成不規(guī)則三角網(wǎng)等。

1.1 并行構建格網(wǎng)DEM

由于空間數(shù)據(jù)源的多樣性與數(shù)據(jù)量巨大，空間數(shù)據(jù)內(nèi)插算法的計算量也隨之增大。內(nèi)插算法的并行化是構建規(guī)則格網(wǎng)DEM的重要研究內(nèi)容［13－19］，如按塊進行分布式管理［20，21］、基于對象的存儲方式［22，23］，采用并行計算策略能有效提升其處理效率［24，25］。鑒于DEM數(shù)據(jù)密集的特點，內(nèi)插算法的并行化研究主要采用數(shù)據(jù)并行策略與主從的計算模式［26］。其中，反距離加權插值算法（IDW）在不同并行環(huán)境中的研究較多［17，18，25］，Armstrong等研究了IDW內(nèi)插算法在MIMD環(huán)境下的并行化［13］，采用SIMD架構并對比不同的計算模式，給出IDW算法的不同實現(xiàn)方法和空間自適應并行化方法［14，15］；其他算法有逐行內(nèi)插的并行IDW算法［18］、自適應方差圖擬合算法［26］、基于四叉樹的域分割算法［17］等。在異構網(wǎng)格計算環(huán)境下，針對分布式的數(shù)據(jù)集，四叉樹的域分解算法和任務管理算法可以有效管理不規(guī)則的數(shù)據(jù)集合［17］。

空間數(shù)據(jù)采集技術的迅速發(fā)展為規(guī)則格網(wǎng)DEM快速構建提出了新的挑戰(zhàn)。在處理大量高密度和高精度的激光點云數(shù)據(jù)過程中，I／O處理成為系統(tǒng)性能提升的瓶頸。雖然眾多學者對I／O處理算法［11］進行了改進，然而由于串行算法的局限性，處理時間仍不能滿足具體的應用要求，并行I／O的設計仍是熱點研究問題。盡管單核CPU的計算能力已有大幅度的提升，但其處理能力幾乎達到了物理極限，很難有較大的提升空間，多核技術則為此提供了新的計算模式。有學者研究如何利用多核技術將點云數(shù)據(jù)分割為部分重疊的塊狀區(qū)域，各數(shù)據(jù)塊采用流水線技術并行內(nèi)插［25］，這些問題將是未來DEM構建的重要研究內(nèi)容。

1.2 并行生成不規(guī)則三角網(wǎng)

常規(guī)構建散點域三角網(wǎng)的較為廣泛算法是Delaunay直接三角剖分算法。根據(jù)Delaunay三角網(wǎng)構建過程的不同，生成Delaunay三角網(wǎng)的思想主要有分割合并、三角網(wǎng)增長和逐點插入［27］。

不規(guī)則三角網(wǎng)的計算較復雜，許多研究者希望利用并行計算提高三角剖分的效率。傳統(tǒng)的解決策略是采用共享內(nèi)存數(shù)據(jù)的方式［28，29］，對串行的三角網(wǎng)生成算法進行并行化改造。Huang等［30］提出了重排序算法以減少三角剖分過程中的操作，該算法可以推斷計算問題的最長時間下限，并利用同等調(diào)度算法實施調(diào)度操作，對實時性要求較高；為解決不同處理器對共享內(nèi)存的訪問沖突問題，該算法采用了緩沖區(qū)存儲數(shù)據(jù)策略，導致其不適宜處理海量的空間數(shù)據(jù)?？紤]到這一問題，Merks［31］采用同時讀／排斥寫模型（CREW PRAM），以解決計算結(jié)點對共享內(nèi)存數(shù)據(jù)的讀寫問題，通過分割合并將計算數(shù)據(jù)分解為各子塊進行并行計算，其時間復雜度和空間復雜度分別為O（log n）和O（n）。

Delaunay三角剖分并行算法的實現(xiàn)主要集中在集群計算環(huán)境下［32－35］，該類并行算法關注三角網(wǎng)生成、分割等問題，如四點共圓的不唯一性及并行處理邊界的任意性問題［33］；當合并兩個子塊三角形時，提取被修改的三角劃分區(qū)域可以減少處理器之間的通信次數(shù)［34］。Kohout［35］等針對隨機增量插入點的Delaunay串行算法進行了并行化改造，并從2維、3維角度分析了樂觀算法、悲觀算法等的計算效率。

提高凸殼計算速度是很多學者進行三角剖分算法設計的預期目標［36，37］，Amato算法［36］將凸殼計算的復雜度降至O（log n）。Lee等［37］提出改進的Delaunay并行剖分算法，通過增量構建的方法，在每個區(qū)域中使用Delaunay邊界和生成的Delaunay三角形，對凸殼邊界區(qū)域進行剖分；由于每個計算結(jié)點的邊界線均已確定，計算結(jié)果的融合簡單易行，且計算效率較高。面對多計算結(jié)點，還需進一步考慮所產(chǎn)生的負載均衡問題。

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

數(shù)字地形分析并行計算具有數(shù)據(jù)密集和計算密集的特征，需要考慮任務并行、算法并行、數(shù)據(jù)并行等問題。針對海量高分辨率DEM數(shù)據(jù)，如何快速提取地形屬性信息和地形特征并將其轉(zhuǎn)化為能直接應用的信息，已成為數(shù)字地形分析研究迫切需要解決的問題。目前，這方面的研究主要集中在算法復雜度較高或全局性算法方面，在可視性分析和流域提取中的研究較多。

2.1 并行可視性分析

可視性分析也稱通視分析，實質(zhì)上是對地形進行最優(yōu)化處理的范疇?？梢曅苑治龅幕疽蜃佑袃牲c之間的通視性和可視域計算。基于規(guī)則格網(wǎng)DEM的可視域算法在GIS分析中應用較廣，研究以規(guī)則格網(wǎng)DEM為主，基于TIN的可視域分析稍有涉及［38］。在規(guī)則格網(wǎng)DEM中，可視域經(jīng)常是以離散的形式表示，將每個格網(wǎng)點表示為可視或不可視，即可視矩陣。一種簡單的計算基于規(guī)則格網(wǎng)DEM可視域的方法就是沿著視線的方向，從視點開始到目標格網(wǎng)點，計算與視線相交的格網(wǎng)單元并判斷該單元是否可視，從而確定視點與目標視點之間是否可視。學者們利用SIMD并行架構對通視分析和可視域算法的并行化設計進行了深入研究［39－41］，對點到區(qū)域、點到點的視線進行并行處理。典型的并行可視域算法是分別計算觀察點到目標區(qū)域內(nèi)每個高程點的可視性，高程矩陣每個點的計算被分配給一個計算單元，每個計算單元將計算結(jié)果返回到格網(wǎng)單元內(nèi)，同時，采用互斥機制避免了共享內(nèi)存中同時讀寫問題［39］。由于高分辨率大尺度DEM數(shù)據(jù)的可視性分析算法計算量巨大，Mills等對串行的點到點的通視算法進行并行化，對源區(qū)域的每個視點的視線進行并行處理，減少了不同處理器之間的全局通信［40］。

MIMD并行架構下的可視性分析也有大量研究［42－44］，可視性算法在并行工作站集群中的數(shù)據(jù)并行策略及性能也有研究［42，43］。完整可視性數(shù)據(jù)庫（CID）［44］存儲了DEM中每個點的可視域，并采用任務重提交進行容錯處理。并行可視性分析也涉及其他應用［45，46］，如處理基于TIN的最短路徑尋找問題［46］、最優(yōu)選址問題［45］。Kidner等［46］提出一種反向的并行可視性分析算法，在各計算結(jié)點采用傳統(tǒng)的通視算法，計算區(qū)域－區(qū)域的可視性，有效利用了各計算結(jié)點的計算能力并取得較優(yōu)的加速比。

2.2 并行流域提取

DEM在水文分析中的應用一直是研究的熱點，尤其是基于DEM提取流域河網(wǎng)算法的并行化設計。由于DEM數(shù)據(jù)量的劇增和水文算法全局依賴的計算復雜性，串行計算模式難以解決高計算量和高復雜性并存的難題。

流域網(wǎng)絡提取工作主要包括：DEM數(shù)據(jù)預處理（偽洼地填充）、生成流向、提取水流累積矩陣、設置臨界集水面積閾值提取河網(wǎng)水系。由于流域提取涉及任務間的約束關系、節(jié)點間負載均衡與流域網(wǎng)絡的拓撲關系等問題，并行流域提取成為研究熱點。早期的并行流域網(wǎng)絡提取主要是基于SIMD并行架構［47，48］，對流域提取算法并行化問題提出不同的解決方案。Mower［47］選取流域提取建模的性能統(tǒng)計量，比較了功能并行策略和數(shù)據(jù)并行策略的性能，驗證了并行算法的可行性。盡管基于行分割的數(shù)據(jù)并行策略取得較好的負載均衡，但通信代價過高，相比通過文件和順序切割DEM數(shù)據(jù)的并行策略其總體性能不理想。內(nèi)存共享的并行架構下處理流域提取中的全局迭代，需要合理地處理結(jié)點間的任務依賴關系，否則，異步操作成為并行算法性能提升的瓶頸［48］。部分學者利用圖理論，并行生成最小流向樹［49］，避免DEM預處理時大量的填洼運算。

近年來，分布式并行計算模式推動了高性能水文分析的發(fā)展［50－53］，如徑流模擬［54］、湍流模擬［55，56］和洪水預測［57］等。不同于共享內(nèi)存架構，分布式并行計算中需要解決數(shù)據(jù)分發(fā)、低通信效率、計算進程調(diào)度與結(jié)果融合等問題。例如，匯流累積量的計算需要確保每個格網(wǎng)單元至少被訪問一次［51］；對各進程實時監(jiān)控以減少進程間通信消耗，也是提升大尺度流域水文并行計算效率的有效途徑［58］。盡管傳統(tǒng)的并行算法在計算能力方面有了一定的改進，但負載均衡問題一直未得到較好的解決。在新型高性能計算系統(tǒng)中，高通量計算有望取得更高的吞吐能力和效能。基于分水嶺邊界對DEM進行數(shù)據(jù)劃分，以小流域為并行計算的基本單位，可有效地保證流域拓撲關系的提?。?2］。成熟的機群作業(yè)系統(tǒng)Condor軟件可用來控制任務隊列的調(diào)度，有效地避免不同數(shù)據(jù)分割粒度造成的計算異步問題。GPU在計算能力和存儲器訪問帶寬上具有優(yōu)勢［59，60］，基于CUDA的并行流域網(wǎng)絡提取算法，可以執(zhí)行計算量更大的矩陣相乘運算，采用優(yōu)化的歸并排序算法及內(nèi)存分配策略，從而提供了適合現(xiàn)代計算機基于GPU的水文分析解決方案。

3 并行數(shù)字地形分析的應用

3.1 海量數(shù)據(jù)的地形可視化

數(shù)字地形分析中可視化分析的重點在于地形特征的可視化表達和信息增強，從而表達地形曲面參數(shù)、地表形態(tài)特征和復合地形屬性的信息。目前主要基于TIN模型實現(xiàn)地形可視化，這類算法通常比較復雜，剖分的粒度較小。地形可視化的主要研究內(nèi)容有：自適應地表模型建立方法、地形簡化模型的誤差標準、空間連續(xù)性、數(shù)據(jù)壓縮與離核繪制［61，62］。傳統(tǒng)的桌面系統(tǒng)難以滿足對與日俱增的DEM數(shù)據(jù)實時可視化分析的需求，有效方法是并行處理［63，65］。并行計算在地形可視化算法領域中研究較多［66］，如并行繪制、高分辨率顯示墻系統(tǒng)等［64］。

海量數(shù)據(jù)的并行可視化技術在地學分析中的應用可以較好地滿足數(shù)據(jù)分析的要求，高分辨的并行顯示技術有助于深入觀察試驗結(jié)果的細節(jié)。圖形硬件技術的發(fā)展要求基于大規(guī)模地形數(shù)據(jù)的可視化算法重新設計，以期充分發(fā)揮CPU與GPU的寬帶通信優(yōu)勢。另外，如何利用硬件可編程語言將部分算法高效地移植到GPU上順利執(zhí)行，仍需進一步研究，實時動態(tài)的大規(guī)模地形可視化技術也將是今后研究的重要內(nèi)容之一。

3.2 高性能地學計算

高性能地學計算實現(xiàn)了地理環(huán)境中全球性或大區(qū)域性以時空演變?yōu)樘卣鞯牡乩憩F(xiàn)象（如數(shù)值天氣預報、全球氣候變化、地理信息系統(tǒng)等）模擬。地學領域中的并行算法研究和應用層出不窮，在面向大尺度地形研究方面，如天氣預測［67，68］①enviroGRIDS項目：http：／／www.envirogrids.net.②ALADIN，高分辨率數(shù)值天氣預報項目：http：／／www.cnrm.meteo.fr／aladin.、石油勘探［69，70］、災害預測［71，72］③天氣研究預測模型：http：／／www.wrf－model.org／index.php.大地震動模擬［73］、海洋波浪模擬［74］等。

隨著高精度、高分辨率的DEM產(chǎn)品逐步產(chǎn)業(yè)化，除提供常規(guī)的DEM產(chǎn)品外，還需要提供DEM數(shù)據(jù)增值服務。數(shù)字地形分析并行技術所提供的高性能計算能力可以很好地實現(xiàn)DEM服務的增值［23，45］和災害預報［57，72］等功能。然而，目前大多數(shù)的實際應用仍停留在“數(shù)據(jù)”層面，忽視了對數(shù)據(jù)內(nèi)容的挖掘與信息的提取，難以實現(xiàn)較高的數(shù)據(jù)應用效益和空間數(shù)據(jù)增值。因此，亟須利用地形分析并行技術，從DEM數(shù)據(jù)中提取實際應用的地形參數(shù)和地形特征信息，提升高性能地學計算中空間數(shù)據(jù)增值服務的質(zhì)量。

4 討論與展望

數(shù)字地形分析并行技術的發(fā)展與并行計算密切相關，各種分析算法必須適應復雜的計算環(huán)境。隨著數(shù)字地形分析內(nèi)涵的不斷深化和應用的日趨廣泛，高性能計算技術的發(fā)展與普及將把數(shù)字地形分析推向一個全新的應用水平。另外，數(shù)字地形分析的發(fā)展也為高性能地學應用提供了新的驅(qū)動力和應用背景。其可能的發(fā)展趨勢和需要探索的方向包括：

（1）數(shù)據(jù)劃分策略。不同的數(shù)據(jù)劃分策略對數(shù)字地形分析并行算法的設計具有不同的影響，這需要選擇最優(yōu)的劃分策略來解決地形特征的影響，以適應不同的并行計算環(huán)境。針對以數(shù)據(jù)密集為特征的并行計算，準確處理具有依賴關系的數(shù)據(jù)和數(shù)據(jù)之間的操作，解決全局性算法的分布式并行實現(xiàn)和不規(guī)則對象的規(guī)則劃分，實現(xiàn)簡單高效地管理數(shù)據(jù)將是研究的重點。地形數(shù)據(jù)的串行預處理和后處理也是性能提高的重要制約因素。

（2）計算結(jié)果的并行融合處理。分析單元間的區(qū)域相關是數(shù)字地形分析的基本特征。對于具有確定相關半徑的數(shù)據(jù)并行單元，結(jié)果融合主要是接邊操作；對于相關半徑強烈依賴于相鄰單元內(nèi)地形特征的并行分析單元［53］或算法之間存在相互依賴，需要設計高耦合度的結(jié)果融合策略，但設計過程應避免頻繁的融合操作。

（3）通用并行算法設計問題。理論上，并行程序在不同體系結(jié)構的平臺上應可移植，但可移植性通常伴隨著性能的降低。只有考慮到體系結(jié)構特征，并行算法的性能才能達到最優(yōu)。不同的并行計算模型以及處理器個數(shù)、帶寬、存儲性能的不同，造成了算法在不同平臺上使用時不能達到期望值。更嚴峻的是，在轉(zhuǎn)向不同的體系結(jié)構時，不僅程序員需要移植現(xiàn)有的應用程序，研究人員也需要選擇或設計相應的算法及子過程。

（4）負載均衡策略。為了提高系統(tǒng)資源利用率和并行計算的性能，尤其是在異構集群環(huán)境中，各結(jié)點的性能有所不同，應選擇適當?shù)挠嬎憬Y(jié)果集合的級別以充分利用系統(tǒng)資源。如何兼顧負載均衡度和同步開銷以提高整體的計算性能，尚需進一步研究。

（5）容錯問題。并行算法的設計還應考慮合適的容錯機制，在高效加速故障恢復的同時降低容錯開銷，保證計算性能的同時盡可能提高系統(tǒng)可靠性，以滿足應用的需要。容錯技術的引入不可避免地帶來一定程度的冗余計算。為了避免重構計算資源并重啟計算的故障恢復，大規(guī)模并行系統(tǒng)需要在檢測到故障之后，恢復故障進程上的計算狀態(tài)。

［1］ 周啟鳴，劉學軍.數(shù)字地形分析［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］ 陳國良，孫廣中，徐云，等.并行計算的一體化研究現(xiàn)狀與發(fā)展趨勢［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］ 胡金星，吳煥萍，潘懋，等.基于格網(wǎng)劃分的海量DEM數(shù)據(jù)生成［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］ 劉家宏，王光謙，王開.大流域數(shù)字高程模型數(shù)據(jù)管理系統(tǒng)［J］.清華大學學報（自然科學版），2004，44（12）：1646－1649.

［21］ 溫菊屏.大規(guī)模地形漫游系統(tǒng)關鍵技術的研究［J］.計算機與數(shù)字工程，2009，37（1）：47－50.

［22］ 王晨，周穎，張德富.一種并行分布對象的互操作模型［J］.軟件學報，1999，10（8）：861－867.

［23］ 鄭勝，喻占武，李忠民.基于OBS的分布并行海量地形數(shù)據(jù)服務系統(tǒng)［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三角網(wǎng)構建方法比較研究［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三角剖分并行算法研究及實現(xiàn)［J］.小型微型計算機系統(tǒng)，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，F(xiàn)OX 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，F(xiàn)rance，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的匯流分析并行算法的研究與實現(xiàn)［J］.計算機應用研究，2010，27（7）：2445－2447，2451.

［61］ 孫敏，薛勇，馬靄乃.基于格網(wǎng)劃分的大數(shù)據(jù)集DEM三維可視化［J］.計算機輔助設計與圖形學學報，2002，14（6）：566－570.

［62］ 張慧杰，孫吉貴，劉雪沽，等.大規(guī)模三維地形可視化算法研究進展［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］ 陳紹林，張懷，石耀霖.地學中海量數(shù)據(jù)的并行可視化研究進展［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）；資源與環(huán)境信息系統(tǒng)國家重點實驗室開放基金項目（2010KF0002SA）

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