Question 3 (45 marks) The following is an assembly language implementation of a for-loop in C. BX is used to hold the variable i. AX and CX somehow hold the array elements a [i] and c [i]. You will notice that there is a conditional branch ( jl ) and an unconditional jump (jmp) instruction. As far as the branch prediction algorithm is concerned, conditional and unconditional branches are treated in the same way. We assume that branch prediction is implemented in the instruction-fetch unit using a small amount of memory to hold the branch prediction buffer. Before the loop is executed, there are no entries in the branch prediction buffer so the first time when the conditional or unconditional branch is encountered, it is predicted as not-taken. (d) Under a 2-bit branch prediction scheme, fill in the following table with simulating the same implementation above: (5 marks) (e) With reference to answer of 2 bits branch prediction scheme in (d), obtain (i) The total number of jump and branch encountered (ii) The total number of incorrect predictions (either jump or branch) (iii) Misprediction rate for all predictions (iv) Misprediction rate per iteration (5 marks) In a certain program, no branch-delay slot can be filled by independent instructions, meaning that NOP instructions will be inserted to the branch delay cycles. Suppose we have a deeply pipelined processor with a fixed branch delay of two processor cycles, and an ideal CPI of 1 when no branch instruction is present in the instruction stream. A branch-target buffer with prediction is now implemented in this pipelined processor, and yields zero-cycle branch delay if there is a hit in the prediction buffer with correct prediction. However, the implementation will incur a 3-cycle penalty if the prediction is incorrect or if the target is not found in the buffer. (f) Assume that the branch prediction is correct 100% of time and 20% of the instructions are conditional branches. Calculate the minimum buffer hit ratio in order to outperform the original implementation. (15 marks)