Home | Legals | Sitemap | KIT

Algorithm Design and Analysis for Power Management

Algorithm Design and Analysis for Power Management
type: lecture
chair: Chair of Micro Hardware Technologies for Automation
semester: >=5

Room 001, Building 40.28


Tuesday 09:45-11:15, weekly

start: 19.04.2011

Juniorprofessor Dr. Jian-Jia Chen

sws: 2
ects: 3
lv-no.: lv24621


Power management has quickly become one of the focal points in modern computing systems. One one hand, computing systems would like to keep high performance; on the other hand, energy consumption should be under control. The advent of battery-powered embedded computing and mobile, ad-hoc and sensor networks increases the scope and significance of power management.

In this course, we will cover the state-of-the-art studies in algorithmic design and analysis in computing systems. Advanced algorithmic topics, such as approximation algorithms and on-line competitive analysis, for power management will be introduced in this course. Algorithmic design and analysis for the following topics for will be covered in this course:

  • Dynamic voltage frequency scaling (DVFS)
  • Dynamic power management (DPM)
  • Thermal (temperature) management
  • Flow control and power management
  • Power management with batteries and energy harvesting devices
  • Energy pricing and power management in servers
  • Power management in wireless sensor networks


The course is particularly suitable for PhD students and advanced MS students interested in hot research issues in the general Systems and Algorithms area.

Prerequisite: Computer Operating Systems or equivalent. A basic background in algorithm design and analysis, data structures, and discrete math is strongly recommended and will be assumed.

Course material: There is no textbook for this course. The course will be based on state-of-the-art research results. The reading material and slides will be available in VAB system.


Date Topic  Slides/handout
 19.04.2011  0. Organization and Introduction Slides
 26.04.2011  1. Optimal Dynamic Power Management (DPM)
Philippe Baptiste, Marek Chrobak, Christoph Dürr: Polynomial Time Algorithms for Minimum Energy Scheduling. ESA 2007: 136-150

Philippe Baptiste: Scheduling unit tasks to minimize the number of idle periods: a polynomial time algorithm for offline dynamic power management. SODA 2006: 364-367


(updated at 29/04/11)

 03.05.2011  2. On-Line Dynamic Power Management (DPM)

John Augustine, Sandy Irani, Chaitanya Swamy: Optimal Power-Down Strategies. SIAM J. Comput. 37(5): 1499-1516 (2008) (conference: FOCS 2004: 530-539)

Anna R. Karlin, Mark S. Manasse, Lyle A. McGeoch, Susan S. Owicki: Competitive Randomized Algorithms for Non-Uniform Problems. SODA 1990: 301-309


(updated at 03/05/11 13:00)

 10.05.2011  3. Offline Dynamic Voltage/Frequency Scaling (DVFS)

F. Frances Yao, Alan J. Demers, Scott Shenker: A Scheduling Model for Reduced CPU Energy. FOCS 1995: 374-382

Minming Li, F. Frances Yao: An Efficient Algorithm for Computing Optimal Discrete Voltage Schedules. SIAM J. Comput. 35(3): 658-671 (2005)

Hakan Aydin, Rami G. Melhem, Daniel Mossé, Pedro Mejía-Alvarez: Determining Optimal Processor Speeds for Periodic Real-Time Tasks with Different Power Characteristics. ECRTS 2001: 225-23


(updated at 16/05/11 19:00)


 17.05.2011   4. Online Dynamic Voltage/Frequency Scaling (DVFS)

F. Frances Yao, Alan J. Demers, Scott Shenker: A Scheduling Model for Reduced CPU Energy. FOCS 1995: 374-382

Nikhil Bansal, Ho-Leung Chan, Kirk Pruhs, Dmitriy Katz: Improved Bounds for Speed Scaling in Devices Obeying the Cube-Root Rule. ICALP (1) 2009: 144-155

Nikhil Bansal, Tracy Kimbrel, Kirk Pruhs: Speed scaling to manage energy and temperature. J. ACM 54(1): (2007)


(updated at 23/05/11 21:00)


 5. Joint Schedule by DVFS and DPM

Sandy Irani, Sandeep K. Shukla, Rajesh Gupta: Algorithms for power savings. ACM Transactions on Algorithms 3(4): (2007)



