一种基于分布式内存的并行数字地形分析优化方法

摘要

本发明属于数字地形分析和并行计算的交叉技术领域，涉及一种基于分布式内存的并行数字地形分析优化方法。包括：面向并行数字地形分析的数据分发粒度和结果融合粒度的模型及其计算方法；基于分布式内存的数据顺序分发和调度策略；考虑计算节点启动与关闭开销的数据拆分块数目的最优化方法；基于最优的数据块数目的集群节点配置参数选择方法。本发明完全可应用于大规模海量数据的并行数字地形分析的高性能计算的数据拆分和集群参数选择场合，例如，规则格网并行插值、坡度坡向并行计算、洼地填平并行计算等地形因子提取；可以应用于地理信息处理的高性能计算；也可以应用于基于地理信息的空间决策分析和数据挖掘等应用场合，提高处理效率。

说明书

技术领域

本发明属于数字地形分析和并行计算的交叉技术领域，涉及基于数据密集型的并行计算数 据拆分的优化方法，给出一种基于分布式内存并行计算模式下面向并行数字地形分析的机群最 优的参数选取方法。

背景技术

数字地形分析(Digital Terrain Analysis，简称DTA)是在数字高程模型(Digital  Elevation Model，简称DEM)的基础上进行地形属性计算和特征提取的数字信息处理技术。 数字高程模型DEM是用一组有序数值阵列形式表示地面高程的一种实体地面模型，是数字地形 模型(Digital Terrain Model，简称DTM)的一个分支，其它各种地形特征值均可由此派生。 并行数字地形分析是使用并行计算的技术来解决数字地形分析中的海量数据量的高效处理问 题。随着各种新型传感器以及测量技术的出现，DEM数据呈级数增长，从而导致单机环境下对 大规模的数据进行处理是一件十分困难的事情。因此使用并行计算技术可以有效地解决单处理 器的计算瓶颈问题以及提高数据处理的效率。目前并行数字地形分析的研究热点主要集中在 DEM数据构建的并行化以及数字地形分析算法并行化，其中基于数据密集型并行计算的策略研 究还处在定性分析阶段，而对于数据密集型并行计算策略的建模分析以及量化研究尚未有所涉 及。

数据密集型并行计算的策略主要是指对海量数据进行拆分，然后分发到各个计算节点进行 并行计算，从而提高计算效率。数据拆分是实现并行数字地形分析的主要策略之一。目前，关 于数据拆分的研究主要集中在采用何种数据管理策略来提高并行计算的效率以及相关的存储 策略来降低DEM数据的存储空间。这些研究方法不仅缺乏对拆分数据的大小以及拆分数据之间 的依赖关系等量化问题的研究，而且没有考虑数据拆分与数据及任务调度方式、并行计算的机 群环境，因而难以给出定量化的数据拆分优化方法。

发明内容

本发明针对上述问题，针对点集均匀分布的规则格网DEM，提出了一种基于分布内存并行 计算环境下可量化的数据拆分优化方法和并行计算集群节点最优参数选择。

本发明的一种基于分布式内存的并行数字地形分析优化方法，包括：

(一)确定面向并行数字地形分析的数据分发粒度和结果融合粒度的大小，其中，数据分 发粒度DDG是指任务的计算时间与该任务需要的数据分发时间的比值，可以表示为：

$\mathrm{DDG}=\frac{T_c}{T_d}---\left(1\right)$

T_c为任务的计算时间，T_d为数据的分发时间，包括数据从外部存储器读取的I/O时间；

结果融合粒度RFG是指任务的计算时间与结果的回收与融合时间的比值，可以表示为：

$\mathrm{RFG}=\frac{T_r}{T_d}---\left(2\right)$

T_r为计算结果的回收与融合时间，也包括数据写入外部存储器的I/O时间；

数据分发粒度DDG和结果融合粒度RFG的具体计算过程如下：

