Article

System-wide energy minimization for real-time tasks: lower bound and approximation

Authors:

Cheng-Zhong XuAuthors Info & Claims

ICCAD '06: Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design

Pages 516 - 521

https://doi.org/10.1145/1233501.1233606

Published: 05 November 2006 Publication History

Abstract

We present a dynamic voltage scaling (DVS) technique that minimizes system-wide energy consumption for both periodic and sporadic tasks. It is known that a system consists of processors and a number of other components. Energy-aware processors can be run in different speed levels; components like memory and I/O subsystems and network interface cards can be in a standby state when they are active but idle. Processor energy optimization solutions are not necessarily efficient from the perspective of systems. Current system-wide energy optimization studies are often limited to periodic tasks with heuristics in getting approximated solutions. In this paper, we develop an exact dynamic programming algorithm for periodic tasks on processors with practical discrete speed levels. The algorithm determines the lower bound of energy expenditure in pseudo-polynomial time. An approximation algorithm is proposed to provide performance guarantee with a given bound in polynomial running time. Because of their time efficiency, both the optimization and approximation algorithms can be adapted for online scheduling of sporadic tasks with irregular task releases. We prove that system-wide energy optimization for sporadic tasks is NP-hard in the strong sense. We develop (pseudo-) polynomialtime solutions by exploiting its inherent properties.

References

[1]

J.-J. Chen, T.-W. Kuo, and C.-S. Shih. (1+ε) approximation clock rate assignment for periodic real-time tasks on a voltage-scaling processor. In Proc. of EMSOFT, 2005.

Digital Library

[2]

H. Cheng and S. Goddard. Integrated device scheduling and processor voltage scaling for system-wide energy conservation. In Proc. of PARC, 2005.

[3]

K. Choi, W. Lee, R. Soma, and M. Pedram. Dynamic voltage and frequency scaling under a precise energy model considering variable and fixed components of the system poweí dissipation. In Proc. of ICCAD, 2004.

Digital Library

[4]

K. Dudzinski and S. Walukiewicz. Exact methods for the knapsack problem and its generalizations. European Journal of Oper. Research, 28:3--21, 1987.

[5]

I. Hong, M. Potkonjak, and M. B. Srivastava. On-line scheduling of hard real-time tasks on variable voltage voltage processor. In Proc. of ICCAD, 1998.

Digital Library

[6]

