多DAG工作流在云计算环境下的可靠性调度方法

doi:10.3969/j.issn.1001-2400.2016.02.015

西安电子科技大学学报 ›› 2016, Vol. 43 ›› Issue (2): 83-88.doi: 10.3969/j.issn.1001-2400.2016.02.015

多DAG工作流在云计算环境下的可靠性调度方法

景维鹏1,2;吴智博1;刘宏伟1;舒燕君1

(1. 哈尔滨工业大学计算机科学与技术学院，黑龙江哈尔滨 150001;
2. 东北林业大学信息与计算机工程学院，黑龙江哈尔滨 150040)

收稿日期:2014-11-03 出版日期:2016-04-20 发布日期:2016-05-27
通讯作者: 景维鹏
作者简介:景维鹏(1979-)，副教授, 博士，E-mail: nefujwp@gmail.com．
基金资助:
国家自然科学基金资助项目(61202091)；国家863重大科技专项资助项目(2013AA01A215)；哈尔滨市科技局科技创新人才基金资助项目(2014RFQXJ132)

Multiple DAGs dynamic workflow reliability scheduling algorithm in a cloud computing system

JING Weipeng1,2;WU Zhibo1;LIU Hongwei1;SHU Yanjun1

(1. School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China;
2. The College of Information and Computer Engineering, Northeast Forestry Univ., Harbin 150040, China)

Received:2014-11-03 Online:2016-04-20 Published:2016-05-27
Contact: JING Weipeng

摘要/Abstract

摘要：

针对云计算环境中多个DAG科学工作流的可靠性调度问题，提出一种考虑虚拟机之间链路通信竞争的动态多DAG分层调度算法．首先使用通信竞争模型描述虚拟机之间的通信，然后分别计算主版本及副版本任务的最早完成时间，并限定任务所调度的虚拟机单元．再对多个同时到达的DAG工作流任务使用动态分层方法，计算每个DAG任务的不公平程度因子．该算法有效解决了当多个DAG中任务的权值相差较大时，之前到达的DAG不会因为剩余任务迟迟得不到调度而导致执行时间跨度增大的问题．仿真实验表明，在保证可靠调度的前提下，该算法不仅能提高多个DAG调度的公平程度，而且能有效地缩短多个DAG调度的平均最早完成时间．

关键词: 云计算, 多个DAG, 可靠性调度, 公平因子

Abstract:

In order to solve the reliable scientific workflow scheduling problem for cloud computing, a dynamic of the RANK-Hierarchical algorithm is put forward which takes account of communication contention as well as supports task dependencies(CCRH). A communication contention model is first defined, as soon as the earliest completion of the primary and backup task is deduced. Besides, the executived processor is limited. We use the dynamic hierarchical method and calculate each DAG unfair degree factor for multiple DAGs scientific workflow. It can deal with the situation that multiple DAGs workflow comes at different times and there are various kinds of structure. Both the theory and experiments have proved that the algorithm can not only improve the scheduling fairness of multiple DAGs workflow but also shorten the average execution Makespan.

Key words: cloud computing, multiple DAGs, reliability scheduling, degree factor

景维鹏;吴智博;刘宏伟;舒燕君. 多DAG工作流在云计算环境下的可靠性调度方法[J]. 西安电子科技大学学报, 2016, 43(2): 83-88.

JING Weipeng;WU Zhibo;LIU Hongwei;SHU Yanjun. Multiple DAGs dynamic workflow reliability scheduling algorithm in a cloud computing system[J]. Journal of Xidian University, 2016, 43(2): 83-88.

参考文献

