基于逆向分层的网格工作流调度改进算法

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于逆向分层的网格工作流调度改进算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要:通过对逆向分层DBL(Deadline Bottom level BL)算法的分析与研究,发现当截止期(δn)大于BLmin的情况下,其对逆向分层浮差(Tws)分配上有不足之处。为此该文提出了一种改进算法DBL-LC(Deadline Bottom level-lower cost)。改进算法使得对逆向分层浮差(Tws)的使用更加充分,减少了流时间碎片。实验证明,在相同的截止期下DBL-LC执行费用比DBL算法平均降低了14.52%。

关键词:DBL;改进;DBL-LC;层扩展时间

中图分类号:TP311文献标识码:A 文章编号:1009-3044(2010)07-1576-04

Improving Bottom Level Based Heuristic for Workflow Scheduling in Grids

TENG Hai-tao, MUYIDING・Kamili, SHI Gang, WANG Ming-jun

(School of Information Science and Engineering, Xinjiang University, Urumqi 830046, China)

Abstract: By analyzing DBL(Deadline Bottom Level) algorithm, there is unreasonable problem in allocating Tws when δn>BLmin. Regarding this problem, a improving algorithm called DBL-LC (deadline bottom level-lower cost) algorithm is proposed. Improving algorithm makes good use of Tws and reduces shattering time of workflow. Experimental results show that at same workflow deadline, comparing DBL algorithm, DBL-LC algorithm averagely save 14.52% cost.

Key words: DBL; improving; DBL-LC; level extend time

网格计算[1]是近年来得到快速发展的广域网络计算技术,它所要解决的问题是在动态多制度的虚拟组织之间协调资源共享与操作,这里的共享是指直接访问计算机、软件、数据和其他资源,而不单指文件交换。网格工作流[2-3]作为网格环境下协同工作的重要技术手段引起了学者的普遍关注。有向无环图DAG(Directed Acyclic Graph)是工作流的一种有效描述方式,大量存在于e-science e-business。同时,Web服务的发展使得网格中存在大量功能相同,服务质量QoS(quality of service如执行时间,费用,可靠性等非功能特性)各异的服务。

在有关时间-费用的优化问题已经有了大量的研究,且已被学者证明该优化问题是一个NP-Hard问题[4]。Buyya等[5-6]基于不同deadline/budget约束提出求解独立任务调度的启发式算法。文献[7]对截止期约束进行分解求解策略DTL。将截止期分解成为各层的截止期。文献[8]针对其不足提出了逆向分层算法(DBL),DBL算法使得工作流的执行费用有了大幅度的降低。DBL算法对当全局截止期大于逆向分层最小完成时间(δn>BLmin)时而产生逆向分层浮差(Tws),在各层上进行分配。在这个过程中产生了大量的时间碎片[9],阻碍了工作流执行费用的近一步优化。

本文在DBL(Deadline Bottom Level)的算法的基础之上,提出一种改进算法DBL-LC(Deadline Bottom Level-Lower Cost)。改进算法对δn>BLmin时所产生的逆向分层浮差(Tws =δn-BLmin),根据各层的层扩展时间LETi(Level extend time)进行重新合理分配。在时间碎片[9]方面,改进算法在内容上进行了丰富,将时间碎片分为任务时间碎片(STt)与流时间碎片(STf)。改进算法(DBL-LC)凭借减少流时间碎片(STf)进一步优化工作流执行费用。实验证明,在相同的截止(δn),DBL-LC算法在DBL算法的基础上,使得工作流的执行费用平均降低了14.52%。

1 DBL算法的描述

网格中的大型任务往往可以由许多小规模的子任务协同来完成。子任务及子任务间的制约与依赖关系可以模型化为一个工作流。在有向无环图记作G={V,E}中,V表示所有子任务;E是有向边集合,表示子任务间的制约与依赖关系。假设i,j是子任务编号,当i

在给定的时间限制下,对?坌i∈V都有一组可以完成该子任务的服务,这一组服务称为i的服务集,记为P(i)。这个集中的元素个数记为L(i);Sik表示能完成子任务i的第k个服务;(cik,tik)表示子任务i在服务Sik的执行费用和执行时间,则。表1给出了图1中各子任务的服务集实例。

