Fast branch misprediction recovery in out-of-order superscalar processors

ABSTRACT

Current trends in modern out-of-order processors involve implementing deeper pipelines and a large instruction window to achieve high performance. However, as pipeline depth increases, the branch misprediction penalty becomes a critical factor in overall processor performance. Current approaches to handling branch mispredictions either incrementally roll back to in-order state by waiting until the mispredicted branch reaches the head of the reorder buffer, or utilize checkpointing at branches for faster recovery. Rolling back to in-order state stalls the pipeline for a significant number of cycles and checkpointing is costly.This paper proposes a fast recovery mechanism, called Eager Misprediction Recovery (EMR), to reduce the branch misprediction penalty. Upon a misprediction, the processor immediately starts fetching and renaming instructions from the correct path without restoring the map table. Those instructions that access incorrect speculative values wait until the correct data are restored; however, instructions that access correct values continue executing while recovery occurs. Thus, the recovery mechanism hides the latency of long branch recovery with useful instructions.EMR achieves a mean performance improvement very close to a recovery mechanism that supports checkpointing at each branch. In addition, EMR provides an average of 9.0% and up to 19.9% better performance than traditional sequential misprediction recovery on the SPEC2000 benchmark suite.

REFERENCES

• 1: Haitham Akkary , Ravi Rajwar , Srikanth T. Srinivasan, Checkpoint Processing and Recovery: Towards Scalable Large Instruction Window Processors, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.423, December 03-05, 2003
• 2: Haitham Akkary , Ravi Rajwar , Srikanth T. Srinivasan, An analysis of a resource efficient checkpoint architecture, ACM Transactions on Architecture and Code Optimization (TACO), v.1 n.4, p.418-444, December 2004 [doi>10.1145/1044823.1044826]
• 3: Juan L. Aragón , José González , Antonio González , James E. Smith, Dual path instruction processing, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA [doi>10.1145/514191.514223]
• 4: David N. Armstrong , Hyesoon Kim , Onur Mutlu , Yale N. Patt, Wrong Path Events: Exploiting Unusual and Illegal Program Behavior for Early Misprediction Detection and Recovery, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.119-128, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.38]
• 5: 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
• 6: George Z. Chrysos , Joel S. Emer, Memory dependence prediction using store sets, Proceedings of the 25th annual international symposium on Computer architecture, p.142-153, June 27-July 02, 1998, Barcelona, Spain
• 7: COMPAQ. Alpha 21264 microprocessor hardware reference manual. July 1999.
• 8: Amit Gandhi , Haitham Akkary , Srikanth T. Srinivasan, Reducing Branch Misprediction Penalty via Selective Branch Recovery, Proceedings of the 10th International Symposium on High Performance Computer Architecture, p.254, February 14-18, 2004 [doi>10.1109/HPCA.2004.10004]
• 9: G. Hinton, D. Sager, M. Upton, D. Boggs, D. Carmean, A. Kyker, and P. Roussel. The microarchitecture of the pentium 4 processor. In Intel Technology Journal, February 2001.
• 10: W. W. Hwu , Y. N. Patt, Checkpoint repair for out-of-order execution machines, Proceedings of the 14th annual international symposium on Computer architecture, p.18-26, June 02-05, 1987, Pittsburgh, Pennsylvania, United States [doi>10.1145/30350.30353]
• 11: Daniel A. Jiménez , Calvin Lin, Dynamic Branch Prediction with Perceptrons, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.197, January 20-24, 2001
• 12: M. Johnson. Superscalar Microprocessor Design. Prentice Hall, 1991.
• 13: A J KleinOsowski , David J. Lilja, MinneSPEC: A New SPEC Benchmark Workload for Simulation-Based Computer Architecture Research, IEEE Computer Architecture Letters, v.1 n.1, p.7, January 2006 [doi>10.1109/L-CA.2002.8]
• 14: José F. Martínez , Jose Renau , Michael C. Huang , Milos Prvulovic , Josep Torrellas, Cherry: checkpointed early resource recycling in out-of-order microprocessors, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 15: S. McFarling, Combining branch predictors. Technical Report WRL-TN-36, Digital Western Research Laboratory, 1993.
• 16: Soner Önder , Rajiv Gupta, Automatic Generation of Microarchitecture Simulators, Proceedings of the 1998 International Conference on Computer Languages, p.80, May 14-16, 1998
• 17: Soner Onder , Rajiv Gupta, Dynamic memory disambiguation in the presence of out-of-order store issuing, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.170-176, November 16-18, 1999, Haifa, Israel
• 18: Subbarao Palacharla , Norman P. Jouppi , J. E. Smith, Complexity-effective superscalar processors, Proceedings of the 24th annual international symposium on Computer architecture, p.206-218, June 01-04, 1997, Denver, Colorado, United States
• 19: S. Palacharla, N. P. Jouppi, and J. E. Smith. Quantifying the complexity of superscalar processors, Technical Report CS-TR-96-1328, University of Wisconsin Technical Report, 1996.
• 20: Dezso Sima , D. Sima , Peter Kacsuk, Advanced Computer Architectures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 21: Eric Sprangle , Doug Carmean, Increasing processor performance by implementing deeper pipelines, Proceedings of the 29th annual international symposium on Computer architecture, p.25, May 25-29, 2002, Anchorage, Alaska
• 22: 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
• 23: Kenneth C. Yeager, The MIPS R10000 Superscalar Microprocessor, IEEE Micro, v.16 n.2, p.28-40, April 1996 [doi>10.1109/40.491460]
• 24: Tse-Yu Yeh , Yale N. Patt, Alternative implementations of two-level adaptive branch prediction, Proceedings of the 19th annual international symposium on Computer architecture, p.124-134, May 19-21, 1992, Queensland, Australia

INDEX TERMS

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

Keywords:
branch misprediction, checkpoint, processor state, recovery