(updated at 23/05/11 21:00)

 31.05.2011  6. DVFS with  Probabilistic Execution Time

Jian-Jia Chen, Lothar Thiele: Expected system energy consumption minimization in leakage-aware DVS systems. ISLPED 2008: 315-320

Ruibin Xu, Daniel Mossé, Rami G. Melhem: Minimizing expected energy in real-time embedded systems. EMSOFT 2005: 251-254

Yan Zhang, Zhijian Lu, John Lach, Kevin Skadron, Mircea R. Stan: Optimal procrastinating voltage scheduling for hard real-time systems. DAC 2005: 905-908

Wanghong Yuan, Klara Nahrstedt: Energy-efficient soft real-time CPU scheduling for mobile multimedia systems. SOSP 2003: 149-163


(updated at 31/05/11 13:00)

 07.06.2011  7. Multiprocessor Energy Minimization

Jian-Jia Chen, Lothar Thiele: Energy-efficient scheduling on homogeneous multiprocessor platforms. SAC 2010: 542-549

Jian-Jia Chen, Lothar Thiele: Task Partitioning and Platform Synthesis for Energy Efficiency. RTCSA 2009: 393-402

Chuan-Yue Yang, Jian-Jia Chen, Tei-Wei Kuo: An Approximation Algorithm for Energy-Efficient Scheduling on A Chip Multiprocessor. DATE 2005: 468-473


(updated at 14/06/11 13:00)

 14.06.2011  8. Temperature-Awareness

Nikhil Bansal, Tracy Kimbrel, Kirk Pruhs: Speed scaling to manage energy and temperature. J. ACM 54(1): (2007)

Devendra Rai, Hoeseok Yang, Iuliana Bacivarov, Jian-Jia Chen, Lothar Thiele: Worst-Case  Temperature Analysis for Real-Time Systems. DATE, 2011.


(updated at 14/006/11 13:00)


Slides for Multicore

(updated at 29/06 2011)

 21.06.2011  no lecture (conference trip)  

 9. Power Management for Servers and Flow Control

Shengquan Wang, Jian-Jia Chen, Jun Liu, Xue Liu: Power Saving Design for Servers under Response Time Constraint. ECRTS 2010: 123-132

David Meisner, Brian T. Gold, Thomas F. Wenisch: The PowerNap Server Architecture. ACM Trans. Comput. Syst. 29(1): 3 (2011)

 Kirk Pruhs, Patchrawat Uthaisombut, Gerhard J. Woeginger: Getting the Best Response for Your Erg. SWAT 2004: 14-25


(updated at 29/06 2011)


 10. Energy Harvesting and Energy Pricing

Nikhil Bansal, Ho-Leung Chan, Kirk Pruhs: Speed Scaling with a Solar Cell. AAIM 2008: 15-26

Clemens Moser, Davide Brunelli, Lothar Thiele, Luca Benini: Real-time scheduling for energy harvesting sensor nodes. Real-Time Systems 37(3): 233-260 (2007)

Clemens Moser, Jian-Jia Chen, Lothar Thiele: An energy management framework for energy harvesting embedded systems. JETC  6(2): (2010)

 Amotz Bar-Noy, Matthew P. Johnson, Ou Liu: Peak Shaving  through Resource Buffering. WAOA 2008: 147-159

(not included due to limited time) Kirk Pruhs, Clifford Stein: How to Schedule When You Have to Buy Your Energy. APPROX-RANDOM 2010: 352-365



(updated at 04/07 2011)


11. Concluding and Open Problems


11. Energy Management for Networking

Guoliang Xing, Chenyang Lu, Ying Zhang, Qingfeng Huang, Robert Pless:
Minimum power configuration in wireless sensor networks. MobiHoc 2005: 390-401

Peter Sanders, Dennis Schieferdecker:
Lifetime Maximization of Monitoring Sensor Networks. ALGOSENSORS 2010: 134-147

Zoë Abrams, Ashish Goel, Serge A. Plotkin:
Set k-cover algorithms for energy efficient monitoring in wireless sensor networks. IPSN 2004: 424-432


(updated at 12/07 2011)



12. Students' Presentations about Power Management

 12. Concluding and Open Problems

slides are not publically available