用户给出工作流截止期δn后,希望在截止期的限制下其任务以最小的费用被执行完成。如果每个子任务在其的服务集中都选择最小费用执行时,则工作流的执行费用即为最小。

在关键路径上的任意子任务都选择最快的服务,其总的执行时间称为工作流下界完成时间(LCT)。并依据关键路径法计算子任务i的最早开始时间ESi,用βi表示子任务i的所允许的最早开始时间,δi表示子任务i的最晚完成时间。形式表示为[8]:

DBL算法是通过将工作流截止时间δn分解为各个子任务的截止时间δi,子任务的开始时间由其前驱子任务来确定。在时间区间[βi,δi]约束下子任务 选择最小费用的服务,其时间约束为[8]:

在有向图DAG中,将子任务i到出口子任务n的最长路径定义为逆向深度BD(i)。再将深度值相同的子任务划为一组,这就构成对DAG逆向分层的BL(i)分组[8]。

第k组所包含的子任务为

BLk={i|BD(i)=k,i∈V} (4)

当每个子任务以最快服务执行时,则BL分组的截止时间与子任务的βi和δi按下式计算得出[8]。

当δn≥BLmin时,DBL算法对Tws采用在各层平均分配的方法从而产生各层的层逆向分差(TLS)。TLS(层浮差)=Tws/(GL-2)(虚子任务除外),公式如下[8]。

DBL算法的基本思想是首先初始化各子任务并查找到相应的资源集,计算出LCT,划分BL分组和求出BLmin。然后根据用户截止期(δn≥ LCT)的大小来选择确定子任务时间区间[βi,δi]的方法:当δn

2 改进算法DBL-LC(Deadline Bottom Level-Lower Cost)

DBL算法将Tws平均分配到BLi各层中,而实际每个子任务的服务集所提供的服务的个数不同,而且每个服务的执行时间也不同。考虑工作流时间―费用的约束时,应当将有限的逆向分层浮差(Tws)进行合理的分配使各层最大限度的降低费用,从而使得全局费用得到进一步的优化。

定义1:在BLmin条件下,子任务i所选取的服务k称为子任务i的标准服务Siks(standard),时间属性值称为标准时间,记为Tiks(standard);费用属性值称为标准费用,记为Ciks (standard)。

定义2:在子任务i的服务集中,时间属性最大者称为子任务i最大执行时间,记为Tikm(max),则该服务对应的费用属性称为子任务i最小费用,记为Cikm(min)(服务的时间属性值与费用属性值成反比,即服务时间越长其费用值越小)。

定义3:在BLi层中,第 层子任务集中各子任务的Tikm与各子任务的Tiks的差值的最大者称为第i层的层扩展时间,记为LETi(Level extend time)。

公式为: (7)

定义4:在BLi层中,第i层子任务集中各子任务的标准费用(Ciks)与其最小费用(Cikm)的差值总和与该层的层扩展时间的比值称为BLi层中第i层的单位时间费用降低值,记为Ri。

公式为: (8)

定义5:工作流中每个子任务都选取服务集中执行时间最短的服务,则在DBL算法下可得出一个最小执行费用的预测执行时间,记为TDBL;在DBL-LC算法下可得出一个工作流最小执行费用的预测执行时间,记为TDBL-LC。

定义6:在算法中(DBL与DBL-LC),某个子任务执行完至它的任一后继子任务开始执行的时间区间称为任务时间碎片,记为STt(Shattering Time of Task)。

如图1中的子任务14有多个前驱子任务(5、8、10、11),在子任务5执行完成后不能立即执行子任务14,这一时间区间即为任务时间碎片。

定义7:在算法中(DBL与DBL-LC),依据算法工作流完成时间小于工作流截止期(此处的工作流截止期小于工作流最小费用的预测完成时间)的那部分时间区间称为流时间碎片,记为STf (Shattering Time Of Flow)。

假定用户给定的截止期为100,在这个时间约束下要使得工作流的执行费用最小。算法是尽最大努力使用这100个时间单位,但在实际执行时却只使用了90个时间单位(些时工作流的执行费用并不是最小费用),那么剩余的10个时间单位即为流时间碎片。

