Fast data-locality profiling of native execution

ABSTRACT

Performance tools based on hardware counters can efficiently profile the cache behavior of an application and help software developers improve its cache utilization. Simulator-based tools can potentially provide more insights and flexibility and model many different cache configurations, but have the drawback of large run-time overhead.We present StatCache, a performance tool based on a statistical cache model. It has a small run-time overhead while providing much of the flexibility of simulator-based tools. A monitor process running in the background collects sparse memory access statistics about the analyzed application running natively on a host computer. Generic locality information is derived and presented in a code-centric and/or data-centric view.We evaluate the accuracy and performance of the tool using ten SPEC CPU2000 benchmarks. We also exemplify how the flexibility of the tool can be used to better understand the characteristics of cache-related performance problems.

REFERENCES

• 1: 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]
• 2: Erik Berg , Erik Hagersten, SIP: Performance Tuning through Source Code Interdependence, Proceedings of the 8th International Euro-Par Conference on Parallel Processing, p.177-186, August 27-30, 2002
• 3: E. Berg and E. Hagersten. StatCache: A probabilistic approach to efficient and accurate data locality analysis. Technical report 2003-57, Department of information technology, Uppsala University, Sweden, 2003.
• 4: E. Berg and E. Hagersten. StatCache: A probabilistic approach to efficient and accurate data locality analysis. In Proceedings of International Symposium on Performance Analysis of Systems And Software, 2004.
• 5: K. Beyls, E. D'Hollander, and Y. Yu. Visualization enables the programmer to reduce cache misses. In Proceedings of Conference on Parallel and Distributed Computing and Systems, 2002.
• 6: S. Browne , J. Dongarra , N. Garner , K. London , P. Mucci, A scalable cross-platform infrastructure for application performance tuning using hardware counters, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.42-es, November 04-10, 2000, Dallas, Texas, United States
• 7: Bryan R. Buck , Jeffrey K. Hollingsworth, Using hardware performance monitors to isolate memory bottlenecks, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.40-es, November 04-10, 2000, Dallas, Texas, United States
• 8: Calin CaΒcaval , David A. Padua, Estimating cache misses and locality using stack distances, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA [doi>10.1145/782814.782836]
• 9: Trishul M. Chilimbi, Efficient representations and abstractions for quantifying and exploiting data reference locality, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.191-202, June 2001, Snowbird, Utah, United States
• 10: Trishul M. Chilimbi , Martin Hirzel, Dynamic hot data stream prefetching for general-purpose programs, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 11: Thomas M. Conte , Mary Ann Hirsch , Wen-mei W. Hwu, Combining Trace Sampling with Single Pass Methods for Efficient Cache Simulation, IEEE Transactions on Computers, v.47 n.6, p.714-720, June 1998 [doi>10.1109/12.689650]
• 12: Intel Corporation. Intel VTune Performance Analyzers http://www.intel.com/software/products/vtune/.
• 13: Luiz DeRose , K. Ekanadham , Jeffrey K. Hollingsworth , Simone Sbaraglia, SIGMA: a simulator infrastructure to guide memory analysis, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-13, November 16, 2002, Baltimore, Maryland
• 14: A. Eustace and A. Srivastava. ATOM: A flexible interface for building high performance program analysis tools. In USENIX Winter, pages 303--314, 1995.
• 15: Somnath Ghosh , Margaret Martonosi , Sharad Malik, Cache miss equations: a compiler framework for analyzing and tuning memory behavior, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.4, p.703-746, July 1999 [doi>10.1145/325478.325479]
• 16: Marty Itzkowitz , Brian J. N. Wylie , Christopher Aoki , Nicolai Kosche, Memory Profiling using Hardware Counters, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.17, November 15-21, 2003
• 17: John Mellor-Crummey , Robert Fowler , David Whalley, Tools for application-oriented performance tuning, Proceedings of the 15th international conference on Supercomputing, p.154-165, June 2001, Sorrento, Italy [doi>10.1145/377792.377826]
• 18: R. E. Kessler , M. D. Hill , D. A. Wood, A Comparison of Trace-Sampling Techniques for Multi-Megabyte Caches, IEEE Transactions on Computers, v.43 n.6, p.664-675, June 1994 [doi>10.1109/12.286300]
• 19: S. Laha , J. H. Patel , R. K. Iyer, Accurate Low-Cost Methods for Performance Evaluation of Cache Memory Systems, IEEE Transactions on Computers, v.37 n.11, p.1325-1336, November 1988 [doi>10.1109/12.8699]
• 20: James R. Larus , Eric Schnarr, EEL: machine-independent executable editing, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.291-300, June 18-21, 1995, La Jolla, California, United States
• 21: Alvin R. Lebeck , David A. Wood, Cache Profiling and the SPEC Benchmarks: A Case Study, Computer, v.27 n.10, p.15-26, October 1994 [doi>10.1109/2.318580]
• 22: Mendel Rosenblum , Edouard Bugnion , Scott Devine , Stephen A. Herrod, Using the SimOS machine simulator to study complex computer systems, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.7 n.1, p.78-103, Jan. 1997 [doi>10.1145/244804.244807]
• 23: J. Maebe, M. Ronsse, and K. De Bosschere. DIOTA: Dynamic instrumentation, optimization and transformation of applications. In Compendium of Workshops and Tutorials. Held in conjunction with International Conference on Parallel Architectures and Compilation Techniques., September 2002.
• 24: P. Magnusson, F. Larsson, A. Moestedt, B. Werner, F. Dahlgren, M. Karlsson, F. Lundholm, J. Nilsson, P. Stenström, and H. Grahn. SimICS/sun4m: A virtual workstation. In Proceedings of the Usenix Annual Technical Conference, pages 119--130, 1998.
• 25: Gabriel Marin , John Mellor-Crummey, Cross-architecture performance predictions for scientific applications using parameterized models, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 26: Margaret Martonosi , Anoop Gupta , Thomas Anderson, MemSpy: analyzing memory system bottlenecks in programs, Proceedings of the 1992 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.1-12, June 01-05, 1992, Newport, Rhode Island, United States
• 27: Margaret Martonosi , Anoop Gupta , Thomas E. Anderson, Tuning Memory Performance of Sequential and Parallel Programs, Computer, v.28 n.4, p.32-40, April 1995 [doi>10.1109/2.375175]
• 28: R. L. Mattson, J. Gecsei, D. R. Slutz, and I. L. Traiger. Evaluation techniques for storage hierarchies. IBM Systems Journal, 9(2):78--117, 1970.
• 29: Tushar Mohan , Bronis R. de Supinski , Sally A. McKee , Frank Mueller , Andy Yoo , Martin Schulz, Identifying and Exploiting Spatial Regularity in Data Memory References, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.49, November 15-21, 2003
• 30: Lisa Noordergraaf , Robert Zak, SMP system interconnect instrumentation for performance analysis, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-9, November 16, 2002, Baltimore, Maryland
• 31: Erez Perelman , Greg Hamerly , Michael Van Biesbrouck , Timothy Sherwood , Brad Calder, Using SimPoint for accurate and efficient simulation, Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 11-14, 2003, San Diego, CA, USA
• 32: Erez Perelman , Greg Hamerly , Brad Calder, Picking Statistically Valid and Early Simulation Points, Proceedings of the 12th International Conference on Parallel Architectures and Compilation Techniques, p.244, September 27-October 01, 2003
• 33: SPEC. Standard performance evaluation corporation http://www.spec.org/.
• 34: Richard Uhlig , David Nagle , Trevor Mudge , Stuart Sechrest, Trap-driven simulation with Tapeworm II, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.132-144, October 05-07, 1994, San Jose, California, United States
• 35: Xavier Vera , Jingling Xue, Let's Study Whole-Program Cache Behaviour Analytically, Proceedings of the 8th International Symposium on High-Performance Computer Architecture, p.175, February 02-06, 2002
• 36: David A. Wood , Mark D. Hill , R. E. Kessler, A model for estimating trace-sample miss ratios, ACM SIGMETRICS Performance Evaluation Review, v.19 n.1, p.79-89, May 1991
• 37: Roland E. Wunderlich , Thomas F. Wenisch , Babak Falsafi , James C. Hoe, SMARTS: accelerating microarchitecture simulation via rigorous statistical sampling, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 38: Yutao Zhong , Steven G. Dropsho , Chen Ding, Miss Rate Prediction across All Program Inputs, Proceedings of the 12th International Conference on Parallel Architectures and Compilation Techniques, p.79, September 27-October 01, 2003

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Performance measures

General Terms:
Measurement, Performance

Keywords:
cache behavior, profiling tool