并行數(shù)字地形分析算法模式與數(shù)據(jù)拆分方法.pdf

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

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

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

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