一种自适应资源精细匹配的DAG调度方法

胡鹏辉　邓晓华　魏静波　陈腊娇

摘 要： 针对目前计算密集或数据密集特征的任务依赖和并行处理的耦合度过高，采用将关联任务的执行顺序控制与并行算法的处理逻辑相分离。该方法通过任务分解的方式和自适应的多资源精细匹配，利用DEM数据建立起十万量级栅格的大流域生态水文过程DAG任务调度模拟。在实验部分，用多重对比的方法评估在分辨率、数据规模、进程数量以及本地资源管理器（LRM）不同条件情况下该方法的性能。实验结果表明，任务分解的自适应多资源精细匹配DAG调度方法大幅度提高了并行性能和效率，具有较好的鲁棒性和扩展性。

关键词： DAG调度； 并行算法； 数据密集； 计算密集； 多资源匹配

中图分类号： TN911.1?34 文献标识码： A 文章编号： 1004?373X（2017）21?0117?04

A DAG scheduling method for adaptive resources subtle matching

HU Penghui1， 2， DENG Xiaohua1， 2， WEI Jingbo1， 2， CHEN Lajiao3

（1. School of Information Engineering， Nanchang University， Nanchang 330031， China；

2. Institute of Space Science and Technology， Nanchang University， Nanchang 330031， China；

3. Institute for Remote Sensing & Digital Earth， Chinese Academy of Sciences， Beijing 100094， China）

Abstract： For the task dependence of computing intensive or data intensive characteristics and the high coupling degree of parallel processing， a method of separating the execution sequence control of correlation task and processing logic of parallel algorithm is adopted. By means of the task decomposition approach and adaptive multi?resource subtle matching， the DEM data is used to establish the DAG task scheduling simulation of the large watershed eco?hydrology process with hundred?thousand magnitude grids. The method performances of resolution， data scale， progress quantity and local resource manager （LRM） are evalua?ted under the condition of different resolutions by means of the multi?comparison method. The experimental results show that the DAG scheduling method of adaptive multi?resource subtle matching for task decomposition can improve the parallel performance and efficiency greatly， and has strong robustness and perfect scalability.

Keywords： DAG scheduling； parallel algorithm； intensive data； intensive computing； multi?resource matching

0 引 言

水文模型是指水文数学模型，而分布式水文模型是指分布式流域水文数学模型[1]。分布式水文模型与DEM结合，用偏微分方程控制基于物理过程的水文循环时空变化，它是探索和认识复杂水文循环过程和机理的有效手段，可用于解决许多水文实际问题。广泛应用于流域水文的模型主要包含SWAT，SHE，DHSVM，HMS，SVAT，TOPMODEL等。上述流域生态水文过程模型由于缺乏对生态水文耦合机制的描述，以及难以获得植被参数等问题造成了无法满足流域水资源管理的需求。因此，本文采用基于生态最优性原理建立起分布式流域生态水文模型[2?4]。同时，全流域的地学分析和模拟对计算性能提出了更高的要求。特别是处理规模扩大至大区域流域模拟时，数据密集计算问题凸显[5]，这对面向计算密集的集群并行处理极具挑战性。

针对大规模高分辨率、长历时流域的分布式水文模拟计算的情况，若能从任务分解的角度将执行控制和处理逻辑进行解耦则能更准确地模拟计算水文过程[6]。该过程将流域划分为大量的模拟计算栅格任务，依据模拟任务计算间的依赖关系，基于DAG[7?9]调度的并行处理方法将这些计算任务分配到多个计算节点上。由于在DAG调度中，缺乏对任务密集特性及任务规模的考虑，任务调度和资源分配存在一定的盲目性。鉴于此，本文提出一种基于数据密集计算DAG调度及自适应资源协同分配的方法。

1 生态水文模拟计算并行化策略endprint

1.1 栅格任务的划分与汇流网络的构建

采用高分辨率的DEM地形分析提取流域数据，以确定的栅格任务计算单元离散化流域，同时，以确定的栅格任务计算单元间流向关系，在流域流向的基础上，建立汇流网络，如图1所示。以此划分出的栅格任务计算单元是后续计算过程的基本单元，充分考虑了空间的交互作用。

1.2 确定及求解侧向水文模拟、汇流计算的方法

考虑侧向水文过程主要为流域坡面汇流过程。在GIS支持下，采用逐栅格任务计算单元汇流的计算方法。为准确地描述径流运动规律，本文采用改进的生态最优性的定量刻画时，采用水流物理运动为基础的逐栅格汇流方法。由于每个栅格任务计算单元上游的来水和本栅格任务计算单元产水均对该栅格单元土壤水的影响变化起关键作用，因此给出每一个时间步长内栅格单元的水量变化则更为合理。

在逐栅格涉及的坡面水流和河道水流的汇流计算中，采用运动波方程简化圣维南方程组：

[?qs?x+?y?t=P-Qinf] （1）

