Online strategies for dynamic power management in systems with multiple power-saving states

ABSTRACT

Online dynamic power management (DPM) strategies refer to strategies that attempt to make power-mode-related decisions based on information available at runtime. In making such decisions, these strategies do not depend upon information of future behavior of the system, or any a priori knowledge of the input characteristics. In this paper, we present online strategies, and evaluate them based on a measure called the competitive ratio that enables a quantitative analysis of the performance of online strategies. All earlier approaches (online or predictive) have been limited to systems with two power-saving states (e.g., idle and shutdown). The only earlier approaches that handled multiple power-saving states were based on stochastic optimization. This paper provides a theoretical basis for the analysis of DPM strategies for systems with multiple power-down states, without resorting to such complex approaches. We show how a relatively simple "online learning" scheme can be used to improve the competitive ratio over deterministic strategies using the notion of "probability-based" online DPM strategies. Experimental results show that the algorithm presented here attains the best competitive ratio in comparison with other known predictive DPM algorithms. The other algorithms that come close to matching its performance in power suffer at least an additional 40% wake-up latency on average. Meanwhile, the algorithms that have comparable latency to our methods use at least 25% more power on average.

REFERENCES

• 1: Luca Benini , Alessandro Bogliolo , Giovanni De Micheli, A survey of design techniques for system-level dynamic power management, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.8 n.3, p.299-316, June 2000 [doi>10.1109/92.845896]
• 2: Benini, L., Bogliolo, A., Paleologo, G., and De Micheli, G. 1999. Policy optimization for dynamic power management. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 18, 6, 813--833.
• 3: Luca Benini , Giovanni de Micheli, Dynamic Power Management: Design Techniques and CAD Tools, Kluwer Academic Publishers, Norwell, MA, 1998
• 4: Benini, L., De Micheli, G., and Macii, E. 2001. Designing low-power circuits: Practical recipes. IEEE Circuits and Systems Magazine 1, 1 (March), 6--25.
• 5: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 6: Eui-Young Chung , Luca Benini , Alessandro Bogiolo , Giovanni De Micheli, Dynamic power management for non-stationary service requests, Proceedings of the conference on Design, automation and test in Europe, p.18-es, January 1999, Munich, Germany [doi>10.1145/307418.307456]
• 7: Eui-Young Chung , Luca Benini , Giovanni De Micheli, Dynamic power management using adaptive learning tree, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.274-279, November 07-11, 1999, San Jose, California, United States
• 8: Tajana Simunic , Luca Benini , Peter Glynn , Giovanni De Micheli, Dynamic power management for portable systems, Proceedings of the 6th annual international conference on Mobile computing and networking, p.11-19, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345914]
• 9: Chi-Hong Hwang , Allen C.-H. Wu, A predictive system shutdown method for energy saving of event-driven computation, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.28-32, November 09-13, 1997, San Jose, California, United States
• 10: IBM. 1996. Technical Specifications of Hard Drive IBM Travelstar VP 2.5 inch. Available at, http://www.storage.ibm.com/storage/oem/data/travvp.htm.
• 11: S. Irani , R. Gupta , S. Shukla, Competitive Analysis of Dynamic Power Management Strategies for Systems with Multiple Power Savings States, Proceedings of the conference on Design, automation and test in Europe, p.117, March 04-08, 2002
• 12: Anna R. Karlin , Mark S. Manasse , Lyle A. McGeoch , Susan Owicki, Competitive randomized algorithms for non-uniform problems, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.301-309, January 22-24, 1990, San Francisco, California, United States
• 13: Keshav, S., Lund, C., Philliips, S., Reaingold, N., and Saran, H. 1995. An empirical evaluation of virtual circuit holding time policies in ip-over-atm networks. IEEE Journal on Selected Areas in Communications 13, 1371--1382.
• 14: Yung-Hsiang Lu , Eui-Young Chung , Tajana Šimunić , Luca Benini , Giovanni De Micheli, Quantitative comparison of power management algorithms, Proceedings of the conference on Design, automation and test in Europe, p.20-26, March 27-30, 2000, Paris, France [doi>10.1145/343647.343688]
• 15: Yung-Hsiang Lu , Giovanni de Micheli, Adaptive Hard Disk Power Management on Personal Computers, Proceedings of the Ninth Great Lakes Symposium on VLSI, p.50, March 04-06, 1999
• 16: Phillips, S. J. and Westbrook, J. R. 1999. On-line algorithms: Competitive analysis and beyond. In Algorithms and Theory of Computation Handbook. CRC Press, Boca Raton, Fl.
• 17: Qinru Qiu , Massoud Pedram, Dynamic power management based on continuous-time Markov decision processes, Proceedings of the 36th ACM/IEEE conference on Design automation, p.555-561, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309997]
• 18: Qinru Qiu , Qing Wu , Massoud Pedram, Stochastic modeling of a power-managed system: construction and optimization, Proceedings of the 1999 international symposium on Low power electronics and design, p.194-199, August 16-17, 1999, San Diego, California, United States [doi>10.1145/313817.313923]
• 19: Qinru Qiu , Qing Wu , Massoud Pedram, Dynamic power management of complex systems using generalized stochastic Petri nets, Proceedings of the 37th conference on Design automation, p.352-356, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337438]
• 20: Dinesh Ramanathan , Rajesh Gupta, High-level timing and power analysis of embedded systems, 2000
• 21: Dinesh Ramanathan , Sandy Irani , Rajesh Gupta, Latency effects of system level power management algorithms, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 22: Ramanathan, D., Irani, S., and Gupta, R. 2002. An analysis of system level power management algorithms and their effects on latency. IEEE Transactions on Computer Aided Design 21, (March) 3.
• 23: Sandeep K. Shukla , Rajesh K. Gupta, A Model Checking Approach to Evaluating System Level Dynamic Power Management Policies for Embedded Systems, Proceedings of the Sixth IEEE International High-Level Design Validation and Test Workshop (HLDVT'01), p.53, December 07-09, 2001
• 24: Tajana Simunic , Giovanni de Micheli , Luca Benini, Event-Driven Power Management of Portable Systems, Proceedings of the 12th international symposium on System synthesis, p.18, November 01-04, 1999
• 25: Mani B. Srivastava , Anantha P. Chandrakasan , R. W. Brodersen, Predictive system shutdown and other architectural techniques for energy efficient programmable computation, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.4 n.1, p.42-55, March 1996 [doi>10.1109/92.486080]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

Additional Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.3 Microcomputers
          Subjects: Portable devices (e.g., laptops, personal digital assistants)

General Terms:
Algorithms, Performance

Keywords:
Dynamic, online algorithms, power management