Algorithmic problems in power management

ABSTRACT

We survey recent research that has appeared in the theoretical computer science literature on algorithmic problems related to power management. We will try to highlight some open problem that we feel are interesting. This survey places more concentration on lines of research of the authors: managing power using the techniques of speed scaling and power-down which are also currently the dominant techniques in practice.

REFERENCES

• 1: http://www-bsac.eecs.berkeley.edu/archive/users/warneke-brett/SmartDust/.
• 2: http://www.microsoft.com/windows2000/techenthusiast/features/standby 1127.asp.
• 3: http://www2.parc.com/spl/projects/cosense/csp/ slides/Srivastava.pdf.
• 4: http://www.rockwellscientific.com/hidra/.
• 5: J. Augustine, S. Irani, K. Pruhs, and P. Uthaisombut. unpublished manuscript.
• 6: John Augustine , Sandy Irani , Chaitanya Swamy, Optimal Power-Down Strategies, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.530-539, October 17-19, 2004 [doi>10.1109/FOCS.2004.50]
• 7: Nikhil Bansal , Tracy Kimbrel , Kirk Pruhs, Dynamic Speed Scaling to Manage Energy and Temperature, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.520-529, October 17-19, 2004 [doi>10.1109/FOCS.2004.24]
• 8: N. Bansal and K. Pruhs. Speed scaling to manage temperature. In Symposium on Theoretical Aspects of Computer Science, 2005.
• 9: Shekhar Borkar, Design Challenges of Technology Scaling, IEEE Micro, v.19 n.4, p.23-29, July 1999 [doi>10.1109/40.782564 ]
• 10: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 11: David M. Brooks , Pradip Bose , Stanley E. Schuster , Hans Jacobson , Prabhakar N. Kudva , Alper Buyuktosunoglu , John-David Wellman , Victor Zyuban , Manish Gupta , Peter W. Cook, Power-Aware Microarchitecture: Design and Modeling Challenges for Next-Generation Microprocessors, IEEE Micro, v.20 n.6, p.26-44, November 2000 [doi>10.1109/40.888701 ]
• 12: Giorgio C. Buttazzo , Giorgio Buttanzo, Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications, Kluwer Academic Publishers, Norwell, MA, 1997
• 13: Anantha Chandrakasan, Rex Min, Manish Bhardwaj, Seong-Hwan Cho, and Alice Wang. Power aware wireless microsensor systems. In European Solid-State Circuits Conference, 2002.
• 14: Carla Schlatter Ellis, The Case for Higher-Level Power Management, Proceedings of the The Seventh Workshop on Hot Topics in Operating Systems, p.162, March 28-30, 1999
• 15: C. Guo, L. C. Zhong, and J. M. Rabaey. Low power distributed mac for ad hoc sensor radio networks. In Proceedings of IEEE GlobeCom, 2001.
• 16: Sandy Irani , Sandeep Shukla , Rajesh Gupta, Algorithms for power savings, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 17: 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
• 18: Sandy Irani , Anna R. Karlin, Online computation, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 19: Sandy Irani , Sandeep Shukla , Rajesh Gupta, Online strategies for dynamic power management in systems with multiple power-saving states, ACM Transactions on Embedded Computing Systems (TECS), v.2 n.3, p.325-346, August 2003 [doi>10.1145/860176.860180]
• 20: Ravindra Jejurikar , Rajesh Gupta, Procrastination scheduling in fixed priority real-time systems, Proceedings of the 2004 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 11-13, 2004, Washington, DC, USA
• 21: R. Jejurikar, C. Pereira, and R. Gupta. Leakage aware energy efficient task scheduling in embedded real-time systems. In Proceedings of the Design Automation Conference, 2004.
• 22: J. M. Kahn , R. H. Katz , K. S. J. Pister, Next century challenges: mobile networking for “Smart Dust”, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.271-278, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313558]
• 23: Bala Kalyanasundaram , Kirk Pruhs, Speed is as powerful as clairvoyance, Journal of the ACM (JACM), v.47 n.4, p.617-643, July 2000 [doi>10.1145/347476.347479]
• 24: 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
• 25: Woo-Cheol Kwon , Taewhan Kim, Optimal voltage allocation techniques for dynamically variable voltage processors, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775867]
• 26: Minming Li, Becky Jie Liu, and Frances F. Yao. Min-energy voltage allocation for tree-structured tasks. In International Computing and Combinatorics Conference, 2005.
• 27: John Markov. http://www.iht.com/articles/520233.html.
• 28: Trevor Mudge, Power: A First-Class Architectural Design Constraint, Computer, v.34 n.4, p.52-58, April 2001 [doi>10.1109/2.917539 ]
• 29: Kirk Pruhs, Jiri Sgall, and Eric Torng. Online scheduling. In Handbook on Scheduling. CRC Press, 2004.
• 30: Kirk Pruhs, Patchrawat Uthaisombut, and Gerhard Woeginger. Getting the best response for your erg. In Scandanavian Workshop on Algorithms and Theory, 2004.
• 31: 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
• 32: D. Ramanathan, S. Irani, and R. Gupta. An Analysis of System Level Power Management Algorithms and their effects on Latency. IEEE Trans. on Computer Aided Design, 21(3), march 2002.
• 33: Jerry E. Sergent and Al Krum. Thermal Management Handbook. McGraw-Hill, 1998.
• 34: Kevin Skadron , Mircea R. Stan , Wei Huang , Sivakumar Velusamy , Karthik Sankaranarayanan , David Tarjan, Temperature-aware microarchitecture, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 35: Donald R. Smith. Variational Methods in Optimization. Prentice-Hall, 1974.
• 36: Vivek Tiwari , Deo Singh , Suresh Rajgopal , Gaurav Mehta , Rakesh Patel , Franklin Baez, Reducing power in high-performance microprocessors, Proceedings of the 35th annual conference on Design automation, p.732-737, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277227]
• 37: F. Yao , A. Demers , S. Shenker, A scheduling model for reduced CPU energy, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.374, October 23-25, 1995
• 38: Wei Ye, John Heidemann, and Deborah Estrin. An energy-efficient mac protocol for wireless sensor networks. In Proceedings 21st International Annual Joint Conference of the IEEE Computer and Communications Societies, 2002.
• 39: Han-Saem Yun , Jihong Kim, On energy-optimal voltage scheduling for fixed-priority hard real-time systems, ACM Transactions on Embedded Computing Systems (TECS), v.2 n.3, p.393-430, August 2003 [doi>10.1145/860176.860183]
• 40: Technical specifications of hard drive IBM Travelstar VP 2.5inch, available at. http://www.storage.ibm.com/storage/oem/data/travvp.htm, 1996.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

General Terms:
Algorithms, Design