More Web Proxy on the site http://driver.im/

research-article

Energy-Aware Modeling and Scheduling for Dynamic Voltage Scaling with Statistical Real-Time Guarantee

Authors:

Cheng-Zhong XuAuthors Info & Claims

IEEE Transactions on Computers, Volume 56, Issue 3

Pages 358 - 372

https://doi.org/10.1109/TC.2007.48

Published: 01 March 2007 Publication History

Abstract

Dynamic voltage scaling (DVS) is a promising technique for battery-powered systems to conserve energy consumption. Most existing DVS algorithms assume information about task periodicity or a priori knowledge about the task set to be scheduled. This paper presents an analytical model of general tasks for DVS assuming job timing information is known only after a task release. It models the voltage scaling process as a transfer function-based filtering system, which facilitates the design of two efficient scaling algorithms. The first is a time-invariant scaling policy and it is proved to be a generalization of several popular DVS algorithms for periodic, sporadic, and aperiodic tasks. A more energy efficient policy is a time-variant scaling algorithm for aperiodic tasks. It is optimal in the sense that it is online without assumed information about future task releases. The algorithm turns out to be a water-filling process with a linear time complexity. It can be applied to scheduling based on worst-case execution times as well as online slack distribution when jobs complete earlier. We further establish two relationships between computation capacity and deadline misses to provide a statistical real-time guarantee with reduced capacity.

References

[1]

H. Aydin, R.G. Melhem, D. Mossé, and P. Mejía-Alvarez, “Power-Aware Scheduling for Periodic Real-Time Tasks,” IEEE Trans. Computers, vol. 53, no. 5, pp. 584-600, May 2004.

Digital Library

[2]

E. Bini, G. Buttazzo, and G. Lipari, “Speed Modulation in Energy-Aware Real-Time Systems,” Proc. Euromicro Conf. Real-Time Systems, pp. 3-10, 2005.

Digital Library

[3]

T. Cover and J. Thomas, Elements of Information Theory, pp. 250-253. John Wiley & Sons, 1991.

Digital Library

[4]

J.K. Dey, J.F. Kurose, and D.F. Towsley, “On-Line Scheduling Policies for a Class of Iris (Increasing Reward with Increasing Service) Real-Time Tasks,” IEEE Trans. Computers, vol. 45, no. 7, pp. 802-813, July 1996.

Digital Library

[5]

J.L. Díaz, D.F. García, K. Kim, C.-G. Lee, L.L. Bello, J.M. López, L. Min, and O. Mirabella, “Stochastic Analysis of Periodic Real-Time Systems,” Proc. IEEE Real-Time Systems Symp., pp. 289-300, 2002.

Digital Library

[6]

D. Duarte, N. Vijaykrishnan, M.J. Irwin, H.S. Kim, and G. McFarland, “Impact of Scaling on the Effectiveness of Dynamic Power Reduction Schemes,” Proc. Int'l Conf. Computer Design, pp.382-387, 2002.

Digital Library

[7]

W. Feller, An Introduction to Probability Theory and Its Applications (Volume II). John Wiley & Sons, 1971.

[8]

S. Gochman, R. Ronen, I. Anati, A. Berkovits, T. Kurts, A. Naveh, A. Saeed, Z. Sperber, and R.C. Valentine, “The Intel Pentium M Processor: Microarchitecture and Performance,” Intel Technology J., vol. 7, no. 2, pp. 31-36, 2003.

[9]

F. Gruian, “Hard Real-Time Scheduling for Low-Energy Using Stochastic Data and DVS Processors,” Proc. Int'l Symp. Low-Power Electronics and Design, pp. 46-51, 2001.

Digital Library

[10]

I. Hong, M. Potkonjak, and M.B. Srivastava, “On-Line Scheduling of Hard Real-Time Tasks on Variable Voltage Voltage Processor,” Proc. Int'l Conf. Computer-Aided Design, pp. 653-656, 1998.

Digital Library

[11]

T. Ishihara and H. Yasuura, “Voltage Scheduling Problem for Dynamically Variable Voltage Processors,” Proc. Int'l Symp. Low-Power Electronics and Design, pp. 197-202, 1998.

Digital Library

[12]

