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

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

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

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

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