ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2018, Vol. 55 ›› Issue (11): 2569-2583.doi: 10.7544/issn1000-1239.2018.20170893

• 软件技术 • 上一篇    

并行任务可靠性约束下的资源最小化调度

徐洪智1,2,李仁发1,曾理宁1   

  1. 1(College of Computer Science and Electronic Engineering, Hunan University, Changsha 410082); 2(College of Software, Jishou University, Zhangjiajie, Hunan 427000)
  • 出版日期: 2018-11-01
  • 基金资助: 
    国家自然科学基金项目(61672217)

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

摘要: 可靠性是系统的一项重要质量指标,在安全关键的系统中极其重要.应用资源冗余的方式可以提高系统的可靠性,但会消耗更多的系统资源.研究了异构多处理器系统执行并行任务时最小化系统资源并保证可靠性的问题.首先以任务在各处理器上的平均最坏执行时间为参考,将系统可靠性目标转换为单个任务的可靠性目标,分别给出了非复制和复制情况下任务可靠性目标的计算方法;然后设计了一个可靠性约束下的资源最小化非复制算法,当给出的可靠性目标要求不高于系统可达到的最高可靠性时,该算法总能将任务分配到合适的处理器并使系统满足可靠性要求.由于非复制算法不能满足系统更高可靠性目标要求,最后设计了2个基于任务复制的算法.应用实际并行任务和随机生成的并行任务将提出的算法和MaxRe算法、RR算法以及MRCRG算法进行比较,实验结果表明:提出的算法在满足系统可靠性目标的同时消耗的资源更少.

关键词: 异构系统, 并行任务, 可靠性目标, 资源消耗, 调度

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

中图分类号: