截止期约束的网格工作流费用优化算法研究
|
摘要
网格工作流任务调度算法本质是资源选择策略,是用于为工作流中具有前后约束关系的任务从功能比较相似、性能有些差异的网格资源中选择适当的资源,以满足不同调度目标的策略。
DAG图(即有向无环图,Directed Acrylic Graph)描述的网格工作流时间-费用优化问题是计算网格中一个基本的且NP-hard的问题,目前已有许多关于最小化完工时间的优化算法。但随着网格应用向商业化方向发展,网格资源变为有偿服务,这使得工作流调度不仅要优化完工时间,还要优化费用。
本文简要介绍了网格及网格工作流的相关概念及关键技术,综述了网格工作流优化问题的相关算法。另外,针对截止期约束的网格工作流费用优化问题,本文提出了三个调度算法:基于贪心策略的网格工作流调度算法GSA-GW (Greedy Scheduling Algorithm for Grid Workflow)、改进贪心算法IGSA-GW (Improved GSA-GW)和分层贪心结合算法BLGA-GW(Bottom Level and Greedy Algorithm for Grid Workflow)。文章首先按照用户提交的截止时间建立数学模型,然后利用上述三个算法求得近似最优解,最后通过模拟实验,证明了这三个算法能较好地满足用户的时间费用要求。
Workflow scheduling is one of the key issues in the workflow management. It allocates suitable resources to execute workflow tasks so that the execution can be completed to meet the requirements of the users or the system. Many grid applications must be modeled as complex workflows. Thus, the scheduling of workflow applications becomes a significant and essential problem in Grids.
Over the last few years, the increasing demand for grid computing resources calls for an incentive-compatible pricing mechanism for differentiated services. In such“pay-per-use”Grids, each service provider charges users a differentiated price according to the requests. Cost and time become two primary factors that users are concerned about. So the time–cost optimization problem for scheduling workflow applications which described by Directed Acyclic Graph (DAG) becomes an essential and complex problem. In general, it is NP-hard.
Firstly, this thesis introduces the related concepts of grid and grid workflow. Secondly, this paper summarizes the correlative scheduling algorithms for Grid workflow. And then, we proposed three new algorithms GSA-GW (Greedy Scheduling Algorithm for Grid Workflow), IGSA-GW(Improved GSA-GW) and BLGA-GW(Bottom Level and Greedy Algorithm for Grid Workflow) to optimize the cost of workflow while meeting the deadline delivered by users. According to the Deadline submitted by users, this paper establishes a mathematical model, and then use the algorithms proposed in this paper to tackle it. Simulation results reveal that the algorithms can satisfy the user’s Deadline and optimize the costs well.
DAG图(即有向无环图,Directed Acrylic Graph)描述的网格工作流时间-费用优化问题是计算网格中一个基本的且NP-hard的问题,目前已有许多关于最小化完工时间的优化算法。但随着网格应用向商业化方向发展,网格资源变为有偿服务,这使得工作流调度不仅要优化完工时间,还要优化费用。
本文简要介绍了网格及网格工作流的相关概念及关键技术,综述了网格工作流优化问题的相关算法。另外,针对截止期约束的网格工作流费用优化问题,本文提出了三个调度算法:基于贪心策略的网格工作流调度算法GSA-GW (Greedy Scheduling Algorithm for Grid Workflow)、改进贪心算法IGSA-GW (Improved GSA-GW)和分层贪心结合算法BLGA-GW(Bottom Level and Greedy Algorithm for Grid Workflow)。文章首先按照用户提交的截止时间建立数学模型,然后利用上述三个算法求得近似最优解,最后通过模拟实验,证明了这三个算法能较好地满足用户的时间费用要求。
Workflow scheduling is one of the key issues in the workflow management. It allocates suitable resources to execute workflow tasks so that the execution can be completed to meet the requirements of the users or the system. Many grid applications must be modeled as complex workflows. Thus, the scheduling of workflow applications becomes a significant and essential problem in Grids.
Over the last few years, the increasing demand for grid computing resources calls for an incentive-compatible pricing mechanism for differentiated services. In such“pay-per-use”Grids, each service provider charges users a differentiated price according to the requests. Cost and time become two primary factors that users are concerned about. So the time–cost optimization problem for scheduling workflow applications which described by Directed Acyclic Graph (DAG) becomes an essential and complex problem. In general, it is NP-hard.
Firstly, this thesis introduces the related concepts of grid and grid workflow. Secondly, this paper summarizes the correlative scheduling algorithms for Grid workflow. And then, we proposed three new algorithms GSA-GW (Greedy Scheduling Algorithm for Grid Workflow), IGSA-GW(Improved GSA-GW) and BLGA-GW(Bottom Level and Greedy Algorithm for Grid Workflow) to optimize the cost of workflow while meeting the deadline delivered by users. According to the Deadline submitted by users, this paper establishes a mathematical model, and then use the algorithms proposed in this paper to tackle it. Simulation results reveal that the algorithms can satisfy the user’s Deadline and optimize the costs well.
引文
[1] Ian Foster, Carl Kesselman. The Grid: Blue Print for a New Computing Infrastructure[M]. Morgan Kaufmann Publisher, 1999: 25-29.
[2] Ian Foster. Grid Technologies and Applications: Architecture & Achievements[C]. Intl Conference on Computing in High Energy and Nuclear Physics,2001:51-63.
[3] Ian Foster. The Grid: A New Infrastructure for 21st Century Science[J]. Physics Today, 2002, 55(2):42-47.
[4] Ian Foster, C.Kesselman, J.Nick, et al. Grid Services for Distributed Systems Intergration[J]. IEEE Computer. 2002, 35(6):135-160.
[5] Suraj Pandey, Rajkumar Buyya. Scheduling of Scientific Work?ows on Data Grids[C]. Eighth IEEE International Symposium on Cluster Computing and the Grid. 2008: 548-553.
[6]徐志伟.织女星网格的总体思路[J].计算机研究与发展. 2002, 39(8): 923-929.
[7]桂小林.网格技术导论[M].北京邮电大学出版社, 2005: 1-30.
[8] I. Foster, C. Kesselman, etal. The Anatonmy of the Grid: Enabling Scalable Virtual Organizations[J]. Journal of High Performance Computing Applications. 2001, 15(3): 200-222.
[9] Basney J, Livny M. Deploying a High Throughput Computing Cluster[J]. High Performance Cluster Computing, Prentice Hall, 1999:193-198 .
[10]都志辉,陈渝,刘鹏.网格计算[M].北京:清华大学出版社,2002: 1-29.
[11] Ian Foster. What is the Grid? A Three Point Checklist[M]. GRID Today, 2002: 5-10.
[12] Ian Foster, Carl Kesselman, et al. The Physiology of the Grid: An Open Grid Services Architecture for Distributed Systems Integration[EB/OL]. http://www.globus.org/research/papers/ogsa.pdf,2008-11-13.
[13]王瑄,李燕.应用Web Services构建多层架构的高效NET应用[M].科学出版社. 2005, 6: 17-31.
[14] Jia Yu, Rajkumar Buyya. A Taxonomy of Workflow Management Systems for Grid Computing [J]. Journal of Grid Computing, 2005, 3(3-4): 171~200.
[15] Workflow Management Coalition. The Workflow Reference Model[S]. WFMC-TC-1003,1994.
[16]黄福华.网格工作流技术综述[J].福建电脑报. 2008, 1: 1-32.
[17]张云峰,葛炜.基于服务质量的网格工作流算法优化[J].计算机科学. 2004, 31(9):230-233.
[18]田国忠,于炯,侯勇,邢剑等.基于资源状态可靠度的网格工作流调度算法[J].计算机工程与应用, 2008, 44(18): 115-118.
[19]余波,周龙骧,钟锡昌,张倪.网格工作流技术综述[J].计算机工程, 2006, 32(2): 4-36.
[20] E. Deelman, J. Blythe, et al. Mapping Abstract Complex Workflows onto Grid Environment. Journal of Grid Computing[J]. 2003, 4(1): 25~29.
[21]李超,朱巧明,李培峰,许兰.网格工作流调度研究综述[J].计算机应用与软件, 2008, 25(10): 279-282.
[22] J.Cao, S.A.Jarvis, S.Saini, et al. Gridflow: Workflow Management for Grid Computing[C]. Proceedings of the 3rd IEEE/ACM International Symposium on Cluster Computing and the Grid. Tokyo: 2003:198~205.
[23]刘洋,桂小林,徐玉文.网格工作流中基于优先级的调度方法研究[J].西安交通大学学报, 2006, 40(4): 411-414.
[24]倪晚成,刘连臣,吴澄.网格工作流中基于商品市场的服务选择[J].计算机应用,2007, 27(12):2973-2975.
[25]金海,陈汉华,吕志鹏. CGSP作业管理其合成服务的QoS优化模型及求解[J].计算机学报, 2005, 28(4): 578-588.
[26]丁一鸣,孙瑞志.基于遗传退火算法的网格工作流调度研究[J].计算机应用, 2007, 6(27): 89-91.
[27] Wei-Neng CHEN, Jun ZHENG, Yang YU. Workflow Scheduling in Grids: An Ant Optimization Approch[C]. Evolutionary Computation, IEEE Congress, 2007: 3308– 3315.
[28] Yingchun Yuan, Xiansong Li, Chenxia Sun. Cost-effective Heuristics for Workflow Scheduling in Grid Computing Economy[C]. The Sixth International Conference on Grid and Cooperative Computing, 2007.
[29] J.Yu, Buyya.R, C.K.Tham. A Cost-based Scheduling of Scientific Workflow Applications on Utility Grids[C]. Proceeding of the 1st IEEE International Conference on e-Science and Grid Computing, Melbourne, Australia: IEEE Press, 2005: 140-147.
[30]苑迎春,李小平,王茜.基于逆向分层的网格工作流调度算法[J].计算机学报,2008, 31(2):282-291.
[31] Hao Xianwen, Dai Yu, Zhang Bin, et al. Reduced Task-Resource Assignment Graph Based Static Scheduling for Grid Workflow Application[C]. The 3rd International Conference on Communication Systems Software and Middleware and Workshops, Comsware: 2008: 736– 743.
[32]苑迎春,李小平,王茜.基于串归约的网格工作流费用优化方法[J].计算机研究与发展, 2008, 45(2): 246-253.
[33]郭文彩,杨扬.一种面向服务的网格工作流调度算法[J].计算机科学, 2006, 6(33): 132-134.
[34]郭文彩,杨扬.基于遗传算法的网格服务工作流调度的研究[J].计算机应用, 2006(26): 54-56.
[35]王勇,胡春明,杜宗霞.服务质量感知的网格工作流调度[J].软件学报, 2006, 17(11): 2341-2350.
[36] Mustafizur Rahman, Srikumar Venugopal, Rajkumar Buyya. A Dynamic Critical Path Algorithm for Scheduling Scientific Workflow Applications on Global Grids[C]. Third IEEE International Conference on e-Science and Grid Computing, 2007: 35-42.
[37]刘洪伟,于炯,田国忠,龚红翠.基于网格资源预测的任务优先级调度算法[J].计算机工程,2009, 35(17): 55-57.
[38]刘红文,刘建勋.基于微粒群算法的网格工作流优化调度问题的研究[J].计算机工程与设计, 2008, 29卷23期:5967-5970.
[39] Guo-Zhong.Tian, Jiong Yu. Grid Workflow Scheduling Based on the Resource Combination Reliability[C]. Fourth International Conference on Natural Computation, 2008: 207-211.
[40] Yuanhui Li, Depeng Zhao, Jun Li. Scheduling Algorithm Based on Integrated Utility of Multiple QoS Attributes on Service Grid[C]. The Sixth International Conference on Grid and Cooperative Computing, 2007.
[41]Rajkumar Buyya, David Abramson, Srikumar Venugopal. The Grid Economy[J]. Proceedings of theIEEE. 2005, 93(3): 689-714.
[42] Buyya R, Giddy J, Abramson D. An Evaluation of Economy-based Resource Trading and Scheduling on Computational Power Grids for Parameter Sweep Applications[C].Proceedings of the 2ndInternational Workshop on Active Middleware Services. Pittsburgh, USA: Kluwer Academic Press, 2000: 221-230.
[43] Xing-jiang Yu, Yang Tao.Classified Optimization Scheduling Algorithm driven by multi-QoS attributes in Economical Grid[J], Proceedings of the IEEE,shanghai,2008,08(4),306-309.
[44] Dazhen Wang, Kwang Mong Sim, Benyun Shi. A Deadline and Cost Constrained Optimization Algorithm for Scheduling Applications in Grids Based on Proportional Share Systems[C]. International Symposium on Electronic Commerce and Security, 2008: 46-50.
[45] Gong Hong-cui, Yu Jiong, Hou Yong, Liu Hong-wei. User QoS and System Index Guided Task Scheduling in Compute Grid[C]. The 7th International Conference on Grid and Cooperative Computing (GCC2008) . Proceedings of the IEEE, 2008:109-112.
[46]付鹤岗,武聪,尤娟.基于服务质量的网格工作流系统研究[J].计算机科学, 2009, 36(6): 162-164.
[47]吕良干,于炯,李静,邓定兰.资源灰预测的反馈任务调度算法[J].计算机应用,2009, 29(5):1276-1278, 1304.
[48]张伟,李守智,高峰等.几种智能最优化算法的比较研究[C]. Proceedings of the 24th Chinese Control Conference, Guangzhou, P.R. China July 15-18, 2005: 1316～1320.
[49]阳明盛,罗长童.最优化原理、方法及求解软件[M].科学出版社, 2006: 128-134.
[50]罗红,慕德俊,邓智群,王晓东.网格计算中任务调度研究综述[J].计算机应用研究, 2005, 22(5): 16-19.
[51]王冰,刁鸣,高洪元.一种改进的粒子群算法求解背包问题[J].应用科技, 2008, 35(3): 16-19.
[52]王旭,王宏,王文辉.人工神经元网络原理与应用[M].东北大学出版社, 2000: 92-98.
[53] Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest, et al. Introduction to Algorithms[M].高等教育出版社, 2002: 370-399.
[2] Ian Foster. Grid Technologies and Applications: Architecture & Achievements[C]. Intl Conference on Computing in High Energy and Nuclear Physics,2001:51-63.
[3] Ian Foster. The Grid: A New Infrastructure for 21st Century Science[J]. Physics Today, 2002, 55(2):42-47.
[4] Ian Foster, C.Kesselman, J.Nick, et al. Grid Services for Distributed Systems Intergration[J]. IEEE Computer. 2002, 35(6):135-160.
[5] Suraj Pandey, Rajkumar Buyya. Scheduling of Scientific Work?ows on Data Grids[C]. Eighth IEEE International Symposium on Cluster Computing and the Grid. 2008: 548-553.
[6]徐志伟.织女星网格的总体思路[J].计算机研究与发展. 2002, 39(8): 923-929.
[7]桂小林.网格技术导论[M].北京邮电大学出版社, 2005: 1-30.
[8] I. Foster, C. Kesselman, etal. The Anatonmy of the Grid: Enabling Scalable Virtual Organizations[J]. Journal of High Performance Computing Applications. 2001, 15(3): 200-222.
[9] Basney J, Livny M. Deploying a High Throughput Computing Cluster[J]. High Performance Cluster Computing, Prentice Hall, 1999:193-198 .
[10]都志辉,陈渝,刘鹏.网格计算[M].北京:清华大学出版社,2002: 1-29.
[11] Ian Foster. What is the Grid? A Three Point Checklist[M]. GRID Today, 2002: 5-10.
[12] Ian Foster, Carl Kesselman, et al. The Physiology of the Grid: An Open Grid Services Architecture for Distributed Systems Integration[EB/OL]. http://www.globus.org/research/papers/ogsa.pdf,2008-11-13.
[13]王瑄,李燕.应用Web Services构建多层架构的高效NET应用[M].科学出版社. 2005, 6: 17-31.
[14] Jia Yu, Rajkumar Buyya. A Taxonomy of Workflow Management Systems for Grid Computing [J]. Journal of Grid Computing, 2005, 3(3-4): 171~200.
[15] Workflow Management Coalition. The Workflow Reference Model[S]. WFMC-TC-1003,1994.
[16]黄福华.网格工作流技术综述[J].福建电脑报. 2008, 1: 1-32.
[17]张云峰,葛炜.基于服务质量的网格工作流算法优化[J].计算机科学. 2004, 31(9):230-233.
[18]田国忠,于炯,侯勇,邢剑等.基于资源状态可靠度的网格工作流调度算法[J].计算机工程与应用, 2008, 44(18): 115-118.
[19]余波,周龙骧,钟锡昌,张倪.网格工作流技术综述[J].计算机工程, 2006, 32(2): 4-36.
[20] E. Deelman, J. Blythe, et al. Mapping Abstract Complex Workflows onto Grid Environment. Journal of Grid Computing[J]. 2003, 4(1): 25~29.
[21]李超,朱巧明,李培峰,许兰.网格工作流调度研究综述[J].计算机应用与软件, 2008, 25(10): 279-282.
[22] J.Cao, S.A.Jarvis, S.Saini, et al. Gridflow: Workflow Management for Grid Computing[C]. Proceedings of the 3rd IEEE/ACM International Symposium on Cluster Computing and the Grid. Tokyo: 2003:198~205.
[23]刘洋,桂小林,徐玉文.网格工作流中基于优先级的调度方法研究[J].西安交通大学学报, 2006, 40(4): 411-414.
[24]倪晚成,刘连臣,吴澄.网格工作流中基于商品市场的服务选择[J].计算机应用,2007, 27(12):2973-2975.
[25]金海,陈汉华,吕志鹏. CGSP作业管理其合成服务的QoS优化模型及求解[J].计算机学报, 2005, 28(4): 578-588.
[26]丁一鸣,孙瑞志.基于遗传退火算法的网格工作流调度研究[J].计算机应用, 2007, 6(27): 89-91.
[27] Wei-Neng CHEN, Jun ZHENG, Yang YU. Workflow Scheduling in Grids: An Ant Optimization Approch[C]. Evolutionary Computation, IEEE Congress, 2007: 3308– 3315.
[28] Yingchun Yuan, Xiansong Li, Chenxia Sun. Cost-effective Heuristics for Workflow Scheduling in Grid Computing Economy[C]. The Sixth International Conference on Grid and Cooperative Computing, 2007.
[29] J.Yu, Buyya.R, C.K.Tham. A Cost-based Scheduling of Scientific Workflow Applications on Utility Grids[C]. Proceeding of the 1st IEEE International Conference on e-Science and Grid Computing, Melbourne, Australia: IEEE Press, 2005: 140-147.
[30]苑迎春,李小平,王茜.基于逆向分层的网格工作流调度算法[J].计算机学报,2008, 31(2):282-291.
[31] Hao Xianwen, Dai Yu, Zhang Bin, et al. Reduced Task-Resource Assignment Graph Based Static Scheduling for Grid Workflow Application[C]. The 3rd International Conference on Communication Systems Software and Middleware and Workshops, Comsware: 2008: 736– 743.
[32]苑迎春,李小平,王茜.基于串归约的网格工作流费用优化方法[J].计算机研究与发展, 2008, 45(2): 246-253.
[33]郭文彩,杨扬.一种面向服务的网格工作流调度算法[J].计算机科学, 2006, 6(33): 132-134.
[34]郭文彩,杨扬.基于遗传算法的网格服务工作流调度的研究[J].计算机应用, 2006(26): 54-56.
[35]王勇,胡春明,杜宗霞.服务质量感知的网格工作流调度[J].软件学报, 2006, 17(11): 2341-2350.
[36] Mustafizur Rahman, Srikumar Venugopal, Rajkumar Buyya. A Dynamic Critical Path Algorithm for Scheduling Scientific Workflow Applications on Global Grids[C]. Third IEEE International Conference on e-Science and Grid Computing, 2007: 35-42.
[37]刘洪伟,于炯,田国忠,龚红翠.基于网格资源预测的任务优先级调度算法[J].计算机工程,2009, 35(17): 55-57.
[38]刘红文,刘建勋.基于微粒群算法的网格工作流优化调度问题的研究[J].计算机工程与设计, 2008, 29卷23期:5967-5970.
[39] Guo-Zhong.Tian, Jiong Yu. Grid Workflow Scheduling Based on the Resource Combination Reliability[C]. Fourth International Conference on Natural Computation, 2008: 207-211.
[40] Yuanhui Li, Depeng Zhao, Jun Li. Scheduling Algorithm Based on Integrated Utility of Multiple QoS Attributes on Service Grid[C]. The Sixth International Conference on Grid and Cooperative Computing, 2007.
[41]Rajkumar Buyya, David Abramson, Srikumar Venugopal. The Grid Economy[J]. Proceedings of theIEEE. 2005, 93(3): 689-714.
[42] Buyya R, Giddy J, Abramson D. An Evaluation of Economy-based Resource Trading and Scheduling on Computational Power Grids for Parameter Sweep Applications[C].Proceedings of the 2ndInternational Workshop on Active Middleware Services. Pittsburgh, USA: Kluwer Academic Press, 2000: 221-230.
[43] Xing-jiang Yu, Yang Tao.Classified Optimization Scheduling Algorithm driven by multi-QoS attributes in Economical Grid[J], Proceedings of the IEEE,shanghai,2008,08(4),306-309.
[44] Dazhen Wang, Kwang Mong Sim, Benyun Shi. A Deadline and Cost Constrained Optimization Algorithm for Scheduling Applications in Grids Based on Proportional Share Systems[C]. International Symposium on Electronic Commerce and Security, 2008: 46-50.
[45] Gong Hong-cui, Yu Jiong, Hou Yong, Liu Hong-wei. User QoS and System Index Guided Task Scheduling in Compute Grid[C]. The 7th International Conference on Grid and Cooperative Computing (GCC2008) . Proceedings of the IEEE, 2008:109-112.
[46]付鹤岗,武聪,尤娟.基于服务质量的网格工作流系统研究[J].计算机科学, 2009, 36(6): 162-164.
[47]吕良干,于炯,李静,邓定兰.资源灰预测的反馈任务调度算法[J].计算机应用,2009, 29(5):1276-1278, 1304.
[48]张伟,李守智,高峰等.几种智能最优化算法的比较研究[C]. Proceedings of the 24th Chinese Control Conference, Guangzhou, P.R. China July 15-18, 2005: 1316～1320.
[49]阳明盛,罗长童.最优化原理、方法及求解软件[M].科学出版社, 2006: 128-134.
[50]罗红,慕德俊,邓智群,王晓东.网格计算中任务调度研究综述[J].计算机应用研究, 2005, 22(5): 16-19.
[51]王冰,刁鸣,高洪元.一种改进的粒子群算法求解背包问题[J].应用科技, 2008, 35(3): 16-19.
[52]王旭,王宏,王文辉.人工神经元网络原理与应用[M].东北大学出版社, 2000: 92-98.
[53] Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest, et al. Introduction to Algorithms[M].高等教育出版社, 2002: 370-399.