Understanding and improving operating system effects in control flow prediction

ABSTRACT

Many modern applications result in a significant operating system (OS) component. The OS component has several implications including affecting the control flow transfer in the execution environment. This paper focuses on understanding the operating system effects on control flow transfer and prediction, and designing architectural support to alleviate the bottlenecks. We characterize the control flow transfer of several emerging applications on a commercial operating system. We find that the exception-driven, intermittent invocation of OS code and the user/OS branch history interference increase the 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 one consists of capturing separate branch correlation information for user and kernel code. The second one involves using separate branch prediction tables for user and kernel code. We study the improvement contributed by the OS-aware prediction to various branch predictors ranging from simple Gshare to more elegant Agree, Multi-Hybrid and Bi-Mode predictors. On 32K entries predictors, incorporating OS-aware techniques yields up to 34%, 23%, 27% and 9% prediction accuracy improvement in Gshare, Multi-Hybrid, Agree and Bi-Mode predictors, resulting in up to 8% execution speedup.

REFERENCES

• 1: Thomas E. Anderson , Henry M. Levy , Brian N. Bershad , Edward D. Lazowska, The interaction of architecture and operating system design, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.108-120, April 08-11, 1991, Santa Clara, California, United States
• 2: James E. Bennett , Michael J. Flynn, Performance Factors for Superscalar Processors, Stanford University, Stanford, CA, 1995
• 3: P. Chang and U. Banerjee, Profile-guided Multi-heuristic Branch Prediction, In Proceedings of the International Conference on Parallel Processing, 1995.
• 4: Po-Yung Chang , Marius Evers , Yale N. Patt, Improving Branch Prediction Accuracy by Reducing Pattern History Table Interference, Proceedings of the 1996 Conference on Parallel Architectures and Compilation Techniques, p.48, October 20-23, 1996
• 5: K. Diefendorff, HP, Intel Complete IA-64 Rollout, Microprocessor Report, pages 1-9, Apr. 2000.
• 6: A. N. Eden , T. Mudge, The YAGS branch prediction scheme, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.69-77, November 1998, Dallas, Texas, United States
• 7: Marius Evers , Po-Yung Chang , Yale N. Patt, Using hybrid branch predictors to improve branch prediction accuracy in the presence of context switches, Proceedings of the 23rd annual international symposium on Computer architecture, p.3-11, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 8: Nicolas Gloy , Cliff Young , J. Bradley Chen , Michael D. Smith, An analysis of dynamic branch prediction schemes on system workloads, Proceedings of the 23rd annual international symposium on Computer architecture, p.12-21, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 9: Daniel A. Jiménez , Stephen W. Keckler , Calvin Lin, The impact of delay on the design of branch predictors, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.67-76, December 2000, Monterey, California, United States [doi>10.1145/360128.360137]
• 10: Chih-Chieh Lee , I-Cheng K. Chen , Trevor N. Mudge, The bi-mode branch predictor, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.4-13, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 11: Tao Li , Lizy Kurian John , Vijaykrishnan Narayanan , Anand Sivasubramaniam , Jyotsna Sabarinathan , Anupama Murthy, Using complete system simulation to characterize SPECjvm98 benchmarks, Proceedings of the 14th international conference on Supercomputing, p.22-33, May 08-11, 2000, Santa Fe, New Mexico, United States [doi>10.1145/335231.335234]
• 12: T. Li, L. K. John, A. Sivasubramaniam, N. Vijaykrishnan and J. Rubio, Understanding and Improving Operating System Effects in Control Flow Prediction, Technical Report, Department of Electrical and Computer Engineering, University of Texas at Austin, June 2002. http://www.ece.utexas.edu/projects/ece/lca/ps/tao-TR-june-2002.pdf.
• 13: Tim Lindholm , Frank Yellin, Java Virtual Machine Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 14: S. McFarling, Combining Branch Predictors, WRL Technical Note TN-36, Digital Equipment Corporation, June 1993.
• 15: Pierre Michaud , André Seznec , Richard Uhlig, Trading conflict and capacity aliasing in conditional branch predictors, Proceedings of the 24th annual international symposium on Computer architecture, p.292-303, June 01-04, 1997, Denver, Colorado, United States
• 16: J. Ousterhout, Why aren't Operating Systems Getting Faster as Fast as Hardware?, In Proceedings of the Summer 1990 USENIX Conference, pages 247-256, 1990.
• 17: Dharmesh Parikh , Kevin Skadron , Yan Zhang , Marco Barcella , Mircea R. Stan, Power Issues Related to Branch Prediction, Proceedings of the 8th International Symposium on High-Performance Computer Architecture, p.233, February 02-06, 2002
• 18: 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]
• 19: "PostgreSQL", http://www.us.postgresql.org/.
• 20: Joshua A. Redstone , Susan J. Eggers , Henry M. Levy, An analysis of operating system behavior on a simultaneous multithreaded architecture, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.245-256, November 2000, Cambridge, Massachusetts, United States
• 21: M. Rosenblum , E. Bugnion , S. A. Herrod , E. Witchel , A. Gupta, The impact of architectural trends on operating system performance, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.285-298, December 03-06, 1995, Copper Mountain, Colorado, United States
• 22: Mendel Rosenblum , Stephen A. Herrod , Emmett Witchel , Anoop Gupta, Complete Computer System Simulation: The SimOS Approach, IEEE Parallel & Distributed Technology: Systems & Technology, v.3 n.4, p.34-43, December 1995 [doi>10.1109/88.473612]
• 23: Stuart Sechrest , Chih-Chieh Lee , Trevor Mudge, Correlation and aliasing in dynamic branch predictors, Proceedings of the 23rd annual international symposium on Computer architecture, p.22-32, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 24: SPEC JVM98 Benchmarks, http://www.spec.org/osg/jvm98/.
• 25: Eric Sprangle , Robert S. Chappell , Mitch Alsup , Yale N. Patt, The agree predictor: a mechanism for reducing negative branch history interference, Proceedings of the 24th annual international symposium on Computer architecture, p.284-291, June 01-04, 1997, Denver, Colorado, United States
• 26: M. Stonebraker , L. A. Rowe , M. Hirohama, The Implementation of POSTGRES, IEEE Transactions on Knowledge and Data Engineering, v.2 n.1, p.125-142, March 1990 [doi>10.1109/69.50912]
• 27: Transaction Processing Council, The TPC-C Benchmark, http://www.tpc.org/tpcc/.
• 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: 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]
• 30: 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
• 31: 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
• 32: Y. Zhang, J. Zhang, A. Sivasubramaniam, C. Liu and H. Franke, Characterizing TPC-H on a Clustered Database Engine from the OS Perspective, In Proceedings of the Workshop on Computer Architecture Evaluation using Commercial Workloads (CAECW-02), 2002.