步骤11，选取一个大小为Q的基本数据块，然后根据算法设计程序，并运行，分别测得 Q_h＝h*Q的数据分发时间，h为整数且h＝1,2,…10,计算时间和结果回收时间；

步骤12，根据公式(1)和(2)的定义，分别计算得到DDG_h和RFG_h的值，然后分别计算数据 分发粒度DDG和结果融合粒度RFG的平均值，即，

$\mathrm{DDG}=\frac{\underset{h=1}{\overset{10}{\Sigma }}{\mathrm{DDG}}_h}{10}$

$\mathrm{RFG}\frac{\underset{h=1}{\overset{10}{\Sigma }}{\mathrm{RFG}}_h}{10};$

(二)分布式内存并行计算模式下，基于分布式内存的数据顺序分发和调度策略：数据分 发和任务计算同时进行，考虑计算节点或进程启动与关闭开销，计算数据拆分的数据块最优数 目和块大小；基于数据块最优数目，对集群节点配置参数进行优化选择；具体过程包括：

步骤21，确定最优的数据块数目和大小：已知待计算的数据大小W，数据分发速度V,进 程启动延迟开销δ，以及由上一步得到的数据分发粒度DDG和结果融合粒度RFG，根据下面 公式计算得到最优的数据块数目K：

$K=\sqrt{\frac{W(\mathrm{DDG}+\mathrm{RFG})}{\mathrm{V\delta }}}$

步骤22，根据数据大小W和拆分的数据块数目K得到单个数据块的大小P：

$P=\frac{W}{K}$

步骤23，由下式得到总的计算时间为：

$T=2\sqrt{\frac{W(\mathrm{DDG}+\mathrm{RFG})\delta }{V}}+\frac{W}{V}$

步骤24，确定并行计算集群的参数，即节点数目或核总数N，最佳的并行计算集群的节点 数目或核总数应为最优的数据块数目K，即一个轮次全部计算完毕。

本发明的技术特点及有益效果：

1、本发明考虑具有数据密集型特征的数字地形分析算法的线性特征，提出数据分发粒度 和结果融合粒度的概念，应用于分布式内存并行计算模式下，定量化地给出数据划分的最佳数 量，提高并行计算集群的使用效率。

2、本发明考虑分布式内存并行计算模式下，计算节点的启动和关闭开销，建立数据顺序 分发策略下的基于数据分发粒度和结果融合粒度的最优化计算方法，得到数据划分最优的数据 块数目，为数据拆分提供了量化依据。

3、本发明提出的数据拆分的优化计算方法，针对网格DEM数据的特点和数字地形分析算 法的线性特征，保证了并行数字地形分析的精确度，提高了并行数字地形分析的效率。

4、本发明完全可应用于大规模海量数据的并行数字地形分析的高性能计算的数据拆分和 集群参数选择场合，例如，规则格网并行插值、坡度坡向并行计算、洼地填平并行计算等地形 因子提取；可以应用于地理信息处理的高性能计算；也可以应用于基于地理信息的空间决策分 析和数据挖掘等应用场合，提高处理效率。

附图说明

图1为本发明的流程框图；

图2给出了坡度算法的a)DDG和b)RFG随数据块大小的变化曲线；

图3给出了分布式内存模式下的调度策略。

具体实施方式

以下对本发明基于分布式内存的并行数字地形分析优化方法进行详细说明。该方法的具体 步骤如下：

i)数据分发粒度与结果融合粒度

(1)数据分发粒度(Data Distributed Granularity，简称DDG)是指任务的计算时间与该 任务需要的数据分发时间的比值，可以表示为：

$\mathrm{DDG}=\frac{T_c}{T_d}---(i-1)$

这里：T_c为任务的计算时间，T_d为数据的分发时间。注意，这里数据的分发时间包括数 据从外部存储器读取的I/O时间。

