【摘要】：數(shù)字地形分析是地理信息系統(tǒng)軟件的重要支撐功能之一。目前眾多應(yīng)用領(lǐng)域?qū)Υ笠?guī)模、高效率數(shù)字地形分析的需求日益增長(zhǎng),而其與計(jì)算資源低利用率之間的矛盾卻日益突出�，F(xiàn)有的數(shù)字地形分析方法很難甚至無(wú)法快速、高效地處理海量DEM數(shù)據(jù),而并行計(jì)算為解決這一難題提供了新的思路。雖然傳統(tǒng)的高性能計(jì)算技術(shù)使得DEM的處理效率得到了有效提升,但是隨著并行計(jì)算集群技術(shù)、多核處理器技術(shù)以及并行計(jì)算模型等新型并行技術(shù)的出現(xiàn),面向新型架構(gòu)的數(shù)字地形分析并行算法亟需發(fā)展與完善。 首先,本文針對(duì)數(shù)字地形分析的數(shù)據(jù)密集、任務(wù)密集的特征,并結(jié)合當(dāng)前并行計(jì)算平臺(tái)的特點(diǎn),提出了數(shù)據(jù)、任務(wù)與結(jié)構(gòu)統(tǒng)一的,面向數(shù)字地形分析的可量化的粒度模型概念和定義,并從數(shù)據(jù)和任務(wù)拆分的角度構(gòu)建了粒度關(guān)系依賴圖。 其次,在粒度模型的基礎(chǔ)上,針對(duì)格網(wǎng)DEM的數(shù)據(jù)特征,構(gòu)建了并行環(huán)境下可有效支撐DEM數(shù)據(jù)規(guī)則拆分的數(shù)據(jù)粒度模型,詳細(xì)定義了數(shù)據(jù)粒度的屬性以及數(shù)據(jù)粒度之間的關(guān)系。利用數(shù)據(jù)粒度的各維屬性對(duì)數(shù)據(jù)粒度進(jìn)行量化,提出了基于內(nèi)存頁(yè)調(diào)度機(jī)制的最小數(shù)據(jù)粒度和基于四叉樹(shù)管理存儲(chǔ)策略的組合數(shù)據(jù)粒度的概念,給出了便于DEM數(shù)據(jù)接邊處理的冗余行列的計(jì)算和劃分方法。綜合考慮最小數(shù)據(jù)粒度和組合數(shù)據(jù)粒度,以及結(jié)構(gòu)粒度,給出了面向并行數(shù)字地形分析的數(shù)據(jù)分發(fā)方法。 再次,為了充分利用多核集群系統(tǒng)的硬件優(yōu)勢(shì),任務(wù)并行能夠更好地提高并行處理效率。本文對(duì)數(shù)字地形分析中的63個(gè)地形因子進(jìn)行分析,構(gòu)建了任務(wù)分解的任務(wù)粒度模型,從任務(wù)粒度的屬性和關(guān)系來(lái)對(duì)其進(jìn)行量化研究。為了厘清可并行性,引入Petri網(wǎng)理論,提出了基于數(shù)據(jù)并行和任務(wù)并行的關(guān)系依賴圖及其構(gòu)建方法,并給出了相應(yīng)的調(diào)度算法,為任務(wù)并行調(diào)度提供了理論依據(jù)。 最后,為保證大規(guī)模并行系統(tǒng)的可靠運(yùn)行和結(jié)果的正確性,本文在數(shù)據(jù)分發(fā)和任務(wù)調(diào)度的基礎(chǔ)上,提出了兩級(jí)調(diào)度機(jī)制,并給出基于冗余的并行容錯(cuò)調(diào)度算法,提高系統(tǒng)的可靠性。
[Abstract]:Digital terrain analysis is one of the important supporting functions of GIS software. At present, the demand for large-scale and efficient digital terrain analysis is increasing in many application fields, but the contradiction between it and the low utilization rate of computing resources is becoming more and more prominent. The existing digital terrain analysis methods are difficult or even unable to deal with massive DEM data quickly and efficiently, and parallel computing provides a new way to solve this problem. Although the traditional high performance computing technology has effectively improved the processing efficiency of DEM, with the emergence of parallel computing cluster technology, multi-core processor technology and parallel computing model and other new parallel technologies, The parallel algorithm of digital terrain analysis for new architecture needs to be developed and improved. First of all, according to the data-intensive and task-intensive characteristics of digital terrain analysis, and combined with the characteristics of the current parallel computing platform, this paper proposes a unified data, task and structure. The concept and definition of quantitative granularity model for digital terrain analysis are constructed, and the dependency graph of granularity relation is constructed from the point of view of data and task resolution. Secondly, on the basis of granularity model, according to the data characteristics of grid DEM, a data granularity model which can effectively support DEM data rule resolution in parallel environment is constructed, and the attributes of data granularity and the relationship between data granularity are defined in detail. The data granularity is quantified by using the attributes of each dimension of data granularity, and the concepts of minimum data granularity based on memory page scheduling mechanism and combined data granularity based on quadtree management storage strategy are proposed. The calculation and partition method of redundant rows and rows which is convenient for DEM data edge processing is given. Considering the minimum data granularity, the combined data granularity and the structure granularity, a data distribution method for parallel digital terrain analysis is presented. Thirdly, in order to make full use of the hardware advantages of multi-core cluster system, task parallelism can improve the efficiency of parallel processing. In this paper, 63 terrain factors in digital terrain analysis are analyzed, and the task granularity model of task decomposition is constructed, and the quantitative research is carried out from the attributes and relations of task granularity. In order to clarify the parallelism, the Petri net theory is introduced, and the relational dependency graph based on data parallelism and task parallelism and its construction method are proposed, and the corresponding scheduling algorithms are given, which provides a theoretical basis for task parallel scheduling. Finally, in order to ensure the reliable operation of large-scale parallel systems and the correctness of the results, a two-level scheduling mechanism is proposed on the basis of data distribution and task scheduling, and a parallel fault-tolerant scheduling algorithm based on redundancy is proposed. Improve the reliability of the system.
【學(xué)位授予單位】：南京師范大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2012
【分類號(hào)】：TP338.6;TP301.1

