| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
OS-Aware Branch Prediction: Improving Microprocessor Control Flow Prediction for Operating Systems
January 2007 (vol. 56 no. 1)
pp. 2-17
Many modern applications have a significant operating system (OS) component. The OS execution affects various architectural states, including the dynamic branch predictions, which are widely used in today's high-performance microprocessor designs to improve performance. This impact tends to become more significant as the designs become more deeply pipelined and more speculative. In this paper, we focus on the issues of understanding the OS effects on the branch predictions and designing architectural support to alleviate the bottlenecks that are created by misprediction. In this work, we characterize the control flow transfer of several emerging applications on a commercial OS. It was observed that the exception-driven, intermittent invocation of OS code and user/OS branch history interference increased misprediction in both user and kernel code. We propose two simple OS-aware control flow prediction techniques to alleviate the destructive impact of user/OS branch interference. The first consists of capturing separate branch correlation information for user and kernel code. The second involves using separate branch prediction tables for user and kernel code. We demonstrate in this paper that OS-aware branch predictions require minimal hardware modifications and additions. Moreover, the OS-aware branch predictions can be integrated with many existing schemes to further improve their performance. We studied the improvement contributed by OS-aware techniques to various branch prediction schemes ranging from the simple Gshare to the more advanced Agree, Multi-Hybrid, and Bi-Mode predictors. On the 32K-entry predictors, incorporating the OS-aware techniques yields up to 34 percent, 23 percent, 27 percent, and 9 percent prediction accuracy improvement on the Gshare, Multi-Hybrid, Agree, and Bi-Mode predictors, respectively.
[1] 2 J. Bennett and M. Flynn, “Performance Factors for Superscalar Processors,” Computer Technical Report CSL-TR-95-661, Systems Laboratory, Stanford Univ., Feb. 1995.[2] P. Chang and U. Banerjee, “Profile-Guided Multi-Heuristic Branch Prediction,” Proc. Int'l Conf. Parallel Processing, 1995.[3] P.-Y. Chang, M. Evers, and Y. Patt, “Improving Branch Prediction Accuracy by Reducing Pattern History Table Interference,” Proc. Int'l Conf. Parallel Architectures and Compilation Techniques, pp. 48-57, 1996.[4] A.N. Eden and T. Mudge, “The YAGS Branch Prediction Scheme,” Proc. 31st Ann. ACM/IEEE Int'l Symp. Microarchitecture, pp. 69-77, 1998.[5] M. Evers, P.Y. Chang, and Y.N. Patt, “Using Hybrid Branch Predictors to Improve Branch Prediction Accuracy in the Presence of Context Switches,” Proc. 23rd Ann. Int'l Symp. Computer Architecture, pp. 3-11, 1996.[6] N. Gloy, C. Young, J.B. Chen, and M.D. Smith, “An Analysis of Dynamic Branch Prediction Schemes on System Workloads,” Proc. 23rd Ann. Int'l Symp. Computer Architecture, pp. 12-21, 1996.[7] C.-C. Lee, I.-C.K. Chen, and T. Mudge, “The Bi-Mode Branch Predictor,” Proc. 30th Ann. IEEE/ACM Int'l Symp. Microarchitecture, pp. 4-13, 1997.[8] T. Li, L.K. John, N. Vijaykrishnan, A. Sivasubramaniam, J. Sabarinathan, and A. Murthy, “Using Complete System Simulation to Characterize SPECjvm98 Benchmarks,” Proc. ACM Int'l Conf. Supercomputing, pp. 22-33, 2000.[9] T. Li, L. John, A. Sivasubramaniam, N. Vijaykrishnan, and J. Rubio, “Understanding and Improving Operating System Effects in Control Flow Prediction,” Proc. Int'l Conf. Architectural Support for Programming Languages and Operating Systems, pp. 68-80, 2002.[10] T. Li, L.K. John, A. Sivasubramaniam, N. Vijaykrishnan, and J. Rubio, “Understanding and Improving Operating System Effects in Control Flow Prediction,” technical report, Dept. of Electrical and Computer Eng., Univ. of Texas at Austin, June 2002, http://www.ece.utexas.edu/projects/ece/lca/ pstao-TR-june-2002.pdf.[11] T. Lindholm and F. Yellin, The Java Virtual Machine Specification, second ed. Addison Wesley, 1999.[12] S. McFarling, “Combining Branch Predictors,” WRL Technical Note TN-36, Digital Equipment Corp., June 1993.[13] P. Michaud, A. Seznec, and R. Uhlig, “Trading Conflict and Capacity Aliasing in Conditional Branch Predictors,” Proc. 24th Int'l Symp. Computer Architecture, pp. 292-303, 1997.[14] J. Ousterhout, “Why Aren't Operating Systems Getting Faster as Fast as Hardware?” Proc. Summer 1990 USENIX Conf., pp. 247-256, 1990.[15] C. Perleberg and A. Smith, “Branch Target Buffer Design and Optimization,” IEEE Trans. Computers, vol. 42, no. 4, pp. 396-412, Apr. 1993.[16] “PostgreSQL,” http:/www.us.postgresql.org/, 2004.[17] M. Stonebraker, L.A. Rowe, and M. Hirohama, “The Implementation of Postgres,” IEEE Trans. Knowledge and Data Eng., vol. 2, no. 1, Mar. 1990.[18] J.A. Redstone, S.J. Eggers, and H.M. Levy, “An Analysis of Operating System Behavior on a Simultaneous Multithreaded Architecture,” Proc. Ninth Int'l Conf. Architectural Support for Programming Languages and Operating Systems, pp. 245-256, 2000.[19] M. Rosenblum, E. Bugnion, S.A. Herrod, E. Witchel, and A. Gupta, “The Impact of Architectural Trends on Operating System Performance,” Proc. 15th ACM Symp. Operating System Principles, pp. 285-298, 1995.[20] M. Rosenblum, S.A. Herrod, E. Witchel, and A. Gupta, “Complete Computer System Simulation: The SimOS Approach,” IEEE Parallel and Distributed Technology: Systems and Applications, vol. 3, no. 4, pp. 34-43, Winter 1995.[21] S. Sechrest, C.-C. Lee, and T. Mudge, “Correlation and Aliasing in Dynamic Branch Predictors,” Proc. 23rd Ann. Int'l Symp. Computer Architecture, pp. 22-32, 1996.[22] SPEC JVM98 Benchmarks, http://www.spec.org/osgjvm98/, 1998.[23] E. Sprangle, R.S. Chappell, M. Alsup, and Y.N. Patt, “The Agree Predictor: A Mechanism for Reducing Negative Branch History Interference,” Proc. 24th Ann. Int'l Symp. Computer Architecture, pp.284-291, 1997.[24] Transaction Processing Council, The TPC-C Benchmark, http://www.tpc.orgtpcc/, 2004.[25] K.C. Yeager, “MIPS R10000,” IEEE Micro, vol. 16, no. 1, pp. 28-40, Apr. 1996.[26] T. Yeh and Y.N. Patt, “Two-Level Adaptive Branch Prediction,” Proc. 24th Int'l Symp. Microarchitecture, pp. 51-61, 1991.[27] T.-Y. Yeh and Y.N. Patt, “A Comparison of Dynamic Branch Predictors that Use Two Levels of Branch History,” Proc. 20th Ann. Int'l Symp. Computer Architecture, pp. 257-266, 1993.[28] C. Young, C. Gloy, and M.D. Smith, “A Comparative Analysis of Schemes for Correlated Branch Prediction,” Proc. 22nd Ann. Int'l Symp. Computer Architecture, pp. 276-286, 1995.[29] R.B. Hilgendorf, G.J. Heim, and W. Rosenstiel, “Evaluation of Branch-Prediction Methods on Traces from Commercial Applications,” IBM J. Research and Development, Digital Multimedia Technology, vol. 43, no. 4, pp. 579-593, 1999.[30] M. Co and K. Skadron, “The Effects of Context Switching on Branch Predictor Performance,” Proc. 2001 IEEE Int'l Symp. Performance Analysis of Systems and Software (ISPASS), 2001.[31] S. Pasricha and A. Veidenbaum, “Improving Branch Prediction Accuracy in Embedded Processors in the Presence of Context Switches,” Proc. Int'l Conf. Computer Design, 2003.[32] A.S. Dhodapkar and J.E. Smith, “Saving and Restoring Implementation Contexts with Co-Designed Virtual Machines,” Proc. Workshop Complexity-Effective Design, 28th Int'l Symp. Computer Architecture, 2001.[33] J.C. Mogul and A. Borg, “The Effect of Context Switches on Cache Performance,” Proc. Int'l Conf. Architectural Support for Programming Languages and Operating Systems, 1991.[34] D.A. Jiménez and C. Lin, “Dynamic Branch Prediction with Perceptrons,” Proc. Int'l Symp. High Performance Computer Architecture, 2001.[35] A. Falcon, J. Stark, A. Ramirez, K. Lai, and M. Valero, “Prophet-Critic Hybrid Branch Prediction,” Proc. Int'l Symp. Computer Architecture, 2004.
Index Terms:
Pipeline processors, branch prediction, processor architectures, hardware/software interfaces, computer system implementation, performance of systems.
Citation:
Tao Li, Lizy Kurian John, Anand Sivasubramaniam, N. Vijaykrishnan, Juan Rubio, "OS-Aware Branch Prediction: Improving Microprocessor Control Flow Prediction for Operating Systems," IEEE Transactions on Computers, vol. 56, no. 1, pp. 2-17, Jan. 2007, doi:10.1109/TC.2007.16
