Architectural and compiler support for effective instruction prefetching: a cooperative approach

ABSTRACT

Instruction cache miss latency is becoming an increasingly important performance bottleneck, especially for commercial applications. Although instruction prefetching is an attractive technique for tolerating this latency, we find that existing prefetching schemes are insufficient for modern superscalar processors, since they fail to issue prefetches early enough (particularly for nonsequential accesses). To overcome these limitations, we propose a new instruction prefetching technique whereby the hardware and software cooperate to hide the latency as follows. The hardware performs aggressive sequential prefetching combined with a novel prefetch filtering mechanism to allow it to get far ahead without polluting the cache. To hide the latency of nonsequential accesses, we propose and implement a novel compiler algorithm which automatically inserts instruction-prefetch the targets of control transfers far enough in advance. Our experimental results demonstrate that this new approach hides 50% or more tof the latecy remaining with the best previous techniques, while at the same time reduces the number of useless prefetches by a factor of six. We find that both the prefetch filtering and compiler-inserted prefetching components of our design are essential and complementary, and that the compiler can limit the code expansion to only 9% on average. In addition, we show that the performance of our technique can be further increased by using profiling information to help reduce cache conflicts and unnecessary prefetches. From an architectural perspective, these performance advantages are sustained over a range of common miss latencies and bandwidth. Finally, our technique is cost effective as well, since it delivers performance comparable to (or even better than) that of larger caches, but requires a much smaller hardware budget.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Iris Bahar , Brad Calder , Dirk Grunwald, A comparison of software code reordering and victim buffers, ACM SIGARCH Computer Architecture News, v.27 n.1, p.51-54, March 1999 [doi>10.1145/309758.309781]
• 3: David Bernstein , Doron Cohen , Ari Freund, Compiler techniques for data prefetching on the PowerPC, Proceedings of the IFIP WG10.3 working conference on Parallel architectures and compilation techniques, p.19-26, June 27-29, 1995, Limassol, Cyprus
• 4: Po-Yung Chang , Eric Hao , Yale N. Patt, Target prediction for indirect jumps, Proceedings of the 24th annual international symposium on Computer architecture, p.274-283, June 01-04, 1997, Denver, Colorado, United States
• 5: Karel Driesen , Urs Hölzle, Accurate indirect branch prediction, Proceedings of the 25th annual international symposium on Computer architecture, p.167-178, June 27-July 02, 1998, Barcelona, Spain
• 6: Karel Driesen , Urs Hölzle, The cascaded predictor: economical and adaptive branch target prediction, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.249-258, November 1998, Dallas, Texas, United States
• 7: Nikolas Gloy , Trevor Blackwell , Michael D. Smith , Brad Calder, Procedure placement using temporal ordering information, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.303-313, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 8: Dirk Grunwald , Artur Klauser , Srilatha Manne , Andrew Pleszkun, Confidence estimation for speculation control, Proceedings of the 25th annual international symposium on Computer architecture, p.122-131, June 27-July 02, 1998, Barcelona, Spain
• 9: Amir H. Hashemi , David R. Kaeli , Brad Calder, Efficient procedure mapping using cache line coloring, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.171-182, June 16-18, 1997, Las Vegas, Nevada, United States
• 10: W. W. Hwu , P. P. Chang, Achieving high instruction cache performance with an optimizing compiler, Proceedings of the 16th annual international symposium on Computer architecture, p.242-251, April 1989, Jerusalem, Israel
• 11: Doug Joseph , Dirk Grunwald, Prefetching using Markov predictors, Proceedings of the 24th annual international symposium on Computer architecture, p.252-263, June 01-04, 1997, Denver, Colorado, United States
• 12: 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
• 13: Gerry Kane , Joe Heinrich, MIPS RISC architectures, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 14: Ann Marie Grizzaffi Maynard , Colette M. Donnelly , Bret R. Olszewski, Contrasting characteristics and cache performance of technical and multi-user commercial workloads, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.145-156, October 05-07, 1994, San Jose, California, United States
• 15: 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
• 16: Robert Muth , Saumya K. Debray , Scott Watterson , Koen De Bosschere, Alto: a link-time optimizer for the Compaq alpha, Software—Practice & Experience, v.31 n.1, p.67-101, Jan. 2001 [doi>10.1002/1097-024X(200101)31:1<67::AID-SPE357>3.0.CO;2-A]
• 17: Karl Pettis , Robert C. Hansen, Profile guided code positioning, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.16-27, June 1990, White Plains, New York, United States
• 18: Jim Pierce , Trevor Mudge, Wrong-path instruction prefetching, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.165-175, December 02-04, 1996, Paris, France
• 19: Glenn Reinman , Brad Calder , Todd Austin, Fetch directed instruction prefetching, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.16-27, November 16-18, 1999, Haifa, Israel
• 20: Glenn Reinman , Todd Austin , Brad Calder, A scalable front-end architecture for fast instruction delivery, Proceedings of the 26th annual international symposium on Computer architecture, p.234-245, May 01-04, 1999, Atlanta, Georgia, United States
• 21: Vatsa Santhanam , Edward H. Gornish , Wei-Chung Hsu, Data prefetching on the HP PA-8000, Proceedings of the 24th annual international symposium on Computer architecture, p.264-273, June 01-04, 1997, Denver, Colorado, United States
• 22: SMITH, A. 1978. Sequential program prefetching in memory hierarchies. IEEE Computer 11, 2, 7-21.
• 23: Alan Jay Smith, Cache Memories, ACM Computing Surveys (CSUR), v.14 n.3, p.473-530, Sept. 1982 [doi>10.1145/356887.356892]
• 24: J. E. Smith , W.-C. Hsu, Prefetching in supercomputer instruction caches, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.588-597, November 16-20, 1992, Minneapolis, Minnesota, United States
• 25: Jared Stark , Paul Racunas , Yale N. Patt, Reducing the performance impact of instruction cache misses by writing instructions into the reservation stations out-of-order, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.34-43, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 26: WEBB, C. F. 1988. Subroutine call/Return stack. IBM Tech. Discl. Bull. 30, 11 (Apr.).
• 27: Chun Xia , Josep Torrellas, Instruction prefetching of systems codes with layout optimized for reduced cache misses, Proceedings of the 23rd annual international symposium on Computer architecture, p.271-282, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 28: Kenneth C. Yeager, The MIPS R10000 Superscalar Microprocessor, IEEE Micro, v.16 n.2, p.28-40, April 1996 [doi>10.1109/40.491460]
• 29: YU, A. AND CHEN, J. 1996. The Postgres95 User Manual v1.0. University of California at Berkeley, Berkeley, CA.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

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

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

General Terms:
Design, Experimentation, Performance

Keywords:
compiler optimization, instruction prefetching