An analysis of the effects of miss clustering on the cost of a cache miss

ABSTRACT

In this paper we describe a new technique, called pipeline spectroscopy, and use it to measure the cost of each cache miss. The cost of a miss is displayed (graphed) as a histogram, which represents a precise readout showing a detailed visualization of the cost of each cache miss throughout all levels of the memory hierarchy. We call the graphs 'spectrograms' because they reveal certain signature features of the processor's memory hierarchy, the pipeline, and the miss pattern itself. Next we provide two examples that use spectroscopy to optimize the processor's hardware or application's software. The first example demonstrates how a miss spectrogram can aid software designers in analyzing the performance of an application. The second example uses a miss spectrogram to analyze bus queueing. Our experiments show that performance gains of up to 8% are possible. Detailed analysis of a spectrogram leads to much greater insight in pipeline dynamics, including effects due to miss cluster, miss overlap, prefetching, and miss queueing delays.

REFERENCES

• 1: A. Glew, "MLP yes! ILP no!," in ASPLOS Wild and Crazy Ideas Session , October 1998.
• 2: Vijay S. Pai , Sarita Adve, Code transformations to improve memory parallelism, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.147-155, November 16-18, 1999, Haifa, Israel
• 3: Huiyang Zhou , Thomas M. Conte, Enhancing memory level parallelism via recovery-free value prediction, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA [doi>10.1145/782814.782859]
• 4: Daniel J. Sorin , Vijay S. Pai , Sarita V. Adve , Mary K. Vernon , David A. Wood, Analytic evaluation of shared-memory systems with ILP processors, Proceedings of the 25th annual international symposium on Computer architecture, p.380-391, June 27-July 02, 1998, Barcelona, Spain
• 5: Vijay S. Pai , Parthasarathy Ranganathan , Sarita V. Adve, The Impact of Instruction-Level Parallelism on Multiprocessor Performance and Simulation Methodology, Proceedings of the 3rd IEEE Symposium on High-Performance Computer Architecture, p.72, February 01-05, 1997
• 6: Parthasarathy Ranganathan , Kourosh Gharachorloo , Sarita V. Adve , Luiz André Barroso, Performance of database workloads on shared-memory systems with out-of-order processors, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.307-318, October 02-07, 1998, San Jose, California, United States
• 7: Yuan Chou , Brian Fahs , Santosh Abraham, Microarchitecture Optimizations for Exploiting Memory-Level Parallelism, Proceedings of the 31st annual international symposium on Computer architecture, p.76, June 19-23, 2004, München, Germany
• 8: Yuan Chou , Lawrence Spracklen , Santosh G. Abraham, Store Memory-Level Parallelism Optimizations for Commercial Applications, Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture, p.183-196, November 12-16, 2005, Barcelona, Spain [doi>10.1109/MICRO.2005.31]
• 9: Moinuddin K. Qureshi , Daniel N. Lynch , Onur Mutlu , Yale N. Patt, A Case for MLP-Aware Cache Replacement, Proceedings of the 33rd annual international symposium on Computer Architecture, p.167-178, June 17-21, 2006
• 10: A. Zahir, V. Hummel, M. Kling, T Yeh, US. Patent 6,353,802, "Apparatus and Method for Cycle Accounting in Microprocessors".
• 11: B. Gaither, R. Smith, US Patent 6,892,173 B1, "Analyzing Effectiveness of a Computer Cache By Estimating a Hit Rate Based on Applying a Subset of Real-time Addresses to a Model of the Cache".
• 12: H. Ravichandran, US Patent 6,341,357 B1, "Apparatus and Method for Processor Performance Monitoring".
• 13: R. Trauben, US Patent 5,594,864, "Method and apparatus for unobtrusively monitoring Processor States and Characterizing Bottlenecks in a Pipeline Processor Executing Grouped Instructions".
• 14: G. Brooks, US Patent 5,845,310 "System and Methods For Performing Cache Latency Diagnostics in Scalable Parallel Processing Architectures Including Calculating CPU Idle Time and Counting Number of Cache Misses.
• 15: W. Flynn, US Patent 6,256,775 B1, "Facilities For Detailed Software Performance Analysis in a Multithreaded Processor".
• 16: F. Levine, B. McCredie, W. Starke, E. Welbon, US Patent 5,862,371, "Method and System for Instruction Trace Reconstruction Utilizing Performance monitor outputs and bus Monitoring".
• 17: F. Levine, B. McCredie, W. Starke, E. Welbon, US Patent 5,894,575 "Method and System for Initial State Determination for Instruction Trace Reconstruction.
• 18: Jeffrey Dean , James E. Hicks , Carl A. Waldspurger , William E. Weihl , George Chrysos, ProfileMe: hardware support for instruction-level profiling on out-of-order processors, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.292-302, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 19: Brian A. Fields , Rastislav Bodik , Mark D. Hill , Chris J. Newburn, Interaction cost and shotgun profiling, ACM Transactions on Architecture and Code Optimization (TACO), v.1 n.3, p.272-304, September 2004 [doi>10.1145/1022969.1022971]
• 20: Tejas S. Karkhanis , James E. Smith, A First-Order Superscalar Processor Model, Proceedings of the 31st annual international symposium on Computer architecture, p.338, June 19-23, 2004, München, Germany
• 21: A. Hartstein and T. Puzak. The optimum pipeline depth for a microprocessor, 29th International Symposium on Microarchitecture, pages 7--13 May 2002.
• 22: A. Hartstein , Thomas R. Puzak, Optimum Power/Performance Pipeline Depth, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.117, December 03-05, 2003
• 23: Thomas R. Puzak , A. Hartstein , P. G. Emma , V. Srinivasan, When prefetching improves/degrades performance, Proceedings of the 2nd conference on Computing frontiers, May 04-06, 2005, Ischia, Italy [doi>10.1145/1062261.1062317]
• 24: Philip G. Emma , Allan Hartstein , Thomas R. Puzak , Vijayalakshmi Srinivasan, Exploring the limits of prefetching, IBM Journal of Research and Development, v.49 n.1, p.127-144, January 2005
• 25: US Patent 5,636,364 Method for enabling concurrent misses in a cache memory.
• 26: US Patent 5,233,702 Cache miss facility with stored sequences for data fetching.
• 27: IBM Technical Disclosure Bulletin, ""A Protocol for Processing Concurrent Misses"", Dec. 1993, vol. 36 No. 12.
• 28: IBM Technical Disclosure Bulletin, vol. ""Design for Improved Cache Performance via Overlapping of Cache Miss Sequences"" vol. 25 No. 1B Apr. 1983 pp. 5962--5966.
• 29: R. Bartoszynski, M Niewiadomska-Bugaj,Probability and Statistical Inference, (Wiley series in probability and statistics) 1996.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques; Modeling techniques; Performance attributes

General Terms:
Algorithms, Measurement, Performance

Keywords:
algorithm, cache, pipeline, spectrogram