Rapid profiling via stratified sampling

ABSTRACT

Sophisticated binary translators and dynamic optimizers demand a program profiler with low overhead, high accuracy, and the ability to collect a variety of profile types. A profiling scheme that achieves these goals is proposed. Conceptually, the hardware compresses a stream of profile data by counting identical events; the compressed profile dam is passed to software for analysis. Compressing the high-bandwidth event stream greatly reduces software overhead. Because optimizations can tolerate some profiling errors, we allow the stream compressor to be lossy, thereby enabling a low-cost sampling-based hardware design. Because the hardware compressor is insensitive to the event content, it supports various profile types and can process multiple types simultaneously.

Basic components of our framework are periodic and random samplers, counters, and hash functions. These components are composed to form a variety of stream compressors. One design is both simple and very effective: the input stream is hash-split into multiple substreams, each of which is fed into a simple periodic sampler that selects every kth event. This stratified periodic sampler performs better than conventional random sampling because it biases each substream towards a small number of unique events, thereby reducing sampling error, and allowing faster convergence to an accurate profile. For example, convergence to a given level of accuracy is about twice as fast for gcc. When sampling overhead is considered, the stratified periodic profiler achieves less than 3% error while incurring an overhead of only 3.5% for gcc.

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?, ACM Transactions on Computer Systems (TOCS), v.15 n.4, p.357-390, Nov. 1997 [doi>10.1145/265924.265925]
• 3: Matthew Arnold , Stephen Fink , David Grove , Michael Hind , Peter F. Sweeney, Adaptive optimization in the Jalapeño JVM, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.47-65, October 2000, Minneapolis, Minnesota, United States
• 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, Optimally profiling and tracing programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.4, p.1319-1360, July 1994 [doi>10.1145/183432.183527]
• 6: 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
• 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: B. Calder, P. Feller, and A. Eustace. Value profiling. Journal of lnstruction Level Parallelism, March 1999.
• 9: Pohua P. Chang , Scott A. Mahlke , William Y. Chen , Wen-mei W. Hwu, Profile-guided automatic inline expansion for C programs, Software—Practice & Experience, v.22 n.5, p.349-369, May 1992 [doi>10.1002/spe.4380220502]
• 10: 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]
• 11: Daniel A. Connors , Wen-mei W. Hwu, Compiler-directed dynamic computation reuse: rationale and initial results, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.158-169, November 16-18, 1999, Haifa, Israel
• 12: Charles Consel, Luke Homof, Francois Noel, Jacques Noye, and Nicolae Volanschi. A Uniform Approach for Compile-time and Runtime Specialization. Technical Report RR-2775, lnria, Institut National de Recherche en lnformatique et en Automatique, 1996.
• 13: Thomas M. Conte , Kishore N. Menezes , Mary Ann Hirsch, Accurate and practical profile-driven compilation using the profile buffer, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.36-45, December 02-04, 1996, Paris, France
• 14: Craig B. Zilles , Gurindar S. Sohi, A Programmable Co-processor for Profiling, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.241, January 20-24, 2001
• 15: Jeffrey Dean , James E. Hicks , Carl A. Waldspurger , William E. Weihl , George Chrysos, ProfileMe: hardware support for instruction-level profiling on out-of-order processors, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.292-302, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 16: Doug Burger, Todd M. Austin, and Steve Bennett. Evaluating Future Microprocessors: The SimpleScalar Tool Set. Technical Report CS- TR-96-1308 (Available from http://www.cs.wisc.edu/trs.html), University of Wisconsin-Madison, July 1996.
• 17: Evelyn Duesterwald , Vasanth Bala, Software profiling for hot path prediction: less is more, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.202-211, November 2000, Cambridge, Massachusetts, United States
• 18: Carole Dulong, The IA-64 Architecture at Work, Computer, v.31 n.7, p.24-32, July 1998 [doi>10.1109/2.689674]
• 19: Kemal Ebcioğlu , Erik R. Altman, DAISY: dynamic compilation for 100% architectural compatibility, Proceedings of the 24th annual international symposium on Computer architecture, p.26-37, June 01-04, 1997, Denver, Colorado, United States
• 20: Joseph A. Fisher. Trace scheduling: A technique for global microcode compaction. IEEE Transactions on Computers, 30(7):478-490, July 1981.
• 21: David M. Gallagher , William Y. Chen , Scott A. Mahlke , John C. Gyllenhaal , Wen-mei W. Hwu, Dynamic memory disambiguation using the memory conflict buffer, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.183-193, October 05-07, 1994, San Jose, California, United States
• 22: William G.Cochran. Sampling Techniques. John Wiley and Sons, 1977.
• 23: Antonio Gonzalez , Jordi Tubella , Carlos Molina, Trace-Level Reuse, Proceedings of the 1999 International Conference on Parallel Processing, p.30, September 21-24, 1999
• 24: B. Grant, M. Mock, M. Philipose, C. Chambers, and S. Eggers. DyC: An Expressive Annotation-Directed Dynamic Compiler for C. Technical Report TR-97-03-03, University of Washington, Department of Computer Science and Engineering, March 1997.
• 25: Urs Hölzle, Adaptive optimization for self: reconciling high performance with exploratory programming, Stanford University, Stanford, CA, 1995
• 26: Urs Hölzle , Craig Chambers , David Ungar, Optimizing Dynamically-Typed Object-Oriented Languages With Polymorphic Inline Caches, Proceedings of the European Conference on Object-Oriented Programming, p.21-38, July 15-19, 1991
• 27: Jian Huang , David Lilja, Exploiting Basic Block Value Locality with Block Reuse, Proceedings of the 5th International Symposium on High Performance Computer Architecture, p.106, January 09-12, 1999
• 28: Neil D. Jones , Carsten K. Gomard , Peter Sestoft, Partial evaluation and automatic program generation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 29: Alexander Klaiber. The technology behind Crusoe(tm) Processors, January 2000.
• 30: Todd B. Knoblock , Erik Ruf, Data specialization, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.215-225, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 31: Mikko H. Lipasti , John Paul Shen, Exceeding the dataflow limit via value prediction, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.226-237, December 02-04, 1996, Paris, France
• 32: Markus Mock , Craig Chambers , Susan J. Eggers, Calpa: a tool for automating selective dynamic compilation, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.291-302, December 2000, Monterey, California, United States [doi>10.1145/360128.360158]
• 33: M. Burrows , U. Erlingson , S-T. A. Leung , M. T. Vandevoorde , C. A. Waldspurger , K. Walker , W. E. Weihl, Efficient and flexible value sampling, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.160-167, November 2000, Cambridge, Massachusetts, United States
• 34: Steve Meloan. The Java HotSpot (tm) Perfomance Engine: An In- Depth Look. Article on Sun's Java Developer Connection site, 1999.
• 35: 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
• 36: Robert Muth , Scott A. Watterson , Saumya K. Debray, Code Specialization Based on Value Profiles, Proceedings of the 7th International Symposium on Static Analysis, p.340-359, June 29-July 01, 2000
• 37: Massimiliano Poletto , Dawson R. Engler , M. Frans Kaashoek, tcc: a system for fast, flexible, and high-level dynamic code generation, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.109-121, June 16-18, 1997, Las Vegas, Nevada, United States
• 38: Yiannakis Sazeides , James E. Smith, The predictability of data values, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.248-258, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 39: Timothy Sherwood and Brad Calder. Time Varying Behavior of Programs. TechReport CS99-630, University of California-San Diego, August 1999.
• 40: James E Smith, Subramanya Sastry, Timothy Hell, and Todd Bezenek. Achieving High Performance via Co-Designed Virtual Machines. In International Workshop on Innovative Architecture, October 1999.
• 41: Avinash Sodani , Gurindar S. Sohi, Dynamic instruction reuse, Proceedings of the 24th annual international symposium on Computer architecture, p.194-205, June 01-04, 1997, Denver, Colorado, United States
• 42: Timothy Heil , James E. Smith, Relational profiling: enabling thread-level parallelism in virtual machines, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.281-290, December 2000, Monterey, California, United States [doi>10.1145/360128.360156]
• 43: Cliff Young , Michael D. Smith, Better global scheduling using path profiles, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.115-123, November 1998, Dallas, Texas, United States

INDEX TERMS

Primary Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.4 Microprogram Design Aids
          Subjects: Optimization

Additional Classification:
  C. Computer Systems Organization
  C.0 GENERAL

      Nouns: Systems Application Architecture

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.2 Installation Management
          Subjects: Benchmarks

General Terms:
Design, Measurement, Performance, Reliability, Standardization, Theory