Skip to Main content Skip to Navigation
Journal articles

Multi-criteria scheduling of precedence task graphs on heterogeneous platforms

Abstract : Latency, fault tolerance and reliability are important requirements for several applications that are time critical in nature: such applications require guarantees in terms of latency, even when processors are subject to failures. In this paper, we propose a fault-tolerant scheduling heuristic for mapping precedence task graphs on heterogeneous systems. Our approach is based on an active replication scheme, capable of supporting ε arbitrary fail-silent/fail-stop processor failures, and hence valid results will be provided even if ε processors fail. First we focus on a bi-criteria approach, where we aim at minimizing the latency given a fixed number of failures supported in the system, or the other way round. Next we derive a more complex algorithm in which we not only minimize latency and support a fixed number of failures, but also improve the overall reliability. Major achievements include low complexity of the new algorithms, and a drastic reduction of the number of additional communications induced by the replication mechanism. Experimental results demonstrate that our heuristics, despite their lower complexity, outperform their direct competitor, the fault-tolerance based active replication scheduling algorithm FTBAR.
Document type :
Journal articles
Complete list of metadatas
Contributor : Equipe Roma <>
Submitted on : Wednesday, February 13, 2013 - 11:54:36 AM
Last modification on : Wednesday, February 26, 2020 - 11:14:08 AM




Anne Benoit, Mourad Hakem, Yves Robert. Multi-criteria scheduling of precedence task graphs on heterogeneous platforms. The Computer Journal, Oxford University Press (UK), 2010, 53 (6), pp.772-785. ⟨10.1093/comjnl/bxp067⟩. ⟨hal-00787907⟩



Record views