[qs=αym] （2）

式中：[qs]为地表單宽流量（单位：[m3s-1]）；[P]为降雨量（单位：mm）；[Qinf]为下渗量（单位：mm）。于是可得：

[?y?t+α?ym?x=P-Qinf] （3）

对于运动波的数值解法采用主流的四点隐式有限差分方法来求解式（3），则：

[qj+1i+1-qj+1iΔt+qj+1i+1-qji+1Δt=（P-Qinf）ji] （4）

因此，不难看出栅格单元[t+1]时刻的水位取决于[t+1]时刻上游栅格来水和[t]时刻本栅格单元水位。对于一个栅格单元，只需知道其上游的入流，利用牛顿迭代法便可完成汇流计算，如此模拟整条流域。

1.3 构建流域栅格任务计算单元DAG

针对每条子流域，分别构建栅格任务计算单元依赖关系的DAG。具体实施如下：从流域出口的栅格任务计算单元开始，其次是追踪上游汇入栅格任务计算单元，出口栅格任务计算单元作为父节点。直接上游栅格任务计算单元作为其子节点，以此类推，直到最上游没有流向向内的栅格任务计算单元为止，从而建立一个栅格任务计算单元相关的DAG，如图2，表1所示。父节点任务计算单元的执行依赖子节点的计算完成，追踪树的任何路径需要按照从上游到下游的顺序执行。每一个栅格任务计算单元即将参与计算时，它的直接上流域栅格流量均是已知的。相比传统的生态水文模拟，不同之处在于每一个栅格都将完成整个模拟时段内生态水文过程计算，而且同层栅格任务计算单元是相互独立的，只有存在依赖关系的栅格任务计算之间才进行隐式有限差分法的汇流计算。

2 生态水文模拟计算的DAG调度和自适应资

源协同分配

2.1 流域栅格任务DAG调度

如图3所示，构建起的流域栅格任务DAG调度模型基本思想为：

（1） 利用高分辨率基于DEM地形分析方法提取流域数据，离散化流域栅格任务计算单元根据栅格流向数据文件建立栅格任务计算单元DAG。

（2） 考虑到大量任务间数据依赖关系，利用关键路径确定DAG调度策略来明确任务执行优先级。

（3） 在栅格任务与资源映射中，考虑到资源性能与任务的数据密集程度，利用不平衡搜索算法评估负载状况，结合模拟退火算法进行资源的自适应匹配。

2.2 任务优先级的确定和资源分配策略

初始化栅格任务计算单元一致的优先级，扫描栅格任务DAG以调整任务优先级：叶节点具有最高执行优先级，同为叶节点时，结合任务高度、动态调整的关键路径[10]来区分；任务高度的确定则以已完成任务的所有后续任务的实际执行时间来重新计算，因此关键路径也是在不断调整当中。确定任务优先级是为了确立任务状态队列，任务状态队列在这里分为运行、就绪和失败三类。为了提升系统调度的有效性，对于失败的任务，设置有限次数的任务重提。

目前DAG调度算法缺乏针对不同规模和数据密集程度的处理任务的多资源协同分配机制，且算法选择上需权衡其复杂度与调度效果，而用粒子群或是遗传算法优化的DAG调度算法[11]效果较好，但调度复杂、控制繁琐、开销过大。鉴于此，在任务调度上采用基于关键路径动态调整任务优先级的MPI编程规范算法加以实现，通过使用异步不平衡搜索算法实现节点负载均衡，模拟退火算法用于任务和资源的协同匹配，最终使任务完成时间最少[12?13]。在资源管理器上，选用适合大量任务并发的PBS进行资源的分配，同时，实验部分对比本地fork方法管理资源的性能。

3 实验结果与分析

3.1 实验硬件环境

选择江西省鄱阳湖支流域作为实验区，鄱阳湖位于江西省北部，北纬28°22′～29°45′，东经115°47′～116°45′。流域面积为162 225平方千米。鄱阳湖属北亚热带季风气候，年均气温为16.5～17.8 ℃，年平均降水量为1 570 mm。每年4—9月为汛期，10月至次年3月为枯水期。选取支流域内土地利用和植被、土壤类型单一的为实验区，汇流参数主要是曼宁系数，采用默认值。实验区包含该流域30 m，90 m和270 m分辨率下对应栅格的任务计算单元分别为289 756，51 653和7 156。实验硬件环境如表2所示。实验算法的评价标准有并行程序的加速比和效率，加速比是指串行运行时间和并行运行时间的比值，并行效率是指加速比和运行核数的比值。实验结果均选取三次实验取平均值的方式，对比不同分辨率下不同栅格任务计算单元间并行方法的性能。在资源调度上，对比PBS资源管理器和本地资源fork方法管理性能。

3.2 结果分析

