METRIC: Memory tracing via dynamic binary rewriting to identify cache inefficiencies

ABSTRACT

With the diverging improvements in CPU speeds and memory access latencies, detecting and removing memory access bottlenecks becomes increasingly important. In this work we present METRIC, a software framework for isolating and understanding such bottlenecks using partial access traces. METRIC extracts access traces from executing programs without special compiler or linker support. We make four primary contributions. First, we present a framework for extracting partial access traces based on dynamic binary rewriting of the executing application. Second, we introduce a novel algorithm for compressing these traces. The algorithm generates constant space representations for regular accesses occurring in nested loop structures. Third, we use these traces for offline incremental memory hierarchy simulation. We extract symbolic information from the application executable and use this to generate detailed source-code correlated statistics including per-reference metrics, cache evictor information, and stream metrics. Finally, we demonstrate how this information can be used to isolate and understand memory access inefficiencies. This illustrates a potential advantage of METRIC over compile-time analysis for sample codes, particularly when interprocedural analysis is required.

REFERENCES

• 1: 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
• 2: Bryan Buck , Jeffrey K. Hollingsworth, An API for Runtime Code Patching, International Journal of High Performance Computing Applications, v.14 n.4, p.317-329, November 2000 [doi>10.1177/109434200001400404]
• 3: 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
• 4: Burrows, M. and Wheeler, D. J. 1994. A block-sorting lossless data compression algorithm. Tech. Rep. 124.
• 5: Martin Burtscher, VPC3: a fast and effective trace-compression algorithm, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 6: Burtscher, M. 2004b. Vpc3 source code. http://www.csl.cornell.edu/burtscher/research/tracecom pression/.
• 7: Siddhartha Chatterjee , Erin Parker , Philip J. Hanlon , Alvin R. Lebeck, Exact analysis of the cache behavior of nested loops, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.286-297, June 2001, Snowbird, Utah, United States
• 8: 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
• 9: Trishul M. Chilimbi , Bob Davidson , James R. Larus, Cache-conscious structure definition, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.13-24, May 01-04, 1999, Atlanta, Georgia, United States
• 10: Trishul M. Chilimbi , Mark D. Hill , James R. Larus, Cache-conscious structure layout, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.1-12, May 01-04, 1999, Atlanta, Georgia, United States
• 11: Cristina Cifuentes , Mike Van Emmerik, UQBT: Adaptable Binary Translation at Low Cost, Computer, v.33 n.3, p.60-66, March 2000 [doi>10.1109/2.825697]
• 12: 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
• 13: Chen Ding , Yutao Zhong, Predicting whole-program locality through reuse distance analysis, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 14: 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]
• 15: Brian Grant , Matthai Philipose , Markus Mock , Craig Chambers , Susan J. Eggers, An evaluation of staged run-time optimizations in DyC, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.293-304, May 01-04, 1999, Atlanta, Georgia, United States
• 16: P. Havlak , K. Kennedy, An Implementation of Interprocedural Bounded Regular Section Analysis, IEEE Transactions on Parallel and Distributed Systems, v.2 n.3, p.350-360, July 1991 [doi>10.1109/71.86110]
• 17: Mark Horowitz , Margaret Martonosi , Todd C. Mowry , Michael D. Smith, Informing memory operations: providing memory performance feedback in modern processors, Proceedings of the 23rd annual international symposium on Computer architecture, p.260-270, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 18: Intel. 2004. Intel Itanium2 Processor Reference Manual for Software Development and Optimization Vol.1, Intel, Santa Clara, CA.
• 19: James R. Larus , Thomas Ball, Rewriting executable files to measure program behavior, Software—Practice & Experience, v.24 n.2, p.197-218, Feb. 1994 [doi>10.1002/spe.4380240204]
• 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: Alvin R. Lebeck , David A. Wood, Active memory: a new abstraction for memory system simulation, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.7 n.1, p.42-77, Jan. 1997 [doi>10.1145/244804.244806]
• 23: Manning, N. 2005. Sequitur source code. http://sequence.rutgers.edu/sequitur/sequitur.cc.
• 24: Marathe, J. and Mueller, F. 2002. Detecting memory performance bottlenecks via binary rewriting. In Proceedings of the Workshop on Binary Translation.
• 25: Jaydeep Marathe , Frank Mueller , Bronis de Supinski, A hybrid hardware/software approach to efficiently determine cache coherence Bottlenecks, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts [doi>10.1145/1088149.1088153]
• 26: Jaydeep Marathe , Frank Mueller , Tushar Mohan , Bronis R. de Supinski , Sally A. McKee , Andy Yoo, METRIC: tracking down inefficiencies in the memory hierarchy via binary rewriting, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 27: Jaydeep Marathe , Anita Nagarajan , Frank Mueller, Detailed cache coherence characterization for OpenMP benchmarks, Proceedings of the 18th annual international conference on Supercomputing, June 26-July 01, 2004, Malo, France [doi>10.1145/1006209.1006250]
• 28: 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]
• 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: Todd C. Mowry , Chi-Keung Luk, Predicting data cache misses in non-numeric applications through correlation profiling, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.314-320, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 31: Mueller, F., Mohan, T., de Supinski, B. R., McKee, S. A., and Yoo, A. 2001. Partial data traces: Efficient generation and representation. In Workshop on Binary Translation. IEEE Technical Committee on Computer Architecture Newsletter.
• 32: Nevill-Manning, C. G. and Witten, I. H. 1997a. Compression and explanation using hierarchical grammars. Comput. J. 40, 2--3.
• 33: Craig G. Nevill-Manning , Ian H. Witten, Linear-Time, Incremental Hierarchy Inference for Compression, Proceedings of the Conference on Data Compression, p.3, March 25-27, 1997
• 34: Seward, J. 2005. Libbzip2 source code. http://www.bzip.org/index.html.
• 35: Richard L. Sites , Anton Chernoff , Matthew B. Kirk , Maurice P. Marks , Scott G. Robinson, Binary translation, Communications of the ACM, v.36 n.2, p.69-81, Feb. 1993 [doi>10.1145/151220.151227]
• 36: Amitabh Srivastava , Alan Eustace, ATOM: a system for building customized program analysis tools, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.196-205, June 20-24, 1994, Orlando, Florida, United States
• 37: Tendler, J. M., Dodson, J. S., Fields, Jr., J. S., Le, H., and Sinharoy, B. 2002. POWER4 system microarchitecture. IBM J. Res. Develop. 46, 1 (Jan.), 5--25.
• 38: Ung, D. and Cifuentes, C. 2000. Optimising hot paths in a dynamic binary translator. In Proceedings of the Workshop on Binary Translation.
• 39: Jeffrey S. Vetter , Frank Mueller, Communication characteristics of large-scale scientific applications for contemporary cluster architectures, Journal of Parallel and Distributed Computing, v.63 n.9, p.853-865, September 2003 [doi>10.1016/S0743-7315(03)00104-7]
• 40: Weikle, D., McKee, S. A., Skadron, K., and Wulf, W. 2000. Caches as filters: A framework for the analysis of caching systems. In Proceedings of the Grace Murray Hopper Conference.
• 41: Wm. A. Wulf, Evaluation of the WM architecture, Proceedings of the 19th annual international symposium on Computer architecture, p.382-390, May 19-21, 1992, Queensland, Australia
• 42: Yutao Zhong , Maksim Orlovich , Xipeng Shen , Chen Ding, Array regrouping and structure splitting using whole-program reference affinity, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

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

Keywords:
Dynamic binary rewriting, cache analysis, data trace compression, data trace generation, program instrumentation