改进算法(DBL-LC)就是针对DBL算法中产生的大量流时间碎片(STf)而做改进。改进算法(DBL-LC)通过减少流时间碎片,使得工作流的执行费用进一步得到优化。

DBL-LC算法在对Tws分配上抛弃了DBL算法的平均分配的方法,而是按照各层的单位时间费用降低值(Ri)的大小来确定其获得分配时间的优先级,然后根据其优先级来确定是否给该层分配时间。单位时间费用降低值(Ri)越大的层被赋予越高的优先级,使其优先从Tws中获得该层的层扩展时间(LETi)的时间需求。当高优先级的层获得了时间分配后,再给具有低优先级的层分配时间,依次类推直至Tws的剩余时间小于任一未获时间分配的层护展时间(LETi)或各层都已获得时间分配为止。(当分配至第i层时,Tws或Tws的剩余时间小于该层的LETi时,则跳过该层给相邻级别低的层分配时间。当Rj=Rj+1时,层扩展时间(LETi)大者具有较高优先级)。从而得到一个按Ri值降序的序列。

OrderBy(Ri)={Rm... Rn}m,n∈BL号

公式(6)改进为公式(9)

其中,XR(i)为布尔变量,其值为1表示BLi层获得了时间分配,否则为0;

如果在BLi层中的各层都获得了各自层的层扩展时间,则工作流的完成时间即为TDBL-LC。

改进算法(DBL-LC):

1)初始化及各子任务的服务集p(i)i∈V;

2)计算求出LCT(最小完成时间);

3)求出各子任务的逆向深度,并划分BL分组;

4)计算出最小完成时间BLmin及工作流的最小费用完成时间TDBL-LC;

5)在截止期有效范围内(TDBL-LC≥ δn≥LCT)输入截止期;

6)当LCT≤δn

7)当δn ≥BLmin时,根据公式(7)求出各层的层扩展时间(LETi);

8)求出各层的Ri,而后按Ri值降序生成一个序列OrderBye(Ri)={Rm… Rn};

9)将逆向分层浮差(Tws)按OrderBye(Ri)依次分配给各层,并得到各层相应的布尔变量XR(i);

10)用公式(9)确定任务的βi和δi;

11)获取就绪子任务队列RL;

12)若RL不空,子任务在约束(2)下从其服务集中选择费用最小服务;否则转步14);

13)子任务在分配资源上执行;

14)等待子任务完成事件;

15)查询是否有还子任务未被调度,有则转步11),否则转步16);

16)汇总各子任务的费用,求出工作流所需总费用Ctotal;

17)输出结果;

3 实例与仿真实验分析

以图1给出的工作流为例。表2是对工作流进行了BL分组,计算出R(i)与XR(i)LETi。

其中,BLi(层子任务集)由公式(3)和公式(4)得出。LETi由DBL-LC算法的定义1,2,3及公式(7)得出。由公式(8)求出各层的Ri值。依据Ri值得出各层获得Tws分配时间的优先级顺序:OrderBy(Ri)={R6,R3,R2,R1,R4,R7,R5}。

由DBL-LC(等同DBL)算法得到的DBLmin=62,逆向分层浮差Tws=38,按优先级排序并得出各层的布尔变量(在本例中,除XR(5) =0外,其余均为1),最后得到XR(i)LETi。

分别计算出DBL与DBL-LC的执行时间与执行费用及其它相关参数,如表3所示。

DBL-LC算法执行中各子任务的开始时间、截止时间及服务集中的服务选择如表4所示。

用DBL-LC算法对实例进行求解中,对用户截止期(δn)使用的更加充分。大大减少了流时间碎片(STf)。在DBL算法中有17个时间单位的流时间碎片,而在DBL-LC算法中流时间碎片减少为1个时间单位。

本例中由于R5(子任务7)的优先级最小,所以子任务7没有获得Tws的时间分配,但在相同的截止期(δn =100)下,工作流执行费用却进一步的降低,Ctotal=448,费用降低率为15.947%。

