Speculative Updates of Local and Global Branch History: A Quantitative Analysis

Abstract:

In today's wide-issue processors, even small branch-misprediction
rates introduce substantial performance penalties. Worse yet,
inadequate branch prediction creates a bottleneck at the fetch stage,
restricting other opportunities for improving performance. The choice
of how to predict conditional-branch outcomes is the primary lever on
prediction accuracy. But the choice of when to update the
predictor with branch outcomes is a second powerful lever, and the
subject of this paper. In history-based predictors like gshare,
many mispredictions result from commit-time update of the history:
typical pipelined processors predict branches in the fetch stage, but
update the predictor in the commit stage, making the predictor's state
temporarily out-of-date. As pipelines grow longer---in particular,
when branches can spend many cycles in the instruction window waiting
to issue---this problem becomes worse. Prior work on this subject has
discussed the need for speculative update in a global-history-based
predictor; this paper evaluates speculative history update for both
global-history and local-history predictors of various configurations,
using cycle-level simulation to show the effects of prediction
accuracy and update time on overall performance. The results show the
importance of speculative history update, but also that speculative
update requires suitable fixup mechanisms for repairing state that has
been corrupted by mispredictions. A number of such mechanisms are
discussed.

This technical report has been published as

Speculative Updates of Local and Global Branch History: A
Quantitative Analysis. K. Skadron, M. Martonosi, and D.W. Clark.
Journal of Instruction-Level Parallelism,
vol. 2, Jan. 2000