Decomposing memory performance: data structures and phases

ABSTRACT

The memory hierarchy continues to have a substantial effect on application performance. This paper explores the potential of high-level application understanding in improving the performance of modern memory hierarchies, decomposing the often-chaotic address stream of an application into multiple more regular streams. We present two orthogonal methodologies. The first is a system called DTrack that decomposes the dynamic reference stream of a C program by tagging each reference with its global variable or heap call-site name. The second is a technique to determine the correct granularity at which to study the global phase behavior of applications. Applying these twin analysis methods to twelve CSPEC2000 benchmarks, we demonstrate that they reveal data structure interactions that remain obscured with traditional aggregation-based analysis methods. Such a characterization creates a rich profile of an application's memory behavior that highlights the most memory-intensive data structures and program phases, and we illustrate how this profile can lead system and application designers to a deeper understanding of the applications they study.

REFERENCES

• 1: Santosh G. Abraham , Rabin A. Sugumar , Daniel Windheiser , B. R. Rau , Rajiv Gupta, Predictability of load/store instruction latencies, Proceedings of the 26th annual international symposium on Microarchitecture, p.139-152, December 01-03, 1993, Austin, Texas, United States
• 2: Murali Annavaram , Ryan Rakvic , Marzia Polito , Jean-Yves Bouguet , Richard A. Hankins , Bob Davies, The Fuzzy Correlation between Code and Performance Predictability, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.93-104, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.34]
• 3: D. Burger and T. M. Austin. The simplescalar tool set version 2.0. Technical Report 1342, Department of Computer Sciences, University of Wisconsin-Madison, June 1997.
• 4: 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
• 5: Robert Cooksey , Stephan Jourdan , Dirk Grunwald, A stateless, content-directed data prefetching mechanism, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 6: Rajagopalan Desikan , Doug Burger , Stephen W. Keckler, Measuring Experimental Error in Microprocessor Simulation, Proceedings of the 28th annual international symposium on Computer architecture, p.266-277, June 30-July 04, 2001, Göteborg, Sweden [doi>10.1145/379240.565338]
• 7: S. Z. Guyer, D. A. Jiménez, and C. Lin. The C-Breeze compiler infrastructure. Technical Report TR 01-43, Dept. of Computer Sciences, University of Texas at Austin, November 2001.
• 8: Ilkka J. Haikala , Petri H. Kutvonen, Split Cache Organizations, Proceedings of the Tenth International Symposium on Computer Performance Modelling, Measurement and Evaluation, p.459-472, December 19-21, 1984
• 9: Mark D. Hill, A Case for Direct-Mapped Caches, Computer, v.21 n.12, p.25-40, December 1988 [doi>10.1109/2.16187 ]
• 10: J. Lau, J. Sampson, E. Perelman, G. Hamerly, and B. Calder. The strong correlation between code signatures and performance. In Proceedings of the IEEE International Symposium on Performance Analysis of Systems and Software, March 2005.
• 11: J. Lau, S. Schoenmackers, and B. Calder. Structures for phase classification. In Proceedings of the IEEE International Symposiumon Performance Analysis of Systems and Software, March 2004.
• 12: 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 ]
• 13: 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
• 14: Kathryn S. McKinley , Olivier Temam, A quantitative analysis of loop nest locality, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.94-104, October 01-04, 1996, Cambridge, Massachusetts, United States
• 15: Priya Nagpurkar , Chandra Krintz , Michael Hind , Peter F. Sweeney , V. T. Rajan, Online Phase Detection Algorithms, Proceedings of the International Symposium on Code Generation and Optimization, p.111-123, March 26-29, 2006 [doi>10.1109/CGO.2006.26]
• 16: Amir Roth , Gurindar S. Sohi, Effective jump-pointer prefetching for linked data structures, Proceedings of the 26th annual international symposium on Computer architecture, p.111-121, May 01-04, 1999, Atlanta, Georgia, United States
• 17: Shai Rubin , Rastislav Bodík , Trishul Chilimbi, An efficient profile-analysis framework for data-layout optimizations, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.140-153, January 16-18, 2002, Portland, Oregon
• 18: Matthew L. Seidl , Benjamin G. Zorn, Segregating heap objects by reference behavior and lifetime, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.12-23, October 02-07, 1998, San Jose, California, United States
• 19: Timothy Sherwood , Erez Perelman , Brad Calder, Basic Block Distribution Analysis to Find Periodic Behavior and Simulation Points in Applications, Proceedings of the 2001 International Conference on Parallel Architectures and Compilation Techniques, p.3-14, September 08-12, 2001
• 20: Timothy Sherwood , Erez Perelman , Greg Hamerly , Brad Calder, Automatically characterizing large scale program behavior, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 21: Timothy Sherwood , Suleyman Sair , Brad Calder, Phase tracking and prediction, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 22: Alan Jay Smith, Second bibliography on Cache memories, ACM SIGARCH Computer Architecture News, v.19 n.4, p.154-182, June 1991 [doi>10.1145/122576.122592]
• 23: James E. Smith , Andrew R. Pleszkun, Implementing Precise Interrupts in Pipelined Processors, IEEE Transactions on Computers, v.37 n.5, p.562-573, May 1988 [doi>10.1109/12.4607 ]
• 24: Srikanth T. Srinivasan , Roy Dz-ching Ju , Alvin R. Lebeck , Chris Wilkerson, Locality vs. criticality, Proceedings of the 28th annual international symposium on Computer architecture, p.132-143, June 30-July 04, 2001, Göteborg, Sweden
• 25: Eric van der Deijl , Gerco Kanbier , Olivier Temam , Elena D. Granston, A Cache Visualization Tool, Computer, v.30 n.7, p.71-78, July 1997 [doi>10.1109/2.596631 ]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.8 Performance and Reliability

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques

General Terms:
Design, Experimentation, Measurement

Keywords:
CPU2000, DTrack, SPEC, data structure, phase, simulation