云环境下科学工作流的调度算法
|
摘要
提出一种云环境下科学工作流的调度算法.针对已有的调度算法和松弛时间资源分配策略均未考虑"或"控制结构的不足,给出了关键活动优先级(Critical Activity Priority, CAP)的概念;定义了活动的服务效益比(Service Benefit Ratio, SBR);提出了活动松弛时间分配策略;并从流程定义和实例运行两个层次,给出了活动截止期限的分配算法.该项研究成果为解决科学工作流调度过程中的时间-成本优化问题提供了更合适的解决方案.
A scheduling algorithm of scientific workflow in commercial clouds is proposed. To solve the problem of the existing scheduling algorithms and the slack time allocation strategies that do not consider the OR control structure, the critical activity priority(CAP) is defined. Also the service benefit ratio(SBR) and slack time allocation strategy of activity are presented. Then, from the two levels of definition time and running time, the deadline distribution algorithm of activity is proposed. The results of this study provide a more suitable solution for solving the time-cost optimization problem in the scientific workflow scheduling.
A scheduling algorithm of scientific workflow in commercial clouds is proposed. To solve the problem of the existing scheduling algorithms and the slack time allocation strategies that do not consider the OR control structure, the critical activity priority(CAP) is defined. Also the service benefit ratio(SBR) and slack time allocation strategy of activity are presented. Then, from the two levels of definition time and running time, the deadline distribution algorithm of activity is proposed. The results of this study provide a more suitable solution for solving the time-cost optimization problem in the scientific workflow scheduling.
引文
1张卫民,刘灿灿,骆志刚.科学工作流技术研究综述.国防科技大学学报,2011,33(3):56-65.[doi:10.3969/j.issn.1001-2486.2011.03.013]
2Barker A,Van Hemert J.Scientific workflow:A survey and research directions.Proceedings of the 7th International Conference on Parallel Processing and Applied Mathematics.Gdansk,Poland.2007.746-753.
3Gil Y,Deelman E,Ellisman M,et al.Examining the challenges of scientific workflows.Computer,2007,40(12):24-32.[doi:10.1109/MC.2007.421]
4Arabnejad V,Bubendorfer K,Ng B,et al.A deadline constrained critical path heuristic for cost-effectively scheduling workflows.Proceedings of the IEEE/ACM 8th International Conference on Utility and Cloud Computing.Limassol,Cyprus.2015.242-250.
5Arabnejad V,Bubendorfer K.Cost effective and deadline constrained scientific workflow scheduling for commercial clouds.Proceedings of the IEEE 14th International Symposium on Network Computing and Applications.Cambridge,MA,USA.2016.106-113.
6Arabnejad V,Bubendorfer K,Ng B.Deadline distribution strategies for scientific workflow scheduling in commercial clouds.Proceedings of the IEEE/ACM 9th International Conference on Utility and Cloud Computing.Shanghai,China.2017.70-78.
7Yu J,Buyya R,Tham CK.Cost-based scheduling of scientific workflow applications on utility grids.Proceedings of 1st International Conference on E-Science and Grid Computing.Melbourne,Australia.2005.140-147.
8Yuan YC,Li XP,Wang Q,et al.Deadline division-based heuristic for cost optimization in workflow scheduling.Information Sciences,2009,179(15):2562-2575.[doi:10.1016/j.ins.2009.01.035]
9Abrishami S,Naghibzadeh M,Epema DHJ.Deadline-constrained workflow scheduling algorithms for infrastructure as a service clouds.Future Generation Computer Systems,2013,29(1):158-169.[doi:10.1016/j.future.2012.05.004]
10Topcuoglu H,Hariri S,Wu MY.Performance-effective and low-complexity task scheduling for heterogeneous computing.IEEE Transactions on Parallel and Distributed Systems,2002,13(3):260-274.[doi:10.1109/71.993206]
11Yu J,Buyya R.Scheduling scientific workflow applications with deadline and budget constraints using genetic algorithms.Scientific Programming,2006,14(3-4):217-230.[doi:10.1155/2006/271608]
12苑迎春,李小平,王茜,等.基于逆向分层的网格工作流调度算法.计算机学报,2008,31(2):282-290.[doi:10.3321/j.issn:0254-4164.2008.02.012]
13郑美光,胡志刚,杨柳,等.使用宽裕时间有效分配优化工作流逆向分层算法.小型微型计算机系统,2016,37(8):1639-1644.[doi:10.3969/j.issn.1000-1220.2016.08.002]
14龙浩,梁毅,邸瑞华.基于相对效费比的网格工作流调度算法.计算机集成制造系统,2010,16(3):589-597.
15彭佳,谭文安,孙勇,等.QoS约束下的分层工作流调度算法.小型微型计算机系统,2015,36(7):1444-1448.[doi:10.3969/j.issn.1000-1220.2015.07.007]
16Xavier S,Lovesum SPJ.A survey of various workflow scheduling algorithms in cloud environment.International Journal of Scientific and Research Publication,2013,3(2):1-3.
17Wu FH,Wu QB,Tan YS.Workflow scheduling in cloud:Asurvey.The Journal of Supercomputing,2015,71(9):3373-3418.[doi:10.1007/s11227-015-1438-4]
18Arya LK,Verma A.Workflow scheduling algorithms in cloud environment-A survey.Proceedings of 2014 Recent Advances in Engineering and Computational Sciences.Chandigarh,India.2014.1-4.
19李慧芳,冯复剑.时间约束工作流的截止期限管理及其动态监控.北京理工大学学报,2011,31(8):937-943.
2Barker A,Van Hemert J.Scientific workflow:A survey and research directions.Proceedings of the 7th International Conference on Parallel Processing and Applied Mathematics.Gdansk,Poland.2007.746-753.
3Gil Y,Deelman E,Ellisman M,et al.Examining the challenges of scientific workflows.Computer,2007,40(12):24-32.[doi:10.1109/MC.2007.421]
4Arabnejad V,Bubendorfer K,Ng B,et al.A deadline constrained critical path heuristic for cost-effectively scheduling workflows.Proceedings of the IEEE/ACM 8th International Conference on Utility and Cloud Computing.Limassol,Cyprus.2015.242-250.
5Arabnejad V,Bubendorfer K.Cost effective and deadline constrained scientific workflow scheduling for commercial clouds.Proceedings of the IEEE 14th International Symposium on Network Computing and Applications.Cambridge,MA,USA.2016.106-113.
6Arabnejad V,Bubendorfer K,Ng B.Deadline distribution strategies for scientific workflow scheduling in commercial clouds.Proceedings of the IEEE/ACM 9th International Conference on Utility and Cloud Computing.Shanghai,China.2017.70-78.
7Yu J,Buyya R,Tham CK.Cost-based scheduling of scientific workflow applications on utility grids.Proceedings of 1st International Conference on E-Science and Grid Computing.Melbourne,Australia.2005.140-147.
8Yuan YC,Li XP,Wang Q,et al.Deadline division-based heuristic for cost optimization in workflow scheduling.Information Sciences,2009,179(15):2562-2575.[doi:10.1016/j.ins.2009.01.035]
9Abrishami S,Naghibzadeh M,Epema DHJ.Deadline-constrained workflow scheduling algorithms for infrastructure as a service clouds.Future Generation Computer Systems,2013,29(1):158-169.[doi:10.1016/j.future.2012.05.004]
10Topcuoglu H,Hariri S,Wu MY.Performance-effective and low-complexity task scheduling for heterogeneous computing.IEEE Transactions on Parallel and Distributed Systems,2002,13(3):260-274.[doi:10.1109/71.993206]
11Yu J,Buyya R.Scheduling scientific workflow applications with deadline and budget constraints using genetic algorithms.Scientific Programming,2006,14(3-4):217-230.[doi:10.1155/2006/271608]
12苑迎春,李小平,王茜,等.基于逆向分层的网格工作流调度算法.计算机学报,2008,31(2):282-290.[doi:10.3321/j.issn:0254-4164.2008.02.012]
13郑美光,胡志刚,杨柳,等.使用宽裕时间有效分配优化工作流逆向分层算法.小型微型计算机系统,2016,37(8):1639-1644.[doi:10.3969/j.issn.1000-1220.2016.08.002]
14龙浩,梁毅,邸瑞华.基于相对效费比的网格工作流调度算法.计算机集成制造系统,2010,16(3):589-597.
15彭佳,谭文安,孙勇,等.QoS约束下的分层工作流调度算法.小型微型计算机系统,2015,36(7):1444-1448.[doi:10.3969/j.issn.1000-1220.2015.07.007]
16Xavier S,Lovesum SPJ.A survey of various workflow scheduling algorithms in cloud environment.International Journal of Scientific and Research Publication,2013,3(2):1-3.
17Wu FH,Wu QB,Tan YS.Workflow scheduling in cloud:Asurvey.The Journal of Supercomputing,2015,71(9):3373-3418.[doi:10.1007/s11227-015-1438-4]
18Arya LK,Verma A.Workflow scheduling algorithms in cloud environment-A survey.Proceedings of 2014 Recent Advances in Engineering and Computational Sciences.Chandigarh,India.2014.1-4.
19李慧芳,冯复剑.时间约束工作流的截止期限管理及其动态监控.北京理工大学学报,2011,31(8):937-943.