Realistic models and efficient algorithms for fault-tolerant scheduling on heterogeneous platforms

Abstract : AbstractMost list scheduling heuristics rely on a simple platform model wherecommunication contention is not taken into account. In addition, it isgenerally assumed that processors in the systems are completely safe. Toschedule precedence graphs in a more realistic framework, we introducean efficient fault tolerant scheduling algorithm that is both contentionawareand capable of supporting " arbitrary fail-silent (fail-stop) processorfailures. We focus on a bi-criteria approach, where we aim atminimizing the total execution time, or latency, given a fixed number offailures supported in the system. Our algorithm has a low time complexity,and drastically reduces the number of additional communicationsinduced by the replication mechanism. Experimental results fullydemonstrate the usefulness of the proposed algorithm, which leads toefficient execution schemes while guaranteeing a prescribed level of faulttolerance.
Document type :
Reports
Complete list of metadatas

Cited literature [28 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02102653
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 3:30:05 PM
Last modification on : Friday, April 19, 2019 - 1:38:16 AM

File

RR2008-09.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02102653, version 1

Collections

Citation

Anne Benoit, Mourad Hakem, Yves Robert. Realistic models and efficient algorithms for fault-tolerant scheduling on heterogeneous platforms. [Research Report] LIP RR-2008-09, Laboratoire de l'informatique du parallélisme. 2008, 2+21p. ⟨hal-02102653⟩

Share

Metrics

Record views

14

Files downloads

45