A Novel Bicriteria Scheduling Heuristics Providing a Guaranteed Global System Failure Rate
A Novel Bicriteria Scheduling Heuristics Providing a Guaranteed Global System Failure Rate
复制标题
DOI：
10.1109/tdsc.2008.50
复制
发表时间：
2009-10
影响因子：
7.3
通讯作者：
A. Girault;H. Kalla
中科院分区：
文献类型：
--
作者：
A. Girault;H. Kalla
我们针对（长度和可靠性）双标准静态多处理器调度问题提出了一个新框架。我们的首要标准仍然是时间表的长度，这对于评估系统的实时性至关重要。对于我们的第二个标准，我们考虑全局系统故障率，就好像整个系统是调度到单个处理器上的单个任务，而不是通常的可靠性，因为它不像可靠性那样依赖于调度长度（由于其在经典指数分布模型中计算）。因此，我们可以根据所需的故障率更好地控制作为规范给出的依赖任务图的每个单独任务的复制因子。为了解决这个双标准优化问题，我们将故障率作为约束，并最小化调度长度。因此，对于给定的依赖任务图和多处理器架构，我们能够生成非支配解决方案的帕累托曲线，用户可以在其中选择最适合他或她的要求的折衷方案。与文献中发现的其他双标准（长度和可靠性）调度算法相比，我们在这里提出的算法是第一个能够将可靠性显着提高几个数量级的算法，使其适用于安全关键系统。
We propose a new framework for the (length and reliability) bicriteria static multiprocessor scheduling problem. Our first criterion remains the schedule's length, which is crucial to assess the system's real-time property. For our second criterion, we consider the global system failure rate, seen as if the whole system were a single task scheduled onto a single processor, instead of the usual reliability, because it does not depend on the schedule length like the reliability does (due to its computation in the classical exponential distribution model). Therefore, we control better the replication factor of each individual task of the dependency task graph given as a specification, with respect to the desired failure rate. To solve this bicriteria optimization problem, we take the failure rate as a constraint, and we minimize the schedule length. We are thus able to produce, for a given dependency task graph and multiprocessor architecture, a Pareto curve of nondominated solutions, among which the user can choose the compromise that fits his or her requirements best. Compared to the other bicriteria (length and reliability) scheduling algorithms found in the literature, the algorithm we present here is the first able to improve significantly the reliability, by several orders of magnitude, making it suitable to safety-critical systems.