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

doi:10.3969/j.issn.1001-2400.2016.02.015

Abstract

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

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.

References

［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]	LI Huadong,ZHANG Xueliang,WANG Xiaolei,LIU Hui,WANG Pengcheng,DU Junzhao. Multi-node cooperative game load balancing strategy in the Kubernetes cluster [J]. Journal of Xidian University, 2021, 48(6): 16-22.
[2]	WANG Yan. Enhanced multi-objective evolutionary algorithm for workflow scheduling on the cloud platform [J]. Journal of Xidian University, 2019, 46(1): 130-136.
[3]	HAN Kun;ZHANG Hailin;XIN Dan;WU Bo;KANG Yuanji. Design method of an identity-based fully homomorphic encryption library [J]. Journal of Xidian University, 2017, 44(4): 56-61.
[4]	JING Weipeng;HUO Shuaiqi;CHEN Guangsheng;LIU Yaqiu. Novel mixed-criticality reliability scheduling strategy and schedulability test [J]. Journal of Xidian University, 2016, 43(6): 158-163.
[5]	HUANG Chunshui;REN Yanli;CAI Jianxing. Verifiable outsourcing scheme for batch modular exponentiations [J]. Journal of Xidian University, 2016, 43(4): 135-140.
[6]	LIU Xing;YUAN Chaowei;YANG Zhen;LI Zhenjun. Services promote Lyapunov-based strategy in mobile cloud computing [J]. J4, 2015, 42(6): 138-144.
[7]	LU Di;MA Jianfeng;WANG Yichuan;XI Ning;ZHANG Liumei;MENG Xianjia. Enhanced fairness-based multi-resource allocation algorithm for cloud computing [J]. J4, 2014, 41(3): 162-168.
[8]	WANG Yichuan;MA Jianfeng;LU Di;ZHANG Liumei;MENG Xianjia. Cloud droplets freezing attack in cloud computing [J]. J4, 2014, 41(3): 116-122.
[9]	ZHU Xudong;LI Hui;GUO Zhen. Privacy-preserving query over the encrypted image in cloud computing [J]. J4, 2014, 41(2): 151-158.

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

PDF (PC)

Like

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 9

Metrics

Comments

Recommended 10