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

Overview & Synopsis

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.