Accurate memory signatures and synthetic address traces for HPC applications

ABSTRACT

Though the performance of many scientific codes is dominated by memory behavior, our ability to describe, capture, compare, and recreate that behavior is quite limited. This inability underlies much of the complexity in the field of performance analysis: it is fundamentally difficult to relate benchmarks and applications or use realistic workloads to guide system design and procurement. An observable, reproducible, and machine-independent memory characterization is needed.

The Chameleon framework is a software suite that includes tools to capture a concise, machine-independent memory signature from any application and produce synthetic memory address traces that mimic that signature. By simultaneously modeling both spatial and temporal locality, Chameleon produces uniquely accurate, general-purpose synthetic traces. Our results demonstrate that the cache hit rates generated by each synthetic trace are nearly identical to those of the application it targets on dozens of memory hierarchies representing many of today's commercial offerings.

We apply the framework to high-performance computing (HPC) by leveraging sampling techniques to capture the memory signatures of full-scale, parallel applications with only a 5x slowdown. The overall result is therefore a concise, observable, and machine-independent representation of the memory requirements of full-scale applications that can be tractably captured and accurately mimicked.

REFERENCES

• 1: High Performance Computing Modernization Program: http://www.hpcmo.hpc.mil/.
• 2: http://www.npaci.edu/DataStar/guide/home.html.
• 3: RandomAccess benchmark: http://icl.cs.utk.edu/projectsfiles/hpcc/RandomAccess/.
• 4: Spec benchmarks: http://www.spec.org/.
• 5: Stream benchmark: http://www.cs.virginia.edu/stream/.
• 6: A. Agarwal , J. Hennessy , M. Horowitz, An analytical cache model, ACM Transactions on Computer Systems (TOCS), v.7 n.2, p.184-215, May 1989 [doi>10.1145/63404.63407]
• 7: Alfred V. Aho , Peter J. Denning , Jeffrey D. Ullman, Principles of Optimal Page Replacement, Journal of the ACM (JACM), v.18 n.1, p.80-93, Jan. 1971 [doi>10.1145/321623.321632]
• 8: George Almási , Cǎlin Caşcaval , David A. Padua, Calculating stack distances efficiently, Proceedings of the 2002 workshop on Memory system performance, p.37-43, June 16-16, 2002, Berlin, Germany
• 9: James Archibald , Jean-Loup Baer, Cache coherence protocols: evaluation using a multiprocessor simulation model, ACM Transactions on Computer Systems (TOCS), v.4 n.4, p.273-298, Nov. 1986 [doi>10.1145/6513.6514]
• 10: D. H. Bailey, E. Barszcz, J. T. Barton, D. S. Browning, R. L. Carter, D. Dagum, R. A. Fatoohi, P. O. Frederickson, T. A. Lasinski, R. S. Schreiber, H. D. Simon, V. Venkatakrishnan, and S. K. Weeratunga. The NAS Parallel Benchmarks. The International Journal of Supercomputer Applications, 5(3):63--73, Fall 1991.
• 11: E. Berg , E. Hagersten, StatCache: a probabilistic approach to efficient and accurate data locality analysis, Proceedings of the 2004 IEEE International Symposium on Performance Analysis of Systems and Software, p.20-27, March 10-12, 2004
• 12: Erik Berg , Erik Hagersten, Fast data-locality profiling of native execution, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 13: K. Beyls and E. D'Hollander. Reuse distance as a metric for cache behavior. In Proceedings of PDCS'01, pages 617--662, August 2001.
• 14: M. Brehob and R. Enbody. An analytical model of locality and caching. Technical Report MSU-CSE-99-31, Michigan State University, September 1999.
• 15: Richard B. Bunt , Jennifer M. Murphy, The measurement of locality and the behaviour of programs, The Computer Journal, v.27 n.3, p.238-253, Aug. 1984 [doi>10.1093/comjnl/27.3.238]
• 16: Laura C. Carrington , Michael Laurenzano , Allan Snavely , Roy L. Campbell , Larry P. Davis, How Well Can Simple Metrics Represent the Performance of HPC Applications?, Proceedings of the 2005 ACM/IEEE conference on Supercomputing, p.48, November 12-18, 2005 [doi>10.1109/SC.2005.33]
• 17: L. Carrington, N. Wolter, A. Snavely, and C. B. Lee. Applying an Automated Framework to Produce Accurate Blind Performance Predictions of Full-Scale HPC Applications. In Proceedings of the 2004 Department of Defense Users Group Conference. IEEE Computer Society Press, 2004.
• 18: R. Cheng and C. Ding. Measuring temporal locality variation across program inputs. Technical Report TR 875, University of Rochester. Computer Science Department., 2005.
• 19: Conte and Hwu. Benchmark characterization for experimental system evaluation. In Proceedings of the Twenty-Third Annual Hawaii International Conference on System Sciences, volume 1, pages 6--18, January 1990.
• 20: Peter J. Denning , Stuart C. Schwartz, Properties of the working-set model, Communications of the ACM, v.15 n.3, p.191-198, March 1972 [doi>10.1145/361268.361281]
• 21: 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
• 22: X. Gao, M. Laurenzano, B. Simon, and A. Snavely. Reducing overheads for acquiring dynamic traces. In International Symposium on Workload Characterization, 2005.
• 23: X. Gao, A. Snavely, and L. Carter. Path grammar guided trace compression and trace approximation. In HPDC'06: Proceedings of the 15th IEEE International Symposium on High Performance Distributed Computing, Paris, France, June 2006.
• 24: K. Grimsrud , J. Archibald , R. Frost , B. Nelson, On the accuracy of memory reference models, Proceedings of the 7th international conference on Computer performance evaluation : modelling techniques and tools: modelling techniques and tools, p.369-388, June 1994, Vienna, Austria
• 25: K. Grimsrud , J. Archibald , R. Frost , B. Nelson, Locality As a Visualization Tool, IEEE Transactions on Computers, v.45 n.11, p.1319-1326, November 1996 [doi>10.1109/12.544490]
• 26: R. Hassan, A. Harris, N. Topham, and A. Efthymiou. A hybrid markov model for accurate memory reference generation. In Proceedings of the IAENG International Conference on Computer Science. IAENG, 2007.
• 27: Rahman Hassan , Antony Harris , Nigel Topham , Aris Efthymiou, Synthetic Trace-Driven Simulation of Cache Memory, Proceedings of the 21st International Conference on Advanced Information Networking and Applications Workshops, p.764-771, May 21-23, 2007 [doi>10.1109/AINAW.2007.345]
• 28: D. J. Kerbyson , H. J. Alme , A. Hoisie , F. Petrini , H. J. Wasserman , M. Gittings, Predictive performance and scalability modeling of a large-scale application, Proceedings of the 2001 ACM/IEEE conference on Supercomputing (CDROM), p.37-37, November 10-16, 2001, Denver, Colorado [doi>10.1145/582034.582071]
• 29: Yul H. Kim , Mark D. Hill , David A. Wood, Implementing stack simulation for highly-associative memories, Proceedings of the 1991 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.212-213, May 21-24, 1991, San Diego, California, United States
• 30: Subhasis Laha, Accurate low-cost methods for performance evaluation of cache memory systems, University of Illinois, Department of Computer Science, Urbana, IL, 1988
• 31: S. Liu and J. Chen. The effect of product gas enrichment on the chemical response of premixed diluted methane/air flames. In Proceedings of the Third Joint Meeting of the U.S. Sections of the Combustion Institute, Chicago, Illinois, March 16-19 2003.
• 32: Chi-Keung Luk , Robert Cohn , Robert Muth , Harish Patil , Artur Klauser , Geoff Lowney , Steven Wallace , Vijay Janapa Reddi , Kim Hazelwood, Pin: building customized program analysis tools with dynamic instrumentation, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 33: P. Luszczek, J. Dongarra, D. Koester, R. Rabenseifner, B. Lucas, J. Kepner, J. McCalpin, D. Baily, and D. Takahashi. Introduction to the HPC Challenge Benchmark Suite, April 2005. Paper LBNL-57493.
• 34: 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
• 35: M. Mathis and D. J. Kerbyson. Performance modeling of mcnp on large-scale systems. In Proceedings of the LACSI Symposium, Los Alamos, NM, 2002. Los Alamos Computer Institute.
• 36: R. Mattson, J. Gecsei, D. Slutz, and I. Traiger. Evaluation Techniques for Storage Hierarchies. IBM System Journal, 9(2):78--117, 1970.
• 37: X. Shen, Y. Zhong, and C. Ding. Regression-based multi-model prediction of data reuse signature. In Proceedings of the 4th Annual Symposium of the Las Alamos Computer Science Institute, Sante Fe, New Mexico, November 2003.
• 38: Allan Snavely , Laura Carrington , Nicole Wolter , Jesus Labarta , Rosa Badia , Avi Purkayastha, A framework for performance modeling and prediction, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-17, November 16, 2002, Baltimore, Maryland
• 39: M. Snir and J. Yu. On the theory of spatial and temporal locality. Technical Report UIUCDCS-R-2005-2611, July 2005.
• 40: E. S. Sorenson. Using locality to predict cache performance. Master's thesis, Brigham Young University, 2001.
• 41: Elizabeth S. Sorenson , J. Kelly Flanagan, Cache characterization and performance studies using locality surfaces, Brigham Young University, Provo, UT, 2005
• 42: E. S. Sorenson , J. K. Flanagan, Cache characterization surfaces and predicting workload miss rates, Proceedings of the Workload Characterization, 2001. WWC-4. 2001 IEEE International Workshop, p.129-139, December 02-02, 2001 [doi>10.1109/WWC.2001.6]
• 43: E. S. Sorenson and J. K. Flanagan. Evaluating synthetic trace models using locality surfaces. In Proceedings of the Fifth IEEE Annual Workshop on Workload Characterization, pages 23--33, November 2002.
• 44: Jeffrey R. Spirn, Program Behavior: Models and Measurements, Elsevier Science Inc., New York, NY, 1977
• 45: Erich Strohmaier , Hongzhang Shan, Apex-Map: A Global Data Access Benchmark to Analyze HPC Systems and Parallel Programming Paradigms, Proceedings of the 2005 ACM/IEEE conference on Supercomputing, p.49, November 12-18, 2005 [doi>10.1109/SC.2005.13]
• 46: Rabin Andrew Sugumar, Multi-configuration simulation algorithms for the evaluation of computer architecture designs, University of Michigan, Ann Arbor, MI, 1993
• 47: Dominique Thiébaut, From the fractal dimension of the intermiss gaps to the cache-miss ratio, IBM Journal of Research and Development, v.32 n.6, p.796-803, November 1988
• 48: Dominique Thiébaut, On the Fractal Dimension of Computer Programs and its Application to the Prediction of the Cache Miss Ratio, IEEE Transactions on Computers, v.38 n.7, p.1012-1026, July 1989 [doi>10.1109/12.30852]
• 49: Joel L. Wolf , Harold S. Stone , Dominique Thiébaut, Synthetic Traces for Trace-Driven Simulation of Cache Memories, IEEE Transactions on Computers, v.41 n.4, p.388-410, April 1992 [doi>10.1109/12.135552]
• 50: Mustafa M Tikir , Laura Carrington , Erich Strohmaier , Allan Snavely, A genetic algorithms approach to modeling the performance of memory-bound computations, Proceedings of the 2007 ACM/IEEE conference on Supercomputing, November 10-16, 2007, Reno, Nevada [doi>10.1145/1362622.1362686]
• 51: M. Tikir, M. Laurenzano, L. Carrington, and A. Snavely. The PMaC binary instrumentation library for PowerPC. In Workshop on Binary Instrumentation and Applications, 2006.
• 52: Jonathan Weinberg , Michael O. McCracken , Erich Strohmaier , Allan Snavely, Quantifying Locality In The Memory Access Patterns of HPC Applications, Proceedings of the 2005 ACM/IEEE conference on Supercomputing, p.50, November 12-18, 2005 [doi>10.1109/SC.2005.59]
• 53: J. Weinberg and A. Snavely. Symbiotic space-sharing on sdsc's datastar system. In The 12th Workshop on Job Scheduling Strategies for Parallel Processing (JSSPP '06), St. Malo, France, June 2006.
• 54: J. Weinberg and A. Snavely. Chameleon: A framework for observing, understanding, and imitating the memory behavior of applications. In PARA08: Workshop on State-of-the-Art in Scientific and Parallel Computing, Trondheim, Norway, May, 2008.
• 55: Tong Wen , Jimmy Su , Phillip Colella , Katherine Yelick , Noel Keen, An adaptive mesh refinement benchmark for modern parallel programming languages, Proceedings of the 2007 ACM/IEEE conference on Supercomputing, November 10-16, 2007, Reno, Nevada [doi>10.1145/1362622.1362676]
• 56: Wing Shing Wong , Robert J. T. Morris, Benchmark Synthesis Using the LRU Cache Hit Function, IEEE Transactions on Computers, v.37 n.6, p.637-645, June 1988 [doi>10.1109/12.2202]
• 57: Y. Zhong, C. Ding, and K. Kennedy. Reuse distance analysis for scientific programs. In Proceedings of Workshop on Languages, Compilers, and Run-time Systems for Scalable Computers, Washington DC, March 2002.
• 58: 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: Complexity measures

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

General Terms:
Measurement, Performance

Keywords:
caches, hpc, locality, synthetic memory traces