Dual path instruction processing

ABSTRACT

The reasons for performance losses due to conditional branch mispredictions are first studied. Branch misprediction penalties are broken into three categories: pipeline-fill penalty, window-fill penalty, and serialization penalty. The first and third of these produce most of the performance loss, but the second is also significant. Previously proposed dual (or multi) path execution methods attempt to reduce all three penalties, but these methods are also quite complex. Most of the complexity is caused by simultaneously executing instructions from multiple paths.A good engineering compromise is to avoid the complexity of multiple path execution by focusing on methods that reduce only the pipeline and window re-fill penalties. Dual Path Instruction Processing (DPIP) is proposed as a simple mechanism that fetches, decodes, and renames, but does not execute, instructions from the alternative path for low confidence predicted branches at the same time as the predicted path is being executed. All the stages of the pipeline front-end are hidden once the misprediction is detected. This method thus targets the pipeline-fill penalty and is shown to achieve a good trade-off between performance and complexity. To reduce the window-fill penalty, we further propose the addition of a pre-scheduling engine that schedules instructions from the alternative path in an estimated execution order. Thus, after a misprediction, a high number of instructions from the alternate path can be immediately issued to execution, achieving an effect similar to very fast re-filling of the window. Performance evaluation of DPIP in a 14-stage superscalar processor (like IBM Power 4) shows an average IPC improvement of up to 10% for the bzip2 benchmark, and an average of 8% for ten benchmarks from the SPECint95 and SPECint2000 suites.

REFERENCES

• 1: Juan L. Aragón , José González , José M. García , Antonio González, Confidence Estimation for Branch Prediction Reversal, Proceedings of the 8th International Conference on High Performance Computing, p.214-223, December 17-20, 2001
• 2: James O. Bondi , Ashwini K. Nanda , Simonjit Dutta, Integrating a misprediction recovery cache (MRC) into a superscalar pipeline, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.14-23, December 02-04, 1996, Paris, France
• 3: D. Burger and T.M. Austin. "The SimpleScalar Tool Set, Version 2.0". Technical Report #1342, University of Wisconsing-Madison, Computer Sciences Department, 1997
• 4: Ramon Canal , Antonio González, A low-complexity issue logic, Proceedings of the 14th international conference on Supercomputing, p.327-335, May 08-11, 2000, Santa Fe, New Mexico, United States [doi>10.1145/335231.335263]
• 5: 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
• 6: W.D. Connors, J. Florkowski and S.K. Patton. "The IBM 3033: An Inside Look". Datamation, pages 198-218, May 1979
• 7: J. Cortadella and J. M. Llaberia. "An Intelligent IFU for Pipelined Processors that Make Control Instrunctions Transparent to the Execution Unit". Proc. of Int. Symp. on Applied Informatics, pp.188-191, Feb. 1987
• 8: P.N. Glaskowsky. "Pentium 4 (Partially) Previewed". Microprocessor Report, August 2000
• 9: A. González, J.M. Llabería and J. Cortadella. "A Mechanism for Reducing the Cost of Branches in RISC Architectures". Microprocessing and Microprogramming, vol. 24,1-5, pp. 565-572, Aug. 1988
• 10: Jose Gonzalez , Antonio Gonzalez, Control-Flow Speculation through Value Prediction for Superscalar Processors, Proceedings of the 1999 International Conference on Parallel Architectures and Compilation Techniques, p.57, October 12-16, 1999
• 11: Dirk Grunwald , Artur Klauser , Srilatha Manne , Andrew Pleszkun, Confidence estimation for speculation control, Proceedings of the 25th annual international symposium on Computer architecture, p.122-131, June 27-July 02, 1998, Barcelona, Spain
• 12: L. Gwennap. "MIPS R10000 Uses Decoupled Architecture". Microprocessor Report, pp.18-22, Oct. 1994
• 13: T.H. Heil and J.E. Smith. "Selective Dual Path Execution". Technical Report, University of Wisconsin-Madison, ECE, 1997
• 14: Erik Jacobsen , Eric Rotenberg , J. E. Smith, Assigning confidence to conditional branch predictions, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.142-152, December 02-04, 1996, Paris, France
• 15: 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]
• 16: E. J. McLellan , D. A. Webb, The Alpha 21264 Microprocessor Architecture, Proceedings of the International Conference on Computer Design, p.90, October 05-05, 1998
• 17: Artur Klauser , Abhijit Paithankar , Dirk Grunwald, Selective eager execution on the PolyPath architecture, Proceedings of the 25th annual international symposium on Computer architecture, p.250-259, June 27-July 02, 1998, Barcelona, Spain
• 18: Artur Klauser , Dirk Grunwald, Instruction fetch mechanisms for multipath execution processors, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.38-47, November 16-18, 1999, Haifa, Israel
• 19: K. Krewell. "IBM's Power4 Unveiling Continues". Microprocessor Report, November 2000
• 20: C.C. Lee, I.C.K. Chen and T.N. Mudge. "The Bi-Mode Branch Predictor". Proc. of the Int. Symp. on Microarchitecture, 1996
• 21: Srilatha Manne , Artur Klauser , Dirk Grunwald, Branch Prediction Using Selective Branch Inversion, Proceedings of the 1999 International Conference on Parallel Architectures and Compilation Techniques, p.48, October 12-16, 1999
• 22: S. McFarling. "Combining Branch Predictors". Tech. Report TN-36. Digital Western Research Lab., 1993
• 23: Pierre Michaud , André Seznec, Data-Flow Prescheduling for Large Instruction Windows in Out-of-Order Processors, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.27, January 20-24, 2001
• 24: 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
• 25: Dean M. Tullsen , Susan J. Eggers , Henry M. Levy, Simultaneous multithreading: maximizing on-chip parallelism, Proceedings of the 22nd annual international symposium on Computer architecture, p.392-403, June 22-24, 1995, S. Margherita Ligure, Italy
• 26: Augustus K. Uht , Vijay Sindagi , Kelley Hall, Disjoint eager execution: an optimal form of speculative execution, Proceedings of the 28th annual international symposium on Microarchitecture, p.313-325, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• 27: Steven Wallace , Brad Calder , Dean M. Tullsen, Threaded multiple path execution, Proceedings of the 25th annual international symposium on Computer architecture, p.238-249, June 27-July 02, 1998, Barcelona, Spain
• 28: 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]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.1 Single Data Stream Architectures

General Terms:
Design, Performance

Keywords:
branch misprediction penalty, confidence estimation, dual path processing, pre-scheduling