云中使用竞价实例的截止时间约束的工作流调度优化算法

doi:10.11896/jsjkx.220100100

计算机科学 ›› 2023, Vol. 50 ›› Issue (4): 257-264.doi: 10.11896/jsjkx.220100100

云中使用竞价实例的截止时间约束的工作流调度优化算法

潘纪奎^1,2, 董心仪^1,2, 卢政昊^1,2, 王子健¹, 孙福权¹

1 东北大学秦皇岛分校河北秦皇岛 066000
2 东北大学研究生院沈阳 110000

收稿日期:2022-01-12 修回日期:2022-06-20 出版日期:2023-04-15 发布日期:2023-04-06
通讯作者: 孙福权(2224765938@qq.com)
作者简介:(panjikuidxy@163.com)
基金资助:
国家重点研发计划(2018YFB1402800)

Deadline Constrained Scheduling Optimization Algorithm for Workflow in Clouds Using Spot Instance

PAN Jikui^1,2, DONG Xinyi^1,2, LU Zhenghao^1,2, WANG Zijian¹, SUN Fuquan¹

1 Northeastern University at Qinhuangdao,Qinhuangdao,Hebei 066000,China
2 Graduate School of Northeastern University,Shenyang 110000,China

Received:2022-01-12 Revised:2022-06-20 Online:2023-04-15 Published:2023-04-06
About author:PAN Jikui,born in 1998,postgraduate.His main research interest is workflow scheduling.
SUN Fuquan,born in 1964,Ph.D,professor.His main research interests include cloud resource scheduling and allocation and big data analysis.
Supported by:
National Key R&D Program of China(2018YFB1402800).

摘要/Abstract

摘要： 近年来,由于按需资源供应和即付即用付费模式具有的明显优势,在云环境中执行大规模工作流应用程序越来越流行。云服务提供商以不同的价格提供不同性能的资源。为了提高资源的利用率,许多云服务商提供的瞬时资源的价格远低于正常资源的价格,Amazon EC2提供的竞价实例,可以大大降低工作流的执行成本。云中工作流调度的主要问题之一是在满足用户给定的截止时间约束的前提下,找到一种更廉价的调度方法。为解决这个问题,提出了一种使用竞价实例的截止时间约束工作流调度优化算法(Spot-ProLis)。该算法考虑了同一虚拟机上数据传输时长为零的情况,使用概率向上排序的方法对任务进行排序。在资源配置阶段,增加了竞价实例作为候选资源,有效降低了执行成本。实验结果表明,相比经典算法ProLis,所提算法在降低执行成本上具有显著优势。

关键词: 云环境, 工作流调度, 竞价实例, 截止时间, 执行成本, 优化

Abstract: In recent years,due the advantages of on-demand resource provisioning and pay-as-you-go billing model,it is increa-singly popular to execute large-scale workflow applications in cloud environments.Cloud service providers offer resources with different capabilities at different prices.In order to improve resource utilization,many cloud service providers provide transient resources at a much lower price than normal resources.Spot instance provided by Amazon EC2 can greatly reduce the execution cost of workflow.One of the main problems of workflow scheduling in cloud is to find a cheaper scheduling method on the premise of meeting the deadline.To solve this problem,a deadline constrained scheduling optimization algorithm for workflow in clouds using spot instance(Spot-ProLis) is proposed.The algorithm takes into account the case that the data transmission time of the same virtual machine is zero,and uses the method of probabilistic upward rank to order tasks.In the resource allocation stage,spot instances are added as candidate resources,which effectively reduces the execution cost.Experiment results show that compared with the classical ProLis algorithm,Spot-ProLis has significant advantages in reducing the execution cost.

Key words: Cloud, Workflow scheduling, Spot instance, Deadline, Cost, Optimization

中图分类号:

TP393

潘纪奎, 董心仪, 卢政昊, 王子健, 孙福权. 云中使用竞价实例的截止时间约束的工作流调度优化算法[J]. 计算机科学, 2023, 50(4): 257-264. https://doi.org/10.11896/jsjkx.220100100

PAN Jikui, DONG Xinyi, LU Zhenghao, WANG Zijian, SUN Fuquan. Deadline Constrained Scheduling Optimization Algorithm for Workflow in Clouds Using Spot Instance[J]. Computer Science, 2023, 50(4): 257-264. https://doi.org/10.11896/jsjkx.220100100

参考文献