【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 胡金星,馬照亭,吳煥萍,潘懋;基于格網(wǎng)劃分的海量數(shù)據(jù)Delaunay三角剖分[J];測(cè)繪學(xué)報(bào);2004年02期

2 楊昕;湯國(guó)安;劉學(xué)軍;李發(fā)源;祝士杰;;數(shù)字地形分析的理論、方法與應(yīng)用[J];地理學(xué)報(bào);2009年09期

3 楊際祥;譚國(guó)真;王榮生;;并行與分布式計(jì)算動(dòng)態(tài)負(fù)載均衡策略綜述[J];電子學(xué)報(bào);2010年05期

4 王霜;李心科;;基于LBT的網(wǎng)格依賴任務(wù)調(diào)度算法[J];合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版);2010年01期

5 曹小華;周勇;;基于主動(dòng)請(qǐng)求與動(dòng)態(tài)分配負(fù)載的CAN容錯(cuò)算法[J];華南理工大學(xué)學(xué)報(bào)(自然科學(xué)版);2010年09期

6 周笛;;軟件容錯(cuò)的方法、模型與實(shí)現(xiàn)[J];計(jì)算機(jī)研究與發(fā)展;1987年02期

7 周恩強(qiáng),盧宇彤,沈志宇;一個(gè)適合大規(guī)模集群并行計(jì)算的檢查點(diǎn)系統(tǒng)[J];計(jì)算機(jī)研究與發(fā)展;2005年06期

8 郭龍;陳閎中;葉青;;構(gòu)造串行程序?qū)?yīng)的并行任務(wù)(DAG)圖[J];計(jì)算機(jī)工程與應(yīng)用;2007年01期

9 杜云飛;唐玉華;楊學(xué)軍;;容錯(cuò)并行算法的性能分析[J];計(jì)算機(jī)科學(xué);2009年09期

10 向建軍,白欣,左繼章;一種用于實(shí)時(shí)集群的多任務(wù)負(fù)載均衡算法[J];計(jì)算機(jī)工程;2003年12期

相關(guān)碩士學(xué)位論文 前3條

1 文劍;并行計(jì)算平臺(tái)的建立及性能分析[D];廣東工業(yè)大學(xué);2007年

2 李永旭;基于MPI標(biāo)準(zhǔn)的并行計(jì)算平臺(tái)的設(shè)計(jì)與實(shí)現(xiàn)[D];東北師范大學(xué);2007年

3 丁峰;有色時(shí)間Petri網(wǎng)與隨機(jī)Petri網(wǎng)應(yīng)用研究[D];合肥工業(yè)大學(xué);2009年

，

本文編號(hào)：2490459