［1］ WIECZOREK M, PRODAN R, FAHRINGER T. Scheduling of Scientific Workflows in the Askalon Grid Environment ［J］. SIGMOD Record, 2005, 3(34): 56-62.
［2］ MANDAL A. Scheduling Strategies for Mapping Application Workflows onto the Grid［C］//Proceedings of the 14th International Symposium on High Performance Distributed Computing. New York: ACM, 2005: 125-134.
［3］田国忠, 肖创柏, 徐竹胜, 等. 异构分布式环境下多DAG工作流的混合调度策略［J］. 软件学报, 2012, 23(10): 2720-2734.
TIAN Guozhong, XIAO Chuangbai, XU Zhusheng, et al. Hybrid Scheduling Strategy for Multiple DAGs Workflow in Heterogeneous System［J］. Journal of Sofware, 2012, 23(10): 2720-2734.
［4］ ZHAO H, SAKELLARIOU R. Scheduling Multiple DAGs onto Heterogeneous Systems［C］//Proceedings of the 20th International Parallel and Distributed Processing Symposium. Piscataway: IEEE, 2006: 1639387.
［5］ ZHANG J, SHA E H M, ZHUGE Q, et al. Efficient Fault-tolerant Scheduling on Multiprocessor Systems via Replication and Deallocation［J］. International Journal of Embedded Systems, 2014, 6(2/3): 216-224.
［6］ BARUAH S, BONIFACI V, MARCHETTI-SPACCAMELA A, et al. A Generalized Parallel Task Model for Recurrent Real-time Processes［C］//Proceedings of the 33th Real-time Systems Symposium. Piscataway: IEEE, 2012: 63-72.
［7］ RAJU R, AMUDHAVEL J, PAVITHRA M, et al. A Heuristic Fault Tolerant Mapreduce Framework for Minimizing Makespan in Hybrid Cloud Environment［C］//Proceedings of the IEEE International Conference on Green Computing, Communication and Electrical Engineering. Piscataway: IEEE, 2014: 6922462.
［8］ XIE G Q, LI R F, LIU L, et al. DAG Reliability Model and Fault-tolerant Algorithm for Heterogeneous Distributed Systems ［J］. Information Processing Letters, 2009, 109(11): 539-542.
［9］ QIN X, JIANG H. A Novel Fault-tolerant Scheduling Algorithm for Precedence Constrained Tasks in Real-time Heterogeneous Systems ［J］. Parallel Computing, 2006, 32(5): 331-356.
［10］ SINNEN O, SOUSA L A. Toward a Realistic Task Scheduling Model［J］. IEEE Transactions on Parallel and Distributed Systems, 2006, 17(3): 263-275.
［11］景维鹏, 吴智博, 刘宏伟, 等. 支持优先级约束任务的容错调度算法［J］. 清华大学学报, 2011, 51(S1): 1440-1444.
JING WEIPENG, WU ZHIBO, LIU HONGWEI, et al. Fault-tolerant Scheduling Algorithm for Precedence Constrained Tasks［J］. Tsinghua Science and Technology, 2011, 51(S1): 1440-1444.
［12］ MACEY B S, ZOMAYA A Y. A Performance Evaluation of CP List Scheduling Heuristics for Communication Intensive Task Graphs［C］//Proceedings of the International Parallel Processing Symposium. Los Alamitos: IEEE Computer Society, 1998: 538-541.
［13］ TOPCUOGLU H, HARIRI S, WU M. Performance Effective and Low-complexity Task Scheduling for Heterogeneous Computing ［J］. IEEE Transactions on Parallel and Distributed Systems, 2002, 13(3): 260-274.
［14］谢国琪, 李仁发, 杨帆, 等. 异构网络化汽车电子系统中多DAG离线任务调度［J］. 通信学报, 2013, 34(12): 20-32.
XIE Guoqi, LI Renfa, YANG Fan, et al. Multiple DAG Off-line Task Scheduling for Heterogeneous Networked Automobile Electronic Systems［J］. Journal on Communications, 2013, 34(12): 20-32.

[1]	李华东,张学亮,王晓磊,刘惠,王鹏程,杜军朝. Kubernetes集群中多节点合作博弈负载均衡策略[J]. 西安电子科技大学学报, 2021, 48(6): 16-22.
[2]	王燕. 改进多目标进化算法的云工作流调度[J]. 西安电子科技大学学报, 2019, 46(1): 130-136.
[3]	韩鹍;张海林;辛丹;吴波;康元基. 利用身份的全同态加密函数库设计方法[J]. 西安电子科技大学学报, 2017, 44(4): 56-61.
[4]	景维鹏;霍帅起;陈广胜;刘亚秋. 混合关键任务可靠调度方法与调度性分析[J]. 西安电子科技大学学报, 2016, 43(6): 158-163.
[5]	黄春水;任艳丽;蔡建兴. 可验证模指数批计算外包方案[J]. 西安电子科技大学学报, 2016, 43(4): 135-140.
[6]	柳兴;袁超伟;杨震;李振军. 一种基于李雅普诺夫优化的业务推送策略[J]. J4, 2015, 42(6): 138-144.
[7]	卢笛;马建峰;王一川;习宁;张留美;孟宪佳. 云计算下保障公平性的多资源分配算法[J]. J4, 2014, 41(3): 162-168.
[8]	王一川;马建峰;卢笛;张留美;孟宪佳. 云环境下的“云滴冻结”攻击[J]. J4, 2014, 41(3): 116-122.
[9]	朱旭东;李晖;郭祯. 云计算环境下加密图像检索[J]. J4, 2014, 41(2): 151-158.

多DAG工作流在云计算环境下的可靠性调度方法

Multiple DAGs dynamic workflow reliability scheduling algorithm in a cloud computing system

PDF (PC)

赞

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 9

Metrics

本文评价

推荐阅读 10