并行數字地形分析算法模式與數據拆分方法.pdf

1、海量數字高程模型(DEM)數據和復雜的地理空間處理算法模式等，使得傳統(tǒng)的基于單核計算機的串行數字地形分析算法在效率上的不足日益凸顯。而面向海量DEM數據，在并行平臺上開發(fā)新的并行數字地形分析算法，是解決數字地形分析算法效率問題的關鍵。
　　設計并行算法時須考慮并行相關性、粒度、局部性、負載均衡等問題。本文首先分析了數據并行、任務并行、遞歸拆分并行、流水線并行等常用模式在并行數字地形分析算法中的應用方法。得出了并行數字地形分析算法適

2、合采用數據并行模式的結論。在此基礎上，設計了一個適用于數字地形分析算法的并行架構。采用主從模式和數據并行方法，將拆分后的每塊數據的計算作為獨立的任務，采用工作隊列動態(tài)在進程之間進行計算分配，減少了進程之間的通信量，并取得較好的負載均衡效果。
　　數據并行的一個關鍵是消除或減少由于數據拆分所導致的不同節(jié)點之間的數據相關性。本文根據各種數字地形分析算法的計算特征將其分為鄰域相關算法與全局相關算法兩大類。針對鄰域相關算法，設計了與上述算

3、法模式和算法特征相適應的數據規(guī)則拆分方法，包括行、列、塊拆分等，提出塊拆分可以較小的數據冗余代價來消除節(jié)點之間的數據相關性;針對全局相關算法，設計了顧及算法計算特征的、基于多次重采樣的不規(guī)則數據拆分方法，以低分辨率重采樣數據上的初步地形分析結果指導高分辨率的數據拆分，消除了不同計算節(jié)點之間的數據相關性。
　　為了驗證上述并行架構和數據拆分方法的合理性，搭建了一個由八臺PC機組成的機群和OpenMP+MPI為軟件的實驗系統(tǒng)，采用本文

4、設計的并行數字地形分析算法模式和數據拆分方法，分別以并行坡度計算為鄰域相關算法的例子，和并行洼地填平計算為全局相關算法的例子，進行了串行算法與并行算法正確性的對比實驗，以及并行算法效率實驗。實驗結果并行計算和串行計算結果一致，并行加速比理想且符合預期。
　　實驗結果表明，本文給出的主從結構和數據并行的數字地形分析算法模式，結合對鄰域相關算法與全局相關算法采用的規(guī)則拆分以及多次重采樣拆分方法，在保持了計算節(jié)點之間動態(tài)負載平衡的同時，