Scheduling Algorithms for new Emerging Applications

May, 29th - June, 2nd 2006, CIRM, Marseille, France

Reliability versus performance for embedded real-time applications

SpeakerErik Saule

Co-authorsAlain Girault and Denis Trystram

As a consequence of the huge development of ubiquitous and mobile computing, embedded systems are more and more popular. Embedded applications are often subject to real-time constraints, dependability issues and low energy consumption. These constraints make scheduling for embedded systems a complex problem.

In this work, we focus on generating high performance schedules with a good reliability. Reliability is a key factor of dependability. Usually, reliability is optimized by the replication of adequate tasks of the algorithm on some well chosen processors. The choice is done in regard to their reliability rate per time unit. We will consider a reliability model corresponding to transitory fault, in which only processors can fault, communication links are reliable.

Multi-objective optimization is a recent field which recently motivated a lot of attention from researchers and engineers. The commonly used approaches consist in fixing one criterion and optimizing the other. We propose a way for optimizing both criteria by providing a set of best compromize solutions. More precisely, we propose a heuristic method that decompose the problem in two successive phases, namely, a spatial allocation with a good reliability and a scheduling for minimizing the execution time. As the reliability problem is not so hard, the first step is implemented using a randomized algorithm. The second one is obtained by a local search algorithm.