Bounds on power savings using runtime dynamic voltage scaling: an exact algorithm and a linear-time heuristic approximation

ABSTRACT

Dynamic voltage/frequency scaling (DVFS) has been shown to be an efficient power/energy reduction technique. Various runtime DVFS policies have been proposed to utilize runtime DVFS opportunities. However, it is hard to know if runtime DVFS opportunities have been fully exploited by a DVFS policy without knowing the upper bounds of possible energy savings. We propose an exact but exponential algorithm to determine the upper bound of energy savings. The algorithm takes into consideration the switching costs, discrete voltage/frequency voltage levels and different program states. We then show a fast linear time heuristic can provide a very close approximate to this bound

REFERENCES

• 1: David Brooks , Vivek Tiwari , Margaret Martonosi, Wattch: a framework for architectural-level power analysis and optimizations, Proceedings of the 27th annual international symposium on Computer architecture, p.83-94, June 2000, Vancouver, British Columbia, Canada
• 2: Thomas D. Burd , Robert W. Brodersen, Design issues for dynamic voltage scaling, Proceedings of the 2000 international symposium on Low power electronics and design, p.9-14, July 25-27, 2000, Rapallo, Italy [doi>10.1145/344166.344181]
• 3: D. Burger, T. M. Austin, and S. Bennett. Evaluating future microprocessors: the SimpleScalar tool set. Tech. Report TR-1308, Univ. of Wisconsin-Madison Computer Sciences Dept., July 1996.
• 4: K. Choi, R. Soma, and M. Pedram. Fine-grained dynamic voltage and frequency scaling for precise energy and performance tradeoff based on the ratio of off-chip access to on-chip computation times. pages 18--28, Jan 2005.
• 5: L. Clark. Circuit Design of XScale (tm) Microprocessors, 2001. In 2001 Symposium on VLSI Circuits, Short Course on Physical Design for Low-Power and High-Performance Microprocessor Circuits.
• 6: Intel Corp. Intel XScale (tm) Core Developer's Manual, 2003. http://developer.intel.com/design/intelxscale/.
• 7: 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]
• 8: Ravindra Jejurikar , Rajesh Gupta, Energy aware task scheduling with task synchronization for embedded real time systems, Proceedings of the 2002 international conference on Compilers, architecture, and synthesis for embedded systems, October 08-11, 2002, Grenoble, France [doi>10.1145/581630.581655]
• 9: Chunho Lee , Miodrag Potkonjak , William H. Mangione-Smith, MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.330-335, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 10: Jacob R. Lorch , Alan Jay Smith, Improving dynamic voltage scaling algorithms with PACE, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.50-61, June 2001, Cambridge, Massachusetts, United States
• 11: Padmanabhan Pillai , Kang G. Shin, Real-time dynamic voltage scaling for low-power embedded operating systems, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 12: Gang Qu, What is the limit of energy saving by dynamic voltage scaling?, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 13: Amit Sinha , Anantha P. Chandrakasan, Dynamic Voltage Scheduling Using Adaptive Filtering of Workload Traces, Proceedings of the The 14th International Conference on VLSI Design (VLSID '01), p.221, January 03-07, 2001
• 14: Transmeta Corporation. Crusoe processor documentation, 2002. http://www.transmeta.com.
• 15: M. Weiser, B. Welch, A. Demers, and S. Shenker. Scheduling for reduced CPU energy. In the 1st Symposuim on Operating Systems Design and Implementation (OSDI-94), pages 13--23, 1994.
• 16: Andreas Weissel , Frank Bellosa, Process cruise control: event-driven clock scaling for dynamic power management, Proceedings of the 2002 international conference on Compilers, architecture, and synthesis for embedded systems, October 08-11, 2002, Grenoble, France [doi>10.1145/581630.581668]
• 17: Fen Xie , Margaret Martonosi , Sharad Malik, Compile-time dynamic voltage scaling settings: opportunities and limits, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 18: 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

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis

General Terms:
Algorithms, Design

Keywords:
bounds on energy savings, dynamic voltage scaling, linear time, low power