Binary translation to improve energy efficiency through post-pass register re-allocation

ABSTRACT

Energy efficiency is rapidly becoming a first class optimization parameter for modern systems. Caches are critical to the overall performance and thus, modern processors (both high and low-end) tend to deploy a cache with large size and high degree of associativity. Due a large size cache power takes up a significant percentage of total system power. One important way to reduce cache power consumption is to reduce the dynamic activities in the cache by reducing the dynamic load-store counts. In this work, we focus on programs that are only available as binaries which need to be improved for energy efficiency. For adapting these programs for energy-constrained devices, we propose a feed-back directed post-pass solution that tries to do register re-allocation to reduce dynamic load/store counts and to improve energy-efficiency. Our approach is based on zero knowledge of original code generator or compiler and performs a post-pass register allocation to get a more power-efficient binary. We attempt to find out the dead as well as unused registers in the binary and then re-allocate them on hot paths to reduce dynamic load/store counts. It is shown that the static code size increase due to our framework is very minimal. Our experiments on SPEC2000 and MediaBench show that our technique is effective. We have seen dynamic spill loads/stores reduction in the data-cache ranging from 0% to 26.4%. Overall, our approach improves the energy-delay product of the program.

REFERENCES

• 1: G. J. Chaitin, Register allocation & spilling via graph coloring, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.98-105, June 23-25, 1982, Boston, Massachusetts, United States
• 2: Preston Briggs , Keith D. Cooper , Linda Torczon, Improvements to graph coloring register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.3, p.428-455, May 1994 [doi>10.1145/177492.177575]
• 3: Fred C. Chow , John L. Hennessy, The priority-based coloring approach to register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.4, p.501-536, Oct. 1990 [doi>10.1145/88616.88621]
• 4: Peter Bergner , Peter Dahl , David Engebretsen , Matthew O'Keefe, Spill code minimization via interference region spilling, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.287-295, June 16-18, 1997, Las Vegas, Nevada, United States
• 5: Keith D. Cooper , L. Taylor Simpson, Live Range Splitting in a Graph Coloring Register Allocator, Proceedings of the 7th International Conference on Compiler Construction, p.174-187, March 28-April 04, 1998
• 6: T. J. Harvey, Reducing the Impact of Spill Code, Master's Thesis, Rice University, May 1998.
• 7: John Lu , Keith D. Cooper, Register promotion in C programs, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.308-319, June 16-18, 1997, Las Vegas, Nevada, United States
• 8: Premkishore Shivakumar and Norman P. Jouppi. CACTI 3.0: An Integrated Cache Timing, Power, and Area Model. WRL research report 2001/2.
• 9: Ching-Long Su , Alvin M. Despain, Cache design trade-offs for power and performance optimization: a case study, Proceedings of the 1995 international symposium on Low power design, p.63-68, April 23-26, 1995, Dana Point, California, United States [doi>10.1145/224081.224093]
• 10: Uming Ko , Poras T. Balsara , Ashwini K. Nanda, Energy optimization of multi-level processor cache architectures, Proceedings of the 1995 international symposium on Low power design, p.45-49, April 23-26, 1995, Dana Point, California, United States [doi>10.1145/224081.224090]
• 11: Johnson Kin , Munish Gupta , William H. Mangione-Smith, The filter cache: an energy efficient memory structure, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.184-193, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 12: Andrea G. M. Cilio , Henk Corporaal, Global Variable Promotion: Using Registers to Reduce Cache Power Dissipation, Proceedings of the 11th International Conference on Compiler Construction, p.247-260, April 08-12, 2002
• 13: 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
• 14: Don Heller. Rabbit: A Performance Counters Library for Intel/AMD Processors and Linux. http://www.scl.ameslab.gov/Projects/Rabbit/
• 15: 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
• 16: Simon Segars. Low Power Design Techniques for Microprocessors. Conference Presentation on IEEE International Solid-State Circuits Conference (ISSCC), Feb. 2001.
• 17: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 18: Mach-Suif Backend Compiler, The Machine-Suif 2.1 compiler documentation set. Harvard University, Sep. 2000, http://ececs.harvard.edu/hube/research/machsuif.html.
• 19: Lal George , Andrew W. Appel, Iterated register coalescing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.3, p.300-324, May 1996 [doi>10.1145/229542.229546]
• 20: David W. Wall, Global register allocation at link time, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.264-275, June 25-27, 1986, Palo Alto, California, United States
• 21: Steven M. Kurlander , Charles N. Fischer, Minimum cost interprocedural register allocation, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.230-241, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237780]
• 22: Vatsa Santhanam , Daryl Odnert, Register allocation across procedure and module boundaries, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.28-39, June 1990, White Plains, New York, United States
• 23: Richard Eugene Hank , Wen-Mei W. Hwu, Region-based compilation, 1996

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:
Design, Experimentation, Measurement, Performance

Keywords:
cache power consumption, dead registers, register re-allocation, unused registers