QoS约束云环境下的工作流能效调度算法

摘要/Abstract

摘要： 云环境可以为大规模工作流的执行提供高效、可靠的运行环境,但工作流执行时带来的高能耗不仅会增加云资源提供方的经济成本,还会影响云系统的可靠性,并对环境产生不利影响。为了在满足用户截止时间QoS需求的同时降低云环境中工作流调度的执行能耗,提出一种工作流能效调度算法QCWES。该算法将工作流的能效调度方案求解划分为3个阶段:截止时间重分配、任务调度选择排序以及基于DVFS的最佳资源选择。截止时间重分配阶段旨在将用户定义的全局工作流截止时间在各个任务间进行重分配,任务调度选择排序阶段旨在通过自顶向下的任务分级方式得到任务调度序列;基于DVFS的最佳资源选择阶段旨在为每个任务选择带有合适电压/频率等级的最优目标资源,在满足任务的子截止时间的前提下使总体能耗达到最小。通过随机工作流和基于高斯消元法的现实工作流结构,对算法的性能进行仿真实验分析。结果表明,所提算法可以在满足截止时间约束下降低工作流的执行能耗,实现用户方的QoS需求与资源方的能耗间的均衡。

关键词: QoS约束, 动态电压/频率缩放, 工作流调度, 能效调度, 云计算

Abstract: Cloud provides a high-efficient and reliable execution environment for scheduling large-scale workflow.However,the high energy consumption resulted by workflow execution not only increases the economic cost of cloud resource providers,but influences the system reliability and has a negative effect to the environment.For meeting user-defined deadline QoS requirement and reducing the execution consumption of workflow scheduling in cloud,a workflow energy-efficient scheduling algorithm QCWES was proposed.QCWES divides the energy-efficient scheduling scheme of workflow into three phases:the deadline redistribution,the ordering of scheduled tasks and the best resource selection based on DVFS.The deadline redistribution phase is to redistribute the user-defined overall workflow deadline among all tasks,the ordering of scheduled tasks is to obtain the scheduling order of tasks by top-down task leveling,the best resource selection based on DVFS is to select the best available resource with appropriate voltage/frequency level for each task so that the total energy consumption is minimal while meeting its sub-deadline.Some simulation experiments were constructed to evaluate the performance of our algorithm by random workflow and the real-world workflow based on Gaussian Elimination.The results show that QCWES can reduce the energy consumption of workflow scheduling under meeting deadline constraint,and achieve the trade-off between users’ QoS requirement and resources’ energy consumption.

Key words: Cloud computing, Dynamic voltage/frequency scaling, Enegy-efficient scheduling, QoS constraint, Workflow scheduling

中图分类号:

TP393

李廷元, 王博岩. QoS约束云环境下的工作流能效调度算法[J]. 计算机科学, 2018, 45(6A): 304-309. https://doi.org/

LI Ting-yuan, WANG Bo-yan. Workflow Energy-efficient Scheduling Algorithm in Cloud Environment with QoS Constraint[J]. Computer Science, 2018, 45(6A): 304-309. https://doi.org/

参考文献

[1]BUYYA R,YEO S,VENUGOPAL S,et al.Cloud computing and emerging IT platforms:Vision,hype,and reality for delivering computing as the 5th utility[J].Future Generation Computer Systems,2011,25(6):599-616.
[2]LIU L,ZHANG M,LIN Y,et al.A survey on workflow ma- nagement and scheduling in cloud computing[C]∥14th IEEE/ACM International Symposium on Cluster,Cloud and Grid Computing.USA:IEEE Press,2014:837-846.
[3]ARROBA P,RISCO-MART J L,ZAPATER M,et al.Server power modeling for run-time energy optimization of cloud computing facilities[C]∥International Conference on Sustainabiility and building.2014:401-410.
[4]TOPCUOGLU H,HARIRI S,WU M Y.Performance-effective and low-complexity task scheduling for heterogeneous computing[J].IEEE Transactions Parallel Distributed Systems,2012,13(3):260-274.
[5]SELVI S,MANIMEGALAI D.Task Scheduling Using Two- Phase Variable Neighborhood Search Algorithm on Heterogeneous Computing and Grid Environments[J].Arabian Journal for Science and Engineering,2015,40(3):817-844.
[6]LEE Y C,HAN H,ZOMAYA A Y,et al.Resource-efficient workflow scheduling in clouds[J].Knowledge-Based Systems,2015,80(C):153-162.
[7]ABUDHAGIR U S,SHANMUGAVEL S.A Novel Dynamic Reliability Optimized Resource Scheduling Algorithm for Grid Computing System[J].Arabian Journal for Science and Engineering,2014,39(10):7087-7096.
[8]ARABNEJAD H,BARBOSA J G.A Budget Constrained Sche- duling Algorithm for Workflow Applications[J].Journal of Grid Computing,2014,12(4):665-679.
[9]LEE Y C,ZOMAYA A Y.Minimizing Energy Consumption for Precedence-Constrained Applications Using Dynamic Voltage Scaling[C]∥IEEE/ACM International Symposium on CLUSTER Computing and the Grid.IEEE Computer Society,2009:92-99.
[10]ZONG Z,MANZANARES A,RUAN X,et al.EAD and PEBD:Two Energy-Aware Duplication Scheduling Algorithms for Pa-rallel Tasks on Homogeneous Clusters[J].IEEE Transactions on Computers,2011,60(3):360-374.
[11]BASKIYAR S,ABDEL-KADER R.Energy aware DAG scheduling on heterogeneous systems[J].Cluster Computing,2013,13(4):373-383.
[12]景维鹏,吴智博,刘宏伟,等.多DAG工作流在云计算环境下的可靠性调度方法[J].西安电子科技大学学报(自然科学版),2016,43(2):83-88.
[13]王润平,陈旺虎,段菊.一种科学工作流的云数据布局与任务调度策略[J].计算机仿真,2015,32(3):421-426.
[14]曹斌,王小统,熊丽荣,等.时间约束云工作流调度的粒子群搜索方法[J].计算机集成制造系统,2016,22(2):372-380.
[15]杨玉丽,彭新光,黄名选,等.基于离散粒子群优化的云工作流调度[J].计算机应用研究,2014,31(12):3677-3681.
[16]CHEN W,DEELMAN E.WorkflowSim:a toolkit for simulating scientific workflows in distributed environments[C]∥IEEE 8th International Conference on E-Science (e-Science).IEEE,2012:1-8.
[17]JUVE G,CHERVENAK A,DEELMAN E,et al.Characterizing and profiling scientific workflows[J].Future Generation Computer Systems,2013,29(3):682-692.

