一种面向并行数字地形分析的数据拆分与分发方法

摘要

本发明公开了一种面向并行数字地形分析的数据拆分与分发方法，属于数字地形分析和并行计算的交叉技术领域。该方法包括以下步骤：（1）读入DEM数据，建立数据粒度模型；（2）基于内存页调度策略，计算最小数据粒度大小；（3）基于四叉树存储策略，计算复合数据粒度大小；（4）计算节点数据粒度的冗余行、列数的计算方法以及切割方式；（5）基于复合数据粒度，计算节点数据的分发数；（6）根据节点的分发数，主节点进行节点数据的分发。本发明提出的方法，独立于空闲节点的个数，使用复合数据粒度作为节点数据分发的基本单位，减少了数据的通信量；在性能相同的计算节点间，保证了负载均衡。

主权项

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=\frac{f\max }{2}$步骤203：根据得到的f值，以内存调度的页的大小4KB为基数，计算最小数据粒度的大小MinSize：MinSize＝f×4KB其中，1≤f≤fmax，且f为正整数；(3)计算基于四叉树的复合数据粒度：步骤301：根据给定的地形因子，统计其中各种操作符的个数OpNum＝{op₁，op₂，...，op_m}，利用各操作符与加法操作符执行时间t的转化关系W＝{ω₁，ω₂，...ω_m}，计算串行地形因子的总执行时间T：$T=\underset{i=1}{\overset{m}{\Sigma }}{\omega }_i\times {\mathrm{op}}_i\times t$步骤302：利用集群节点上地形因子的计算效率α以及集群节点I/O速度V_I/O，计算四叉树的最大深度N：步骤303：根据四叉树的最大深度N，确定四叉树的最佳深度λ的取值，其中，1≤λ≤N，且λ为正整数：$\lambda =\frac{N}{2}$步骤304：计算复合数据粒度MultiSzie，MultiSize＝4^λ×MinSize(4)计算冗余数据的行、列数以及划分边界冗余数据：a)根据DEM数据的分辨率Resolution以及最大冗余面积m×n，计算所需的冗余行及冗余列：其中，RedundantRow是冗余数据的行数，RedundantCol是冗余数据的列数；b)划分边界冗余数据的方法：(i)对于非最后一行和非最后一列的数据粒度的冗余行列，使用与此数据粒度右相邻和下相邻的数据粒度的行列作为冗余数据；(ii)对于最后一行和非最后一列的数据粒度的冗余只需进行列切割，使用与所述列右相邻的数据粒度的行列作为冗余数据；(iii)对于最后一列和非最后一行的数据粒度的冗余只需进行行切割，使用与所述行下相邻的数据粒度的行列作为冗余数据；(iv)对于最后一行和最后一列的数据粒度的冗余不需要进行切割；(5)计算基于复合数据粒度的节点数据分发数：步骤501：根据全幅DEM数据大小GSize以及复合数据粒度大小MultiSize，计算划分为复合数据粒度的个数p：$p=\frac{\mathrm{GSize}}{\mathrm{MultiSize}}$步骤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)中计算出的所需冗余数据的行、列数以及划分边界冗余数据的方法，给从节点发送冗余行、列。