Algorithmic power management - Energy minimisation under real-time constraints

Research output: ThesisPhD Thesis - Research UT, graduation UT

Abstract

Energy consumption is a major concern for designers of embedded devices. Especially for battery operated systems (like many embedded systems), the energy consumption limits the time for which a device can be active, and the amount of processing that can take place. In this thesis we study how the energy consumption can be reduced for certain classes of real-time applications. To minimise the energy consumption, we introduce several algorithms that combine power management techniques with scheduling (algorithmic power management). The power management techniques that we focus on are speed scaling and sleep modes. When the processor (or some peripheral) is active, its speed, and with it the supply voltage, can be decreased to reduce the power consumption (speed scaling), while when the processor is idle it can be put in a low power mode (sleep modes). The resulting problem is to determine a schedule, speeds for the processors (which may vary over time) and/or times when a device is put to sleep. We discuss energy minimisation for three classes of real-time systems, namely (1) real-time systems with agreeable deadlines, (2) real-time systems with precedence constraints, and (3) frame-based real-time systems. Below we elaborate on these classes of real-time systems. (1) For real-time systems with agreeable deadlines it holds that an earlier arrival time implies an earlier deadline (and vice versa). Compared to existing methods our algorithms can reduce the energy consumption by up to 54% for the considered multimedia workloads, and our evaluation shows that these algorithms are near optimal even with inaccurate predictions. (2) The second class of real-time systems we focus on are tasks with precedence constraints that must be scheduled on a multicore system and for which the speeds have to be determined. We derive a scheduling criterion that implicitly assigns speeds and minimises the energy consumption. (3) In the third setting, we study the optimal combination of speed scaling, sleep modes and scheduling for frame-based real-time systems. While the literature considers only trivial schedules for this problem, we study energy optimal schedules for such systems.
LanguageUndefined
Supervisors/Advisors
  • Smit, Gerardus Johannes Maria, Supervisor
  • Kuper, Jan , Advisor
Thesis sponsors
Award date18 Jun 2014
Place of PublicationEnschede
Publisher
Print ISBNs978-90-365-3679-0
DOIs
StatePublished - 18 Jun 2014

Keywords

  • Real time systems
  • EWI-24855
  • Power Management
  • Constrained optimisation
  • NWO 612.063.715

Cite this

Gerards, M. E. T. (2014). Algorithmic power management - Energy minimisation under real-time constraints Enschede: Centre for Telematics and Information Technology (CTIT) DOI: 10.3990/1.9789036536790
Gerards, Marco Egbertus Theodorus. / Algorithmic power management - Energy minimisation under real-time constraints. Enschede : Centre for Telematics and Information Technology (CTIT), 2014. 162 p.
@phdthesis{c69d24ad220a469988c1fa5425f66f18,
title = "Algorithmic power management - Energy minimisation under real-time constraints",
abstract = "Energy consumption is a major concern for designers of embedded devices. Especially for battery operated systems (like many embedded systems), the energy consumption limits the time for which a device can be active, and the amount of processing that can take place. In this thesis we study how the energy consumption can be reduced for certain classes of real-time applications. To minimise the energy consumption, we introduce several algorithms that combine power management techniques with scheduling (algorithmic power management). The power management techniques that we focus on are speed scaling and sleep modes. When the processor (or some peripheral) is active, its speed, and with it the supply voltage, can be decreased to reduce the power consumption (speed scaling), while when the processor is idle it can be put in a low power mode (sleep modes). The resulting problem is to determine a schedule, speeds for the processors (which may vary over time) and/or times when a device is put to sleep. We discuss energy minimisation for three classes of real-time systems, namely (1) real-time systems with agreeable deadlines, (2) real-time systems with precedence constraints, and (3) frame-based real-time systems. Below we elaborate on these classes of real-time systems. (1) For real-time systems with agreeable deadlines it holds that an earlier arrival time implies an earlier deadline (and vice versa). Compared to existing methods our algorithms can reduce the energy consumption by up to 54{\%} for the considered multimedia workloads, and our evaluation shows that these algorithms are near optimal even with inaccurate predictions. (2) The second class of real-time systems we focus on are tasks with precedence constraints that must be scheduled on a multicore system and for which the speeds have to be determined. We derive a scheduling criterion that implicitly assigns speeds and minimises the energy consumption. (3) In the third setting, we study the optimal combination of speed scaling, sleep modes and scheduling for frame-based real-time systems. While the literature considers only trivial schedules for this problem, we study energy optimal schedules for such systems.",
keywords = "Real time systems, EWI-24855, Power Management, Constrained optimisation, NWO 612.063.715",
author = "Gerards, {Marco Egbertus Theodorus}",
note = "NWO 612.063.715",
year = "2014",
month = "6",
day = "18",
doi = "10.3990/1.9789036536790",
language = "Undefined",
isbn = "978-90-365-3679-0",
publisher = "Centre for Telematics and Information Technology (CTIT)",
address = "Netherlands",

}