R. Jejurikar and R.K. Gupta, “Dynamic Slack Reclamation with Procrastination Scheduling in Real-Time Embedded Systems,” Proc. Design Automation Conf., pp. 111-116, 2005.

Digital Library

[13]

R. Jejurikar, C. Pereira, and R.K. Gupta, “Leakage Aware Dynamic Voltage Scaling for Real-Time Embedded Systems,” Proc. Design Automation Conf., pp. 275-280, 2004.

Digital Library

[14]

M.A. Khojastepour and A. Sabharwal, “Delay-Constrained Scheduling: Power Efficiency, Filter Design, and Bounds,” Proc. IEEE Infocom, pp. 1938-1949, 2004.

[15]

W.-C. Kwon and T. Kim, “Optimal Voltage Allocation Techniques for Dynamically Variable Voltage Processors,” ACM Trans. Embedded Computing Systems, vol. 4, no. 1, pp. 211-230, 2005.

Digital Library

[16]

C.-H. Lee and K.G. Shin, “On-Line Dynamic Voltage Scaling for Hard Real-Time Systems Using the EDF Algorithm,” Proc. IEEE Int'l Real-Time Systems Symp., pp. 319-327, 2004.

Digital Library

[17]

J.W. Liu, Real-Time Systems. Prentice Hall, 2000.

[18]

J.R. Lorch and A.J. Smith, “Improving Dynamic Voltage Scaling Algorithms With PACE,” Proc. ACM SIGMETRICS Conf., pp. 50-61, 2001.

Digital Library

[19]

A. Manzak and C. Chakrabarti, “Variable Voltage Task Scheduling Algorithms for Minimizing Energy/Power,” IEEE Trans. Very Large Scale Integration Systems, vol. 11, no. 2, pp. 270-276, 2003.

Digital Library

[20]

P. Mejía-Alvarez, E. Levner, and D. Mossé, “Adaptive Scheduling Server for Power-Aware Real-Time Tasks,” ACM Trans. Embedded Computing Systems, vol. 3, no. 2, pp. 284-306, 2004.

Digital Library

[21]

P. Peebles Jr., Probability, Random Variables, and Random Signal Principles, chapter 6. McGraw-Hill, 2001.

[22]

P. Pillai and K.G. Shin, “Real-Time Dynamic Voltage Scaling for Low-Power Embedded Operating Systems,” Proc. 18th Symp. Operating Systems Principles, pp. 89-102, 2001.

Digital Library

[23]

A. Qadi, S. Goddard, and S. Farritor, “A Dynamic Voltage Scaling Algorithm for Sporadic Tasks,” Proc. IEEE Real-Time Systems Symp., pp. 52-62, 2003.

Digital Library

[24]

G. Quan and X.S. Hu, “Energy Efficient Fixed-Priority Scheduling for Real-Time Systems on Variable Voltage Processors,” Proc. Design Automation Conf., pp. 828-833, 2001.

Digital Library

[25]

G. Quan, L. Niu, S. Hu, and B. Mochocki, “Fixed Priority Scheduling for Reducing Overall Energy on Variable Voltage Processors,” Proc. IEEE Real-Time Systems Symp., pp. 309-318, 2004.

Digital Library

[26]

D. Roychowdhury, I. Koren, C.M. Krishna, and Y.-H. Lee, “A Voltage Scheduling Heuristic for Real-Time Task Graphs,” Proc. Int'l Conf. Dependable Systems and Networks, pp. 741-750, 2003.

[27]

C. Rusu, R. Xu, R.G. Melhem, and D. Mossé, “Energy-Efficient Policies for Request-Driven Soft Real-Time Systems,” Proc. Euromicro Conf. Real-Time Systems, pp. 175-183, 2004.

Digital Library

[28]

V. Sharma, A. Thomas, T. Abdelzaher, K. Skadron, and Z. Lu, “Power-Aware QoS Management in Web Servers,” Proc. IEEE Real-Time Systems Symp., pp. 63-72, 2003.

Digital Library

[29]

Y. Shin and K. Choi, “Power Conscious Fixed Priority Scheduling for Hard Real-Time Systems,” Proc. Design Automation Conf., pp.134-139, 1999.

Digital Library

[30]

