Fast Branch Misprediction Recovery in Out-of-order Superscalar Processors

Current trends in modern out-of-order processors involve imple-menting 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 mispredic-tions either incrementally roll back to in-order state by waiting un-til 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 mispredic-tion penalty. Upon a misprediction, the processor immediately starts fetching and renaming instructions from the correct path with-out 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 re-covery 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