Algorithmic power management - Energy minimisation under real-time constraints. / Gerards, Marco Egbertus Theodorus.

Enschede : Centre for Telematics and Information Technology (CTIT), 2014. 162 p.

Research output: ThesisPhD Thesis - Research UT, graduation UT

TY - THES

T1 - Algorithmic power management - Energy minimisation under real-time constraints

AU - Gerards,Marco Egbertus Theodorus

N1 - NWO 612.063.715

PY - 2014/6/18

Y1 - 2014/6/18

N2 - Energy consumption is a major concern for designers of embedded devices. Especially for battery operated systems (like many embedded systems), the energy consumption limits the time for which a device can be active, and the amount of processing that can take place. In this thesis we study how the energy consumption can be reduced for certain classes of real-time applications. To minimise the energy consumption, we introduce several algorithms that combine power management techniques with scheduling (algorithmic power management). The power management techniques that we focus on are speed scaling and sleep modes. When the processor (or some peripheral) is active, its speed, and with it the supply voltage, can be decreased to reduce the power consumption (speed scaling), while when the processor is idle it can be put in a low power mode (sleep modes). The resulting problem is to determine a schedule, speeds for the processors (which may vary over time) and/or times when a device is put to sleep. We discuss energy minimisation for three classes of real-time systems, namely (1) real-time systems with agreeable deadlines, (2) real-time systems with precedence constraints, and (3) frame-based real-time systems. Below we elaborate on these classes of real-time systems. (1) For real-time systems with agreeable deadlines it holds that an earlier arrival time implies an earlier deadline (and vice versa). Compared to existing methods our algorithms can reduce the energy consumption by up to 54% for the considered multimedia workloads, and our evaluation shows that these algorithms are near optimal even with inaccurate predictions. (2) The second class of real-time systems we focus on are tasks with precedence constraints that must be scheduled on a multicore system and for which the speeds have to be determined. We derive a scheduling criterion that implicitly assigns speeds and minimises the energy consumption. (3) In the third setting, we study the optimal combination of speed scaling, sleep modes and scheduling for frame-based real-time systems. While the literature considers only trivial schedules for this problem, we study energy optimal schedules for such systems.

AB - Energy consumption is a major concern for designers of embedded devices. Especially for battery operated systems (like many embedded systems), the energy consumption limits the time for which a device can be active, and the amount of processing that can take place. In this thesis we study how the energy consumption can be reduced for certain classes of real-time applications. To minimise the energy consumption, we introduce several algorithms that combine power management techniques with scheduling (algorithmic power management). The power management techniques that we focus on are speed scaling and sleep modes. When the processor (or some peripheral) is active, its speed, and with it the supply voltage, can be decreased to reduce the power consumption (speed scaling), while when the processor is idle it can be put in a low power mode (sleep modes). The resulting problem is to determine a schedule, speeds for the processors (which may vary over time) and/or times when a device is put to sleep. We discuss energy minimisation for three classes of real-time systems, namely (1) real-time systems with agreeable deadlines, (2) real-time systems with precedence constraints, and (3) frame-based real-time systems. Below we elaborate on these classes of real-time systems. (1) For real-time systems with agreeable deadlines it holds that an earlier arrival time implies an earlier deadline (and vice versa). Compared to existing methods our algorithms can reduce the energy consumption by up to 54% for the considered multimedia workloads, and our evaluation shows that these algorithms are near optimal even with inaccurate predictions. (2) The second class of real-time systems we focus on are tasks with precedence constraints that must be scheduled on a multicore system and for which the speeds have to be determined. We derive a scheduling criterion that implicitly assigns speeds and minimises the energy consumption. (3) In the third setting, we study the optimal combination of speed scaling, sleep modes and scheduling for frame-based real-time systems. While the literature considers only trivial schedules for this problem, we study energy optimal schedules for such systems.

KW - Real time systems

KW - EWI-24855

KW - Power Management

KW - Constrained optimisation

KW - NWO 612.063.715

U2 - 10.3990/1.9789036536790

DO - 10.3990/1.9789036536790

M3 - PhD Thesis - Research UT, graduation UT

SN - 978-90-365-3679-0

PB - Centre for Telematics and Information Technology (CTIT)

CY - Enschede

ER -

Gerards MET. Algorithmic power management - Energy minimisation under real-time constraints. Enschede: Centre for Telematics and Information Technology (CTIT), 2014. 162 p. Available from, DOI: 10.3990/1.9789036536790