Hardware Support for Control Transfers in Code Caches

ABSTRACT

Many dynamic optimization and/or binary translationsystems hold optimized/translated superblocks in a codecache. Conventional code caching systems suffer fromoverheads when control is transferred from one cachedsuperblock to another, especially via register-indirectjumps. The basic problem is that instruction addresses inthe code cache are different from those in the original programbinary. Therefore, performance for register-indirectjumps depends on the ability to translate efficiently fromsource binary PC values to code cache PC values.We analyze several key aspects of superblock chainingand find that a conventional baseline code cache withsoftware jump target prediction results in 14.6% IPC lossversus the original binary. We identify the inability to usea conventional return address stack as the most significantperformance limiter in code cache systems. We introduce amodified software prediction technique that reduces theIPC loss to 11.4%. This technique is based on a techniqueused in threaded code interpreters.A number of hardware mechanisms, including a specializedreturn address stack and a hardware cache fortranslated jump target addresses, are studied for efficientlysupporting register-indirect jumps. Once all the chainingoverheads are removed by these support mechanisms, asuperblock-based code cache improves performance due toa better branch prediction rate, improved I-cache locality,and increased chances of straight-line fetches. Simulationresults show a 7.7% IPC improvement over a current generation4-way superscalar processor.

REFERENCES

