Page 115 - Computer_Science_F5

Computer Science Iteration BPB prediction Actual branch Outcome update

1 (Taken)
6
Correct Prediction (No update)
Taken
Taken
1 (Taken)
7
Correct Prediction (No update)
8
Correct Prediction (No update)
1 (Taken)
Taken
FOR ONLINE READING ONLY
Not taken
9
1 (Taken)
Incorrect Prediction (update
BPB to 0 (Not taken))
10 0 (Not taken) Taken Incorrect Prediction (update
BPB to 1 (Taken))
Prediction accuracy = (Correct predictions / Total predictions) * 100% = 80%. The
1-bit scheme is simpler but less accurate because it struggles with branches that
change behaviuor frequently.
Branch History Tables (BHTs) with 2-Bit Scheme

A Branch History Table (BHT) is a small memory indexed by the lower bits of
a branch instruction’s address, storing multiple bits for more sophisticated and
accurate predictions than a BPB. In a 2-bit scheme, as shown in Figure 2.11, the
states are: 00 (strongly not taken), 01 (weakly not taken), 10 (weakly taken), and 11
(strongly taken).
taken

Strongly not Weakly not
Not taken taken not taken taken
00 01

not taken taken

not taken
taken Strongly taken Weakly taken
11 10
taken

Figure 2.11: States in a 2-bit prediction scheme
Consider the previous example with a loop branch that is taken nine times in a
row, and then is not taken once. Assume the initial state of the BHT 2-bit predictor
is Strongly taken (11). From Table 2.7, we see that a 2-bit scheme improves the
prediction accuracy to 90%.

106
for Advanced Secondary Schools

Computer Science Form 5.indd 106 23/07/2024 12:33