ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2018, Vol. 55 ›› Issue (11): 2569-2583.doi: 10.7544/issn1000-1239.2018.20170893

Previous Articles    

Parallel Task Scheduling for Resource Consumption Minimization with Reliability Constraint

Xu Hongzhi1,2, Li Renfa1, Zeng Lining1   

  1. 1(湖南大学信息科学与工程学院 长沙 410082); 2(吉首大学软件学院 湖南张家界 427000) (xuhongzhi9@163.com)
  • Online:2018-11-01

Abstract: Reliability is an important figure of merit for the system and it must be satisfied in safety-critical applications. The systems’ reliability can be improved by resource redundancy, however, it must consume more system resources. The problem of minimizing resource consumption to satisfy reliability goal for parallel applications on heterogeneous systems is investigated. First, the reliability goal of the system is transformed to that of each single task, in which the average worst-case execution time (WCET) of a task on each processor is used as a reference for calculating the reliability goal. Two methods for calculating the reliability goal of each task are proposed for task replication and non-replication. Then, an algorithm of task non-replication for minimizing resource consumption with reliability goal (MRC) is designed. When the system reliability goal requirement isn’t higher than the reachable maximum reliability, the tasks can always be assigned to the appropriate processor so that the reliability goal of the system can be satisfied. Considering that the high-reliability requirements of the system cannot be satisfied by using MRC. Finally, two algorithms for task replication are designed to satisfy system reliability goal. The proposed algorithms are compared with MaxRe, RR, and MRCRG by using real parallel applications and randomly generated parallel applications. Experimental results demonstrate that the proposed algorithms consume fewer resources while satisfying the system reliability goal.

Key words: heterogeneous systems, parallel task, reliability goal, resource consumption, scheduling

CLC Number: