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

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

摘要/Abstract

摘要：

针对异构系统中基于多副本机制的容错调度方法忽略调度makespan、任务间依赖与系统链路失效及严格调度方式调度 makespan 较长问题，首先提出通用调度方式下同时考虑节点和链路失效的可靠性计算方法；然后给出该通用调度问题的 0-1 整数规划模型；接着提出可靠性意识多副本任务通用调度(RAMD_TGS,reliability-aware multi-duplication task general scheduling)算法，通过遗传算法种群进化来搜索副本映射节点和开始执行时间。实验表明该算法不仅满足可靠性要求，而且与严格调度方式相比能进一步减小调度makespan，该算法资源占用开销也是可接受的。

关键词: 容错调度, 异构分布式系统, 任务副本, 遗传算法

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

何忠政,门朝光,陈拥军,李香. 基于遗传算法的异构系统多副本容错调度算法[J]. 通信学报, 2015, 36(7): 153-165.

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.

图/表 18

图1

图2

图3

图4

图5

图6

图7

图8

图9

表1

图10

图11

图12

图13

图14

图15

表2

表3

参考文献 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.

任务数量	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⁵