Home | Legals | Sitemap | KIT

Algorithm Design and Analysis for Power Management

Algorithm Design and Analysis for Power Management
type: Vorlesung (V)
semester: SS 2012
place:

50.34 Raum -107

time:

Tuesdays 14:00-15:30 (weekly)

lecturer: Prof. Dr. Jian-Jia Chen
sws: 2
ects: 3
lv-no.: 24621
exam: Oral Exam

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

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

Prerequisite: Computer Operating Systems and Algorithms 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.

Scehdule:

Date Topic  Slides/handout
24.04.2012 0. Organization and Introduction  slides
01.05.2012 break (Labour Day)
 
08.05.2012 1. Offline 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
 slides
15.05.2012 2. Offline Dynamic Power Management (DPM) - Approximation    

Sandy Irani, Sandeep K. Shukla, Rajesh Gupta: Algorithms for power savings. ACM Transactions on Algorithms 3(4): (2007)   [Algorithm left-to-right with DPM only]

Pi-Cheng Hsiu, Chun-Han Lin, Cheng-Kang Hsieh: Dynamic backlight scaling optimization for mobile streaming applications. ISLPED 2011: 309-314

slides

exercise

22.05.2012

3. 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

slides

 
29.05.2012 4. 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

slides

 
05.06.2012 5. 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)
slides 
12.06.2012 6. Joint Schedule by DVFS and DPM

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

slides 
19.06.2012 7. 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
 slides 
26.06.2012 No lecture (conference trip)  
03.07.2012

8. 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
 slides
10.07.2012 9. 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
 slides
17.07.2012 break due to requests (move to 24. 07)  
24.07.2012

Important: This week has two consecutive sessions 14:00 to 15:30 and 15:45 to 17:15 at Building 40.28 room 001.

10. 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.

11. 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

12. Concluding and Open Problem

 slides

 slides

 slides