如果要使整个工作流中的各个子任务都以最低费用执行,则总执行时间为工作流的最小费用执行时间。如果为了使工作流以最小费用的执行,则在不同的算法下,产生预期最低费用的执行时间不同,本例在DBL算法下TDBL=167(62+15*7),才能使得工作流以最小费用被执行,而在DBL-LC算法下 TDBL-LC=104(即再满足子任务7的时间需求)。

为了验证改进算法(DBL-LC)的有效性,本文对改进算法进行了实验仿真和性能分析。实验中工作流采用不同的子任务数随机生成有向图进行模拟,服务集中提供服务的时间属性与费用属性成反比。截止期以BLmin为下界,TDBL-LC为上界,在这之间随机取十个值作为截止期,最后求出费用平均值。

从表5列出的数据所示,在相同的δn下DBL-LC算法比DBL算法在费用上有了进一步的降低,其平均降低率为14.52%。

用户给定的工作流有效截止期(δn)影响着工作流实际执行费用。在一般情况下,截止期越大则其工作流的费用也就越小,随着有效截止期的变化对不同的算法产生不同的影响。图2是含有200个子任务的工作流实例,其显示了DBL-LC算法与DBL算法随有效截止期的变化其费用相应发生变化的情况。

从图2可以看出,当有效截止期大于BLmin时,随着截止期(δn)的增大,DBL与DBL-LC算法的执行费用都相应的降低,但在相同的δn下,DBL-LC算法的费用降低的幅度大于DBL算法。尤其是在δn≥BLmin的初始阶段,DBL-LC算法的费用降低幅度明显优于DBL算法,随后费用降低幅度逐惭减小(降低幅度仍然优于DBL)。其原因是当δn≥BLmin时DBL-LC算法是按其单位时间费用降低值(Ri)的优先级来分配Tws,Ri值大的层优先获得时间分配。

5 结束语

基于逆向分层算法(DBL)在对逆向分层浮差(Tws)分配的不足之处,提出了层的扩展时间(LETi)概念,并依据其各层具有的不同优先级来确定那些层在Tws中获得时间分配。由此而产生了一种改进算法(DBL-LC),改进算法使得在相同的截止期(δn)下,其执行费用较DBL算法有了进一步的降低。

然而,DBL-LC算法仍有许多不足之处。如在减少大量流时间碎片的同时没有减少任务时间碎片,甚至还增大了个别子任务的任务时间碎片。又如在实际工作中,服务池中服务的可靠度也应作为一个重要的参数在本算法中进行研究。

参考文献:

[1] Foster I,Kesselman C,Tuecke S.The Anatomy of the Grid: Enabling Scalable Virtual Organizations[J].International J. Supercomputer Application,2001,15(3):200-222.

[2] Foster I,Kesselman C.The Grid:Blueprint for a Future Computing Infrastructure[M].USA:Morgan Kaufmann Publishers,1999.

[3] Foster I,Kesselman C,Nick J M,et al.Grid service for distributed system integration[J].IEEE Computer,2002,35(6):37-46.

[4] Blythe J,jain S,Deelman E,et al.Task scheduling strategies for workflow-based applications in grids//proceedings of the IEEE International Symposium on Cluster Computing and Grid[M].Cardiff,Wales,UK,2005:759-767

[5] Buyya R,Abramson D,Giddy J,et al.Economic models for resource management and scheduling in grid computing[J].Concurrency and Computation:Practice and Experience Journal (Special Issue on Grid Computing Environments),2002,14(13-15):1507-1542.

[6] Abramson D,Buyya R,Giddy J.A computational economy for grid computing and its Implementation in the Nimrod-G resource broker[J].Future Gendration Computer Systems(FGCS) Journal,2002,18(8):1061-1074.

[7] Yu J,Buyya R,Tham C K.Cost-based Scheduling of work-flow applications on utility grids//Proceedings of the 1st IEEE International Conference on e-Sceence and Grid Computing[M].Melbourne,Australia:IEEE press,2005:140-147.

[8] 苑迎春,李小平,王茜,等.基于逆向分层的网格工作流调度算法[J].计算机学报,2008(2).

[9] 苑迎春,李小平,王茜.基于串归约的网格工作流费用优化方法[J].计算机研究与发展,2008,45(2):246-253.