Software profiling for hot path prediction: less is more

ABSTRACT

Recently, there has been a growing interest in exploiting profile information in adaptive systems such as just-in-time compilers, dynamic optimizers and, binary translators. In this paper, we show that sophisticated software profiling schemes that provide highly accurate information in an offline setting are ill-suited for these dynamic code generation systems. We experimentally demonstrate that hot path predictions must be made early in order to control the rising cost of missed opportunity that result from the prediction delay. We also show that existing sophisticated path profiling schemes, if used in an online setting, offer no prediction advantages over simpler schemes that exhibit much lower runtime overheads.Based on these observation we developed a new low-overhead software profiling scheme for hot path prediction. Using an abstract metric we compare our scheme to path profile based prediction and show that our scheme achieves comparable prediction quality. In our second set of experiments we include runtime overhead and evaluate the performance of our scheme in a realistic application: Dynamo, a dynamic optimization system. The results show that our prediction scheme clearly outperforms path profile based prediction and thus confirm that less profiling as exhibited in our scheme will actually lead to more effective hot path prediction.

REFERENCES

• 1: Glenn Ammons , Thomas Ball , James R. Larus, Exploiting hardware performance counters with flow and context sensitive profiling, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.85-96, June 16-18, 1997, Las Vegas, Nevada, United States
• 2: Jennifer M. Anderson , Lance M. Berc , Jeffrey Dean , Sanjay Ghemawat , Monika R. Henzinger , Shun-Tak A. Leung , Richard L. Sites , Mark T. Vandevoorde , Carl A. Waldspurger , William E. Weihl, Continuous profiling: where have all the cycles gone?, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.1-14, October 05-08, 1997, Saint Malo, France
• 3: Bala, V., Duesterwald, E., and Banerjia, S. Transparent dynamic optimization: The design and implementation of Dynamo. Hewlett Packard Laboratories Technical Report HPL-1999-78. June 1999.
• 4: 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
• 5: Thomas Ball , James R. Larus, Efficient path profiling, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.46-57, December 02-04, 1996, Paris, France
• 6: Thomas Ball , Peter Mataga , Mooly Sagiv, Edge profiling versus path profiling: the showdown, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.134-148, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268958]
• 7: Michael G. Burke , Jong-Deok Choi , Stephen Fink , David Grove , Michael Hind , Vivek Sarkar , Mauricio J. Serrano , V. C. Sreedhar , Harini Srinivasan , John Whaley, The Jalapeño dynamic optimizing compiler for Java, Proceedings of the ACM 1999 conference on Java Grande, p.129-141, June 12-14, 1999, San Francisco, California, United States [doi>10.1145/304065.304113]
• 8: 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]
• 9: B. Calder , D. Grunwald, Fast and accurate instruction fetch and branch prediction, Proceedings of the 21ST annual international symposium on Computer architecture, p.2-11, April 18-21, 1994, Chicago, Illinois, United States
• 10: Cmelik, R.F. and Keppel, D. Shade: a fast instruction set simulator for execution profiling. Technical Report UWCSE- 93-06-06, Dept. Comp. Science and Engineering, Univ. Washington. 1993.
• 11: Kemal Ebcioglu , Erik R. Altman , Sumedh W. Sathaye , Michael Gschwind, Execution-Based Scheduling for VLIW Architectures, Proceedings of the 5th International Euro-Par Conference on Parallel Processing, p.1269-1280, August 31-September 03, 1999
• 12: S. McFarling , J. Hennesey, Reducing the cost of branches, Proceedings of the 13th annual international symposium on Computer architecture, p.396-403, June 02-05, 1986, Tokyo, Japan
• 13: Matthew C. Merten , Andrew R. Trick , Christopher N. George , John C. Gyllenhaal , Wen-mei W. Hwu, A hardware-driven profiling scheme for identifying program hot spots to support runtime optimization, Proceedings of the 26th annual international symposium on Computer architecture, p.136-147, May 01-04, 1999, Atlanta, Georgia, United States
• 14: Shien-Tai Pan , Kimming So , Joseph T. Rahmeh, Improving the accuracy of dynamic branch prediction using branch correlation, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.76-84, October 12-15, 1992, Boston, Massachusetts, United States
• 15: 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
• 16: Michael Sannella , John Maloney , Bjorn Freeman-Benson , Alan Borning, Multi-way versus one-way constraints in user interfaces: experience with the DeltaBlue algorithm, Software—Practice & Experience, v.23 n.5, p.529-566, May 1993 [doi>10.1002/spe.4380230507]
• 17: Sathaye, S., Ledak, P., LeBlanc, J., Kosonocky, S., Gschwind, M., Fritts, J., Filan, Z., Bright, A., AppenzeUer, D., Airman, E., and Agricola, C. BOA: Targeting multigigahertz with binary translation. In Proc. of the 1999 Workshop on Binary Translation, Newport Beach, CA., October 1999.
• 18: Smith, M. Private communication, March 2000.
• 19: 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
• 20: Cliff Young , Michael D. Smith, Static correlated branch prediction, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.5, p.1028-1075, Sept. 1999 [doi>10.1145/330249.330255]
• 21: Xiaolan Zhang , Zheng Wang , Nicholas Gloy , J. Bradley Chen , Michael D. Smith, System support for automatic profiling and optimization, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.15-26, October 05-08, 1997, Saint Malo, France

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: User profiles and alert services