[發明專利]一種面向并行數字地形分析的數據拆分與分發方法

無效

• 申請號: 201110405693.9
• 申請日: 2011-12-08
• 公開（公告）號: CN102495888A
• 公開（公告）日: 2012-06-13
• 發明（設計）人: 竇萬峰;劉學軍;趙菁;湯國安
• 申請（專利權）人: 南京師范大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 南京知識律師事務所 32207
• 代理人: 汪旭東

1.一種面向并行數字地形分析的數據拆分與分發方法，其特征在于，所述方法包括以下過程：

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

G＝(E，A，R)

其中，G代表數據粒度，由三元組E、R、A組成；E表示粒度實體；A代表粒度實體所具有的屬性；R代表粒度實體之間的關系；屬性A包括的維度為：數據粒度的分辨率、數據粒度的行數和列數、數據粒度的大小、冗余的行數和列數、數據塊的起始坐標；粒度實體之間的關系R包括：鄰接關系、派生關系包含關系；

(2)計算基于計算機內存頁調度策略的最小數據粒度：

步驟201：以內存調度的頁的大小4KB作為基數，根據數據粒度所占可用內存L的比例δ以及全幅DEM數據的大小GSize，計算最小數據粒度可包含內存頁數的上限值fmax：

步驟202：根據得到的fmax值，計算f的取值：

f=fmax2]]>

步驟203：根據得到的f值，以內存調度的頁的大小4KB為基數，計算最小數據粒度的大小MinSize：

MinSize＝f×4KB

其中，1≤f≤fmax，且f為正整數；

(3)計算基于四叉樹的復合數據粒度：

步驟301：根據給定的地形因子，統計其中各種操作符的個數OpNum＝{op₁，op₂，...，op_m}，利用各操作符與加法操作符執行時間t的轉化關系W＝{ω₁，ω₂，...ω_m}，計算串行地形因子的總執行時間T：

T=Σi=1mωi×opi×t]]>

步驟302：利用集群節點上地形因子的計算效率α以及集群節點I/O速度V_I/O，計算四叉樹的最大深度N：

步驟303：根據全幅DEM數據的大小GSize以及N，確定四叉樹的深度λ的取值，其中，1≤λ≤N，且λ為正整數：

λ=N2]]>

步驟304：計算復合數據粒度MultiSzie，

MultiSize＝4^λ×MinSize

(4)計算冗余數據的行、列數以及劃分邊界冗余數據：

a)根據DEM數據的分辨率Resolution以及最大冗余面積m×n：

其中，RedundantRow是冗余數據的行數，RedundantCol是冗余數據的列數；

b)劃分邊界冗余數據的方法：

(i)對于非最后一行和非最后一列的數據粒度的冗余行列，使用與此數據粒度右相鄰和下相鄰的數據粒度的行列作為冗余數據；

(ii)對于最后一行和非最后一列的數據粒度的冗余只需進行列切割，使用與所述列右相鄰的數據粒度的行列作為冗余數據；

(iii)對于最后一列和非最后一行的數據粒度的冗余只需進行行切割，使用與所述行下相鄰的數據粒度的行列作為冗余數據；

(iv)對于最后一行和最后一列的數據粒度的冗余不需要進行切割；

(5)計算基于復合數據粒度的節點數據分發數：

步驟501：全幅DEM數據的大小GSize，則劃分為復合數據粒度的個數p的計算方法為：

p=GSizeMultiSize]]>

步驟502：掃描集群系統中的空閑節點數c，空閑節點計算機按從小到大編號PC＝{pc₁，pc₂，...pc_c}，計算每個節點的最大數據粒度分發數SP：

其中，r為的余數，0＜r＜c；

(6)節點數據的靜態分發：

步驟601：復合數據粒度的編號ID＝{id₁，id₂，...id_p}，空閑節點計算機編號PC＝{pc₁，pc₂，...pc_c}，根據靜態分發策略，主節點為各節點分發復合數據粒度：

步驟602：根據上述過程(4)中計算出的所需冗余數據的行、列數以及劃分邊界冗余數據的方法，給從節點發送冗余行、列。