Speed scaling to manage energy and temperature

ABSTRACT

Speed scaling is a power management technique that involves dynamically changing the speed of a processor. We study policies for setting the speed of the processor for both of the goals of minimizing the energy used and the maximum temperature attained. The theoretical study of speed scaling policies to manage energy was initiated in a seminal paper by Yao et al. [1995], and we adopt their setting. We assume that the power required to run at speed s is P(s) = s^α for some constant α > 1. We assume a collection of tasks, each with a release time, a deadline, and an arbitrary amount of work that must be done between the release time and the deadline. Yao et al. [1995] gave an offline greedy algorithm YDS to compute the minimum energy schedule. They further proposed two online algorithms Average Rate (AVR) and Optimal Available (OA), and showed that AVR is 2^{α − 1} α^α-competitive with respect to energy. We provide a tight α^α bound on the competitive ratio of OA with respect to energy.

We initiate the study of speed scaling to manage temperature. We assume that the environment has a fixed ambient temperature and that the device cools according to Newton's law of cooling. We observe that the maximum temperature can be approximated within a factor of two by the maximum energy used over any interval of length 1/b, where b is the cooling parameter of the device. We define a speed scaling policy to be cooling-oblivious if it is simultaneously constant-competitive with respect to temperature for all cooling parameters. We then observe that cooling-oblivious algorithms are also constant-competitive with respect to energy, maximum speed and maximum power. We show that YDS is a cooling-oblivious algorithm. In contrast, we show that the online algorithms OA and AVR are not cooling-oblivious. We then propose a new online algorithm that we call BKP. We show that BKP is cooling-oblivious. We further show that BKP is e-competitive with respect to the maximum speed, and that no deterministic online algorithm can have a better competitive ratio. BKP also has a lower competitive ratio for energy than OA for α ≥5.

Finally, we show that the optimal temperature schedule can be computed offline in polynomial-time using the Ellipsoid algorithm.

REFERENCES

• 1: Apple. 2005. Why apple chose intel. http://www.business2.com/b2/web/articles/0,17863,1084781,00.html.
• 2: 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]
• 3: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 4: 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]
• 5: Giorgio C. Buttazzo , Giorgio Buttanzo, Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications, Kluwer Academic Publishers, Norwell, MA, 1997
• 6: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 7: Crusoe. 2002. Crusoe tm550/tm5800 thermal design guide. http://crusoe.com/crusoe_docs/TM5800_ThermDesGuide_6-18-02.pdf.
• 8: 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
• 9: Gabriel, R. M. 1931. An additional proof of a maximal theorem of hardy and littlewood. J. London Math. Soc. 6, 163--166.
• 10: Hardy, G. H., and Littlewood, J. 1930. A maximal theorem with function-theoretic applications. Acta Math. 54, 81--116.
• 11: Hardy, G. H., Littlewood, J. E., and Polya, G. 1952. Inequalities. Cambridge University Press, Cambridge, MA.
• 12: 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
• 13: Sandy Irani , Kirk R. Pruhs, Algorithmic problems in power management, ACM SIGACT News, v.36 n.2, June 2005 [doi>10.1145/1067309.1067324]
• 14: 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]
• 15: Li, M., Liu, B. J., and Yao, F. F. 2006a. Min-energy voltage allocation for tree-structured tasks. J. Combin. Optim. 11, 3, 305--319.
• 16: Li, M., Yao, A. C., and Yao, F. F. 2006b. Discrete and continuous min-energy schedules for variable voltage processors. In Proceedings of the National Academy of Sciences USA. Vol. 103. 3983--3987.
• 17: Minming Li , Frances F. Yao, An Efficient Algorithm for Computing Optimal Discrete Voltage Schedules, SIAM Journal on Computing, v.35 n.3, p.658-671, 2005 [doi>10.1137/050629434]
• 18: Markoff, J. 2004. Intel's big shift after hitting technical wall, New York Times (May 17, 2004). http://www.nytimes.com/2004/05/17/business/17intel.html?ex=1400212800&en=482e58801aa02ede&ei=5007&partner=USERLAND.
• 19: Trevor Mudge, Power: A First-Class Architectural Design Constraint, Computer, v.34 n.4, p.52-58, April 2001 [doi>10.1109/2.917539]
• 20: Nestorov, Y. 2003. Introductory lectures on convex programming.
• 21: Sergent, J. E., and Krum, A. 1998. Thermal Management Handbook. McGraw-Hill, New York.
• 22: 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
• 23: Smith, D. R. 1974. Variational Methods in Optimization. Prentice-Hall, Englewood Cliffs, NJ.
• 24: 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]
• 25: 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
• 26: 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]

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Performance

Keywords:
Speed scaling, power management, voltage scaling