• 1: [1] Erik R. Altman, Michael Gschwind, Sumedh Sathaye, S. Kosonocky, Arthur Bright, Jason Fritts, Paul Ledak, David Appenzeller, Craig Agricola, Zachary Filan, "BOA: The Architecture of a Binary Translation Processor," IBM Research Report RC21665, Dec. 2000.
• 2: Vasanth Bala , Evelyn Duesterwald , Sanjeev Banerjia, Dynamo: a transparent dynamic optimization system, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.1-12, June 18-21, 2000, Vancouver, British Columbia, Canada
• 3: Marc Berndl , Laurie Hendren, Dynamic profiling and trace cache generation, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 4: [4] Derek Bruening, Evelyn Duesterwald, Saman Amarasinghe, "Design and Implementation of a Dynamic Optimization Framework for Windows," The 4th Workshop on Feedback-Directed and Dynamic Optimization, Dec. 2001.
• 5: Derek Bruening , Timothy Garnett , Saman Amarasinghe, An infrastructure for adaptive dynamic optimization, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 6: [6] Douglas C. Burger, Todd M. Austin, "The SimpleScalar Toolset, Version 2.0" Technical Report CS-TR-97-1342, University of Wisconsin-Madison, Jun. 1997.
• 7: [7] Wen-Ke Chen, Sorin Lerner, Ronnie Chaiken, David M. Gillies, "Mojo: A Dynamic Optimization System," The 3rd Workshop on Feedback-Directed and Dynamic Optimization , Dec. 2000.
• 8: [8] Dean Deaver, Rick Gorton, Norman Rubin, "Wiggins/Redstone: An Online Program Specializer," The 11th HotChips Symposim, Jun. 1999.
• 9: Giuseppe Desoli , Nikolay Mateev , Evelyn Duesterwald , Paolo Faraboschi , Joseph A. Fisher, DELI: a new run-time control point, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 10: Kemal Ebcioglu , Erik Altman , Michael Gschwind , Sumedh Sathaye, Dynamic Binary Translation and Optimization, IEEE Transactions on Computers, v.50 n.6, p.529-548, June 2001 [doi>10.1109/12.931892]
• 11: M. Anton Ertl , David Gregg, The Behavior of Efficient Virtual Machine Interpreters on Modern Architectures, Proceedings of the 7th International Euro-Par Conference Manchester on Parallel Processing, p.403-412, August 28-31, 2001
• 12: Brian Fahs , Satarupa Bose , Matthew Crum , Brian Slechta , Francesco Spadini , Tony Tung , Sanjay J. Patel , Steven S. Lumetta, Performance characterization of a hardware mechanism for dynamic optimization, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 13: [13] Michael Gschwind, "Method and Apparatus for Determining Branch Addresses in Programs Generated by Binary Translation, IBM Disclosures YOR819980334, Jul. 1998.
• 14: [14] Michael Gschwind, "Method and Apparatus for Rapid Return Address Computation in Binary Translation," IBM Disclosures YOR819980410, Sep. 1998.
• 15: [15] Tom R. Halfhill, "Transmeta Breaks x86 Low-Power Barrier," Microprocessor Report, Feb. 14, 2000.
• 16: [16] Hewlett Packard Co., "PA-RISC 8×00 Family of Microprocessors with Focus on PA-8700," www.cpus.hp.com/technical_references/PA-8700wp.pdf.
• 17: [17] Glenn Hinton, Dave Sager, Mike Upton, Darrel Boggs, Doug Carmean, Alan Kyker, Patrice Roussel, "The Microarchitecture of the Pentium 4 Processor," Intel Technology Journal Q1, 2001.
• 18: Raymond J. Hookway , Mark A. Herdeg, DIGITAL FX!32: combining emulation and binary translation, Digital Technical Journal, v.9 n.1, p.3-12, 1997
• 19: Wen-Mei W. Hwu , Scott A. Mahlke , William Y. Chen , Pohua P. Chang , Nancy J. Warter , Roger A. Bringmann , Roland G. Ouellette , Richard E. Hank , Tokuzo Kiyohara , Grant E. Haab , John G. Holm , Daniel M. Lavery, The superblock: an effective technique for VLIW and superscalar compilation, The Journal of Supercomputing, v.7 n.1-2, p.229-248, May 1993 [doi>10.1007/BF01205185]
• 20: Daniel A. Jiménez , Stephen W. Keckler , Calvin Lin, The impact of delay on the design of branch predictors, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.67-76, December 2000, Monterey, California, United States [doi>10.1145/360128.360137]
• 21: David R. Kaeli , Philip G. Emma, Branch history table prediction of moving target branches due to subroutine returns, Proceedings of the 18th annual international symposium on Computer architecture, p.34-42, May 27-30, 1991, Toronto, Ontario, Canada
• 22: [22] Edmund J. Kelly, Robert F. Cmelik, Malcolm J. Wing, "Memory Controller for a Microprocessor for Detecting a Failure of Speculation on the Physical Nature of a Component Being Addressed," US Patent 5,832,205, Nov. 1998.
• 23: Chetana N. Keltcher , Kevin J. McGrath , Ardsher Ahmed , Pat Conway, The AMD Opteron Processor for Multiprocessor Servers, IEEE Micro, v.23 n.02, p.66-76, March 2003
• 24: Ho-Seop Kim , James E. Smith, Dynamic binary translation for accumulator-oriented architectures, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 25: Bich C. Le, An out-of-order execution technique for runtime binary translators, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.151-158, October 02-07, 1998, San Jose, California, United States
• 26: P. Geoffrey Lowney , Stefan M. Freudenberger , Thomas J. Karzes , W. D. Lichtenstein , Robert P. Nix , John S. O'Donnell , John Ruttenberg, The multiflow trace scheduling compiler, The Journal of Supercomputing, v.7 n.1-2, p.51-142, May 1993 [doi>10.1007/BF01205182]
• 27: Matthew C. Merten , Andrew R. Trick , Erik M. Nystrom , Ronald D. Barnes , Wen-mei W. Hmu, A hardware mechanism for dynamic extraction and relayout of program hot spots, Proceedings of the 27th annual international symposium on Computer architecture, p.59-70, June 2000, Vancouver, British Columbia, Canada
• 28: Alex Ramirez , Josep L. Larriba-Pey , Mateo Valero, The Effect of Code Reordering on Branch Prediction, Proceedings of the 2000 International Conference on Parallel Architectures and Compilation Techniques, p.189, October 15-19, 2000
• 29: Eric Rotenberg , Steve Bennett , James E. Smith, Trace cache: a low latency approach to high bandwidth instruction fetching, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.24-35, December 02-04, 1996, Paris, France
• 30: K. Scott , N. Kumar , S. Velusamy , B. Childers , J. W. Davidson , M. L. Soffa, Retargetable and reconfigurable software dynamic translation, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 31: Gabriel M. Silberman , Kemal Ebcioglu, An Architectural Framework for Supporting Heterogeneous Instruction-Set Architectures, Computer, v.26 n.6, p.39-56, June 1993 [doi>10.1109/2.214441]
• 32: [32] Sun Microsystems, "UltraSPARC IIIi Processor," www.sun.com/processors/UltraSPARC-IIIi/us3i_datasheet.pdf, 2003.
• 33: [33] Joel M. Tendler, Steve Dodson, Steve Fields, Hung Le, Balaram Sinharoy, "POWER4 System Microarchitecture," IBM Journal of Research and Development, Vol. 46, No. 1, pp. 5-26, Jan. 2002.
• 34: [34] David Ung, Cristina Cifuentes, "Optimizing Hot Paths in a Dynamic Binary Translator," The 2nd Workshop on Binary Translation, Oct. 2000.
• 35: John Whaley, Partial method compilation using dynamic profile information, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.166-179, October 14-18, 2001, Tampa Bay, FL, USA
• 36: Emmett Witchel , Mendel Rosenblum, Embra: fast and flexible machine simulation, Proceedings of the 1996 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.68-79, May 23-26, 1996, Philadelphia, Pennsylvania, United States
• 37: Cindy Zheng , Carol Thompson, PA-RISC to IA-64: Transparent Execution, No Recompilation, Computer, v.33 n.3, p.47-52, March 2000 [doi>10.1109/2.825695]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Memory technologies

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration); Algorithms implemented in hardware
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

General Terms:
Measurement, Performance