Stéphan Plassart - Online Energy Optimization for real-time systems

The energy consumption is a crucial issue for real-time systems, that's why optimizing it online, i.e. while the processor is running, has become essential and will be the goal of this thesis. This optimization is done by adapting the processor speed during the job execution. This thesis addresses several situations with different knowledge on past, active and future job characteristics.  Firstly, we consider that all job characteristics are known (the offline case), and we propose a linear time algorithm to determine the speed schedule to execute n jobs on a single processor. Secondly, using Markov decision processes, we solve the case where past and active job characteristics are entirely known, and for future jobs only the probability distribution of the jobs characteristics (arrival times, execution times and deadlines) are known. Thirdly we study a more general case: the execution is only discovered when the job is completed.  In addition we also consider the case where we have no statistical knowledge on jobs, so we have to use learning methods to determine the optimal processor speeds online.  Finally, we propose a feasibility analysis (the processor ability to execute all jobs before its deadline when it works always at maximal speed) of several classical online policies, and we show that our dynamic programming algorithm is also the best in terms of feasibility.