An analysis of dynamic branch prediction schemes on system workloads

ABSTRACT

Recent studies of dynamic branch prediction schemes rely almost exclusively on user-only simulations to evaluate performance. We find that an evaluation of these schemes with user and kernel references often leads to different conclusions. By analyzing our own Atom-generated system traces and the system traces from the Instruction Benchmark Suite, we quantify the effects of kernel and user interactions on branch prediction accuracy. We find that user-only traces yield accurate prediction results only when the kernel accounts for less than 5% of the total executed instructions. Schemes that appear to predict well under user-only traces are not always the most effective on full-system traces: the recently-proposed two-level adaptive schemes can suffer from higher aliasing than the original per-branch 2-bit counter scheme. We also find that flushing the branch history state at fixed intervals does not accurately model the true effects of user/kernel interaction.

REFERENCES

• 1: M. Accetta, et al. "Mach: A New Kernel Foundation for Unix Development," Proc. Summer 1986 USENIX Conf., Jul. 1986.
• 2: J. Chen. "Software Methods for System Address Tracing," Proc. Fourth Workshop on Workstation Operating Systems, Oct. 1993.
• 3: J. Bradley Chen , Brian N. Bershad, The impact of operating system structure on memory system performance, Proceedings of the fourteenth ACM symposium on Operating systems principles, p.120-133, December 05-08, 1993, Asheville, North Carolina, United States
• 4: J. Chen and A. Eustace. "Kernel Instrumentation Tools and Techniques," Technical Report 26-95, Center for Research in Computing Technology, Harvard University, Cambridge, MA, Nov. 1995.
• 5: A. Eustace and A. Srivastava. "ATOM: A Flexible Interface for Building High Performance Program Analysis Tools". Proc. Winter 1995 USENIX Technical Conf. on UNIX and Advanced Computing Systems, Jan. 1995
• 6: L. Gwennap. "New Algorithm Improves Branch Prediction," Microprocessor Report, 9(4):i7-21, Mar. 27, 1995.
• 7: L. Gwennap. "Pentium Competitors Go Head to Head," Microprocessor Report, 9(8):16, Jun. 19, 1995.
• 8: L. Gwennap. "Nx868 Goes Toe-to-Toe with Pentium Pro," Microprocessor Report, 9(14):8, Oct. 23, 1995.
• 9: Andreas Krall, Improving semi-static branch prediction by code replication, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.97-106, June 20-24, 1994, Orlando, Florida, United States
• 10: J. Lee and A. Smith. "Branch Prediction Strategies and Branch Target Buffer Design," Computer, 17(1), Jan. 1984.
• 11: S. McFarling. "Combining Branch Predictors," WRL Technical Note TN-36, June 1993.
• 12: S. McFarling , J. Hennesey, Reducing the cost of branches, Proceedings of the 13th annual international symposium on Computer architecture, p.396-403, June 02-05, 1986, Tokyo, Japan
• 13: 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
• 14: 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
• 15: C. H. Perleberg , A. J. Smith, Branch Target Buffer Design and Optimization, IEEE Transactions on Computers, v.42 n.4, p.396-412, April 1993 [doi>10.1109/12.214687]
• 16: Stuart Sechrest , Chih-Chieh Lee , Trevor Mudge, The role of adaptivity in two-level adaptive branch prediction, Proceedings of the 28th annual international symposium on Microarchitecture, p.264-269, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• 17: 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
• 18: Richard Uhlig , David Nagle , Trevor Mudge , Stuart Sechrest , Joel Emer, Instruction fetching: coping with code bloat, Proceedings of the 22nd annual international symposium on Computer architecture, p.345-356, June 22-24, 1995, S. Margherita Ligure, Italy
• 19: ULTRIX Documentation Group. ULTRIX Documentation Overview for RISC Processors, Digital Equipment Corporation, I989.
• 20: Tse-Yu Yeh , Yale N. Patt, Two-level adaptive training branch prediction, Proceedings of the 24th annual international symposium on Microarchitecture, p.51-61, September 1991, Albuquerque, New Mexico, Puerto Rico [doi>10.1145/123465.123475]
• 21: Tse-Yu Yeh , Yale N. Patt, A comparison of dynamic branch predictors that use two levels of branch history, Proceedings of the 20th annual international symposium on Computer architecture, p.257-266, May 16-19, 1993, San Diego, California, United States
• 22: Cliff Young , Michael D. Smith, Improving the accuracy of static branch prediction using branch correlation, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.232-241, October 05-07, 1994, San Jose, California, United States
• 23: Cliff Young , Nicolas Gloy , Michael D. Smith, A comparative analysis of schemes for correlated branch prediction, Proceedings of the 22nd annual international symposium on Computer architecture, p.276-286, June 22-24, 1995, S. Margherita Ligure, Italy

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.2 Control Structure Performance Analysis and Design Aids
          Subjects: Simulation**

General Terms:
Experimentation, Human Factors, Measurement, Theory

Keywords:
2-level adaptive prediction, branch prediction, correlation, system traces