發(fā)布時間：2018-06-20 23:19

  本文選題：數(shù)字地形分析 + 并行計算��； 參考：《南京師范大學》2013年碩士論文

【摘要】：海量數(shù)字高程模型(DEM)數(shù)據(jù)和復雜的地理空間處理算法模式等,使得傳統(tǒng)的基于單核計算機的串行數(shù)字地形分析算法在效率上的不足日益凸顯。而面向海量DEM數(shù)據(jù),在并行平臺上開發(fā)新的并行數(shù)字地形分析算法,是解決數(shù)字地形分析算法效率問題的關鍵。 設計并行算法時須考慮并行相關性、粒度、局部性、負載均衡等問題。本文首先分析了數(shù)據(jù)并行、任務并行、遞歸拆分并行、流水線并行等常用模式在并行數(shù)字地形分析算法中的應用方法。得出了并行數(shù)字地形分析算法適合采用數(shù)據(jù)并行模式的結論。在此基礎上,設計了一個適用于數(shù)字地形分析算法的并行架構。采用主從模式和數(shù)據(jù)并行方法,將拆分后的每塊數(shù)據(jù)的計算作為獨立的任務,采用工作隊列動態(tài)在進程之間進行計算分配,減少了進程之間的通信量,并取得較好的負載均衡效果。 數(shù)據(jù)并行的一個關鍵是消除或減少由于數(shù)據(jù)拆分所導致的不同節(jié)點之間的數(shù)據(jù)相關性。本文根據(jù)各種數(shù)字地形分析算法的計算特征將其分為鄰域相關算法與全局相關算法兩大類。針對鄰域相關算法,設計了與上述算法模式和算法特征相適應的數(shù)據(jù)規(guī)則拆分方法,包括行、列、塊拆分等,提出塊拆分可以較小的數(shù)據(jù)冗余代價來消除節(jié)點之間的數(shù)據(jù)相關性；針對全局相關算法,設計了顧及算法計算特征的、基于多次重采樣的不規(guī)則數(shù)據(jù)拆分方法,以低分辨率重采樣數(shù)據(jù)上的初步地形分析結果指導高分辨率的數(shù)據(jù)拆分,消除了不同計算節(jié)點之間的數(shù)據(jù)相關性。 為了驗證上述并行架構和數(shù)據(jù)拆分方法的合理性,搭建了一個由八臺PC機組成的機群和OpenMP+MPI為軟件的實驗系統(tǒng),采用本文設計的并行數(shù)字地形分析算法模式和數(shù)據(jù)拆分方法,分別以并行坡度計算為鄰域相關算法的例子,和并行洼地填平計算為全局相關算法的例子,進行了串行算法與并行算法正確性的對比實驗,以及并行算法效率實驗。實驗結果并行計算和串行計算結果一致,并行加速比理想且符合預期。 實驗結果表明,本文給出的主從結構和數(shù)據(jù)并行的數(shù)字地形分析算法模式,結合對鄰域相關算法與全局相關算法采用的規(guī)則拆分以及多次重采樣拆分方法,在保持了計算節(jié)點之間動態(tài)負載平衡的同時,較好的解決了并行數(shù)字地形分析的數(shù)據(jù)相關性問題,適合于大部分的數(shù)字地形分析算法的并行化改造,具有一定的普適性,本研究為基于大范圍高分辨率DEM數(shù)據(jù)進行精細化的并行數(shù)字地形分析應用提供了有益的理論和技術支撐。
[Abstract]:Mass digital elevation model (DEM) data and complex geospatial processing algorithms make the traditional serial digital terrain analysis algorithm based on single core computer more and more inefficient. The key to solve the problem of efficiency of digital terrain analysis algorithm is to develop a new parallel digital terrain analysis algorithm based on parallel platform for massive Dem data. Parallel correlation, granularity, locality and load balance should be considered in designing parallel algorithms. In this paper, the application methods of data parallelism, task parallelism, recursive split parallelism and pipeline parallelism in parallel digital terrain analysis algorithms are analyzed. It is concluded that the parallel digital terrain analysis algorithm is suitable for data parallel mode. On this basis, a parallel architecture for digital terrain analysis algorithm is designed. By using master-slave mode and data parallel method, the computation of each block of data after splitting is regarded as an independent task, and the work queue is used to dynamically calculate and distribute between processes, thus reducing the communication between processes. And achieved better load balancing effect. One of the keys of data parallelism is to eliminate or reduce the data correlation between different nodes caused by data splitting. According to the computational characteristics of various digital terrain analysis algorithms, this paper divides them into two categories: neighborhood correlation algorithm and global correlation algorithm. Aiming at the neighborhood correlation algorithm, this paper designs a method of data rule splitting, including row, column, block partition and so on, which adapts to the above algorithm pattern and algorithm features. It is proposed that block splitting can reduce the cost of data redundancy in order to eliminate the data correlation between nodes. For the global correlation algorithm, an irregular data splitting method based on multiple resampling is designed, which takes into account the computational characteristics of the algorithm. The preliminary terrain analysis results on the low-resolution resampling data are used to guide the high-resolution data splitting, and the data correlation between different computing nodes is eliminated. In order to verify the rationality of the parallel architecture and the method of data splitting, an experimental system composed of eight PCs and OpenMP MPI is built. The parallel digital terrain analysis algorithm and the method of data splitting are adopted in this paper. Taking the parallel slope calculation as an example of neighborhood correlation algorithm and the parallel low-fill calculation as a global correlation algorithm, the comparison between the correctness of the serial algorithm and the parallel algorithm and the experiment of the efficiency of the parallel algorithm are carried out. The experimental results are consistent with those of serial computation, and the parallel speedup is ideal and in line with the expectation. The experimental results show that the master-slave structure and the data parallel digital terrain analysis algorithm model, combined with the neighborhood correlation algorithm and the global correlation algorithm of the rule split and multiple resampling split method, At the same time, it can solve the data correlation problem of parallel digital terrain analysis, which is suitable for the parallel transformation of most digital terrain analysis algorithms, and has certain universality. This study provides useful theoretical and technical support for the application of fine parallel digital terrain analysis based on large range and high resolution Dem data.
【學位授予單位】：南京師范大學
【學位級別】：碩士
【學位授予年份】：2013
【分類號】：P208

【參考文獻】

相關期刊論文 前4條

1 應申;李霖;梅洋;高玉榮;肖劍平;;增量法地形可視計算與分析[J];測繪學報;2007年02期

2 吳艷蘭;基于參考面的可視域算法[J];測繪信息與工程;2001年01期

3 劉曉平;曹力;;基于MPI的并行八叉樹碰撞檢測[J];計算機輔助設計與圖形學學報;2007年02期

4 閆長青;岳天祥;;GPU加速的高精度數(shù)字地面模型建模方法[J];計算機工程與應用;2012年22期

，

本文編號：2046078