Pipeline spectroscopy

ABSTRACT

Pipeline Spectroscopy is a new technique that allows us 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 characteristics of the processor's memory hierarchy, the pipeline, and the miss pattern itself. We show that in a memory hierarchy with N cache levels (L1, L2, ..., LN, and memory) and a miss cluster of size C, there are (C+N/C) possible miss penalties. This represent all possible sums from all possible combinations of the miss latencies from each level of the memory hierarchy (L2, L3, ... Memory) for a given cluster size. Additionally, a theory is presented that describes the shape of a spectrogram, and we use this theory to predict the shape of spectrograms for larger miss clusters. Detailed analysis of a spectrograph leads to much greater insight in pipeline dynamics, including effects due to prefetching, and miss queueing delays.

REFERENCES

• 1: A. Glew, "MLP yes! ILP no!," in ASPLOS Wild and Crazy Idea 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: 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
• 18: 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]
• 19: 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
• 20: A. Hartstein , Thomas R. Puzak, The optimum pipeline depth for a microprocessor, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
• 21: 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
• 22: Peter J. Denning, The working set model for program behavior, Communications of the ACM, v.11 n.5, p.323-333, May 1968 [doi>10.1145/363095.363141]
• 23: R. Bartoszynski, M Niewiadomska-Bugaj, Probability and Statistical Inference, (Wiley series in probability and statistics) 1996
• 24: J. S. Liptay, Design of the IBM Enterprise System/9000 high-end processor, IBM Journal of Research and Development, v.36 n.4, p.713-731, July 1992
• 25: D. B. Fite, J. E. Murray, D. P. Manley, M. M. McKeon, E. H. Fite, R. M. Salett, and T. Fossum, "Branch Prediction," U.S. Patent #5142634, assigned to Digital Equipment Corporation, Filed Feb. 3, 1989, Issued Aug. 25, 1992.
• 26: N. Suzuki, "Microprocessor Having Branch Prediction Function," U.S. Patent #5327536, assigned to NEC Corporation, Filed May 22, 1991, Issued July 5, 1994.
• 27: C. H. Perleberg , A. J. Smith, Branch Target Buffer Design and Optimization, IEEE Transactions on Computers, v.42 n.4, p.396-412, April 1993 [doi>10.1109/12.214687]
• 28: B. Calder , D. Grunwald, Fast and accurate instruction fetch and branch prediction, Proceedings of the 21st annual international symposium on Computer architecture, p.2-11, April 18-21, 1994, Chicago, Illinois, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features

General Terms:
Algorithms, Measurement, Performance, Theory

Keywords:
cache, convex combination, cost of a miss, probability transition matrix