The block-based trace cache

ABSTRACT

The trace cache is a recently proposed solution to achieving high instruction fetch bandwidth by buffering and reusing dynamic instruction traces. This work presents a new block-based trace cache implementation that can achieve higher IPC performance with more efficient storage of traces. Instead of explicitly storing instructions of a trace, pointers to blocks constituting a trace are stored in a much smaller trace table. The block-based trace cache renames fetch addresses at the basic block level and stores aligned blocks in a block cache. Traces are constructed by accessing the replicated block cache using block pointers from the trace table. Performance potential of the block-based trace cache is quantified and compared with perfect branch prediction and perfect fetch schemes. Comparing to the conventional trace cache, the block-based design can achieve higher IPC, with less impact on cycle time.Results: Using the SPECint95 benchmarks, a 16-wide realistic design of a block-based trace cache can improve performance 75% over a baseline design and to within 7% of a baseline design with perfect branch prediction. With idealized trace prediction, it is shown the block-based trace cache with an 1K-entry block cache achieves the same performance of the conventional trace cache with 32K entries.

REFERENCES

• 1: Bryan Black , John Paul Shen, Calibration of Microprocessor Performance Models, Computer, v.31 n.5, p.59-65, May 1998 [doi>10.1109/2.675637]
• 2: Brad Calder , Dirk Grunwald, Next cache line and set prediction, Proceedings of the 22nd annual international symposium on Computer architecture, p.287-296, June 22-24, 1995, S. Margherita Ligure, Italy
• 3: Thomas M. Conte , Kishore N. Menezes , Patrick M. Mills , Burzin A. Patel, Optimization of instruction fetch mechanisms for high issue rates, Proceedings of the 22nd annual international symposium on Computer architecture, p.333-344, June 22-24, 1995, S. Margherita Ligure, Italy
• 4: Keith Diefendorff , Ed Silha, The PowerPC User Instruction Set Architecture, IEEE Micro, v.14 n.5, p.30-41, October 1994 [doi>10.1109/MM.1994.363069]
• 5: Daniel Holmes Friendly , Sanjay Jeram Patel , Yale N. Patt, Alternative fetch and issue policies for the trace cache fetch mechanism, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.24-33, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 6: Eric Hao , Po-Yung Chang , Marius Evers , Yale N. Patt, Increasing the instruction fetch rate via block-structured instruction set architectures, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.191-200, December 02-04, 1996, Paris, France
• 7: IBM Microelectronics Division, PowerPC 604 RISC Microprocessor User's Manual, 1994
• 8: 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
• 9: Stephan Jourdan , Tse-Hao Hsing , Jared Stark , Yale N. Patt, The Effects of Mispredicted-Path Execution on Branch Prediction Structures, Proceedings of the 1996 Conference on Parallel Architectures and Compilation Techniques, p.58, October 20-23, 1996
• 10: S. McFarling, "Combining Branch Predictors." Technical Report TN-36, Digital Equipment Corp., June 1993
• 11: Stephen Melvin , Yale Patt, Enhancing instruction scheduling with a block-structured ISA, International Journal of Parallel Programming, v.23 n.3, p.221-243, June 1995 [doi>10.1007/BF02577867]
• 12: Ravi Nair, Dynamic path-based branch correlation, Proceedings of the 28th annual international symposium on Microarchitecture, p.15-23, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• 13: Shien-Tai Pan , Kimming So , Joseph T. Rahmeh, Improving the accuracy of dynamic branch prediction using branch correlation, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.76-84, October 12-15, 1992, Boston, Massachusetts, United States
• 14: 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
• 15: 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
• 16: André Seznec , Stéphan Jourdan , Pascal Sainrat , Pierre Michaud, Multiple-block ahead branch predictors, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.116-127, October 01-04, 1996, Cambridge, Massachusetts, United States
• 17: S. Peter Song , Marvin Denman , Joe Chang, The PowerPC 604 RISC microprocessor, IEEE Micro, v.14 n.5, p.8-17, October 1994 [doi>10.1109/MM.1994.363071]
• 18: Steven Wallace , Nader Bagherzadeh, Multiple Branch and Block Prediction, Proceedings of the 3rd IEEE Symposium on High-Performance Computer Architecture, p.94, February 01-05, 1997
• 19: Tse-Yu Yeh , Deborah T. Marr , Yale N. Patt, Increasing the instruction fetch rate via multiple branch prediction and a branch address cache, Proceedings of the 7th international conference on Supercomputing, p.67-76, July 19-23, 1993, Tokyo, Japan [doi>10.1145/165939.165956]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING

  D. Software
  D.4 OPERATING SYSTEMS

General Terms:
Design, Experimentation, Management, Performance