[20 Marks In this question you will investigate the effects of adding global history bits to a standard branch prediction mechanism. Assume that the MIPS ISA has no delay slots. Throughout this problem we will be working with the following program. loop : LW R4, O (R3) ADDI R3, R3, 4 SUBI R1, R1, 1 Sample Tables are at the end of Question Paper bi: BEQZ R4, b2 ADDI R2, R2, 1 b2: BNEZ Ri, loop Assume the initial value of Rl is n (n>0). Assume the initial value of R2 is 0 (R2 holds the result of the program). Assume the initial value of R3 is p (a pointer to the beginning of an array of 32-bit integers). You will be using a 2-bit predictor state machine, as shown in figure on next page. 11 taken taken taken taken 00 10 taken taken taken taken 01 In state IX we will guess not taken. In state OX we will guess taken. Assume that bl and b2 do not conflict in the BHT. a) What does the program compute? That is what does R2 contain when we exit the loop? (02) b) Now we will investigate how well our standard 2-bit branch predictor performs. Assume the inputs to the program are n-8 and p[0] - 1. p[1] = 0, p[2] - 1. p[3] = 0.... etc. That is the array elements exhibit an alternating pattern of l's and O's. Fill out Table 1 (note that the first few lines are filled out for you). What is the number of mis-predicts? Table I contains an entry for every branch (either bl or b2) that is executed. The Branch Predictor (BP) bits in the table are the bits from the BHT. For each branch, check the corresponding BP bits (indicated by the bold entries in the examples) to make a prediction, then update the BP bits in the following entry. (05) c) Now we add a global history bit to the branch predictor, as described in the lecture. Fill out Table 2, and again give the total number of mis-predicts you get when running the program with the same inputs. (05) d) Now we add a second global history bit. Fill out Table 3. Again, compute the number of mis-predicts you get for the same input (05) e) Compare your results from 2b, 2c and 2d. When do most of the mis-predicts occur in each case (at the beginning, periodically, at the end, etc.)? What does this tell you about global history bits in general? For a large n. what prediction scheme will work best? Explain briefly. (03) Table - 1 Branch Predictor System State R3/R4 4/1 4/1 8/0 8/0 12/1 12/1 b1 bits 10 10 10 b2 bits 10 10 11 Branch Behavior Predicted Actual N N N T N T N T 11 11 11 00 PC b1 b2 b1 b2 b1 b2 b1 b2 b1 b2 b1 b2 b1 b2 b1 b2 b1 b2 b1 b2 b1 b2 b1 b2 Table-2 Branch Predictor Behavior PC set 1 System State R3/R4 history bit 4/1 1 4/1 0 8/0 1 8/0 12/1 12/1 b1 bits set 0 10 10 10 10 10 10 b2 bits set 0 set 1 Predicted 10 10 N 10 10 N 11 10 Actual N T b1 b2 b1 b2 b1 b2 b1 b2 b1 b2 b1 b2 b1 b2 b1 b2 b1 b2 b1 b2 b1 b2 b1 b2 Branch Predictor Behavior b1 bits b2 bits set 00 set 01 set 10 set 11 set 00 set 01 set 10 set 11 Predicted Actual 10 10 10 10 10 10 10 10 N N 10 10 10 10 10 10 10 10 N 10 10 10 10 10 11 10 10 Table - 3 System State PC R3/R4 history bits b1 4/1 11 b2 4/1 01 b1 8/0 10 b28/0 b1 12/1 b2 12/1 b1 b2 b1 b2 b1 b2 b1 b2 b1 b2 b1 b2 b1 b2 b1 b2 b1 b2