A. Sinha and A.P. Chandrakasan, “Energy Efficient Real-Time Scheduling,” Proc. Int'l Conf. Computer-Aided Design, pp. 458-470, 2001.

Digital Library

[31]

V. Swaminathan and K. Chakrabarty, “Network Flow Techniques for Dynamic Voltage Scaling in Hard Real-Time Systems,” IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, vol. 23, no. 10, pp. 1385-1398, 2004.

Digital Library

[32]

T.-S. Tia, Z. Deng, M. Shankar, M. Storch, J. Sun, L.-C. Wu, and J.W.-S. Liu, “Probabilistic Performance Guarantee for Real-Time Tasks with Varying Computation Times,” Proc. IEEE Real-Time Technology and Applications Symp., pp. 164-173, 1995.

Digital Library

[33]

E. Uysal-Biyikoglu and A.E. Gamal, “On Adaptive Transmission for Energy Efficiency in Wireless Data Networks,” IEEE Trans. Information Theory, vol. 50, no. 12, pp. 3081-3094, 2004.

Digital Library

[34]

F. Yao, A. Demers, and A. Shenker, “A Scheduling Model for Reduced CPU Energy,” Proc. IEEE Symp. Foundations of Computer Science, pp. 374-382, 1995.

Digital Library

[35]

W. Yu, W. Rhee, S. Boyd, and J.M. Cioffi, “Iterative Water-Filling for Gaussian Vector Multiple-Access Channels,” IEEE Trans. Information Theory, vol. 50, no. 1, pp. 145-152, 2004.

Digital Library

[36]

W. Yuan and K. Nahrstedt, “Energy-Efficient Soft Real-Time CPU Scheduling for Mobile Multimedia Systems,” Proc. 19th ACM Symp. Operating System Principles, pp. 149-163, 2003.

Digital Library

[37]

F. Zhang and S.T. Chanson, “Blocking-Aware Processor Voltage Scheduling for Real-Time Tasks,” ACM Trans. Embedded Computing Systems, vol. 3, no. 2, pp. 307-335, 2004.

Digital Library

[38]

X. Zhong and C.-Z. Xu, “Energy Aware Modeling and Scheduling of Real-Time Tasks for Dynamic Voltage Scaling,” Proc. IEEE Real-Time Systems Symp., pp. 366-375, 2005.

Digital Library

[39]

X. Zhong and C.-Z. Xu, “System-Wide Energy Minimization for Real-Time Tasks: Lower Bound and Approximation,” Proc. Int'l Conf. Computer-Aided Design, 2006.

Digital Library

[40]

D. Zhu, R.G. Melhem, and B.R. Childers, “Scheduling with Dynamic Voltage/Speed Adjustment Using Slack Reclamation in Multiprocessor Real-Time Systems,” IEEE Trans. Parallel and Distributed Systems, vol. 14, no. 7, pp. 686-700, July 2003.

Digital Library

[41]

Y. Zhu and F. Mueller, “Feedback EDF Scheduling Exploiting Dynamic Voltage Scaling,” Proc. IEEE Real-Time and Embedded Technology and Applications Symp., pp. 203-212, 2004.

Digital Library

Cited By

Grami M(2022)An energy-aware scheduling of dynamic workflows using big data similarity statistical analysis in cloud computingThe Journal of Supercomputing10.1007/s11227-021-04016-878:3(4261-4289)Online publication date: 1-Feb-2022
https://dl.acm.org/doi/10.1007/s11227-021-04016-8
Pérez Rodríguez JMeumeu Yomsi P(2021)An Efficient Proactive Thermal-Aware Scheduler for DVFS-enabled Single-Core ProcessorsProceedings of the 29th International Conference on Real-Time Networks and Systems10.1145/3453417.3453430(144-154)Online publication date: 7-Apr-2021
https://dl.acm.org/doi/10.1145/3453417.3453430
Balsini APannocchi LCucinotta T(2019)Modeling and simulation of power consumption and execution times for real-time tasks on embedded heterogeneous architecturesACM SIGBED Review10.1145/3373400.337340816:3(51-56)Online publication date: 25-Nov-2019
https://dl.acm.org/doi/10.1145/3373400.3373408
Show More Cited By

Index Terms

Recommendations

