Top

Journal of Scheduling

Published in:

02-07-2020

Dynamic speed scaling minimizing expected energy consumption for real-time tasks

Authors: Bruno Gaujal, Alain Girault, Stephan Plassart

Published in: Journal of Scheduling | Issue 5/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

previous article A decomposition heuristic for rotational workforce scheduling

next article Scheduling a proportionate flow shop of batching machines

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

Different communities use the term “speed” or “frequency,” which are equivalent for a processor. In this paper, we use the term “speed.”

When the actual workload can be smaller than WCET, our approach still applies by modifying the state evolution Eq. (6), to take into account early termination of jobs.

càdlàg = continue à droite, limite à gauche = right continuous with left limits.

Actually, we use the fact that the sum \(\sum _{i=0}^{u-1} j(s)\) is Schur-convex when j is convex (see Marshall and Olkin 1979).

An estimation of the distribution of their size can be obtained through the measurement of many traces of the real-time system.

i.i.d. = independent and identically distributed random variables.

Aydin, H., Melhem, R. G., Mossé, D., & Mejía-Alvarez, P. (2001). Determining optimal processor speeds for periodic real-time tasks with different power characteristics. In Euromicro conference on real-time systems, ECRTS’01 (pp. 225–232). Delft: IEEE Computer Society.

Bandari, M., Simon, R., & Aydin, H. (2014). Energy management of embedded wireless systems through voltage and modulation scaling under probabilistic workloads. In International green computing conference, IGCC’14 (pp. 1–10). Dallas, TX: IEEE Computer Society.

Bansal, N., Kimbrel, T., & Pruhs, K. (2007). Speed scaling to manage energy and temperature. Journal of the ACM, 54(1), 1–39.CrossRef

Bastoni, A., Brandenburg, B., & Anderson, J. (2010). Cache-related preemption and migration delays: Empirical approximation and impact on schedulability. In Workshop on operating systems platforms for embedded real-time applications, OSPERT’10 (pp. 33–44).

Bertsekas, D., & Tsitsiklis, J. (1996). Neuro-dynamic programming. Belmont, MA: Athena Scientific.

Bini, E., & Scordino, C. (2009). Optimal two-level speed assignment for real-time systems. IJES, 4(2), 101–111.CrossRef

Brandenburg, B. (2011). Scheduling and locking in multiprocessor real-time operating systems. Ph.D. thesis, The University of North Carolina at Chapel Hill, Chapel Hill (NC), USA.

Brandenburg, B., & Gul, M. (2016). Global scheduling not required: Simple, near-optimal multiprocessor real-time scheduling with semi-partitioned reservations. In Real-time systems symposium, RTSS’16 (pp. 99–110). IEEE Computer Society.

Burd, T., & Brodersen, R. (2000). Design issues for dynamic voltage scaling. In International symposium on low power electronics and design, ISLPED’00. Rapallo, Italy.

Gaujal, B., Girault, A., & Plassart, S. (2017). Dynamic speed scaling minimizing expected energy consumption for real-time tasks. Technical Report, hal-01615835, Inria.

Gaujal, B., Girault, A., & Plassart, S. (2019). A discrete time markov decision process for energy minimization under deadline constraints. Research report, Grenoble Alpes; Inria Grenoble Rhône-Alpes, Université de Grenoble. https://hal.inria.fr/hal-02391948.

Gaujal, B., Navet, N., & Walsh, C. (2005). Shortest path algorithms for real-time scheduling of FIFO tasks with minimal energy use. ACM Transactions on Embedded Computing Systems (TECS), 4(4), 907–933.CrossRef

Gruian, F. (2001). On energy reduction in hard real-time systems containing tasks with stochastic execution times. In IEEE workshop on power management for real-time and embedded systems (pp. 11–16).

Hilton, P., & Pedersen, J. (1991). Catalan numbers, their generalization, and their uses. The Mathematical Intelligencer, 13(2), 64–75.CrossRef

Horn, W. (1974). Some simple scheduling algorithms. Naval Research Logistics, 21(1), 177–185.CrossRef

Li, K. (2016). Energy and time constrained task scheduling on multiprocessor computers with discrete speed levels. Journal of Parallel and Distributed Computing, 95, 15–28.CrossRef

Lorch, J., & Smith, A. (2001). Improving dynamic voltage scaling algorithms with PACE. In ACM SIGMETRICS 2001 conference (pp. 50–61).

Mao, J., Cassandras, C. G., & Zhao, Q. (2007). Optimal dynamic voltage scaling in energy-limited nonpreemptive systems with real-time constraints. IEEE Transaction on Mobile Computing, 6(6), 678–688. https://doi.org/10.1109/TMC.2007.1024.CrossRef

Marshall, A., & Olkin, I. (1979). Inequalitites: Theory of majorization and its applications, Mathematics in Science and Engineering (Vol. 143). New York: Academic Press.

Müller, A., & Stoyan, D. (2002). Comparison methods for stochastic models and risks. Wiley Series in Probability and Statistics. London: Wiley. ISBN: 978-0-471-49446-1

Pillai, P., & Shin, K. G. (2001). Real-time dynamic voltage scaling for low-power embedded operating systems. SIGOPS Operating Systems Review, 35(5), 89–102.CrossRef

Puterman, M. L. (2005). Markov decision process : Discrete stochastic dynamic programming, Wiley Series in Probability and Statistics. New York: Wiley.

Wang, J., Roop, P., & Girault, A. (2016). Energy and timing aware synchronous programming. In International conference on embedded software, EMSOFT’16. Pittsburgh (PA), USA. https://doi.org/10.1145/2968478.2968500. https://hal.inria.fr/hal-01412100.

Wu, Q., Juang, P., Martonosi, M., & Clark, D. (2005). Voltage and frequency control with adaptive reaction time in multiple-clock-domain processors. In International conference on high-performance computer architecture, HPCA’05 (pp. 178–189). San Francisco, CA: IEEE.

Yao, F., Demers, A., & Shenker, S. (1995). A scheduling model for reduced CPU energy. In Proceedings of IEEE annual foundations of computer science (pp. 374–382).

Title: Dynamic speed scaling minimizing expected energy consumption for real-time tasks
Authors: Bruno Gaujal
Alain Girault
Stephan Plassart
Publication date: 02-07-2020
Publisher: Springer US
Published in: Journal of Scheduling / Issue 5/2020
Print ISSN: 1094-6136
Electronic ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-020-00660-9

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 5/2020

A decomposition heuristic for rotational workforce scheduling

Serial-batching scheduling with two agents to minimize makespan and maximum cost

Near-linear-time approximation algorithms for scheduling a batch-processing machine with setups and job rejection

Scheduling a proportionate flow shop of batching machines

Two-stage open-shop scheduling with a two-machine flow shop as a stage: approximation algorithms and empirical experiments

Scheduling two projects with controllable processing times in a single-machine environment