Yeh\'s dynamic branch prediction algorithm, used on the Pentium 4, is a two-leve
ID: 3869231 • Letter: Y
Question
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 entr 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 14 (e.g., Figure 1). 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 2. Identify which three of these schemes correspond to those shown in Figures 3 and 4. 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 strategyExplanation / Answer
a)
Figure 2(d) is equivalent to Figure 3
Figure 2(b) is equivalent to Figure 4(a)
Figure 2(c) is equivalent to Figure 4(b)
Figure 2(a) If the last branch was taken , predict that this branch will be taken. If the last branch was not taken , predict that it will not be taken.
Figure 2(e) It is almost similar to Figure 2(c) but the only difference is in prediction followed by error, the previous prdiction is restored.
b)
In loop-closing branches the past history of branches is a good approach. This guide for the future behaviour with more complex control structures. The direction of branch depends on direction taken by related branches. If we consider each of the possible paths that lead to a given nested branch, then it is clear that prdiction in such a case should be based on histories determined by such paths, i.e. how the particular branch is arrived at rather than just on individual history of a branch instruction. In sequence of conditions there will be instances when the outcome of one condition test depend on the preceding condition if the conditions are related in some way.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.