Detailed cache simulation for detecting bottleneck, miss reason and optimization potentialities

ABSTRACT

Cache locality optimization is an efficient way for reducing the idle time of modern processors in waiting for needed data. This kind of optimization can be achieved either on the side of programmers or compilers with code level optimization or at system level through appropriate schemes, like reconfigurable cache organization and adequate prefetching or replacement strategies. For the former users need to know the problem, the reason, and the solution, while for the latter a platform is required for evaluating proposed and novel approaches.As existing simulation systems do not provide such information and platforms, we implemented a cache simulator that models the complete cache hierarchy and associated techniques. More specifically, it analyzes the feature of cache miss and provides information about the runtime accesses to data structures and the cache access behavior. Together with a visualization tool, this information enables the user to detect access hotspots and optimization strategies for tackling them. For supporting the study of different techniques with respect to cache configuration and management, this simulator models a variety of cache line replacement and prefetching policies, and allows the user to specify any cache organization, including cache size, cache set size, block size, and associativity. The simulator hence forms a research platform for investigating the influence of these techniques on the execution behavior of applications.

REFERENCES

• 1: Todd Austin , Eric Larson , Dan Ernst, SimpleScalar: An Infrastructure for Computer System Modeling, Computer, v.35 n.2, p.59-67, February 2002 [doi>10.1109/2.982917]
• 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: D. B. et. al. The NAS Parallel Benchmarks. Technical Report RNR-94-007, Department of Mathematics and Computer Science, Emory University, March 1994.
• 4: John L. Henning, SPEC CPU2000: Measuring CPU Performance in the New Millennium, Computer, v.33 n.7, p.28-35, July 2000 [doi>10.1109/2.869367]
• 5: Stephen Alan Herrod , Mendel Rosenblum, Using complete machine simulation to understand computer system behavior, 1998
• 6: Hung-Chang Hsiao , Chung-Ta King, MICA: A Memory and Interconnect Simulation Environment for Cache-Based Architectures, Proceedings of the 33rd Annual Simulation Symposium, p.317, April 16-22, 2000
• 7: Intel Corporation. Intel Itanium Architecture Software Developer's Manual, volume 1--3. 2002. available at http://developer.intel.com/design/itanium/manuals/iiasdmanual.htm.
• 8: Teresa L. Johnson , Matthew C. Merten , Wen-Mei W. Hwu, Run-time spatial locality detection and optimization, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.57-64, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 9: P. Magnusson , B. Werner, Efficient memory simulation in SimICS, Proceedings of the 28th Annual Simulation Symposium, p.62, April 25-28, 1995
• 10: 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]
• 11: Shubhendu S. Mukherjee , Steven K. Reinhardt , Babak Falsafi , Mike Litzkow , Mark D. Hill , David A. Wood , Steven Huss-Lederman , James R. Larus, Wisconsin Wind Tunnel II: A Fast, Portable Parallel Architecture Simulator, IEEE Concurrency, v.8 n.4, p.12-20, October 2000 [doi>10.1109/4434.895100]
• 12: Anthony-Trung Nguyen , Maged Michael , Arun Sharma , Josep Torrella, The Augmint multiprocessor simulation toolkit for Intel x86 architectures, Proceedings of the 1996 International Conference on Computer Design, VLSI in Computers and Processors, p.486, October 07-09, 1996
• 13: V. S. Pai, P. Ranganathan, and S. V. Adve. RSIM: An Execution-Driven Simulator for ILP-Based Shared-Memory Multiprocessors and Uniprocessors. In Proceedings of the Third Workshop on Computer Architecture Education, February 1997.
• 14: B. Quaing, J. Tao, and W. Karl. YACO: A User Conducted Visualization Tool for Supporting Cache Optimization. In High Performance Computing and Communications: First International Conference, HPCC 2005. Proceedings, volume 3726 of Lecture Notes in Computer Science, pages 694--703, Sorrento, Italy, September 2005.
• 15: Gabriel Rivera , Chau-Wen Tseng, Data transformations for eliminating conflict misses, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.38-49, June 17-19, 1998, Montreal, Quebec, Canada
• 16: E. H. Welbon , C. C. Chan-Nui , D. J. Shippy , D. A. Hicks, The POWER2 performance monitor, IBM Journal of Research and Development, v.38 n.5, p.545-554, Sept. 1994
• 17: Steven Cameron Woo , Moriyoshi Ohara , Evan Torrie , Jaswinder Pal Singh , Anoop Gupta, The SPLASH-2 programs: characterization and methodological considerations, Proceedings of the 22nd annual international symposium on Computer architecture, p.24-36, June 22-24, 1995, S. Margherita Ligure, Italy
• 18: WWW.Cachegrind: a cache-miss profiler. available at http://developer.kde.org/sewardj/docs-2.2.0/cg_main.html#cg-top.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES

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

General Terms:
Performance

Keywords:
cache simulation, code optimization, performance visualization