Using branch handling hardware to support profile-driven optimization

ABSTRACT

Profile-based optimizations can be used for instruction scheduling, loop scheduling, data preloading, function in-lining, and instruction cache performance enhancement. However, these techniques have not been embraced by software vendors because programs instrumented for profiling run 2–30 times slower, an awkward compile-run-recompile sequence is required, and a test input suite must be collected and validated for each program. This paper proposes using existing branch handling hardware to generate profile information in real time. Techniques are presented for both one-level and two-level branch hardware organizations. The approach produces high accuracy with small slowdown in execution (0.4%–4.6%). This allows a program to be profiled while it is used, eliminating the need for a test input suite. This practically removes the inconvenience of profiling. With contemporary processors driven increasingly by compiler support, hardware-based profiling is important for high-performance systems.

REFERENCES

• 1: J. A. Fisher, "Trace scheduhng: A technique for global microcode compaction," IEEE Trans. Cornput., vol. C-30, no. 7, pp. 478-490, July 1981.
• 2: Pohua P. Chang , Scott A. Mahlke , Wen-mei W. Hwu, Using profile information to assist classic code optimizations, Software—Practice & Experience, v.21 n.12, p.1301-1321, Dec. 1991 [doi>10.1002/spe.4380211204]
• 3: William Yu-Wei Chen, Jr., Data preload for superscalar and VLIW processors, University of Illinois at Urbana-Champaign, Champaign, IL, 1993
• 4: P. P. Chang , W.-W. Hwu, Inline function expansion for compiling C programs, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.246-257, June 19-23, 1989, Portland, Oregon, United States
• 5: W. W. Hwu , P. P. Chang, Achieving high instruction cache performance with an optimizing compiler, Proceedings of the 16th annual international symposium on Computer architecture, p.242-251, April 1989, Jerusalem, Israel
• 6: Joseph A. Fisher , Stefan M. Freudenberger, Predicting conditional branch directions from previous runs of a program, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.85-95, October 12-15, 1992, Boston, Massachusetts, United States
• 7: David W. Wall, Predicting program behavior using real or estimated profiles, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.59-70, June 24-28, 1991, Toronto, Ontario, Canada
• 8: Thomas Ball , James R. Larus, Branch prediction for free, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.300-313, June 21-25, 1993, Albuquerque, New Mexico, United States
• 9: Richard E. Hank , Scott A. Mahlke , Roger A. Bringmann , John C. Gyllenhaal , Wen-mei W. Hwu, Superblock formation using static program analysis, Proceedings of the 26th annual international symposium on Microarchitecture, p.247-255, December 01-03, 1993, Austin, Texas, United States
• 10: Donald Alpert , Dror Avnon, Architecture of the Pentium Microprocessor, IEEE Micro, v.13 n.3, p.11-21, May 1993 [doi>10.1109/40.216745]
• 11: S. P. Song and M. Denman, "The PowerPC 604 RISC microprocessor," tech. rep., Somerset Design Center, Austin, TX, Apr. 1994.
• 12: James E. Smith, A study of branch prediction strategies, Proceedings of the 8th annual symposium on Computer Architecture, p.135-148, May 12-14, 1981, Minneapolis, Minnesota, United States
• 13: Tse-Yu Yeh , Yale N. Patt, Two-level adaptive training branch prediction, Proceedings of the 24th annual international symposium on Microarchitecture, p.51-61, September 1991, Albuquerque, New Mexico, Puerto Rico [doi>10.1145/123465.123475]
• 14: Tse-Yu Yeh , Yale N. Patt, A comparison of dynamic branch predictors that use two levels of branch history, Proceedings of the 20th annual international symposium on Computer architecture, p.257-266, May 16-19, 1993, San Diego, California, United States
• 15: P. P. Chang , W. W. Hwu, Trace selection for compiling large C application programs to microcode, Proceedings of the 21st annual workshop on Microprogramming and microarchitecture, p.21-29, November 28-December 02, 1988, San Diego, California, United States
• 16: M.L. Golden, "Issues in trace collection through program instrumentation," Master's thesis, Department of Electrical and Computer Engineering, University of Illinois, Urbana-Champaign, Illinois, 1991.
• 17: T. Ball and J. R. Larus, "Optimally profiling and tracing programs," Tech. Rep. 1031, Computer Sciences Dept., University of Wisconsin-Madison, 1991.
• 18: S. I. Feldman, "Make- A program for maintaining computer programs," Software-Practice and Experience, vol. 9, pp. 255-265, Apr. 1979.
• 19: Tim A. Wagner , Vance Maverick , Susan L. Graham , Michael A. Harrison, Accurate static estimators for program optimization, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.85-96, June 20-24, 1994, Orlando, Florida, United States

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Instruction set design (e.g., RISC, CISC, VLIW)

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.5 Microcode Applications
          Subjects: Instruction set interpretation

  C. Computer Systems Organization

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

General Terms:
Design, Performance