不同分辨率的DEM地形分析提取流域数据时，分辨率越高数据越密集，划分的栅格任务计算单元越多。在30 m，90 m和270 m分辨率下，实验结果如表3所示，评价效果如图4，图5所示。在同一分辨率下，一定的栅格任务计算单元，随着进程数不断增加，并行效率逐渐减小。endprint

例如，在270 m分辨率下，本地资源管理器采用fork的自管理方法时，并行效率下降明显；在进程量为4的情况下并行加速比为3.72；当进程量为64，128时，对应加速比只有26.3，47.1。这表明一方面并行算法能够利用到多核的并行计算环境，另一方面，并行效率提升微弱。这主要是因为，对于低分辨率采集的流域数据任务量较少，并行程度低，用在调度上的开销（进程的上下文切换）、进程间的通信以及其他的系统开销占总的运行时间的比重大。

在不同的分辨率下，将流域划分成不同数据密集程度计算任务时，越密集的计算任务具有更高的加速比。这极大的体现了基于任务分解的DAG调度方法的优势。此时，用于任务的调度开销、进程间的通信和系统开销相对于计算密集和数据密集的并行任务耗费时间比重下降明显。因此，该方法具有更好的并行性能。

随着任务规模的提升，数据密集、计算密集程度加剧，进程量成倍增加时，并行效率平稳下降。这证明了并行程序具有高度的可扩展性。同规模的计算任务，并行效率的提升受进程的数量影响巨大。在大规模的并行任务中，可并行的任务线程量达到一定程度，消耗最多的资源是内存，一旦内存达到瓶颈，整个系统将面临崩潰。对此，提供的自适应资源的分配策略就是限定资源池的最大量，进而约束最大并行线程量，同时根据内存的耗费情况反馈给资源调度器以达到资源分配的自适应性，最终保证了系统的鲁棒性。实验对比了并行算法在PBS和本地自管理fork（）资源两种情况下，采用PBS多任务并行调度，能将数以十万级栅格任务并行效率提升18.8%～23.6%，特别是任务规模较小、并行进程量为128时，效率提升更加明显。

4 结 论

本文针对计算密集和数据密集特征的任务依赖与并行处理的耦合度过高的情况，提出将关联任务的执行顺序控制与并行算法的处理逻辑相分离。实验中采用了多重对比的方法，在数据规模、进程数量以及本地资源管理器三个方面评估了该方法的性能，本文的并行算法在大规模并行任务计算当中表现出良好的鲁棒性和扩展性。在并行效率方面，数以十万级的并行任务，进程数量高达128时，并行效率在75%以上，较高限度地利用了多核计算环境，大幅度降低任务执行时间。同时，配合多任务并行的资源管理器（PBS），实际并行效率能提高18.8%～23.6%。

参考文献

[1] 徐宗学，程磊.分布式水文模型研究与应用进展[J].水利学报， 2010，41（9）：1009?1017.

[2] CHEN L J， ZHU A X， QIN C Z， et al. Review of eco?hydrological models of watershed scale [J]. Progress in geography， 2011， 30（5）： 535?544.

[3] CHEN L J. An optimality?based fully distributed watershed ecohydrological model [D]. Beijing： University of Chinese Academy of Sciences， 2012.

[4] 陈腊娇.基于生态最优性原理的全分布式流域生态水文模型[D].北京：中国科学院研究生院，2012.

[5] FURHT B， ESCALANTE A. Handbook of data intensive computing [M]. New York： Springer， 2011.

[6] 刘军志，朱阿兴，秦承志，等.分布式水文模型的并行计算研究进展[J].地理科学进展，2013，32（4）：538?547.

[7] LIU Fang， WANG Zhiyong. DAG?extended deletion algorithm in graphical abstract grid workflow model for remote sensing quantitative retrieval [C]// Proceedings of 2010 the 2nd International Conference on Education Technology and Computer. [S.l.]： IEEE， 2010： 369?373.

[8] CANON L C， JEANNOT E. Evaluation and optimization of the robustness of DAG schedules in heterogeneous environments [J]. IEEE transactions on parallel and distributed systems， 2010， 21（4）： 532?546.

[9] CHEN Jinlin. An updown directed acyclic graph approach for sequential pattern mining [J]. IEEE transactions on knowledge and data engineering， 2010， 22（7）： 913?928.

[10] 陈养平，王来熊，黄士坦.DAG任务模型的粒子群优化调度算法[J].武汉大学学报，2007，40（2）：130?138.

[11] 张聪，沈惠璋.基于量子粒子群优化的DAG并行任务调度研究[J].计算机应用研究，2010，27（7）：2459?2461.

[12] LUSK E L， PIEPER S C， BUTLER R M. More scalability， less pain： a simple programming model and its implementation for extreme computing [J]. SciDAC review， 2010， 17： 30?37.

[13] KIRKPATRICK S， GELATT C D， VECCHI M P. Optimization by simulated annealing [J]. Science， 1983， 220（4598）： 671?680.endprint