基于遗传算法的异构系统多副本容错调度算法

doi:10.11959/j.issn.1000-436x.2015203

Abstract

Abstract:

The fault-tolerant task scheduling mechanisms based on multi-duplication didn’t consider the scheduling makespan,the dependencies between tasks,the failures of the links and the longer scheduling makespan caused by the strict scheduling method in the heterogeneous distributed system.So the reliability calculation method that can involve the processor failures and the link failures was proposed firstly.Then the 0-1 integer linear program was proposed for the general scheduling problem.At last,the RAMD_TGS(reliability-aware multi-duplication task general scheduling) algorithm was proposed to solve the 0-1 integer linear program.The algorithm searched the mapped processor and the start execution time on the mapped processor for the task duplication by the evolution of the genetic algorithm.The experiments show that the RAMD_TGS algorithm can meet the reliability requirements and outperforms the existing scheduling algorithms based on the strict scheduling method in terms of scheduling makespan.The resource usages of the algorithm are also acceptable.

Key words: fault tolerant scheduling, heterogeneous distributed system, task duplication, genetic algorithm

Zhong-zheng HE,Chao-guang MEN,Yong-jun CHEN,Xiang LI. Multi-duplication fault tolerant scheduling algorithm based on genetic algorithm in heterogeneous systems[J]. Journal on Communications, 2015, 36(7): 153-165.

Figures/Tables 18

References 21

[1]	XIAO Y T , KENLI L , RENFA L , et al. Reliability-aware scheduling strategy for heterogeneous distributed computing systems[J]. Journal of Parallel and Distributed Computing, 2010,70(9): 941-952.
[2]	ZHAO L , REN Y , XIANG Y , et al. Fault tolerant scheduling with dynamic number of replicas in heterogeneous system[A]. IEEE International Conference on High Performance Computing and Communications[C]. Melbourne, 2010. 434-441.
[3]	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.
[4]	QIN Z , BHARADWAJ V . On the design of communication-aware fault-tolerant scheduling algorithms for precedence constrained tasks in grid computing systems with dedicated communication devices[J]. Journal of Parallel and Distributed Computing, 2009,69(3): 282-294.
[5]	QIN Z , BHARADWAJ V , CHEN K . On the design of fault-tolerant scheduling strategies using primary-backup approach for computational grids with low replication costs[J]. IEEE Transactions on Computers, 2009,58(3): 380-393.
[6]	王吉, 包卫东, 朱晓敏 . 虚拟化云平台中实时任务容错调度算法研究[J]. 通信学报, 2014,35(10): 171-180. WANG J , BAOW D , ZHU X M . Fault-tolerant scheduling algorithm forreal-time tasks in virtualized cloud[J]. Journal on Communications, 2014,35(10): 171-180.
[7]	GIRAULT A , KALLA H . A novel bicriteria scheduling heuristics providing a guaranteed global system failure rate[J]. IEEE Transactions on Dependable and Secure Computing, 2009,6(4): 241-254.
[8]	GIRAULT A , KALLA H , SIGHIREANU M , et al. An algorithm for automatically obtaining distributed and fault-tolerant static schedules[A]. International Conference on Dependable Systems and Networks[C]. 2003. 159-168.
[9]	ANNE B , MOURAD H , YVES R . Fault tolerant scheduling of precedence task graphs on heterogeneous platforms[A]. Proceedings of the 22nd International Conference on Parallel and Distributed Processing[C]. 2008. 1-8.
[10]	PAUL P , VIACHESLAV I , PETRU E , et al. Design optimization of time and cost-constrained fault-tolerant embedded systems with check pointing and replication[J]. IEEE Transactions on Very Large Scale Integration Systems, 2009,17(3): 389-402.
[11]	ANNE B , MOURAD H , YVES R . Contention awareness and fault-tolerant scheduling for precedence constrained tasks in heterogeneous systems[J]. Parallel Computing, 2009,35(2): 83-108.
[12]	ZHAO L , REN Y , SAKURAI K . Reliable workflow scheduling with less resource redundancy[J]. Parallel Computing, 2013,39(10): 567-585.
[13]	ALAIN G,éRIK S , DENIS T . Reliability versus performance for critical applications[J]. Journal of Parallel and Distributed Computing, 2009,69(3): 326-336.
[14]	ZHAO L , REN Y Z , SAKURAI K . A resource minimizing scheduling algorithm with ensuring the deadline and reliability in heterogeneous systems[A]. International Conference on Advanced Information Networking and Applications[C]. 2011. 275-282.
[15]	谢国琪, 李仁发, 刘琳等. 异构分布式系统 DAG 可靠性模型与容错算法[J]. 计算机学报, 2013,36(10): 2019-2032. XIEG Q , LIR F , LIUL , et al. DAG reliability model and fault-tolerant algorithm for heterogeneous distributed systems[J]. ChineseJournal of Computers, 2013,36(10): 2019-2032.
[16]	CHIN S H , SUH T , YU H C . Genetic algorithm based scheduling method for efficiency and reliability in mobile grid[A]. International Conference on Ubiquitous Information Technologies ＆ Applications[C]. 2009. 1-6.
[17]	ATAKAN D,FüSUN ? . Biobjective scheduling algorithms for execution time-reliability trade-off in heterogeneous computing systems[J]. The Computer Journal, 2005,48(3): 300-314.
[18]	WANG X F , YEO C S , BUYYA R , et al. Optimizing the makespan and reliability for workflow applications with reputation and a look-ahead genetic algorithm[J]. Future Generation Computer Systems, 2011,27(8): 1124-1134.
[19]	BENOIT A , DUFOSSé F , GIRAULT A , et al. Reliability and performance optimization of pipelined real-time systems[J]. Journal of Parallel and Distributed Computing, 2013,73(6): 851-865.
[20]	ANNE BENOIT , CANON L C , JEANNOT E , et al. Reliability of task graph schedules with transient and fail-stop failures:complexity and algorithms[J]. Journal of Scheduling, 2012,15(5): 615-627.
[21]	TOPCUOGLU H , HARIRI S , WU M . Performance-effective and lowcomplexity task scheduling for heterogeneous computing[J]. IEEE Transactions on Parallel and Distributed Systems, 2002,13(3): 260-274.