一般，T_c是由任务实现的特定算法决定的，即算法的复杂度。当DDG<<1时，本发明称 之为粗粒度的数据分发粒度。也就是说，数据分发的时间远远大于其计算时间，算法非常简单。 在这种情况下，数据的读取与分发要花费很多的时间，计算节点需要较多的等待时间，造成时 间上的浪费。相反，当DDG>>1时，本发明称之为细粒度的数据分发粒度，即任务的计算时 间较长，说明算法是非常复杂的，而数据读取与分发非常迅速。

(2)结果融合粒度(Results Fusion Granularity，简称RFG)是指任务的计算时间与结果 的回收与融合时间的比值，可以表示为：

$\mathrm{RFG}=\frac{T_r}{T_d}---(i-2)$

这里：T_r为计算结果的回收与融合时间，也包括数据写入外部存储器的I/O时间。

当RFG<<1时，说明计算结果回收与融合的时间远远小于其数据分发时间，结果非常简单。 相反，当RFG>>1时，结果回收融合与I/O写入要花费很多的时间，计算节点需要较多的时 间等待下一个任务，造成时间上的浪费。

在数据密集型的并行计算中，要合理的划分数据，需要考虑数据分发粒度和结果回收与融 合的粒度，以确定合理的数据块大小。在分布式并行计算模式下，数据分发粒度和结果回收与 融合粒度主要影响着数据块的大小。例如，当DDG等于1时，假设不考虑结果回收的情况， 当主节点完成分发数据给第一个计算节点后，第一个从节点开始计算；然后主节点分发数据给 第二个从节点。当分发完成时，第一个节点也计算完毕，则主节点再次给第一个节点分发数据。 这样，依次类推，只需要两个从节点就可以完成并行计算。但是，可以看到，这样的方式不能 有效提高并行计算的效率，即加速比很难超过2，也不能充分利用并行计算机群的优势。当然， 很多的算法的DDG都是远远大于1的，本发明可以根据其数据分发粒度来建立最有的机群的 配置参数。

对于数据地形分析的许多算法，DDG和RFG都是一个相对固定的值，且都是远大于1的 值。这是由于，数字地形分析的大多数算法具有局部特征，计算复杂度与数据存在线性关系， 都是在数字高程模型的基础上进行地形特征因子分析。例如，图2给出了坡度算法的DDG和 RFG随数据块大小的变化曲线。

从图2中可以看出，坡度算法的DDG接近于10.41，RFG接近于10.15。

ii)分布式内存模式下的调度策略

在分布式内存模式下，并行计算的调度策略是数据分发和任务计算同时进行，即主节点分 发数据的同时，已经得到数据的从节点立即进行计算，它们可以同时进行。图2给出了分布式 内存模式下的调度策略。当主节点分发数据到第一个计算节点，第一个计算节点开始启动计算。 若没有结果返回，则主节点分发数据块给下一个计算节点；若有结果返回，主节点启动一个线 程接收结果和结果融合，并写入磁盘，然后继续分发数据给下一个空闲的计算节点。依此类推。

从图2中可以看出，当数据分发到第1+DDG+RFG节点时，第一个节点已经计算完毕， 并返回结果，处于空闲状态，可以再次接收数据进行计算。也就是说，集群只需要1+DDG+RFG 个计算节点就可以高效地完成计算任务，再增加节点并不会提高计算效率。

iii)数据拆分的最优计算方法

按照图2的计算方式，考虑到计算节点的子进程的启动和关闭需要一定的开销，设为δ， 则总共K个数据块的总计算时间可表示为：

$\left(\begin{array}{c}T=K\times T_{\mathrm{kd}}+\mathrm{K\delta }+T_{\mathrm{kc}}+k_{\mathrm{kr}}=T_d+T_d\times \frac{\mathrm{DDG}+\mathrm{RFG}}{K}+\mathrm{K\delta }\\ ={(\sqrt{\frac{T_d(\mathrm{DDG}+\mathrm{RFG})}{K}}-\sqrt{\mathrm{K\delta }})}^2+2\sqrt{T_d(\mathrm{DDG}+\mathrm{RFG})\delta }+T_d\end{array}\right)---(\mathrm{iii}-1)$

