Trace preconstruction

ABSTRACT

Trace caches enable high bandwidth, low latency instruction supply, but have a high miss penalty and relatively large working sets. Consequently, their performance may suffer due to capacity and compulsory misses. Trace preconstruction augments a trace cache by performing a function analogous to prefetching. The trace preconstruction mechanism observes the processor's instruction dispatch stream to detect opportunities for jumping ahead of the processor. After doing so, the preconstruction mechanism fetches static instructions from the predicted future region of the program, and constructs a set of traces in advance of when they are needed. Trace preconstruction can significantly increase both the performance of the trace cache and the robustness of the trace cache to varying workloads. All but one of the SPECint95 benchmarks see a notable reduction in trace cache miss rates from preconstruction. The three benchmarks that have the largest working set (gee, go and vortex) see a 30% to 80% reduction in trace cache misses. We also consider the integration of preconstruction with another trace-specific mechanism (preprocessing) to produce a high performance frontend. When combined, preconstruction and trace preprocessing produce an average speedup of 14% for the SPECint95 benchmarks.

REFERENCES

• 1: Haitham Akkary , Michael A. Driscoll, A dynamic multithreading processor, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.226-236, November 1998, Dallas, Texas, United States
• 2: D. Burger, T. Austin and S. Bennett, "Evaluating Future Microprocessors: The SimpleScalar Tool Set," University of Wisconsin- Madison Technical Report #1308, July 1996.
• 3: Manoj Franklin , Gurindar S. Sohi, ARB: A Hardware Mechanism for Dynamic Reordering of Memory References, IEEE Transactions on Computers, v.45 n.5, p.552-571, May 1996 [doi>10.1109/12.509907]
• 4: Daniel Holmes Friendly , Sanjay Jeram Patel , Yale N. Patt, Putting the fill unit to work: dynamic optimizations for trace cache microprocessors, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.173-181, November 1998, Dallas, Texas, United States
• 5: Anoop Gupta , John Hennessy , Kourosh Gharachorloo , Todd Mowry , Wolf-Dietrich Weber, Comparative evaluation of latency reducing and tolerating techniques, Proceedings of the 18th annual international symposium on Computer architecture, p.254-263, May 27-30, 1991, Toronto, Ontario, Canada
• 6: Quinn Able Jacobson , James E. Smith, High-performance frontends for trace processors, 1999
• 7: Quinn Jacobson , Eric Rotenberg , James E. Smith, Path-based next trace prediction, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.14-23, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 8: Q. Jacobson , J. E. Smith, Instruction Pre-Processing in Trace Processors, Proceedings of the 5th International Symposium on High Performance Computer Architecture, p.125, January 09-12, 1999
• 9: S. Patel, D. Friendly and Y. Patt, "Critical Issues Regarding the Trace Cache Fetch Mechanism." University of Michigan Technical Report CSE-TR- 335-97, 1997.
• 10: Eric Rotenberg , Steve Bennett , James E. Smith, Trace cache: a low latency approach to high bandwidth instruction fetching, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.24-35, December 02-04, 1996, Paris, France
• 11: Eric Rotenberg , Quinn Jacobson , Yiannakis Sazeides , Jim Smith, Trace processors, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.138-148, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 12: A. J. Smith, "Sequential Program Prefetching in Memory Hierarchies," IEEE Computer 11 (12), pp. 7- 21, Dec 1978.
• 13: James E. Smith, A study of branch prediction strategies, Proceedings of the 8th annual symposium on Computer Architecture, p.135-148, May 12-14, 1981, Minneapolis, Minnesota, United States
• 14: 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
• 15: C. Young, E. Shekita, "An Intelligent I-Cache Prefetch Mechanism," in Proceedings of the International Conference on Computer Design, pp. 44-49, Oct 1993.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.2 ARITHMETIC AND LOGIC STRUCTURES

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES

General Terms:
Design, Experimentation, Performance