Dynamic speed scaling minimizing expected energy consumption for real-time tasks
- PDF / 885,696 Bytes
- 20 Pages / 595.276 x 790.866 pts Page_size
- 36 Downloads / 191 Views
Dynamic speed scaling minimizing expected energy consumption for real-time tasks Bruno Gaujal1 · Alain Girault1
· Stephan Plassart1
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract This paper proposes a discrete time Markov decision process approach to compute the optimal on-line speed scaling policy to minimize the energy consumption of a single processor executing a finite or infinite set of jobs with real-time constraints. We provide several qualitative properties of the optimal policy: monotonicity with respect to the jobs parameters, comparison with on-line deterministic algorithms. Numerical experiments in several scenarios show that our proposition performs well when compared with off-line optimal solutions and out-performs on-line solutions oblivious to statistical information on the jobs. Keywords Optimization · Real-time systems · Markov decision process · Dynamic voltage and frequency scaling
1 Introduction Minimizing the energy consumption of embedded system is becoming more and more important. This is due to the fact that more functionalities and better performances are expected from such systems, together with a need to limit the energy consumption, mainly because batteries are becoming the standard power supplies. The starting point of this work is the seminal paper of Yao et al. (1995) followed by the paper of Bansal et al. (2007), both of which solve the following problem. Let (ri , ci , di )i∈N be a set of jobs, where ri is the release date (or arrival time) of job i, ci is its size (or WCET, or workload) i.e., the number of processor cycles needed to complete the job, and di is its relative deadline, i.e., the amount of time given to the processor to execute job i. The problem is to
This work has been partially supported by the LabEx PERSYVAL-Lab.
B
Alain Girault [email protected] Bruno Gaujal [email protected] Stephan Plassart [email protected]
1
Inria, CNRS, Grenoble INP, LIG, Univ. Grenoble Alpes, 38000 Grenoble, France
choose the speed s(t) of the processor1 as a function of the time t, such that the processor can execute all the jobs before their deadlines, and such that the total energy consumption J is minimized. In this problem, J is the dynamic energy T consumed by the processor: J = 0 j(s(t))dt, where T is the time horizon of the problem (in the finite horizon case) and j(s) is the power consumption when the speed is s. This problem has been solved in Yao et al. (1995) when the power function j is a convex function of the speed, in the off-line case, i.e., when all jobs are known in advance. Many variants have been proposed to this off-line solution, for different job and energy models (see e.g., Aydin et al. 2001). However, in practice the exact characteristics of all the upcoming jobs cannot be known in advance, so the offline case is unrealistic. Several solutions have been investigated by Bansal et al. (2007) in the on-line case, i.e., when only the jobs released at or before time t can be used to select the speed s(t). Bansal
Data Loading...
