Computer Science

Computer Science ›› 2023, Vol. 50 ›› Issue (4): 257-264.doi: 10.11896/jsjkx.220100100

• Computer Network • Previous Articles     Next Articles

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

PAN Jikui1,2, DONG Xinyi1,2, LU Zhenghao1,2, WANG Zijian1, SUN Fuquan1   

  1. 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).

PDF (PC)

289

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

CLC Number: 

  • TP393
[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.
[1] LIU Xiaonan, AN Jiale, HE Ming, SONG Huichao. Chaotic Adaptive Quantum Firefly Algorithm [J]. Computer Science, 2023, 50(4): 204-211.
[2] XIE Yongsheng, HUANG Xiangheng, CHEN Ningjiang. Self-balanced Scheduling Strategy for Container Cluster Based on Improved DQN Algorithm [J]. Computer Science, 2023, 50(4): 233-240.
[3] PEI Cui, FAN Guisheng, YU Huiqun, YUE Yiming. Auction-based Edge Cloud Deadline-aware Task Offloading Strategy [J]. Computer Science, 2023, 50(4): 241-248.
[4] ZHONG Jialin, WU Yahui, DENG Su, ZHOU Haohao, MA Wubin. Multi-objective Federated Learning Evolutionary Algorithm Based on Improved NSGA-III [J]. Computer Science, 2023, 50(4): 333-342.
[5] CAO Chenyang, YANG Xiaodong, DUAN Pengsong. WiDoor:Close-range Contactless Human Identification Approach [J]. Computer Science, 2023, 50(4): 388-396.
[6] HU Zhongyuan, XUE Yu, ZHA Jiajie. Survey on Evolutionary Recurrent Neural Networks [J]. Computer Science, 2023, 50(3): 254-265.
[7] Peng XU, Jianxin ZHAO, Chi Harold LIU. Optimization and Deployment of Memory-Intensive Operations in Deep Learning Model on Edge [J]. Computer Science, 2023, 50(2): 3-12.
[8] CHANG Sha, WU Yahui, DENG Su, MA Wubin, ZHOU Haohao. Online Task Allocation Strategy Based on Lyapunov Optimization in Mobile Crowdsensing [J]. Computer Science, 2023, 50(2): 50-56.
[9] SHANG Yuye, YUAN Jiabin. Task Offloading Method Based on Cloud-Edge-End Cooperation in Deep Space Environment [J]. Computer Science, 2023, 50(2): 80-88.
[10] GUO Nan, LI Jingyuan, REN Xi. Survey of Rigid Object Pose Estimation Algorithms Based on Deep Learning [J]. Computer Science, 2023, 50(2): 178-189.
[11] LIU Likang, ZHOU Chunlai. RCP:Mean Value Protection Technology Under Local Differential Privacy [J]. Computer Science, 2023, 50(2): 333-345.
[12] HE Xionghui, TAN Jiefu, LIU Zhe, XUE Chao, YANG Shaowu, ZHANG Yongjun. Viewpoint-tolerant Scene Recognition Based on Segmentation of Sparse Point Cloud [J]. Computer Science, 2023, 50(1): 87-97.
[13] MENG Huaru, WU Guowei. Cloth Simulation Filtering Algorithm with Topography Cognition [J]. Computer Science, 2023, 50(1): 156-165.
[14] LI Bei, WU Hao, HE Xiaowei, WANG Bin, XU Ergang. Survey of Storage Scalability in Blockchain Systems [J]. Computer Science, 2023, 50(1): 318-333.
[15] WANG Shaojiang, LIU Jia, ZHENG Feng, PAN Yicheng. Survey on Hierarchical Clustering for Machine Learning [J]. Computer Science, 2023, 50(1): 9-17.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.