The design, implementation, and evaluation of a compiler algorithm for CPU energy reduction

ABSTRACT

This paper presents the design and implementation of a compiler algorithm that effectively optimizes programs for energy usage using dynamic voltage scaling (DVS). The algorithm identifies program regions where the CPU can be slowed down with negligible performance loss. It is implemented as a source-to-source level transformation using the SUIF2 compiler infrastructure. Physical measurements on a high-performance laptop show that total system (i.e., laptop) energy savings of up to 28% can be achieved with performance degradation of less than 5% for the SPECfp95 benchmarks. On average, the system energy and energy-delay product are reduced by 11% and 9%, respectively, with a performance slowdown of 2%. It was also discovered that the energy usage of the programs using our DVS algorithm is within 6% from the theoretical lower bound. To the best of our knowledge, this is one of the first work that evaluates DVS algorithms by physical measurements.

REFERENCES

• 1: N. AbouGhazaleh, D. Mossé, B. Childers, and R. Melhem. Toward the placement of power management points in real time applications. In Proceedings of the Workshop on Compilers and Operating Systems for Low Power, September 2001.
• 2: Advanced Micro Devices, Inc. Mobile AMD athlon 4 processor model 6 CPGA data sheet. Publication 24319, November 2001.
• 3: A. Azevedo , I. Issenin , R. Cornea , R. Gupta , N. Dutt , A. Veidenbaum , A. Nicolau, Profile-Based Dynamic Voltage Scheduling Using Program Checkpoints, Proceedings of the conference on Design, automation and test in Europe, p.168, March 04-08, 2002
• 4: D. Bailey. 21st century high-end computing. In Invited Talk, Applications, Algorithms, and Architectures Workshop for BlueGene/L, August 2002.
• 5: Frank Bellosa, The benefits of event: driven energy accounting in power-sensitive systems, Proceedings of the 9th workshop on ACM SIGOPS European workshop: beyond the PC: new challenges for the operating system, September 17-20, 2000, Kolding, Denmark [doi>10.1145/566726.566736]
• 6: Shekhar Borkar, Design Challenges of Technology Scaling, IEEE Micro, v.19 n.4, p.23-29, July 1999 [doi>10.1109/40.782564]
• 7: 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
• 8: T. D. Burd , R. W. Brodersen, Energy efficient CMOS microprocessor design, Proceedings of the 28th Hawaii International Conference on System Sciences (HICSS'95), p.288, January 04-07, 1995
• 9: Douglas Christopher Burger , James Richard Goodman, Hardware techniques to improve the performance of the processor/memory interface, 1998
• 10: Lama H. Chandrasena , Michael J. Liebelt, A rate selection algorithm for quantized undithered dynamic supply voltage scaling (poster session), Proceedings of the 2000 international symposium on Low power electronics and design, p.213-215, July 25-27, 2000, Rapallo, Italy [doi>10.1145/344166.344591]
• 11: Transmeta Corporation. http://www.transmeta.com.
• 12: Krisztián Flautner , Trevor Mudge, Vertigo: automatic performance-setting for Linux, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060300]
• 13: Krisztián Flautner , Steve Reinhardt , Trevor Mudge, Automatic performance setting for dynamic voltage scaling, Proceedings of the 7th annual international conference on Mobile computing and networking, p.260-271, July 2001, Rome, Italy [doi>10.1145/381677.381702]
• 14: R. Gonzalez and M. Horowitz. Energy dissipation in general purpose microprocessors. IEEE Journal of Solid-State Circuits, 31(9):1277--1284, September 1996.
• 15: D. Grunwald, P. Levis, K. Farkas, C. Morrey III, and M. Neufeld. Policies for dynamic clock scheduling. In Proceedings of the 4th Symposium on Operating System Design and Implementation, October 2000.
• 16: C.-H. Hsu and U. Kremer. Dynamic voltage and frequency scaling for scientific applications. In Proceedings of the 14th annual workshop on Languages and Compilers for Parallel Computing, August 2001.
• 17: C.-H. Hsu and U. Kremer. Compiler-directed dynamic voltage scaling for memory-bound applications. Technical Report DCS-TR-498, Department of Computer Science, Rutgers University, August 2002.
• 18: C.-H. Hsu and U. Kremer. Single region vs. multiple regions: A comparison of different compiler-directed dynamic voltage scheduling approaches. In Workshop on Power-Aware Computer Systems, 2002.
• 19: Chung-Hsing Hsu , Ulrich Kremer , Michael Hsiao, Compiler-Directed Dynamic Frequency and Voltage Scheduling, Proceedings of the First International Workshop on Power-Aware Computer Systems-Revised Papers, p.65-81, November 12, 2000
• 20: Chung-Hsing Hsu , Ulrich Kremer , Michael Hsiao, Compiler-directed dynamic voltage/frequency scheduling for energy reduction in mircoprocessors, Proceedings of the 2001 international symposium on Low power electronics and design, p.275-278, August 2001, Huntington Beach, California, United States [doi>10.1145/383082.383165]
• 21: 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]
• 22: S. Kim and A. Somani. Characterization of an extended multimedia benchmark on a general purpose microprocessor architecture. Technical Report DCNL-CA-2000-002, Electrical and Computer Engineering Department, Iowa State University, 2000.
• 23: Kanishka Lahiri , Sujit Dey , Debashis Panigrahi , Anand Raghunathan, Battery-Driven System Design: A New Frontier in Low Power Design, Proceedings of the 2002 conference on Asia South Pacific design automation/VLSI Design, p.261, January 07-11, 2002
• 24: Byeong Kil Lee , Lizy Kurian John, Implications of Programmable General Purpose Processors for Compression/Encryption Applications, Proceedings of the IEEE International Conference on Application-Specific Systems, Architectures, and Processors, p.233, July 17-19, 2002
• 25: Seongsoo Lee , Takayasu Sakurai, Run-time voltage hopping for low-power real-time systems, Proceedings of the 37th conference on Design automation, p.806-809, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337785]
• 26: 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
• 27: Zhijian Lu , Jason Hein , Marty Humphrey , Mircea Stan , John Lach , Kevin Skadron, Control-theoretic dynamic frequency and voltage scaling for multimedia workloads, Proceedings of the 2002 international conference on Compilers, architecture, and synthesis for embedded systems, October 08-11, 2002, Grenoble, France [doi>10.1145/581630.581654]
• 28: D. Marculescu. On the use of microarchitecture-driven dynamic voltage scaling. In Workshop on Complexity-Effective Design, June 2000.
• 29: Thomas L. Martin , Daniel P. Siewiorek, Nonideal battery and main memory effects on CPU speed-setting for low power, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.9 n.1, p.29-34, Feb. 2001 [doi>10.1109/92.920816]
• 30: Thomas L. Martin , Daniel P. Siewiorek, Balancing batteries, power, and performance: system issues in cpu speed-setting for mobile computing, 1999
• 31: K. Masahiro, K. Kazuo, H. Kazuo, and O. Eiichi. WT110/WT130 digital power meters. Yokogawa Technical Report 22, 1996.
• 32: 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]
• 33: D. Mossé, H. Aydin, B. Childers, and R. Melhem. Compiler-assisted dynamic power-aware scheduling for real-time applications. In Workshop on Compiler and Operating Systems for Low Power, October 2000.
• 34: Trevor Mudge, Power: A First-Class Architectural Design Constraint, Computer, v.34 n.4, p.52-58, April 2001 [doi>10.1109/2.917539]
• 35: Massoud Pedram , Qing Wu, Design considerations for battery-powered electronics, Proceedings of the 36th ACM/IEEE conference on Design automation, p.861-866, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.310089]
• 36: Trevor Pering , Tom Burd , Robert Brodersen, The simulation and evaluation of dynamic voltage scaling algorithms, Proceedings of the 1998 international symposium on Low power electronics and design, p.76-81, August 10-12, 1998, Monterey, California, United States [doi>10.1145/280756.280790]
• 37: 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
• 38: R. Rajamony and R. Bianchini. Energy management for server clusters. In Tutorial, 16th Annual ACM International Conference on Supercomputing, June 2002.
• 39: H. Saputra , M. Kandemir , N. Vijaykrishnan , M. J. Irwin , J. S. Hu , C-H. Hsu , U. Kremer, Energy-conscious compilation based on voltage scaling, Proceedings of the joint conference on Languages, compilers and tools for embedded systems: software and compilers for embedded systems, June 19-21, 2002, Berlin, Germany
• 40: Dongkun Shin , Jihong Kim, A profile-based energy-efficient intra-task voltage scheduling algorithm for real-time applications, Proceedings of the 2001 international symposium on Low power electronics and design, p.271-274, August 2001, Huntington Beach, California, United States [doi>10.1145/383082.383162]
• 41: Tajana Simunic , Luca Benini , Andrea Acquaviva , Peter Glynn , Giovanni De Micheli, Dynamic voltage scaling and power management for portable systems, Proceedings of the 38th conference on Design automation, p.524-529, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379016]
• 42: 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
• 43: Nathan T. Slingerland , Alan Jay Smith, Cache performance for multimedia applications, Proceedings of the 15th international conference on Supercomputing, p.204-217, June 2001, Sorrento, Italy [doi>10.1145/377792.377833]
• 44: Sohum Sohoni , Rui Min , Zhiyong Xu , Yiming Hu, A study of memory system performance of multimedia applications, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.206-215, June 2001, Cambridge, Massachusetts, United States
• 45: SUIF. Stanford University Intermediate Format.
• 46: RLX Technologies. Serverblade. http://www.rlxtechnologies.com.
• 47: Kees van den Doel , Paul G. Kry , Dinesh K. Pai, FoleyAutomatic: physically-based sound effects for interactive simulation and animation, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.537-544, August 2001 [doi>10.1145/383259.383322]
• 48: 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
• 49: 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
• 50: W. Ye , N. Vijaykrishnan , M. Kandemir , M. J. Irwin, The design and use of simplepower: a cycle-accurate energy estimation tool, Proceedings of the 37th conference on Design automation, p.340-345, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337436]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

General Terms:
Algorithms, Experimentation, Measurement, Performance

Keywords:
dynamic voltage scaling, energy savings