[1]JUVE G,CHERVENAK A,DEELMAN E,et al.Characterizing and profiling scientific workflows[J].Future Generation Computer Systems,2013,29(3):682-692.
[2]HEE K V.Workflow Management:Models,Methods,and Systems[M].Cambridge:The MIT Press,2004.
[3]SU S,LI J,HUANG Q J,et al.Cost-efficient task scheduling for executing large programs in the cloud[J].Parallel Computing,2013,39(4/5):177-188.
[4]WU F H,WU Q B,TAN Y S.Workflow scheduling in cloud:a survey[J].Journal of Supercomputing,2015,71(9):3373-3418.
[5]MICHZEL L,PINED O.Scheduling:Theory,Algorithms,andSystems[M].Berlin:Springer,2012.
[6]CAO S J,DENG K F,REN K J,et al.An optimizing algorithm for deadline constrained scheduling of scientific workflows in IaaS clouds using spot instances[C]//2019 IEEE International Conference on Parallel & Distributed Processing with Applications,Big Data & Cloud Computing,Sustainable Computing & Communications,Social Computing & Networking.2019:1421-1428.
[7]WU Q W,FUYUKI I,ZHU Q S,et al.Deadline-constrained cost optimization approaches for workflow scheduling in clouds[J].IEEE Transactions on Parallel and Distributed Systems,2017,(12):3401-3412.
[8]YU-KWONG K,ISHFAQ A.Static scheduling algorithms forallocating directed task graphs to multiprocessors[J].ACM Computing Surveys(CSUR),1999,31(4):406-471.
[9]JIA Y,RAJKUMAR B,KOTAGIRI R.Workflow scheduling algorithms for grid computing[J].Studies in Computational Intelligence,2008,146:173-214.
[10]JIA Y,RAJKUMAR B.Scheduling scientific workflow applications with deadline and budget constraints using genetic algorithms[J].Scientific Programming,2006,14(3/4):217-230.
[11]WU Z J,NI Z W,GU L C,et al.A revised discrete particleswarm optimization for cloud workflow scheduling[C]//2010 International Conference on Computational Intelligence and Security.2010:184-188.
[12]MARIA A R,RAJKUMAR B.Deadline based resource provisioning and scheduling algorithm for scientific workflows on clouds[J].IEEE Transactions on Cloud Computing,2014,2(2):222-235.
[13]CHEN Z G,ZHAN Z H,LI H H,et al.Deadline constrained cloud computing resources scheduling through an ant colony system approach[C]//2015 International Conference on Cloud Computing Research and Innovation(ICCCRI).2016:112-119.
[14]WANG P W,LEI Y H,PROMISE R,et al.Makespan-drivenworkflow scheduling in clouds using immune-based PSO algorithm[J].IEEE Access,2020,8:29281-29290.
[15]MARKUS L,MOHAN B C,QUOC B V,et al.On Estimating Minimum Bids for Amazon EC2 Spot Instances[C]//Cluster,Cloud and Grid Computing.2017:391-400.
[16]MATT B,CHRISTIAN H,RICH W,et al.Predicting Amazon Spot Prices with LSTM Networks[C]//Scientific Cloud Computing.2018:1-7.
[17]VEENA K,ANAND K C,CHANDRA P G.Amazon EC2 spot price prediction using regression random forests[J].IEEE Transactions on Cloud Computing,2020,8(1):59-72.
[18]RICH W,JOHN B,RYAN C,et al.Probabilistic guarantees of execution duration for Amazon spot instances[C]//Proceedings of the International Conference for High Performance Computing,Networking,Storage and Analysis.Association for Computing Machinery.2017:1-11.
[19]GUO W H,CHEN K,WU Y W,et al.Bidding for Highly Avai-lable Services with Low Price in Spot Instance Market[C]//High-Performance Parallel and Distributed Computing.2015:191-202.
[20]LIU W Q,WANG P W,MENG Y,et al.Cloud spot instance price prediction using kNN regression[J].Human-centric Computing and Information Sciences,2020,10(34):1-14.
[21]DEEPAK P,KOTAGIRI R,RAJKUMAR B.Enhancing Reliability of Workflow Execution Using Task Replication and Spot Instances[J].ACM Transactions on Autonomous and Adaptive Systems,2016,10(4):1-21.
[22]BRUM R C,SOUSA W P,MELO A,et al.A Fault Tolerant and Deadline Constrained Sequence Alignment Application on Cloud-Based Spot GPU Instances[C]//Parallel Processing.2021:317-333.
[23]ZHOU J,ZHANG Y,WONG W F.Fault Tolerant Stencil Computation on Cloud-based GPU Spot Instances[J].IEEE Transa-ctions on Cloud Computing,2017,7(4):1013-1024.
[24]TOPCUOGLU H,HARIRI S,WU M Y.Performance-effective and low-complexity task scheduling for heterogeneous computing[J].IEEE Transactions on Parallel and Distributed Systems,2002,13(3):260-274.

相关文章 15

