Dynamic Branch Prediction

The purpose of branch prediction is to attempt to recover branch and jump delay penalties.

The simplest scheme is a single bit predictor which stores the history of branches and predicts the branch will go the same was as it did last time:

But the behavior of a one bit predictor is not very good. Consider: 


     for( i = 0; i < rows; i++ )
          for( j = 0; j < cols; j++)
          {  ...   }
The branch in the j loop will be predicted incoreectly twice per loop! This is worse than static prediction.

Instead, we can use a 2-bit predictor:

How about performance?

Can we do better?

[up] to Branch Prediction.