Using Interaction Costs for Microarchitectural Bottleneck Analysis

ABSTRACT

Attacking bottlenecks in modern processors is difficultbecause many microarchitectural events overlap witheach other. This parallelism makes it difficult to both(a) assign a cost to an event (e.g., to one of two overlappingcache misses) and (b) assign blame for each cycle(e.g., for a cycle where many, overlapping resources areactive). This paper introduces a new model for understandingevent costs to facilitate processor design andoptimization.First, we observe that everything in a machine (instructions,hardware structures, events) can interact inonly one of two ways (in parallel or serially). Wequantify these interactions by defining interaction cost,which can be zero (independent, no interaction), positive(parallel), or negative (serial).Second, we illustrate the value of using interactioncosts in processor design and optimization.Finally, we propose performance-monitoring hardwarefor measuring interaction costs that is suitable formodern processors.

REFERENCES

• 1: Jennifer M. Anderson , Lance M. Berc , Jeffrey Dean , Sanjay Ghemawat , Monika R. Henzinger , Shun-Tak A. Leung , Richard L. Sites , Mark T. Vandevoorde , Carl A. Waldspurger , William E. Weihl, Continuous profiling: where have all the cycles gone?, ACM Transactions on Computer Systems (TOCS), v.15 n.4, p.357-390, Nov. 1997 [doi>10.1145/265924.265925]
• 2: Eric Borch , Srilatha Manne , Joel Emer , Eric Tune, Loose Loops Sink Chips, Proceedings of the 8th International Symposium on High-Performance Computer Architecture, p.299, February 02-06, 2002
• 3: Eric L. Boyd , Edward S. Davidson, Hierarchical performance modeling with MACS: a case study of the convex C-240, Proceedings of the 20th annual international symposium on Computer architecture, p.203-210, May 16-19, 1993, San Diego, California, United States
• 4: [4] D. C. Burger and T. M. Austin. The simplescalar tool set, version 2.0. Technical Report CS-TR-1997-1342, University of Wisconsin, Madison, Jun. 1997.
• 5: Brad Calder , Glenn Reinman , Dean M. Tullsen, Selective value prediction, Proceedings of the 26th annual international symposium on Computer architecture, p.64-74, May 01-04, 1999, Atlanta, Georgia, United States
• 6: [6] J. Casmira and D. Grunwald. Dynamic instruction scheduling slack. In Kool Chips Workshop in conjunction with MICRO 33, Dec. 2000.
• 7: [7] Intel Corporation. Intel Itanium 2 processor reference manual for software development and optimization. Apr. 2003.
• 8: [8] Intel Corporation. Intel Pentium 4 processor manual. In [http://developer.intel.com/design/pentium4/manuals/], 2003.
• 9: 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
• 10: Brian Fahs , Satarupa Bose , Matthew Crum , Brian Slechta , Francesco Spadini , Tony Tung , Sanjay J. Patel , Steven S. Lumetta, Performance characterization of a hardware mechanism for dynamic optimization, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 11: Brian Fields , Rastislav Bodík , Mark D. Hill, Slack: maximizing performance under technological constraints, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
• 12: Brian Fields , Shai Rubin , Rastislav Bodík, Focusing processor policies via critical-path prediction, Proceedings of the 28th annual international symposium on Computer architecture, p.74-85, June 30-July 04, 2001, Göteborg, Sweden
• 13: [13] B. R. Fisk and R. I. Bahar. The non-critical buffer: Using load latency tolerance to improve data cache efficiency. Oct. 1999.
• 14: [14] R. D. Fleischmann et al. Whole-genome random sequencing and assembly of haemophilus-influenzae. Science, 269:496- 512, 1995.
• 15: 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
• 16: John L. Hennessy , David A. Patterson, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 02
• 17: M. S. Hrishikesh , Doug Burger , Norman P. Jouppi , Stephen W. Keckler , Keith I. Farkas , Premkishore Shivakumar, The optimal logic depth per pipeline stage is 6 to 8 FO4 inverter delays, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
• 18: [18] Raj Jain. The Art of Computer Systems Performance Analysis. Wiley Professional Computing, 1991.
• 19: Mikko H. Lipasti , John Paul Shen, Exceeding the dataflow limit via value prediction, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.226-237, December 02-04, 1996, Paris, France
• 20: 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
• 21: Sanjay Jeram Patel , Marius Evers , Yale N. Patt, Improving trace cache effectiveness with branch promotion and trace packing, Proceedings of the 25th annual international symposium on Computer architecture, p.262-271, June 27-July 02, 1998, Barcelona, Spain
• 22: Ravi Rajwar , James R. Goodman, Speculative lock elision: enabling highly concurrent multithreaded execution, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 23: Deepak Limaye, Non-vital Loads, Proceedings of the 8th International Symposium on High-Performance Computer Architecture, p.165, February 02-06, 2002
• 24: [24] P. Ranganathan, K. Gharachorloo, S. V. Adve, and L. A. Barroso. Performance of database workloads on shared-memory systems with out-of-order processors. Oct. 1998.
• 25: M. Rosenblum , E. Bugnion , S. A. Herrod , E. Witchel , A. Gupta, The impact of architectural trends on operating system performance, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.285-298, December 03-06, 1995, Copper Mountain, Colorado, United States
• 26: Ruchira Sasanka , Christopher J. Hughes , Sarita V. Adve, Joint local and global hardware adaptations for energy, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 27: Greg Semeraro , Grigorios Magklis , Rajeev Balasubramonian , David H. Albonesi , Sandhya Dwarkadas , Michael L. Scott, Energy-Efficient Processor Design Using Multiple Clock Domains with Dynamic Voltage and Frequency Scaling, Proceedings of the 8th International Symposium on High-Performance Computer Architecture, p.29, February 02-06, 2002
• 28: John S. Seng , Eric S. Tune , Dean M. Tullsen, Reducing power with dynamic critical path information, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 29: John S. Seng , Eric S. Tune , Dean M. Tullsen, Reducing power with dynamic critical path information, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 30: Avinash Sodani , Gurindar S. Sohi, Dynamic instruction reuse, Proceedings of the 24th annual international symposium on Computer architecture, p.194-205, June 01-04, 1997, Denver, Colorado, United States
• 31: Eric Sprangle , Doug Carmean, Increasing processor performance by implementing deeper pipelines, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
• 32: Brinkley Sprunt, Pentium 4 Performance-Monitoring Features, IEEE Micro, v.22 n.4, p.72-82, July 2002 [doi>10.1109/MM.2002.1028478]
• 33: 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
• 34: Srikanth T. Srinivasan , Alvin R. Lebeck, Load latency tolerance in dynamically scheduled processors, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.148-159, November 1998, Dallas, Texas, United States
• 35: J. Greggory Steffan , Christopher B. Colohan , Antonia Zhai , Todd C. Mowry, A scalable approach to thread-level speculation, Proceedings of the 27th annual international symposium on Computer architecture, p.1-12, June 2000, Vancouver, British Columbia, Canada
• 36: Dongning Liang, Dynamic Prediction of Critical Path Instructions, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.185, January 20-24, 2001
• 37: Eric Tune , Dean M. Tullsen , Brad Calder, Quantifying Instruction Criticality, Proceedings of the 2002 International Conference on Parallel Architectures and Compilation Techniques, p.104, September 22-25, 2002
• 38: Joshua J. Yi , David J. Lilja , Douglas M. Hawkins, A Statistically Rigorous Approach for Improving Simulation Methodology, Proceedings of the 9th International Symposium on High-Performance Computer Architecture, p.281, February 08-12, 2003
• 39: Marco Zagha , Brond Larson , Steve Turner , Marty Itzkowitz, Performance analysis using the MIPS R10000 performance counters, Proceedings of the 1996 ACM/IEEE conference on Supercomputing (CDROM), p.16-es, January 01-01, 1996, Pittsburgh, Pennsylvania, United States [doi>10.1145/369028.369059]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Modeling of computer architecture

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

General Terms:
Design, Measurement, Performance