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

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

作　　者：何忠政[1] 门朝光[1] 陈拥军 李香[1] 

机构地区：[1]哈尔滨工程大学计算机科学与技术学院,黑龙江哈尔滨150001 [2]中国新兴建设开发总公司,北京100143

出　　处：《通信学报》2015年第7期153-165,共13页Journal on Communications

基　　金：国家自然科学基金资助项目(60873138;61100004);中央高校基本科研业务费专项基金资助项目(HEUCF100607)~~

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

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

分 类 号：TP302[自动化与计算机技术—计算机系统结构]