Blocking-aware processor voltage scheduling for real-time tasks

As mobile computing is getting popular, there is a growing need for techniques that minimize energy consumption on battery-powered mobile devices. Processor voltage scheduling can effectively reduce processor energy consumption by lowering the processor ...
Voltage-Clock-Scaling Adaptive Scheduling Techniques for Low Power in Hard Real-Time Systems

Abstract--Many embedded systems operate under severe power and energy constraints. Voltage clock scaling is one mechanism by which energy consumption may be reduced: It is based on the fact that power consumption is a quadratic function of the voltage, ...
Frequency-aware energy optimization for real-time periodic and aperiodic tasks
LCTES '07: Proceedings of the 2007 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems

Energy efficiency is an important factor in embedded systems design. We consider an embedded system with a dynamic voltage scaling (DVS) capable processor and its system-wide power consumption is dominated by the processor and memory. We present speed ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Computers

IEEE Transactions on Computers Volume 56, Issue 3

March 2007

143 pages

ISSN:0018-9340

Issue’s Table of Contents

Copyright © 2007.

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 March 2007

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 16 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Grami M(2022)An energy-aware scheduling of dynamic workflows using big data similarity statistical analysis in cloud computingThe Journal of Supercomputing10.1007/s11227-021-04016-878:3(4261-4289)Online publication date: 1-Feb-2022
https://dl.acm.org/doi/10.1007/s11227-021-04016-8
Pérez Rodríguez JMeumeu Yomsi P(2021)An Efficient Proactive Thermal-Aware Scheduler for DVFS-enabled Single-Core ProcessorsProceedings of the 29th International Conference on Real-Time Networks and Systems10.1145/3453417.3453430(144-154)Online publication date: 7-Apr-2021
https://dl.acm.org/doi/10.1145/3453417.3453430
Balsini APannocchi LCucinotta T(2019)Modeling and simulation of power consumption and execution times for real-time tasks on embedded heterogeneous architecturesACM SIGBED Review10.1145/3373400.337340816:3(51-56)Online publication date: 25-Nov-2019
https://dl.acm.org/doi/10.1145/3373400.3373408
Li K(2016)Energy and time constrained task scheduling on multiprocessor computers with discrete speed levelsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2016.02.00695:C(15-28)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.1016/j.jpdc.2016.02.006
Tang ZQi LCheng ZLi KKhan SLi K(2016)An Energy-Efficient Task Scheduling Algorithm in DVFS-enabled Cloud EnvironmentJournal of Grid Computing10.1007/s10723-015-9334-y14:1(55-74)Online publication date: 1-Mar-2016
https://dl.acm.org/doi/10.1007/s10723-015-9334-y
Zhang LLi KXu YMei JZhang FLi K(2015)Maximizing reliability with energy conservation for parallel task scheduling in a heterogeneous clusterInformation Sciences: an International Journal10.5555/2794084.2794133319:C(113-131)Online publication date: 20-Oct-2015
https://dl.acm.org/doi/10.5555/2794084.2794133
Kuo CLu Y(2015)Task assignment with energy efficiency considerations for non-DVS heterogeneous multiprocessor systemsACM SIGAPP Applied Computing Review10.1145/2724928.272492914:4(8-18)Online publication date: 22-Jan-2015
https://dl.acm.org/doi/10.1145/2724928.2724929
Zheng WHuang S(2015)An adaptive deadline constrained energy-efficient scheduling heuristic for workflows in cloudsConcurrency and Computation: Practice & Experience10.1002/cpe.359227:18(5590-5605)Online publication date: 25-Dec-2015
https://dl.acm.org/doi/10.1002/cpe.3592
Zhang YGuo R(2014)Power-aware fixed priority scheduling for sporadic tasks in hard real-time systemsJournal of Systems and Software10.5555/2747013.274713690:C(128-137)Online publication date: 1-Apr-2014
https://dl.acm.org/doi/10.5555/2747013.2747136
Tian YLin CLi K(2014)Managing performance and power consumption tradeoff for multiple heterogeneous servers in cloud computingCluster Computing10.1007/s10586-013-0326-z17:3(943-955)Online publication date: 1-Sep-2014
https://dl.acm.org/doi/10.1007/s10586-013-0326-z
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents