[發(fā)明專利]一種面向并行數(shù)字地形分析的數(shù)據(jù)拆分與分發(fā)方法

無效

• 申請?zhí)枺?/td>: 201110405693.9
• 申請日: 2011-12-08
• 公開（公告）號: CN102495888A
• 公開（公告）日: 2012-06-13
• 發(fā)明（設(shè)計(jì)）人: 竇萬峰;劉學(xué)軍;趙菁;湯國安
• 申請（專利權(quán)）人: 南京師范大學(xué)
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 南京知識律師事務(wù)所 32207
• 代理人: 汪旭東

技術(shù)領(lǐng)域

本發(fā)明屬于數(shù)字地形分析和并行計(jì)算的交叉技術(shù)領(lǐng)域，涉及利用數(shù)據(jù)并行的方法實(shí)現(xiàn)數(shù)字地形分析的并行化，特別是涉及一種基于量化的數(shù)據(jù)拆分方法。?

背景技術(shù)

數(shù)字地形分析(Digital?Terrain?Analysis，簡稱DTA)是在數(shù)字高程模型(Digital?Elevation?Model，簡稱DEM)的基礎(chǔ)上進(jìn)行地形屬性計(jì)算和特征提取的數(shù)字信息處理技術(shù)。數(shù)字高程模型DEM是用一組有序數(shù)值陣列形式表示地面高程的一種實(shí)體地面模型，是數(shù)字地形模型(Digital?Terrain?Model，簡稱DTM)的一個(gè)分支，其它各種地形特征值均可由此派生。并行數(shù)字地形分析是使用并行計(jì)算的技術(shù)來解決數(shù)字地形分析中的海量數(shù)據(jù)量的高效處理問題。隨著各種新型傳感器以及測量技術(shù)的出現(xiàn)，DEM數(shù)據(jù)呈級數(shù)增長，從而導(dǎo)致單機(jī)環(huán)境下對大規(guī)模的數(shù)據(jù)進(jìn)行處理是一件十分困難的事情。因此使用并行計(jì)算技術(shù)可以有效地解決單處理器的計(jì)算瓶頸問題以及提高數(shù)據(jù)處理的效率。DEM的數(shù)字表示方法有格網(wǎng)、三角網(wǎng)、等高線三種，其中格網(wǎng)方式因其簡單直觀、存儲方便的優(yōu)點(diǎn)而被廣泛使用。目前并行數(shù)字地形分析的研究熱點(diǎn)主要集中在DEM數(shù)據(jù)構(gòu)建的并行化以及數(shù)字地形分析算法并行化，其中對于數(shù)據(jù)并行策略的研究還處在定性分析階段，而對于數(shù)據(jù)并行策略的建模分析以及量化研究尚未有所涉及。?

目前，數(shù)據(jù)并行策略主要是指對大規(guī)模數(shù)據(jù)進(jìn)行拆分，拆分方法可以分為兩類：規(guī)則拆分和不規(guī)則拆分。拆分方式的選擇由地形因子的算法特性決定。?

(1)規(guī)則拆分：將DEM數(shù)據(jù)塊按規(guī)則圖形進(jìn)行劃分，如正方形或長方形等還有其它的方式，例如可視域分析可以按照角度進(jìn)行拆分。其中，四叉樹算法在管理和存儲DEM數(shù)據(jù)方面性能優(yōu)越，因此被廣泛使用。格網(wǎng)DEM由于使用矩陣進(jìn)行存儲，因此采用按行和按列方式對數(shù)據(jù)塊進(jìn)行拆分的方法也較多。規(guī)則拆分的優(yōu)點(diǎn)在于數(shù)據(jù)的管理和存儲方便，可以使用順序存儲或鏈表的方式，數(shù)據(jù)處理后的融合也易操作。缺點(diǎn)在于需要對DEM數(shù)據(jù)進(jìn)行規(guī)則化處理。對于坡度、坡向等局部地形因子，通常選擇規(guī)則拆分方式。?

(2)不規(guī)則拆分：計(jì)算單元依賴的數(shù)字地形分析如果以規(guī)則格網(wǎng)進(jìn)行DEM?數(shù)據(jù)分析，分析單元的相關(guān)半徑具有不定長性，具體大小與周邊分析單元地形特征強(qiáng)相關(guān)。對于這類分析模型，課題擬以區(qū)域相關(guān)性較小的獨(dú)立不規(guī)則地理單元為數(shù)據(jù)分析單元，通過任務(wù)約束圖和動(dòng)態(tài)調(diào)度機(jī)制解決如何準(zhǔn)確高效確定并行單元邊界、消除分析單元邊界效應(yīng)、計(jì)算結(jié)果的拼接與融合。對于流域網(wǎng)絡(luò)、山脊線、山谷線等地形結(jié)構(gòu)因子，通常選擇不規(guī)則拆分方式。?

數(shù)據(jù)拆分是實(shí)現(xiàn)并行數(shù)字地形分析的重要步驟之一，目前關(guān)于數(shù)據(jù)拆分的研究主要集中在采用何種數(shù)據(jù)管理策略來提高并行計(jì)算的效率以及相關(guān)的存儲策略來降低DEM數(shù)據(jù)的存儲空間，缺少對拆分?jǐn)?shù)據(jù)的大小以及拆分?jǐn)?shù)據(jù)之間的依賴關(guān)系等量化問題的研究，而這些問題對于數(shù)據(jù)并行的效率以及數(shù)據(jù)的調(diào)度策略都是關(guān)鍵。?

發(fā)明內(nèi)容

本發(fā)明針對上述技術(shù)問題，針對點(diǎn)集均勻分布的規(guī)則格網(wǎng)DEM，提出了一種基于數(shù)據(jù)粒度模型與量化的數(shù)據(jù)拆分方法，不僅能保證并行數(shù)字地形分析的精確度，同時(shí)能提高并行數(shù)字地形分析的效率。?

為實(shí)現(xiàn)上述發(fā)明目的，本發(fā)明方法采用的技術(shù)方案如下，?

一種面向并行數(shù)字地形分析的數(shù)據(jù)拆分與分發(fā)方法，包括以下過程：?

a)讀入DEM數(shù)據(jù)，建立面向并行數(shù)字地形分析的數(shù)據(jù)粒度模型：?

數(shù)據(jù)粒度模型是對并行數(shù)字地形分析中數(shù)據(jù)的抽象，具體的數(shù)學(xué)表示為：?

G＝(E，A，R)????(a.1)?

其中，G代表數(shù)據(jù)粒度，由三元組E、R、A組成，E表示粒度實(shí)體，A代表粒度實(shí)體所具有的屬性，R代表粒度實(shí)體之間的關(guān)系；?

對于屬性A包括的維度為：數(shù)據(jù)粒度的分辨率(Resolution)，數(shù)據(jù)粒度的行數(shù)(Col)和列數(shù)(Row)，數(shù)據(jù)粒度的大小(Size)，冗余的行數(shù)(RCol)、列數(shù)(RRow)，和數(shù)據(jù)塊的起始坐標(biāo)(x，y)；?

對于粒度實(shí)體之間的關(guān)系R包括三種：鄰接關(guān)系(AdjR)、派生關(guān)系(DerR)和包含關(guān)系(InR)；?

b)計(jì)算基于計(jì)算機(jī)內(nèi)存頁調(diào)度策略的最小數(shù)據(jù)粒度：?

最小數(shù)據(jù)粒度是不可再分的數(shù)據(jù)粒度實(shí)體，是進(jìn)行數(shù)據(jù)分發(fā)時(shí)的最小數(shù)據(jù)單位，最小數(shù)據(jù)粒度的計(jì)算方法為：?

MinSize＝f×4KB????(b.1)?

1≤f≤fmax且f為正整數(shù)(b.2)?