Energy optimal speed control of devices with discrete speed sets

ABSTRACT

We obtain analytically, the energy optimal speed profile of a generic multi-speed device with a discrete set of speeds, to execute a given task within a given time. Current implementations of energy efficient speed control policies (including DVFS) almost exclusively use the minimum feasible speed pair, which has been shown before to be suboptimal. Unlike previous works, ours does not require an explicit functional relationship between the device's power and speed (e.g. the CMOS power model), but only assumes that the power-speed relationship is a W-convex (a discrete equivalent of a convex) function. This assumption allowed us to show that the optimal speed profile uses at most two speeds, and that all the essential characteristics of the power-speed relationship can be encapsulated within a single speed, ω_u. The latter speed is intrinsic to the device (i.e. task independent) and can be readily computed from its power-speed values (without any curve fit). Further, ω_u is also the speed at which the the device consumes the least energy per unit work done. The problem formulation reduces to a linear program in the number of supported speeds, which in general, is difficult to solve analytically. However, the optimum solution has a very simple form - it is either ω_u, or the minimum feasible speed pair for the given task. We verified that a number of commercial DVFS processors, and other devices like disk drives satisfied our model of the W-convex power-speed relationship.

REFERENCES

• 1: Advanced Micro Devices. AMD Athlon 64 Processor Power and Thermal Data Sheet.
• 2: M. S. Bazaara, H. D. Sherali, and C. M. Shetty. Nonlinear Programming: Theory and Algorithms. John Wiley and Sons, second edition, 1993.
• 3: L. Benini, A. Bogliolo, G. A. Paleologo, and G. De Micheli. Policy optimization for dynamic power management. IEEE Trans. CAD, 18(6):813--833, June 1999.
• 4: Naehyuck Chang , Inseok Choi , Hojun Shim, DLS: dynamic backlight luminance scaling of liquid crystal display, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.8, p.837-846, August 2004 [doi>10.1109/TVLSI.2004.831472]
• 5: M. Fleischmann. Longrun power managementTM: Dynamic power management for CrusoeTM processors.
• 6: Sudhanva Gurumurthi , Anand Sivasubramaniam , Mahmut Kandemir , Hubertus Franke, Reducing Disk Power Consumption in Servers with DRPM, Computer, v.36 n.12, p.59-66, December 2003 [doi>10.1109/MC.2003.1250884]
• 7: Intel Corp. Enhanced Intel SpeedStep Technology for the Intel Pentium M Processor.
• 8: Intel Corp. Intel Pentium M Processor on 90nm Process with 2-MB L2 Cache.
• 9: Intel Corp. Intel PXA26x Processor Family : Electrical, Mechanical, and Thermal Specification.
• 10: 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
• 11: 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]
• 12: Tohru Ishihara , Hiroto Yasuura, Voltage scheduling problem for dynamically variable voltage processors, Proceedings of the 1998 international symposium on Low power electronics and design, p.197-202, August 10-12, 1998, Monterey, California, United States [doi>10.1145/280756.280894]
• 13: Ravindra Jejurikar , Cristiano Pereira , Rajesh Gupta, Leakage aware dynamic voltage scaling for real-time embedded systems, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996650]
• 14: PACE: A New Approach to Dynamic Voltage Scaling, IEEE Transactions on Computers, v.53 n.7, p.856-869, July 2004 [doi>10.1109/TC.2004.35]
• 15: Steven M. Martin , Krisztian Flautner , Trevor Mudge , David Blaauw, Combined dynamic voltage scaling and adaptive body biasing for lower power microprocessors under dynamic workloads, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.721-725, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774678]
• 16: Akihiko Miyoshi , Charles Lefurgy , Eric Van Hensbergen , Ram Rajamony , Raj Rajkumar, Critical power slope: understanding the runtime effects of frequency scaling, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA [doi>10.1145/514191.514200]
• 17: K. Okada, N. Kojima, and K. Yamashita. A novel drive architecture of HDD: "multimode hard disc drive". In Proc. Intl' Conf. Consumer Electroncis (ICCE), pages 92--93. IEEE Press, 2000.
• 18: Johan Pouwelse , Koen Langendoen , Henk J. Sips, Application-directed voltage scaling, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.11 n.5, p.812-826, October 2003 [doi>10.1109/TVLSI.2003.814324]
• 19: Q. Qiu, Q. Wu, and M. Pedram. Stochastic modeling of a power-managed system-construction and optimization. IEEE Trans. CAD, 20(10):1200--1217, October 2001.
• 20: R. Rao. Energy optimal speed control for components of portable systems. Master's thesis, University of Arizona, Tucson, 2004.
• 21: R. Rao , S. Vrudhula, Energy optimization for a two-device data flow chain, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.268-274, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382585]
• 22: Ravishankar Rao , Sarma Vrudhula , Musaravakkam S. Krishnan, Disk drive energy optimization for audio-video applications, Proceedings of the 2004 international conference on Compilers, architecture, and synthesis for embedded systems, September 22-25, 2004, Washington DC, USA [doi>10.1145/1023833.1023848]
• 23: Curt Schurgers , Olivier Aberthorne , Mani Srivastava, Modulation scaling for Energy Aware Communication Systems, Proceedings of the 2001 international symposium on Low power electronics and design, p.96-99, August 2001, Huntington Beach, California, United States [doi>10.1145/383082.383103]
• 24: M. Weiser, B. Welch, A. Demers, and S. Shenker. Scheduling for reduced CPU energy. In Proc. Symp. Operating Sys. Design and Implementation (OSDI), pages 13--23, 1994.

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability

General Terms:
Algorithms, Experimentation, Performance, Theory

Keywords:
convex, energy optimization, frequency scaling, functions, low-power, speed control, voltage scaling