这里，T_kd,T_kc,T_kr分别为一个数据块的数据分发时间、计算时间和结果回收时间。

要使式(iii-1)达到最小，则第一项为0，即

$\frac{T_d(\mathrm{DDG}+\mathrm{RFG})}{K}=\mathrm{K\delta }---(\mathrm{iii}-2)$

求解式(iii-2)，得到划分的数据块数目K的最优值，

$K=\sqrt{\frac{T_d(\mathrm{DDG}+\mathrm{RFG})}{\delta }}---(\mathrm{iii}-3)$

其中，T_d是数据的分发时间。

设W是要计算的目标数据，以字节为单位，V为数据分发的速度(包括从外部文件读取 和分发给计算节点的时间)，则T_d给出如下：

$T_d=\frac{W}{V}---(\mathrm{iii}-4)$

将式(iii-4)代入式(iii-3)，则得到K的计算公式：

$K=\sqrt{\frac{W(\mathrm{DDG}+\mathrm{RFG})}{\mathrm{V\delta }}}---(\mathrm{iii}-5)$

此时，由式(iii-1)得到总的计算时间为：

$T=2\sqrt{T_d(\mathrm{DDG}+\mathrm{RFG})\delta }+T_d=2\sqrt{\frac{W(\mathrm{DDG}+\mathrm{RFG})\delta }{V}}+\frac{W}{V}---(\mathrm{iii}-6)$

从公式(iii-5)和(iii-6)知道，只要知道了一个并行计算任务对应的算法的数据分发粒 度DDG和结果融合粒度RFG，以及要计算的数据规模W、磁盘I/O速度V和进程启动开销δ， 就能够得出划分数据块最优的数目K和总的计算时间T。

当确立了最佳的数据块数目，可以确定并行计算集群最佳的核总数或节点数目。一般计算 节点(单核)数目或核总数(多核)接近于拆分的数据块数，效率最优。如果计算节点或核总 数多于数据块数目，不会提高计算的效率。

iv)数字地形分析算法的数据块拆分优化和集群参数选择的步骤

a)确定数据分发粒度和结果回收粒度的大小

(1)采用一个大小为Q(MB)基本数据块，然后根据算法设计程序，并运行。分别测得 Q_h＝h*Q,h＝1,2,…10,(h为整数)的数据分发时间，计算时间和结果回收时间。根据公式(i-1) 和(i-2)的定义，分别计算得到DDG_h和RFG_h的值，然后分别计算DDG和RFG的平均值，即，

$\mathrm{DDG}=\frac{\underset{h=1}{\overset{10}{\Sigma }}{\mathrm{DDG}}_h}{10}---(\mathrm{iv}-1)$

$\mathrm{RFG}\frac{\underset{h=1}{\overset{10}{\Sigma }}{\mathrm{RFG}}_h}{10}---(\mathrm{iv}-2)$

b)确定最优的数据块数目和大小

根据公式(iii-5),用已知的待计算的数据大小W，数据分发速度V,进程启动延迟开销δ， 以及由上一步得到的DDG和RFG，就可以计算得到最优的数据块数目K。

然后根据数据大小W和拆分的数据块数得到单个数据块的大小P，即:

$P=\frac{W}{K}---(\mathrm{iv}-3)$

c)确定并行计算集群的参数，即节点数目或核总数

最佳的并行计算集群的节点数或核总数应为数据块数目K，即一个轮次全部计算完毕。

实施例

本发明的实施例提供了一种针对数字地形分析的坡度算法的数据拆分最优的划分数目。设 坡度算法的DDG为10.41，RFG为10.15。假设要计算的数据W大小为1.69GB,数据分发的速度 V为72MB/秒，启动进程的延时δ为0.2秒，则最优的数据块数目为；

最小计算时间近似为：