[1]	钟佳淋, 吴亚辉, 邓苏, 周浩浩, 马武彬. 基于改进NSGA-III的多目标联邦学习进化算法 Multi-objective Federated Learning Evolutionary Algorithm Based on Improved NSGA-III 计算机科学, 2023, 50(4): 333-342. https://doi.org/10.11896/jsjkx.220300033
[2]	曹晨阳, 杨晓东, 段鹏松. WiDoor:一种近距离非接触式身份识别方法 WiDoor:Close-range Contactless Human Identification Approach 计算机科学, 2023, 50(4): 388-396. https://doi.org/10.11896/jsjkx.220300278
[3]	刘晓楠, 安家乐, 何明, 宋慧超. 混沌自适应量子萤火虫算法 Chaotic Adaptive Quantum Firefly Algorithm 计算机科学, 2023, 50(4): 204-211. https://doi.org/10.11896/jsjkx.220100242
[4]	胡中源, 薛羽, 查加杰. 演化循环神经网络研究综述 Survey on Evolutionary Recurrent Neural Networks 计算机科学, 2023, 50(3): 254-265. https://doi.org/10.11896/jsjkx.220600007
[5]	刘利康, 周春来. RCP:本地差分隐私下的均值保护技术 RCP:Mean Value Protection Technology Under Local Differential Privacy 计算机科学, 2023, 50(2): 333-345. https://doi.org/10.11896/jsjkx.220700273
[6]	常沙, 吴亚辉, 邓苏, 马武彬, 周浩浩. 基于李雅普诺夫优化的移动群智感知在线任务分配策略 Online Task Allocation Strategy Based on Lyapunov Optimization in Mobile Crowdsensing 计算机科学, 2023, 50(2): 50-56. https://doi.org/10.11896/jsjkx.221100179
[7]	郭楠, 李婧源, 任曦. 基于深度学习的刚体位姿估计方法综述 Survey of Rigid Object Pose Estimation Algorithms Based on Deep Learning 计算机科学, 2023, 50(2): 178-189. https://doi.org/10.11896/jsjkx.211200164
[8]	李贝, 吴昊, 贺小伟, 王宾, 徐尔刚. 区块链系统的存储可扩展性综述 Survey of Storage Scalability in Blockchain Systems 计算机科学, 2023, 50(1): 318-333. https://doi.org/10.11896/jsjkx.211200042
[9]	鲁晨阳, 邓苏, 马武彬, 吴亚辉, 周浩浩. 基于分层抽样优化的面向异构客户端的联邦学习 Federated Learning Based on Stratified Sampling Optimization for Heterogeneous Clients 计算机科学, 2022, 49(9): 183-193. https://doi.org/10.11896/jsjkx.220500263
[10]	李其烨, 邢红杰. 基于最大相关熵的KPCA异常检测方法 KPCA Based Novelty Detection Method Using Maximum Correntropy Criterion 计算机科学, 2022, 49(8): 267-272. https://doi.org/10.11896/jsjkx.210700175
[11]	王灿, 刘永坚, 解庆, 马艳春. 基于软标签和样本权重优化的Anchor Free目标检测算法 Anchor Free Object Detection Algorithm Based on Soft Label and Sample Weight Optimization 计算机科学, 2022, 49(8): 157-164. https://doi.org/10.11896/jsjkx.210600240
[12]	陈俊, 何庆, 李守玉. 基于自适应反馈调节因子的阿基米德优化算法 Archimedes Optimization Algorithm Based on Adaptive Feedback Adjustment Factor 计算机科学, 2022, 49(8): 237-246. https://doi.org/10.11896/jsjkx.210700150
[13]	王兵, 吴洪亮, 牛新征. 基于改进势场法的机器人路径规划 Robot Path Planning Based on Improved Potential Field Method 计算机科学, 2022, 49(7): 196-203. https://doi.org/10.11896/jsjkx.210500020
[14]	唐枫, 冯翔, 虞慧群. 基于自适应知识迁移与资源分配的多任务协同优化算法 Multi-task Cooperative Optimization Algorithm Based on Adaptive Knowledge Transfer andResource Allocation 计算机科学, 2022, 49(7): 254-262. https://doi.org/10.11896/jsjkx.210600184
[15]	张翀宇, 陈彦明, 李炜. 边缘计算中面向数据流的实时任务调度算法 Task Offloading Online Algorithm for Data Stream Edge Computing 计算机科学, 2022, 49(7): 263-270. https://doi.org/10.11896/jsjkx.210300195

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

云中使用竞价实例的截止时间约束的工作流调度优化算法

Deadline Constrained Scheduling Optimization Algorithm for Workflow in Clouds Using Spot Instance

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0