多DAG工作流在云计算环境下的可靠性调度方法景维鹏;吴智博;刘宏伟;舒燕君【摘要】In order to solve the reliable scientific workflow scheduling problem for cloud computing, a dynamic of the RANK-Hierarchical algorithm is put forward which takes account of communication contention as well as supports task dependencies (CCRH). A communication contention model is first defined, as soon as the earliest completion of the primary and backup task is deduced. Besides, the executived processor is limited. We use the dynamic hierarchical method and calculate each DAG unfair degree factor for multiple DAGs scientific workflow. It can deal with the situation that multiple DAGs workflow comes at different times and there are various kinds of structure. Both the theory and experiments have proved that the algorithm can not only improve the scheduling fairness of multiple DAGs workflow but also shorten the average execution Makespan.%针对云计算环境中多个DAG科学工作流的可靠性调度问题,提出一种考虑虚拟机之间链路通信竞争的动态多DAG分层调度算法.首先使用通信竞争模型描述虚拟机之间的通信,然后分别计算主版本及副版本任务的最早完成时间,并限定任务所调度的虚拟机单元.再对多个同时到达的DAG工作流任务使用动态分层方法,计算每个DAG任务的不公平程度因子.该算法有效解决了当多个DAG中任务的权值相差较大时,之前到达的DAG不会因为剩余任务迟迟得不到调度而导致执行时间跨度增大的问题.仿真实验表明,在保证可靠调度的前提下,该算法不仅能提高多个DAG调度的公平程度,而且能有效地缩短多个DAG调度的平均最早完成时间.【期刊名称】《西安电子科技大学学报（自然科学版）》【年(卷),期】2016(043)002【总页数】6页(P83-88)【关键词】云计算;多个DAG;可靠性调度;公平因子【作者】景维鹏;吴智博;刘宏伟;舒燕君【作者单位】哈尔滨工业大学计算机科学与技术学院,黑龙江哈尔滨 150001;东北林业大学信息与计算机工程学院,黑龙江哈尔滨 150040;哈尔滨工业大学计算机科学与技术学院,黑龙江哈尔滨 150001;哈尔滨工业大学计算机科学与技术学院,黑龙江哈尔滨 150001;哈尔滨工业大学计算机科学与技术学院,黑龙江哈尔滨 150001【正文语种】中文【中图分类】TP306云计算作为一种崭新的计算模式得到越来越多的关注.它将各种分布的计算、存储及应用资源进行整合并实现多层次的虚拟化与抽象化,有效地将各类资源以服务的形式提供给用户.云计算中资源调度的目的是实现计算资源、存储资源集合与调度任务集合满足有效空间和时间映射关系.因此,云计算环境下设计有效解决任务之间依赖关系的资源调度策略,是实现云计算科学工作流高可扩展、高可用性的关键. 在云计算科学工作流的应用中,面临的是海量密集型数据的处理,具体表现为:在云计算科学工作流调度过程中,存在多个有向无环图(Directed Acyclic Graph,DAG)同时提交或在计算过程中动态提交的情况,因此要求多DAG的科学工作流的调度算法必须要满足环境的动态变化和对动态到达的工作流进行实时处理的需求;企业级的工作流应用中,需要设置有效的容错保障机制以容忍系统运行时遇到的故障;合理地调度机制应该保障用户提交的科学计算请求不因数据中心的负载、位置而受到影响.文献[1]从不同角度证明了调度算法在科学工作流应用中的重要性.近年来,针对单个DAG任务的科学工作流调度,无论是调度模型,或是调度目标的多样性均取得很大进展,然而针对科学工作流应用的多DAG调度的研究相对较少,文献[13]提出一种逐个执行多DAG任务的方法,该方法导致虚拟机会产生大量的空闲等待时间,延长了任务的执行时间.文献[2,4,13]提出将多个DAG合并成为一个复合DAG后,再使用调度整个DAG任务的方法来调度负荷后的DAG任务.这些方法均忽略了存在于各DAG之间调度的不公平性问题.文献[3]提出了一种Planner-guided的调度策略,算法使用动态RANK-HYBD方法对多DAG任务分配优先级,但该算法未考虑DAG任务在不同时间到达的情况.另外,由文献[3]分析表明,简单的DAG任务合并,并不能显著提升算法的性能.文献[14]提出了一种面向数据密集型应用的离线时间开销多DAG任务调度算法,但该算法没有解决之前到达的DAG任务不会因为剩余任务迟迟得不到调度而导致执行时间跨度增大的问题.综上,如何有效地解决多DAG任务调度的公平性,满足多个DAG任意时间提交的可靠性调度技术是云计算环境下多DAG调度问题的关键.由于云计算是建立在大规模廉价服务集群上的一种新的服务模式,加上计算任务的复杂性和动态性,导致计算节点极易出现故障,因此,调度算法必须在探求整体任务的最短完成时间的情况下进行,提高任务调度的可靠性.文献[5-8]中论述使用主副版本的调度机制是有效提高调度算法可靠性的主要方法.文献[5]提出使用完全复制方法对任务进行复制,并定义执行副本的具体时间;文献[6]提出一种能够满足最佳最早完成时间(Makespan)和可靠性的实时调度算法;文献[7]在文献[6]算法的基础上使用Map Reduce编程框架,实现可靠性和性能最优;文献[8]提出优先级约束、可靠性代价驱动的容错调度方法,该算法强调“强主版本复制”,要求任务必须收到它所有前驱节点的结果,使该算法只考虑任务的前驱节点,而没有考虑所有节点任务的完成问题.文献[5,7-8]使用复制的方法在可靠性和系统性能之间取得折衷.但这些方法仅仅对复制任务本身进行判断,没有算法对副版本任务开始时间进行准确的计算,这样使得算法性能受到极大影响.另外,上述调度算法均假设任意网络的虚拟机是全互连结构,同时也假设调度器与虚拟机之间及虚拟机之间是可以随时获取相关调度信息,而在实际应用中,在云计算复杂环境中这种假设是不成立的.文献[11]的研究表明,考虑通信链路通信竞争的调度算法能有效提高算法的精度.文献[9]在异构计算环境下的通信竞争模型,利用该模型证明了调度算法的有效性,但该模型是考虑任意网络互连情况;文献[10]在通信竞争模型下,使用最短路径的搜索算法实现了任意互连网络中虚拟机的查找问题及调度问题.综上,笔者提出一种面向科学工作流应用的动态多DAG分层调度算法(CCRH).该算法首先使用通信竞争模型描述虚拟机之间的通信竞争,使用主副版本技术提高调度算法的可靠性,针对多DAG使用公平因子的分层调度策略;仿真实验表明了算法的有效性.典型的云计算科学工作流的应用,在不同时刻动态提交的任务用DAG来表示,进行形式化定义如下.定义1 四元组G=(V,E,w,c),表示节点和边的DAG图,其中,V={v1,v2,v3,…,vN},表示任务集合,N表示任务数,任务之间具有的依赖关系用E={eij|vi,vj∈V}表示,w(vi)表示任务vi的计算代价,c(eij)表示任务vi和vj之间的通信代价.定义2 集合{vx∈V:exi∈E}表示任务vi前驱节点集合,记为pred(vi).集合{vx∈V:eix∈E}表示任务vi后继节点集合,记为succ(vi).如果pred(vi)=Ø,则任务节点vi是入口节点,记为ven try.如果succ(vi)=Ø,则任务节点vi是出口节点,记为vexit.定义3 云计算的计算资源由于进行虚拟化,这里将虚拟化后异构的虚拟机集合描述为P={P1,P2…,PM},其中M表示虚拟机个数,调度到虚拟机Pk上的任务vi的主版本开始时间表示为tps(vi,pk),完成时间分别表示为tpf(vi,pk);任务vj副版本开始时间和完成时间分别表示为tBs(vj,pk),tBf(vj,pk),任务vi的主、副版本任务被调度的虚拟机表示为Pp(vi)和PB(vi).定义4 云计算系统是任意互联的网络结构.虚拟机之间的网络连接包括计算节点内部、同一机柜内部以及不同机柜,这里用lhk表示Ph与Pk之间的通信代价.2.1 任务优先级单个DAG任务优先级使用静态调度方法计算,受HEFT[12]算法启发,假设任务vi和vj具有依赖关系,且vj的运行直接依赖于vi的运行结果.考虑计算与通信总体消耗的任务优先级表示为其中,表示任务vi在所有虚拟机上的平均执行代价表示任务vi和vj之间的平均通信代价.由式(1)可知,任务vi的优先权是其直接后继任务优先权与相应通信代价之和的最大值加上自身的计算代价.由于所有任务的优先权都是从出口任务向上遍历任务图,因此,出口任务优先权表示为云计算环境下的通信存在于处理机内、机柜内、机柜之间,因此必须将通信边调度考虑进来,以此实现更加严谨的调度模型.文中使用文献[11]提出的基于插入策略的最短路径搜索算法,实现云计算环境下任意网络互连异构计算系统的通信路径查找.这里,定义LST(eij,l),LFT(eij,l)为eij在通信链路l的通信开始时间和完成时间,且LFT(eij,l)≥LST(eij,l)+c(eij).2.2 主副版本任务调度为了提高云计算系统的可靠性,文中使用主副版本的调度方法,即通过在备份虚拟机上执行冗余任务来实现容错,同时保证任务的实时性.通过准确分析主、副版本任务的开始时间及满足所调度的虚拟机(虚拟计算节点)的约束,在满足系统可靠性的前提下,获得较好的Makespan.2.2.1 主版本任务调度调度方法首先解决主版本任务调度,依据前驱节点集合pred(vj)中任务的副版本完成时间,任务vj的主版本的开始时间tps(vj,p)有以下3种状态:(1)任务vj的主版本的完成时间小于集合pred(vj)中任务的副版本最迟完成时间与通信链路完成时间的最大值.(2)任务vj的主版本开始时间大于集合pred(vj)中的任务的副版本最迟完成时间与通信链路完成数据传输时间的最大值.(3)任务vj的主版本开始时间介于pred(vj)中任务主、副两个版本最迟完成时间与通信链路完成时间的最大值之间,且其完成时间在其最大副版本完成时间之后.由以上3种情况可知,算法CCRH中不同DAG任务的主版本调度约束,在满足其自身优先级任务约束的情况下,可以对其进行独立调度,只需依据调度虚拟机队列寻找最早开始的完成任务的虚拟机即可,其调度的虚拟机也没有严格的限制.2.2.2 副版本任务调度下面分析任务vj的副版本任务执行的最早开始时间.首先定义副版本调度满足的约束条件,当任务vj的主版本调度满足状态(2)或(3)时,它的副版本任务的开始时间必须满足当任务vj的主版本调度满足状态(1)时,副版本任务的最迟开始时间必须满足任务vj的主版本调度满足状态(2)时,它的副版本任务的所能调度虚拟机满足任务vj的主版本调度满足状态(1)或(3)时,pred(vj)2表示集合pred(vj)中满足状态(1)或(3)的任务集合,pd(vj)为vj所有任务中与vj存在间接与直接依赖关系满足状态(1)或(3)的任务集合.由于因此,有这里,表示pd(vi)所有主版本任务所在虚拟机.云计算环境下科学工作流任务调度的一个重要目标是获取任务的最早完成时间(Makespan).多DAG任务的最早完成时间可以用出口节点副版本的完成时间表示,CCRH寻求的副版本的最早开始时间,即完成了对整个任务调度策略的出口任务的副版本最早完成时间即可,即2.3 多DAG分层调度在云计算系统的多DAG调度模型中,由于一个DAG工作流a要与其他的DAG工作流争用同一组计算资源,所以工作流a的Makespan(从提交DAG a开始到DAG a的最后一个任务执行完毕所用的时间)很可能比a单独使用该云计算环境的Makespan要长,这两个Makespan可分别被表示为Mmulti(a)和Mown(a),文献[12]定义Slowdown描述这一比值:SSlowdown=Mmulti(a)Mown(a),因此某个调度算法S的不公平程度因子UUn faines(s)定义为其中,A为给定的多个DAG的集合,AAvgSlowdown是所有DAG的SSlowdown 平均值,即AAvgSlowdown=表示集合A的基.UUn fairn ess(S)是用来衡量多DAG调度算法S调度的不公平程度的重要指标.由此笔者提出基于分层的多DAG 调度方法,其基本原则是对任意时刻到达云计算环境的每一个DAG进行分层,而后到达的DAG中的每一层依次归并到之前DAG中还未执行的任务所在的每一层,然后对每一层中的任务,按照式(1)的权值计算公式进行递增排序.这样即可有效地避免先前DAG因剩余任务迟迟得不到调度而导致时间跨度增大的问题.仿真实验将算法与HEFT[12]、BMCT[13]分别采用公平因子调度后的公平性、调度时长、虚拟机利用率、任务运行时间这4个方面性能进行比较(HEFT的多DAG 任务采用与文献[13]相同的分层方法).为了更好体现算法在科学工作流调度中的优势,使用两种类型的DAG任务:随机DAG任务、快速傅里叶变换(Fast Fourier Transform,FFT),其中每种类型的DAG包括2～10个DAG任务,每个DAG包含10～50个任务.使用CCR描述DAG任务图中通信与计算比率,CCR的值选择0.1～1的随机数.实验环境为Inter(R)Xeon E7420 2.13 GHz,RAM 4GB,硬盘1 TB的10台服务器搭建具有30个虚拟计算平台,为了模拟云计算平台,在每个计算节点上使用虚拟化Xen创建了虚拟集群,以模拟数据中心的云计算环境,3.1 公平性算法的公平性能够有效反应调度算法在处理多个DAG任务时,能够公平的对待不同优先级以及不同时间提交的问题,实验通过不同的科学工作流的DAG任务,对CCRH、HEFT、BMCT算法的公平性进行比较.图1表示3种算法在随机DAG任务、FFT下的DAG任务的公平性.由图1可以看出,由于HEFT与BMCT采用相同的分层的方法,其公平性没有太大的差异,而CCRH由于采用动态分层的方法,其公平性有了较大的提高,而且没有出现较大的跳变现象.3.2 算法Makespan算法Makespan性能可以有效反应不同调度算法的调度时长,实验通过不同的科学工作流的DAG任务,对CCRH、HEFT、BMCT算法的Makespan进行比较.图2表示3种算法在随机DAG任务、FFT图中的Makespan.由图2可以看出,3种算法的Makespan性能均在可接受的范围之内.其主要原因是,3种算法选择相似的优先级比较算法.BMCT优于HEFT的原因是BMCT考虑任务之间的通信约束,而CCRH由于采用主副版本技术,提高系统可靠性,但其副版本任务的执行增加了算法的Makespan.可以看到,在提高系统可靠性的前提下,系统增加的Makespan在可接受的范围内.3.3 大规模数据运算时间为了更好测试算法的在大规模数据运算时的Makespan性能,验证主副版本技术在提高系统可靠性同时,对计算性能的牺牲.实验分别对比3种算法在随机产生的100个DAG图任务的运行时间(Makespan)进行比较,由图3可以看出,HEFT在3种算法在40个任务时,其Makespan基本相同,随后BMCT表现出较差的Makespan,在DAG任务达到80时,CCRH的Makespan性能下降较为明显,在100个DAG 任务时调度算法获得的Makespan为原来的2倍,其牺牲的系统运行时间在可接受范围之内.3.4 资源利用率为了更好体现算法对云环境资源的利用,考查不同的科学工作流负载中,虚拟计算节点的平均使用情况.从图4中可以看出,CCRH拥有较高的虚拟机利用率,因而在资源使用计费的云环境中,CCRH拥有较好的效益,并且能提高系统的负载均衡性.笔者针对云计算系统中科学工作流的可靠调度问题,通过使用主副版本技术,利用动态分层调度的方法,有效解决了多DAG调度的不公平性问题.仿真实验表明,该算法在满足可靠性要求的前提下,其公平性、Makespan、资源利用率、系统运行时间均表现出较好的性能.【相关文献】[1]WIECZOREK M,PRODAN R,FAHRINGER T.Scheduling of Scientific Workflows in the Askalon Grid Environment [J].SIGMOD Record,2005,3(34):56-62.[2]MANDAL A.Scheduling Strategies for Mapping Application Workflows onto theGrid[C]//Proceedings of the 14th International Symposium on High Performance Distributed Computing.New York:ACM,2005:125-134.[3]田国忠,肖创柏,徐竹胜,等.异构分布式环境下多DAG工作流的混合调度策略[J].软件学报,2012,23(10):2720-2734.TIAN Guozhong,XIAO Chuangbai,XU Zhusheng,et al.Hybrid Scheduling Strategy for Multiple DAGs Workflow in Heterogeneous System[J].Journal of Sofware,2012,23(10):2720-2734.[4]ZHAO H,SAKELLARIOU R.Scheduling Multiple DAGs onto HeterogeneousSystems[C]//Proceedings of the 20th International Parallel and Distributed Processing Symposium.Piscataway:IEEE,2006:1639387.[5]ZHANG J,SHA E H M,ZHUGE Q,et al.Efficient Fault-tolerant Scheduling on Multiprocessor Systems via Replication and Deallocation[J].International Journal of Embedded Systems,2014,6(2/3):216-224.[6]BARUAH S,BONIFACI V,MARCHETTI-SPACCAMELA A,et al.A Generalized Parallel TaskModel for Recurrent Real-time Processes[C]//Proceedings of the 33th Real-time Systems Symposium.Piscataway:IEEE,2012:63-72.[7]RAJU R,AMUDHAVEL J,PAVITHRA M,et al.A Heuristic Fault Tolerant Mapreduce Framework for Minimizing Makespan in Hybrid Cloud Environment[C]//Proceedings of the IEEE International Conference on Green Computing,Communication and Electrical Engineering.Piscataway:IEEE,2014:6922462.[8]XIE G Q,LI R F,LIU L,et al.DAG Reliability Model and Fault-tolerant Algorithm for Heterogeneous Distributed Systems[J].Information Processing Letters,2009,109(11):539-542.[9]QIN X,JIANG H.A Novel Fault-tolerant Scheduling Algorithm for Precedence Constrained Tasks in Real-time Heterogeneous Systems[J].ParallelComputing,2006,32(5):331-356.[10]SINNEN O,SOUSA L A.Toward a Realistic Task Scheduling Model[J].IEEE Transactions on Parallel and Distributed Systems,2006,17(3):263-275.[11]景维鹏,吴智博,刘宏伟,等.支持优先级约束任务的容错调度算法[J].清华大学学报,2011,51(S1):1440-1444.JING WEIPENG,WU ZHIBO,LIU HONGWEI,et al.Fault-tolerant Scheduling Algorithm for Precedence Constrained Tasks[J].Tsinghua Science and Technology,2011,51(S1):1440-1444.[12]MACEY B S,ZOMAYA A Y.A Performance Evaluation of CP List Scheduling Heuristics for Communication Intensive Task Graphs[C]//Proceedings of the International Parallel Processing Symposium.Los Alamitos:IEEE Computer Society,1998:538-541.[13]TOPCUOGLU H,HARIRI S,WU M.Performance Effective and Low-complexity Task Scheduling for Heterogeneous Computing[J].IEEE Transactions on Parallel and Distributed Systems,2002,13(3):260-274.[14]谢国琪,李仁发,杨帆,等.异构网络化汽车电子系统中多DAG离线任务调度[J].通信学报,2013,34(12):20-32.XIE Guoqi,LI Renfa,YANG Fan,et al.Multiple DAG Off-line Task Scheduling for Heterogeneous Networked Automobile Electronic Systems[J].Journal on Communications,2013,34(12):20-32.。
