高级检索
    徐洪智, 李仁发, 曾理宁. 并行任务可靠性约束下的资源最小化调度[J]. 计算机研究与发展, 2018, 55(11): 2569-2583. DOI: 10.7544/issn1000-1239.2018.20170893
    引用本文: 徐洪智, 李仁发, 曾理宁. 并行任务可靠性约束下的资源最小化调度[J]. 计算机研究与发展, 2018, 55(11): 2569-2583. DOI: 10.7544/issn1000-1239.2018.20170893
    Xu Hongzhi, Li Renfa, Zeng Lining. Parallel Task Scheduling for Resource Consumption Minimization with Reliability Constraint[J]. Journal of Computer Research and Development, 2018, 55(11): 2569-2583. DOI: 10.7544/issn1000-1239.2018.20170893
    Citation: Xu Hongzhi, Li Renfa, Zeng Lining. Parallel Task Scheduling for Resource Consumption Minimization with Reliability Constraint[J]. Journal of Computer Research and Development, 2018, 55(11): 2569-2583. DOI: 10.7544/issn1000-1239.2018.20170893

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

    Parallel Task Scheduling for Resource Consumption Minimization with Reliability Constraint

    • 摘要: 可靠性是系统的一项重要质量指标,在安全关键的系统中极其重要.应用资源冗余的方式可以提高系统的可靠性,但会消耗更多的系统资源.研究了异构多处理器系统执行并行任务时最小化系统资源并保证可靠性的问题.首先以任务在各处理器上的平均最坏执行时间为参考,将系统可靠性目标转换为单个任务的可靠性目标,分别给出了非复制和复制情况下任务可靠性目标的计算方法;然后设计了一个可靠性约束下的资源最小化非复制算法,当给出的可靠性目标要求不高于系统可达到的最高可靠性时,该算法总能将任务分配到合适的处理器并使系统满足可靠性要求.由于非复制算法不能满足系统更高可靠性目标要求,最后设计了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.

       

    /

    返回文章
    返回