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

Anne Benoit (1) , Mourad Hakem (1) , Yves Robert (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

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.

Mots clés: Communication contention; Fault tolerance; Heterogeneous systems; Multi-criteria scheduling

Domaines: Informatique [cs]

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⟩