Two-bit branch prediction

 
Figure: State transition diagram for 2-bit branch prediction


• Prediction misses twice before being changed
• Need two bits for each table entry
• Implementation: either separate cache-like BHT, or extra bits held with each entry of the I-cache
• Still mispredicts 5% - 20%; many more sophisticated schemes...