Informing memory operations: providing memory performance feedback in modern processors

ABSTRACT

Memory latency is an important bottleneck in system performance that cannot be adequately solved by hardware alone. Several promising software techniques have been shown to address this problem successfully in specific situations. However, the generality of these software approaches has been limited because current architectures do not provide a fine-grained, low-overhead mechanism for observing and reacting to memory behavior directly. To fill this need, we propose a new class of memory operations called informing memory operations, which essentially consist of a memory operation combined (either implicitly or explicitly) with a conditional branch-and-link operation that is taken only if the reference suffers a cache miss. We describe two different implementations of informing memory operations---one based on a cache-outcome condition code and another based on low-overhead traps---and find that modern in-order-issue and out-of-order-issue superscalar processors already contain the bulk of the necessary hardware support. We describe how a number of software-based memory optimizations can exploit informing memory operations to enhance performance, and look at cache coherence with fine-grained access control as a case study. Our performance results demonstrate that the runtime overhead of invoking the informing mechanism on the Alpha 21164 and MIPS R10000 processors is generally small enough to provide considerable flexibility to hardware and software designers, and that the cache coherence application has improved performance compared to other current solutions. We believe that the inclusion of informing memory operations in future processors may spur even more innovative performance optimizations.

REFERENCES

• ABC+95: Anant Agarwal , Ricardo Bianchini , David Chaiken , Kirk L. Johnson , David Kranz , John Kubiatowicz , Beng-Hong Lim , Kenneth Mackenzie , Donald Yeung, The MIT Alewife machine: architecture and performance, Proceedings of the 22nd annual international symposium on Computer architecture, p.2-13, June 22-24, 1995, S. Margherita Ligure, Italy
• ACC+90: Robert Alverson , David Callahan , Daniel Cummings , Brian Koblenz , Allan Porterfield , Burton Smith, The Tera computer system, Proceedings of the 4th international conference on Supercomputing, p.1-6, June 11-15, 1990, Amsterdam, The Netherlands
• AKK+93: Anant Agarwal , John Kubiatowicz , David Kranz , Beng-Hong Lim , Donald Yeung , Godfrey D'Souza , Mike Parkin, Sparcle: An Evolutionary Processor Design for Large-Scale Multiprocessors, IEEE Micro, v.13 n.3, p.48-61, May 1993 [doi>10.1109/40.216748]
• AKL79: W. Abu-Sufah, D. J. Kuck, and D. H. Lawrie. Automatic Program Transformations for Virtual Memory Computers. Proc. 1979 National Computer Conf. pp 969-974, June 1979.
• BLA+94: M. A. Blumrich , K. Li , R. Alpert , C. Dubnicki , E. W. Felten , J. Sandberg, Virtual memory mapped network interface for the SHRIMP multicomputer, Proceedings of the 21ST annual international symposium on Computer architecture, p.142-153, April 18-21, 1994, Chicago, Illinois, United States
• BLRC94: Brian N. Bershad , Dennis Lee , Theodore H. Romer , J. Bradley Chen, Avoiding conflict misses dynamically in large direct-mapped caches, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.158-170, October 05-07, 1994, San Jose, California, United States
• BM89: H. Burkhart , R. Millen, Performance-Measurement Tools in a Multiprocessor Environment, IEEE Transactions on Computers, v.38 n.5, p.725-737, May 1989 [doi>10.1109/12.24274]
• CDV+94: Rohit Chandra , Scott Devine , Ben Verghese , Anoop Gupta , Mendel Rosenblum, Scheduling and page migration for multiprocessor compute servers, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.12-24, October 05-07, 1994, San Jose, California, United States
• CMCH91: William Y. Chen , Scott A. Mahlke , Pohua P. Chang , Wen-mei W. Hwu, Data access microarchitectures for superscalar processors with compiler-assisted data prefetching, Proceedings of the 24th annual international symposium on Microarchitecture, p.69-73, September 1991, Albuquerque, New Mexico, Puerto Rico [doi>10.1145/123465.123478]
• CMM+88: R. C. Covington , S. Madala , V. Mehta , J. R. Jump , J. B. Sinclair, The rice parallel processing testbed, Proceedings of the 1988 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.4-11, May 24-27, 1988, Santa Fe, New Mexico, United States
• Dix92: Kaivalya M. Dixit, New CPU benchmark suites from SPEC, Proceedings of the thirty-seventh international conference on COMPCON, p.305-310, January 1992, San Francisco, California, United States
• DBKF90: J. J. Dongarra , Orlie Brewer , James Arthur Kohl , Samuel Fineberg, A tool to aid in the design, implementation, and understanding of matrix algorithms for parallel processors, Journal of Parallel and Distributed Computing, v.9 n.2, p.185-202, June 1990 [doi>10.1016/0743-7315(90)90045-Q]
• DEC92: Digital Equipment Corp. DECChip 21064 RISC Microprocessor Preliminary Data Sheet. Technical report, 1992.
• ECGS92: Thorsten von Eicken , David E. Culler , Seth Copen Goldstein , Klaus Erik Schauser, Active messages: a mechanism for integrated communication and computation, Proceedings of the 19th annual international symposium on Computer architecture, p.256-266, May 19-21, 1992, Queensland, Australia
• ERB+95: John H. Edmondson , Paul I. Rubinfeld , Peter J. Bannon , Bradley J. Benschneider , Debra Bernstein , Ruben W. Castelino , Elizabeth M. Cooper , Daniel E. Dever , Dale R. Donchin , Timothy C. Fischer , Anil K. Jain , Shekhar Mehta , Jeanne E. Meyer , Ronald P. Preston , Vidya Rajagopalan , Chandrasekhara Somanathan , Scott A. Taylor , Gilbert M. Wolrich, Internal organization of the Alpha 21164, a 300-MHz 64-bit quad-issue CMOS RISC microprocessor, Digital Technical Journal, v.7 n.1, p.119-135, Jan. 1995
• FJ94: K. I. Farkas , N. P. Jouppi, Complexity/performance tradeoffs with non-blocking loads, Proceedings of the 21ST annual international symposium on Computer architecture, p.211-222, April 18-21, 1994, Chicago, Illinois, United States
• GH93: A. J. Goldberg , J. L. Hennessy, Mtool: An Integrated System for Performance Debugging Shared Memory Multiprocessor Applications, IEEE Transactions on Parallel and Distributed Systems, v.4 n.1, p.28-40, January 1993 [doi>10.1109/71.205651]
• GJMS87: K. Gallivan, W. Jalby, U. Meier, and A. Sameh. The Impact of Hierarchical Memory Systems on Linear Algebra Algorithm Design. Technical Report UIUCSRD 625, Univ. of Illinois, 1987.
• HMMS95: Mark Horowitz , Margaret Martonosi , Todd C. Mowry , Michael D. Smith, Informing Loads: Enabling Software to Observe and React to Memory Behavior, Stanford University, Stanford, CA, 1995
• JHei95: Joe Heinrich. MIPS R10000 Microprocessor User's Manual. 1995.
• Jou90: Norman P. Jouppi, Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers, Proceedings of the 17th annual international symposium on Computer Architecture, p.364-373, May 28-31, 1990, Seattle, Washington, United States
• KOH+94: J. Kuskin , D. Ofelt , M. Heinrich , J. Heinlein , R. Simoni , K. Gharachorloo , J. Chapin , D. Nakahira , J. Baxter , M. Horowitz , A. Gupta , M. Rosenblum , J. Hennessy, The Stanford FLASH multiprocessor, Proceedings of the 21ST annual international symposium on Computer architecture, p.302-313, April 18-21, 1994, Chicago, Illinois, United States
• LGH94: James Laudon , Anoop Gupta , Mark Horowitz, Interleaving: a multithreading technique targeting multiprocessors and workstations, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.308-318, October 05-07, 1994, San Jose, California, United States
• LW94: Alvin R. Lebeck , David A. Wood, Cache Profiling and the SPEC Benchmarks: A Case Study, Computer, v.27 n.10, p.15-26, October 1994 [doi>10.1109/2.318580]
• Mat94: Terje Mathison. Pentium Secrets. Byte, pp 191-192, July 1994.
• MGA95: 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]
• MLG92: Todd C. Mowry , Monica S. Lam , Anoop Gupta, Design and evaluation of a compiler algorithm for prefetching, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.62-73, October 12-15, 1992, Boston, Massachusetts, United States
• NAB+94: A. Nowatzyk, G. Aybay, M. Browne, et al. The S3.mp Scalable Shared Memory Multiprocessor. Proc. 27th Hawaii Intl. Conf. on System Sciences Vol. I: Architecture. pp 144-53. Jan, 1994.
• Pau94: Richard P. Paul, SPARC architecture, assembly language programming, and C, Prentice-Hall, Inc., Upper Saddle River, NJ, 1994
• Por89: Allan Kennedy Porterfield , K. W. Kennedy, Software methods for improvement of cache performance on supercomputer applications, 1989
• RLW94: S. K. Reinhardt , J. R. Larus , D. A. Wood, Tempest and typhoon: user-level shared memory, Proceedings of the 21ST annual international symposium on Computer architecture, p.325-336, April 18-21, 1994, Chicago, Illinois, United States
• SFL+94: Ioannis Schoinas , Babak Falsafi , Alvin R. Lebeck , Steven K. Reinhardt , James R. Larus , David A. Wood, Fine-grain access control for distributed shared memory, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.297-306, October 05-07, 1994, San Jose, California, United States
• SG94: A. Singhal , A. J. Goldberg, Architectural support for performance tuning: a case study on the SPARCcenter 2000, Proceedings of the 21ST annual international symposium on Computer architecture, p.48-59, April 18-21, 1994, Chicago, Illinois, United States
• Smi81: B. J. Smith. Architecture and Applications of the HEP Multiprocessor Computer System. SPIE Real-Time Signal Processing IV, Vol. 298, 1981.
• TE94: Radhika Thekkath , Susan J. Eggers, The effectiveness of multiple hardware contexts, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.328-337, October 05-07, 1994, San Jose, California, United States
• TL94: Chandramohan A. Thekkath , Henry M. Levy, Hardware and software support for efficient exception handling, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.110-119, October 05-07, 1994, San Jose, California, United States
• WL91: Michael E. Wolf , Monica S. Lam, A data locality optimizing algorithm, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.30-44, June 24-28, 1991, Toronto, Ontario, Canada

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

  D. Software
  D.4 OPERATING SYSTEMS

General Terms:
Design, Experimentation, Measurement, Performance, Theory