Computer-Organization-and-Architecture-10th-edition-chapter-16-problem-8P

https://www.chegg.com/homework-help/Computer-Organization-and-Architecture-10th-edition-chapter-16-problem-8P-solution-9780134101613

(there is no solution yet, the question is quite long)

16.8 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 Execute Write Decode I1 12 12 Cycle 1 2 11 I1 12 14 3 4 13 15 15 12 14 11 12 5 16 16 13 13 6 15 15 16 13 14 7 8 15 16 9 Figure 16.14 An In-Order Issue, In-Order-Completion Execution Sequence Fetch Decode Execute stage Store stage stage (write Multiplier back) ml m2 m3 f1 d1 Adder sl al a2 f2 d2 Logic el f3 d3 Load Lookahead window e2 Figure 16.15 A Dual-Pipeline Superscalar Processor 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 O 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 14 (e.g., Figure 14.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. From w To x, y, z Tox (a) From w To y To z (b) Tox To y From w To z (c) Figure 16.16 Figure for Problem 16.7 T T N 1/T 3/T 2/T 3/T 2/T T N T N T N T O/N 1/T O/N 1/N O/N T (a) (b) (c) N N 3/T 2/T 3/T 2/T T T T T N N N 1/N 0/N 1/N O/N T T N (d) (e) Figure 16.17 Figure for Problem 16.8 a. In testing the performance of this scheme, Yeh tried five different prediction schemes, illustrated in Figure 16.17. Identify which three of these schemes cor- respond to those shown in Figures 14.19 and 14.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 pat- terns of branches that match the n-bit pattern in the BHT entry for this instruc- tion. Suggest a rationale for such a strategy