Metrics

Recommended 0

No Suggested Reading articles found!

任务数量	FTSA_BL	RAMD_TGS	RR
20	90.836%	94.286%	96.356%
30	90.365%	93.457%	95.684%
40	90.015%	92.846%	95.185%
50	89.564%	92.259%	95.067%
60	89.356%	91.948%	94.646%
70	89.249%	91.649%	93.452%
80	88.934%	91.146%	92.126%
90	88.948%	90.264%	91.568%
100	86.684%	90.576%	91.249%

故障次数	FTSA_BL	RAMD_TGS	RR
1	0.599×10⁴	0.589×10⁴	0.588×10⁴
2	1.499×10⁴	0.797×10⁴	0.748×10⁴
3	2.128×10⁴	1.249×10⁴	0.985×10⁴
4	2.569×10⁴	1.465×10⁴	1.168×10⁴

故障次数	FTSA_BL	RAMD_TGS	RR
1	1.984×10⁵	1.623×10⁵	1.094×10⁵
2	4.127×10⁵	1.649×10⁵	1.154×10⁵
3	6.858×10⁵	3.639×10⁵	2.662×10⁵
4	10.256×10⁵	4.562×10⁵	3.469×10⁵

Multi-duplication fault tolerant scheduling algorithm based on genetic algorithm in heterogeneous systems

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 18

References 21

Related Articles 15

Metrics

Recommended 0

[1]	Hang QIU, Hongbo TANG, Wei YOU, Yu ZHAO, Yi BAI. QGA-based network service extension algorithm in NFV [J]. Journal on Communications, 2022, 43(11): 44-52.
[2]	Yuliang CONG, Wenxi SUN, Ke XUE, Zhihong QIAN, Mianshu CHEN. Research on task offloading strategy of Internet of vehicles based on improved hybrid genetic algorithm [J]. Journal on Communications, 2022, 43(10): 77-85.
[3]	Xin SU, Haoyang XUE, Yiqing ZHOU, Jinxiu ZHU. Research on computing offloading method for maritime observation monitoring sensor network [J]. Journal on Communications, 2021, 42(5): 149-163.
[4]	Yi LU,Mengying XU,Jie ZHOU. Multi-constraints QoS routing optimization based on improved immune clonal shuffled frog leaping algorithm [J]. Journal on Communications, 2020, 41(5): 141-149.
[5]	Zhen ZHANG,Peng WEI,Yufeng LI,Julong LAN,Ping XU,Bo CHEN. Feature selection algorithm based on improved particle swarm joint taboo search [J]. Journal on Communications, 2018, 39(12): 60-68.
[6]	Haoran LIU,Pan DING,Changjiang GUO,Jinfeng CHANG,Jingchuang CUI. Study on Chinese spam filtering system based on Bayes algorithm [J]. Journal on Communications, 2018, 39(12): 151-159.
[7]	Hao FENG,Lei LUO,Yong WANG,Miao YE. Multi-objective data collecting strategies for wireless sensor network based on the time variable multi-salesman problem and genetic algorithm [J]. Journal on Communications, 2017, 38(3): 112-123.
[8]	Jian WANG,Guo-sheng ZHAO,Zhi-xin LI. Research on mapping algorithm of virtual network oriented to SDN [J]. Journal on Communications, 2017, 38(10): 26-35.
[9]	Yan-mei ZHANG,Ying-ying HUANG,Shi-jie GAN,Yi DING,Zhi-long MA. Weibo spammers’ identification algorithm based on Bayesian model [J]. Journal on Communications, 2017, 38(1): 44-53.
[10]	Er-fu WANG,Yuan-shuo ZHENG,Xin-wu CHEN. Neural network blind equalization optimized by parallel genetic algorithm with partial elitist strategy [J]. Journal on Communications, 2016, 37(7): 193-200.
[11]	Yue SHI,song QIUXue,yong GUOShao,Feng QI. Optimal planning of optical transmission network using improved genetic algorithm [J]. Journal on Communications, 2016, 37(1): 116-122.
[12]	Fu-you FAN,Guo-wu YANG,Qian-qi LE,Feng-mao LV,Chao ZHAO. Optimized coverage algorithm of wireless video sensor network based on quantum genetic algorithm [J]. Journal on Communications, 2015, 36(6): 94-104.
[13]	HOUWei Z,INGBo J,UANGYi-feng H,IAOXiao-xuan J,UJia-xing H,IANGWei L. CS-based data collection method for airborne clustering WSN [J]. Journal on Communications, 2015, 36(5): 130-139.
[14]	. Research on distributed genetic k-means for anomaly detection in MANET [J]. Journal on Communications, 2015, 36(11): 167-173.
[15]	Hui-qiang WANG,Xiao-ming CHEN,Hong-wu LV,Guang-sheng FENG,Qiang ZHU. Access point selection mechanism based on cross-layer awareness for cognitive networks [J]. Journal on Communications, 2015, 36(10): 188-199.