Intel-XScale Microarchitecture (http://www.intel.com).

[7]

R. Jejurikar and R. K. Gupta. Dynamic voltage scaling for systemwide energy minimization in real-time embedded systems. In Proc. of ISLPED, 2004.

Digital Library

[8]

R. Jejurikar, C. Pereira, and R. K. Gupta. Leakage aware dynamic voltage scaling for real-time embedded systems. In Proc. of DAC, 2004.

Digital Library

[9]

H. Kellerer, U. Pferschy, and D. Pisinger. Knapsack Problems. Springer Verlag, 2004.

[10]

S. M. Martin, K. Flautner, T. N. Mudge, and D. Blaauw. Combined dynamic voltage scaling and adaptive body biasing for lower power microprocessors under dynamic workloads. In Proc. of ICCAD, 2002.

Digital Library

[11]

P. Mejía-Alvarez, E. Levner, and D. Mossé. Adaptive scheduling server for power-aware real-time tasks. ACM Trans. Embedded Comput. Syst., 3(2):284--306, 2004.

Digital Library

[12]

D. N. Rakhmatov and S. B. K. Vrudhula. Energy management for battery-powered embedded systems. ACM Trans. Embedded Comput. Syst., 2(3):277--324, 2003.

Digital Library

[13]

F. Xie, M. Martonosi, and S. Malik. Bounds on power savings using runtime dynamic voltage scaling: an exact algorithm and a linear-time heuristic approximation. In Proc. of ISLPED, 2005.

Digital Library

[14]

R. Xu, C. Xi, R. G. Melhem, and D. Mossé. Practical pace for embedded systems. In Proc. of EMSOFT, 2004.

Digital Library

[15]

L. Yan, J. Luo, and N. K. Jha. Combined dynamic voltage scaling and adaptive body biasing for heterogeneous distributed real-time embedded systems. In Proc. of ICCAD, 2003.

Digital Library

[16]

X. Zhong and C.-Z. Xu. Energy aware modeling and scheduling of real-time tasks for dynamic voltage scaling. In Proc. of RTSS, 2005.

Digital Library

[17]

J. Zhuo and C. Chakrabarti. System-level energy-efficient dynamic task scheduling. In Proc. of DAC, 2005.

Digital Library

Cited By

Hajiamini SShirazi BCrandall AGhasemzadeh H(2020)A Dynamic Programming Framework for DVFS-Based Energy-Efficiency in Multicore SystemsIEEE Transactions on Sustainable Computing10.1109/TSUSC.2019.29114715:1(1-12)Online publication date: 1-Jan-2020
https://doi.org/10.1109/TSUSC.2019.2911471
Zheng HZhang X(2017)Optimizing Task Assignment with Minimum Cost on Heterogeneous Embedded Multicore Systems Considering Time Constraint2017 IEEE 3rd International Conference on Big Data Security on Cloud (BigDataSecurity), IEEE International Conference on High Performance and Smart Computing, (HPSC) and IEEE International Conference on Intelligent Data and Security (IDS)10.1109/BigDataSecurity.2017.45(225-230)Online publication date: May-2017
https://doi.org/10.1109/BigDataSecurity.2017.45
Li YNiu JAtiquzzaman MLong X(2017)Energy-aware scheduling on heterogeneous multi-core systems with guaranteed probabilityJournal of Parallel and Distributed Computing10.1016/j.jpdc.2016.11.014103:C(64-76)Online publication date: 1-May-2017
https://dl.acm.org/doi/10.1016/j.jpdc.2016.11.014
Show More Cited By

Index Terms

Recommendations

System-wide energy minimization for real-time tasks: Lower bound and approximation

We present a dynamic voltage scaling (DVS) technique that minimizes system-wide energy consumption for both periodic and sporadic tasks. It is known that a system consists of processors and a number of other components. Energy-aware processors can be ...
Energy minimization of real-time tasks on variable voltage processors with transition energy overhead
ASP-DAC '03: Proceedings of the 2003 Asia and South Pacific Design Automation Conference

In this paper, we address the problem of minimizing energy consumption of real-time tasks on variable voltage processors whose transition energy overhead is not negligible. Voltage settings with minimum number of transitions are found first and sequences ...
System-Level Energy-Efficiency for Real-Time Tasks
ISORC '07: Proceedings of the 10th IEEE International Symposium on Object and Component-Oriented Real-Time Distributed Computing

Dynamic voltage scaling (DVS) has been adopted in many computing systems to reduce the energy consumption of the processor by slowing down the processor speed. However, for system devices without DVS capability, the longer a task executes, the more ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

ICCAD '06: Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design

November 2006

147 pages

ISBN:1595933891

DOI:10.1145/1233501

General Chair:
Soha Hassoun
Tufts Univ., Medford, MA

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IEEE-CAS: Circuits & Systems
IEEE-CS: Computer Society

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 November 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ICCAD06

Sponsor:

SIGDA
IEEE-CAS
IEEE-CS

ICCAD06: The International Conference on Computer-Aided Design 2006

November 5 - 9, 2006

California, San Jose

Acceptance Rates

Overall Acceptance Rate 457 of 1,762 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

25
Total Citations
View Citations
139
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Hajiamini SShirazi BCrandall AGhasemzadeh H(2020)A Dynamic Programming Framework for DVFS-Based Energy-Efficiency in Multicore SystemsIEEE Transactions on Sustainable Computing10.1109/TSUSC.2019.29114715:1(1-12)Online publication date: 1-Jan-2020
https://doi.org/10.1109/TSUSC.2019.2911471
Zheng HZhang X(2017)Optimizing Task Assignment with Minimum Cost on Heterogeneous Embedded Multicore Systems Considering Time Constraint2017 IEEE 3rd International Conference on Big Data Security on Cloud (BigDataSecurity), IEEE International Conference on High Performance and Smart Computing, (HPSC) and IEEE International Conference on Intelligent Data and Security (IDS)10.1109/BigDataSecurity.2017.45(225-230)Online publication date: May-2017
https://doi.org/10.1109/BigDataSecurity.2017.45
Li YNiu JAtiquzzaman MLong X(2017)Energy-aware scheduling on heterogeneous multi-core systems with guaranteed probabilityJournal of Parallel and Distributed Computing10.1016/j.jpdc.2016.11.014103:C(64-76)Online publication date: 1-May-2017
https://dl.acm.org/doi/10.1016/j.jpdc.2016.11.014
Gowtham SPoongothai M(2016)Timing based energy efficient task assignment algorithm for real time embedded systems2016 International Conference on Circuit, Power and Computing Technologies (ICCPCT)10.1109/ICCPCT.2016.7530189(1-5)Online publication date: Mar-2016
https://doi.org/10.1109/ICCPCT.2016.7530189
Jia ZLi YWang YWang MShao Z(2015)Temperature-Aware Data Allocation for Embedded Systems with Cache and Scratchpad MemoryACM Transactions on Embedded Computing Systems10.1145/262965014:2(1-24)Online publication date: 9-Mar-2015
https://dl.acm.org/doi/10.1145/2629650
Poongothai MRajeswari ASanmukapriya V(2014)Energy Efficient Scheduling Using Simulated Annealing Algorithm for Multi-Core ProcessorsApplied Mechanics and Materials10.4028/www.scientific.net/AMM.550.178550(178-186)Online publication date: May-2014
https://doi.org/10.4028/www.scientific.net/AMM.550.178
Wang WDong GDeng ZZeng GLiu WXiong HBalaji PGuo MHuang Z(2014)Reachability Analysis of Cost-Reward Timed Automata for Energy Efficiency SchedulingProceedings of Programming Models and Applications on Multicores and Manycores10.1145/2578948.2560695(140-148)Online publication date: 7-Feb-2014
https://dl.acm.org/doi/10.1145/2578948.2560695
Wang WDong GDeng ZZeng GLiu WXiong HBalaji PGuo MHuang Z(2014)Reachability Analysis of Cost-Reward Timed Automata for Energy Efficiency SchedulingProceedings of Programming Models and Applications on Multicores and Manycores10.1145/2560683.2560695(140-148)Online publication date: 7-Feb-2014
https://dl.acm.org/doi/10.1145/2560683.2560695
Niu JLiu CGao YQiu M(2014)Energy Efficient Task Assignment with Guaranteed Probability Satisfying Timing Constraints for Embedded SystemsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2013.25125:8(2043-2052)Online publication date: Aug-2014
https://doi.org/10.1109/TPDS.2013.251
He DMueller W(2013)A heuristic energy-aware approach for hard real-time systems on multi-core platformsMicroprocessors & Microsystems10.1016/j.micpro.2013.04.00737:8(858-870)Online publication date: 1-Nov-2013
https://dl.acm.org/doi/10.1016/j.micpro.2013.04.007
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten