Yeh's dynamic branch prediction algorithm, used on the Pentium 4, is a two-level branch prediction algorithm. The first level is the history of the last n branches. The second level is the branch behavior of the last s occurrences of that unique pattern of the last n branches. For each conditional branch instruction in a program, there is an entry in a Branch History Table (BHT). Each entry consists of n bits corresponding to the last n executions of the branch instruction, with a 1 if the branch was taken and a 0 if the branch was not. Each BHT entry indexes into a Pattern Table (PT) that has 2n entries, one for each possible pattern of n bits. Each PT entry consists of s bits that are used in branch prediction, as was described in Chapter 12 (e.g., Figure 12.19).When a conditional branch is encountered during instruction fetch and decode, the address of the instruction is used to retrieve the appropriate BHT entry, which shows the recent history of the instruction. Then, the BHT entry is used to retrieve the appropriate PT entry for branch prediction. After the branch is executed, the BHT entry is updated, and then the appropriate PT entry is updated.
a. In testing the performance of this scheme, Yeh tried five different prediction schemes, illustrated in Figure 14.16. Identify which three of these schemes correspond to those shown in Figures 12.19 and 12.28. Describe the remaining two schemes.
b. With this algorithm, the prediction is not based on just the recent history of this particular branch instruction. Rather, it is based on the recent history of all patterns of branches that match the n-bit pattern in the BHT entry for this instruction. Suggest a rationale for such a strategy.

Figure 14.16 Figure for Problem 14.8

Transcribed Image Text:

3/T 2/T 1/T 0/N O/N 3/T 3/T ) 2/T 1/N 0/N L/N