相关文章 15

[1]	高诗尧, 陈燕俐, 许玉岚. 云环境下基于属性的多关键字可搜索加密方案 Expressive Attribute-based Searchable Encryption Scheme in Cloud Computing 计算机科学, 2022, 49(3): 313-321. https://doi.org/10.11896/jsjkx.201100214
[2]	林潮伟, 林兵, 陈星. 边缘环境下基于模糊理论的科学工作流调度研究 Study on Scientific Workflow Scheduling Based on Fuzzy Theory Under Edge Environment 计算机科学, 2022, 49(2): 312-320. https://doi.org/10.11896/jsjkx.201000102
[3]	王政, 姜春茂. 一种基于三支决策的云任务调度优化算法 Cloud Task Scheduling Algorithm Based on Three-way Decisions 计算机科学, 2021, 48(6A): 420-426. https://doi.org/10.11896/jsjkx.201000023
[4]	潘瑞杰, 王高才, 黄珩逸. 云计算下基于动态用户信任度的属性访问控制 Attribute Access Control Based on Dynamic User Trust in Cloud Computing 计算机科学, 2021, 48(5): 313-319. https://doi.org/10.11896/jsjkx.200400013
[5]	陈玉平, 刘波, 林伟伟, 程慧雯. 云边协同综述 Survey of Cloud-edge Collaboration 计算机科学, 2021, 48(3): 259-268. https://doi.org/10.11896/jsjkx.201000109
[6]	蒋慧敏, 蒋哲远. 企业云服务体系结构的参考模型与开发方法 Reference Model and Development Methodology for Enterprise Cloud Service Architecture 计算机科学, 2021, 48(2): 13-22. https://doi.org/10.11896/jsjkx.200300044
[7]	王文娟, 杜学绘, 任志宇, 单棣斌. 基于因果知识和时空关联的云平台攻击场景重构 Reconstruction of Cloud Platform Attack Scenario Based on Causal Knowledge and Temporal- Spatial Correlation 计算机科学, 2021, 48(2): 317-323. https://doi.org/10.11896/jsjkx.191200172
[8]	毛瀚宇, 聂铁铮, 申德荣, 于戈, 徐石成, 何光宇. 区块链即服务平台关键技术及发展综述 Survey on Key Techniques and Development of Blockchain as a Service Platform 计算机科学, 2021, 48(11): 4-11. https://doi.org/10.11896/jsjkx.210500159
[9]	王勤, 魏立斐, 刘纪海, 张蕾. 基于云服务器辅助的多方隐私交集计算协议 Private Set Intersection Protocols Among Multi-party with Cloud Server Aided 计算机科学, 2021, 48(10): 301-307. https://doi.org/10.11896/jsjkx.210300308
[10]	雷阳, 姜瑛. 云计算环境下关联节点的异常判断 Anomaly Judgment of Directly Associated Nodes Under Cloud Computing Environment 计算机科学, 2021, 48(1): 295-300. https://doi.org/10.11896/jsjkx.191200186
[11]	徐蕴琪, 黄荷, 金钟. 容器技术在科学计算中的应用研究 Application Research on Container Technology in Scientific Computing 计算机科学, 2021, 48(1): 319-325. https://doi.org/10.11896/jsjkx.191100111
[12]	张恺琪, 涂志莹, 初佃辉, 李春山. 基于排队论的服务资源可用性相关研究综述 Survey on Service Resource Availability Forecast Based on Queuing Theory 计算机科学, 2021, 48(1): 26-33. https://doi.org/10.11896/jsjkx.200900211
[13]	马堉银, 郑万波, 马勇, 刘航, 夏云霓, 郭坤银, 陈鹏, 刘诚武. 一种基于深度强化学习与概率性能感知的边缘计算环境多工作流卸载方法 Multi-workflow Offloading Method Based on Deep Reinforcement Learning and ProbabilisticPerformance-awarein Edge Computing Environment 计算机科学, 2021, 48(1): 40-48. https://doi.org/10.11896/jsjkx.200900195
[14]	李彦, 申德荣, 聂铁铮, 寇月. 面向加密云数据的多关键字语义搜索方法 Multi-keyword Semantic Search Scheme for Encrypted Cloud Data 计算机科学, 2020, 47(9): 318-323. https://doi.org/10.11896/jsjkx.190800139
[15]	张龙信, 周立前, 文鸿, 肖满生, 邓晓军. 基于异构云计算的成本约束下的工作流能量高效调度算法 Energy Efficient Scheduling Algorithm of Workflows with Cost Constraint in Heterogeneous Cloud Computing Systems 计算机科学, 2020, 47(8): 112-118. https://doi.org/10.11896/jsjkx.200300038

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed