Compiler-directed high-level energy estimation and optimization

ABSTRACT

The demand for high-performance architectures and powerful battery-operated mobile devices has accentuated the need for power optimization. While many power-oriented hardware optimization techniques have been proposed and incorporated in current systems, the increasingly critical power constraints have made it essential to look for software-level optimizations as well. The compiler can play a pivotal role in addressing the power constraints of a system as it wields a significant influence on the application's runtime behavior. This paper presents a novel Energy-Aware Compilation (EAC) framework that estimates and optimizes energy consumption of a given code, taking as input the architectural and technological parameters, energy models, and energy/performance/code size constraints. The framework has been validated using a cycle-accurate architectural-level energy simulator and found to be within 6% error margin while providing significant estimation speedup. The estimation speed of EAC is the key to the number of optimization alternatives that can be explored within a reasonable compilation time. As shown in this paper, EAC allows compiler writers and system designers to investigate power-performance tradeoffs of traditional compiler optimizations and to develop energy-conscious high-level code transformations.

REFERENCES

• 1: David H. Albonesi, Selective cache ways: on-demand cache resource allocation, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.248-259, November 16-18, 1999, Haifa, Israel
• 2: Amirali Baniasadi , Andreas Moshovos, Asymmetric-frequency clustering: a power-aware back-end for high-performance processors, Proceedings of the 2002 international symposium on Low power electronics and design, August 12-14, 2002, Monterey, California, USA [doi>10.1145/566408.566474]
• 3: Luca Benini , Alessandro Bogliolo , Stefano Cavallucci , Bruno Riccó, Monitoring system activity for OS-directed dynamic power management, Proceedings of the 1998 international symposium on Low power electronics and design, p.185-190, August 10-12, 1998, Monterey, California, United States [doi>10.1145/280756.280887]
• 4: Luca Benini , Robin Hodgson , Polly Siegel, System-level power estimation and optimization, Proceedings of the 1998 international symposium on Low power electronics and design, p.173-178, August 10-12, 1998, Monterey, California, United States [doi>10.1145/280756.280881]
• 5: William Blume , Rudolf Eigenmann , Keith Faigin , John Grout , Jay Hoeflinger , David A. Padua , Paul Petersen , William M. Pottenger , Lawrence Rauchwerger , Peng Tu , Stephen Weatherford, Polaris: Improving the Effectiveness of Parallelizing Compilers, Proceedings of the 7th International Workshop on Languages and Compilers for Parallel Computing, p.141-154, August 08-10, 1994
• 6: Bodin, F., Chamski, Z., Eisenbeis, C., Rohou, E., and Seznec, A. 1998. Gcds: A compiler strategy for trading code size against performance in embedded applications. Tech. Rep. RR-3346, INRIA, Rocquencourt, France. Jan.
• 7: Shekhar Borkar, Design Challenges of Technology Scaling, IEEE Micro, v.19 n.4, p.23-29, July 1999 [doi>10.1109/40.782564]
• 8: 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
• 9: Burger, D., Austin, T., and Bennett, S. 1996. Evaluating future microprocessors: The simplescalar tool set. Tech. Rep. CS-TR-96-103, (July). Computer Science Dept., University of Wisconsin, Madison, WI.
• 10: J. Adam Butts , Gurindar S. Sohi, A static power model for architects, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.191-201, December 2000, Monterey, California, United States [doi>10.1145/360128.360148]
• 11: Francky Catthoor , Eddy de Greef , Sven Suytack, Custom Memory Management Methodology: Exploration of Memory Organisation for Embedded Multimedia System Design, Kluwer Academic Publishers, Norwell, MA, 1998
• 12: Anantha P. Chandrakasan , Robert W. Brodersen, Low Power Digital CMOS Design, Kluwer Academic Publishers, Norwell, MA, 1995
• 13: Anantha P. Chandrakasan , William J. Bowhill , Frank Fox, Design of High-Performance Microprocessor Circuits, Wiley-IEEE Press, 2000
• 14: G. Chen , B. Kang , M. Kandemir , N. Vijaykrishnan , M. J. Irwin , R. Chandramouli, Energy-Aware Compilation and Execution in Java-Enabled Mobile Devices, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.34.1, April 22-26, 2003
• 15: Rita Yu Chen , Mary Jane Irwin , Raminder S. Bajwa, Architecture-level power estimation and design experiments, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.6 n.1, p.50-66, Jan. 2001 [doi>10.1145/371254.371262]
• 16: Keith D. Cooper , Ken Kennedy , Nathaniel McIntosh, Cross-Loop Reuse Analysis and Its Application to Cache Optimizations, Proceedings of the 9th International Workshop on Languages and Compilers for Parallel Computing, p.1-19, August 08-10, 1996
• 17: and M. J. Irwin, DRAM Energy Management Using Sof ware and Hardware Directed Power Mode Control, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.159, January 20-24, 2001
• 18: David Duarte , Vijaykrishnan Narayanan , Mary Jane Irwin , Mahmut Kandemir, Formulation and Validation of an Energy Dissipation Model for the Clock Generation Circuitry and Distribution Networks, Proceedings of the The 14th International Conference on VLSI Design (VLSID '01), p.248, January 03-07, 2001
• 19: Krisztián Flautner , Nam Sung Kim , Steve Martin , David Blaauw , Trevor Mudge, Drowsy caches: simple techniques for reducing leakage power, Proceedings of the 29th annual international symposium on Computer architecture, p.148, May 25-29, 2002, Anchorage, Alaska
• 20: Catherine H. Gebotys, Low energy memory and register allocation using network flow, Proceedings of the 34th annual conference on Design automation, p.435-440, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266192]
• 21: Kanad Ghose , Milind B. Kamble, Reducing power in superscalar processor caches using subbanking, multiple line buffers and bit-line segmentation, Proceedings of the 1999 international symposium on Low power electronics and design, p.70-75, August 16-17, 1999, San Diego, California, United States [doi>10.1145/313817.313860]
• 22: Gonzales, R. and Horowitz, M. 1996. Energy dissipation in general purpose processors. IEEE Journal of Solid-State Circuits 31, 9 (Sept.), 1277--1283.
• 23: Rajiv Gupta , Santosh Pande , Kleanthis Psarris , Vivek Sarkar, Compilation techniques for parallel systems, Parallel Computing, v.25 n.13-14, p.1741-1783, Dec. 1999 [doi>10.1016/S0167-8191(99)00086-1]
• 24: Chung-Hsing Hsu , Ulrich Kremer, The design, implementation, and evaluation of a compiler algorithm for CPU energy reduction, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 25: Irwin, M. J. and Vijaykrishnan, N. 2000. Low power design: From soup to nuts. In Tutorial Notes, ISCA' 2000.
• 26: I. Kadayif , M. Kandemir , N. Vijaykrishnan , M. Irwin , A. Sivasubramaniam, EAC: A Compiler Framework for High-Level Energy Estimation and Optimization, Proceedings of the conference on Design, automation and test in Europe, p.436, March 04-08, 2002
• 27: Milind B. Kamble , Kanad Ghose, Analytical energy dissipation models for low-power caches, Proceedings of the 1997 international symposium on Low power electronics and design, p.143-148, August 18-20, 1997, Monterey, California, United States [doi>10.1145/263272.263310]
• 28: M. B. Kamble , K. Ghose, Energy-Efficiency of VLSI Caches: A Comparative Study, Proceedings of the Tenth International Conference on VLSI Design: VLSI in Multimedia Applications, p.261, January 04-07, 1997
• 29: Mahmut T. Kandemir , Narayanan Vijaykrishnan , Mary Jane Irwin , Hyun Suk Kim, Experimental Evaluation of Energy Behavior of Iteration Space Tiling, Proceedings of the 13th International Workshop on Languages and Compilers for Parallel Computing-Revised Papers, p.142-157, August 10-12, 2000
• 30: M. Kandemir , N. Vijaykrishnan , M. J. Irwin , W. Ye, Influence of compiler optimizations on system power, Proceedings of the 37th conference on Design automation, p.304-307, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337425]
• 31: Stefanos Kaxiras , Zhigang Hu , Margaret Martonosi, Cache decay: exploiting generational behavior to reduce cache leakage power, Proceedings of the 28th annual international symposium on Computer architecture, p.240-251, June 30-July 04, 2001, Göteborg, Sweden
• 32: M. Lam, Software pipelining: an effective scheduling technique for VLIW machines, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.318-328, June 20-24, 1988, Atlanta, Georgia, United States
• 33: Monica D. Lam , Edward E. Rothberg , Michael E. Wolf, The cache performance and optimizations of blocked algorithms, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.63-74, April 08-11, 1991, Santa Clara, California, United States
• 34: Alvin R. Lebeck , Xiaobo Fan , Heng Zeng , Carla Ellis, Power aware page allocation, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.105-116, November 2000, Cambridge, Massachusetts, United States
• 35: Lorch, J. R. and Smith, A. J. 1998. Software strategies for portable computer energy management. IEEE Personal Communications, 60--73.
• 36: Markus Lorenz , Lars Wehmeyer , Thorsten Dräger, Energy aware compilation for DSPs with SIMD instructions, 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
• 37: Yung-Hsiang Lu , Luca Benini , Giovanni De Micheli, Operating-system directed power reduction, Proceedings of the 2000 international symposium on Low power electronics and design, p.37-42, July 25-27, 2000, Rapallo, Italy [doi>10.1145/344166.344189]
• 38: Srilatha Manne , Artur Klauser , Dirk Grunwald, Pipeline gating: speculation control for energy reduction, Proceedings of the 25th annual international symposium on Computer architecture, p.132-141, June 27-July 02, 1998, Barcelona, Spain
• 39: Kathryn S. McKinley , Steve Carr , Chau-Wen Tseng, Improving data locality with loop transformations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.4, p.424-453, July 1996 [doi>10.1145/233561.233564]
• 40: Andreas Moshovos, Checkpointing alternatives for high performance, power-aware processors, Proceedings of the 2003 international symposium on Low power electronics and design, August 25-27, 2003, Seoul, Korea [doi>10.1145/871506.871585]
• 41: Musoll, E. 2000. Estimation of the upper-bound useless energy dissipation in a high-performance processor. Kool-Chips.
• 42: Preeti R. Panda , Nikil D. Dutt, Reducing Address Bus Transitions for Low Power Memory Mapping, Proceedings of the 1996 European conference on Design and Test, p.63, March 11-14, 1996
• 43: 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]
• 44: Daler Rakhmatov , Sarma Vrudhula , Deborah A. Wallach, Battery lifetime prediction for energy-aware computing, Proceedings of the 2002 international symposium on Low power electronics and design, August 12-14, 2002, Monterey, California, USA [doi>10.1145/566408.566449]
• 45: Siddharth Rele , Santosh Pande , Soner Önder , Rajiv Gupta, Optimizing Static Power Dissipation by Functional Units in Superscalar Processors, Proceedings of the 11th International Conference on Compiler Construction, p.261-275, April 08-12, 2002
• 46: 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
• 47: Schwab, H. 2004. lp_solve mixed integer linear program solver. ftp://ftp.es.ele.tue.nl/pub/lp_solve/.
• 48: Shiue, W.-T. and Chakrabarti, C. 1999. Memory exploration for low power, embedded systems. Tech. Rep. CLPE-TR-9-1999-20, Arizona State University, AZ.
• 49: Tajana Šimunić , Luca Benini , Giovanni De Micheli, Cycle-accurate simulation of energy consumption in embedded systems, Proceedings of the 36th ACM/IEEE conference on Design automation, p.867-872, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.310090]
• 50: Christian Früh , Avideh Zakhor, Constructing 3D City Models by Merging Aerial and Ground Views, IEEE Computer Graphics and Applications, v.23 n.6, p.52-61, November 2003 [doi>10.1109/MCG.2003.1242382]
• 51: Ching-Long Su , A. M. Despain, Cache designs for energy efficiency, Proceedings of the 28th Hawaii International Conference on System Sciences (HICSS'95), p.306, January 04-07, 1995
• 52: Robert P. Wilson , Robert S. French , Christopher S. Wilson , Saman P. Amarasinghe , Jennifer M. Anderson , Steve W. K. Tjiang , Shih-Wei Liao , Chau-Wen Tseng , Mary W. Hall , Monica S. Lam , John L. Hennessy, SUIF: an infrastructure for research on parallelizing and optimizing compilers, ACM SIGPLAN Notices, v.29 n.12, p.31-37, Dec. 1994 [doi>10.1145/193209.193217]
• 53: O. Temam , E. D. Granston , W. Jalby, To copy or not to copy: a compile-time technique for assessing when data copying should be used to eliminate cache conflicts, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.410-419, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169762]
• 54: Vivek Tiwari , Sharad Malik , Andrew Wolfe , Mike Tien-Chien Lee, Instruction level power analysis and optimization of software, Journal of VLSI Signal Processing Systems, v.13 n.2-3, p.223-238, Aug./Sept. 1996 [doi>10.1007/BF01130407]
• 55: Toburen, M. C., Conte, T. M., and Reilly, M. 1998. Instruction scheduling for low power dissipation in high performance processors. In Proc. the Power Driven Micro-architecture Workshop in conjunction with the ISCA'98, Barcelona, Spain.
• 56: P. Unnikrishnan , G. Chen , M. Kandemir , D. R. Mudgett, Dynamic compilation for energy adaptation, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.158-163, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774595]
• 57: N. Vijaykrishnan , M. Kandemir , M. J. Irwin , H. S. Kim , W. Ye, Energy-driven integrated hardware-software optimizations using SimplePower, Proceedings of the 27th annual international symposium on Computer architecture, p.95-106, June 2000, Vancouver, British Columbia, Canada
• 58: Viswanath, R., Wakharkar, V., Watwe, A., and Lebonheur, V. 2000. Thermal performance challenges from silicon to systems. Intel Technology Journal Q3.
• 59: Willems, M. and Zivojnovic, V. 1996. DSP-compiler: Product quality for control oriented applications? In Proc. ICSPAT'96. 752--756.
• 60: Michael E. Wolf , Dror E. Maydan , Ding-Kai Chen, Combining loop transformations considering caches and scheduling, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.274-286, December 02-04, 1996, Paris, France
• 61: Michael E. Wolf , Monica S. Lam, A data locality optimizing algorithm, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.30-44, June 24-28, 1991, Toronto, Ontario, Canada
• 62: 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
• 63: W. Zhang , M. Kandemir , N. Vijaykrishnan , M. J. Irwin , V. De, Compiler Support for Reducing Leakage Energy Consumption, Proceedings of the conference on Design, Automation and Test in Europe, p.11146, March 03-07, 2003

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.m Miscellaneous

General Terms:
Languages

Keywords:
Energy-Aware Compilation (EAC), mobile devices