1. Consider the execution of the following sequence of three instructions on the 5-stage MIPS pipeline.
add
8
9
10
lw
10 400(8)
sub
9
10
8
(a) List all dependences and their types
(b) Show all forwarding links between each instruction pair assuming full forwarding
Assume three cases separately – (i) no forwarding (ii) ALU-ALU forwarding only and
(iii) full forwarding. Also assume that the pipeline clock cycle times are 250,
270 and 280 picosecs. for the three cases respectively. Answer the following questions for each of the three cases.
(c) Draw a multicycle pipeline diagram showing clearly the stage each instruction is in during each cycle
(d) What is the total execution time?
(e) What is the average utilization of the pipeline?
(f) Can the instructions be re-ordered to decrease the total execution time? If so, how?
2. The goal of this problem is to compare the performance (accuracy) of different predictors for the snippet below.
main:
move
t3
$0
addi
t0
$0 100
chalo:
andi
t1
t0
7
branch:
bgt
t1
2 here
sll
t2
t0
2
add
t3
t3
t2
• join
here:
sll
t2
t0
1
sub
t3
t3
t2
join:
addi
t0
t0
-1
bnez t0 chalo
In each part below assume that the branch predictor is initially in the “Strong NOT Taken”state.
(a) The number of mispredictions with a (0, 2) branch predictor is ______ out of 100 and is asymptotically _______ .
(b) The number of mispredictions with a (0, 3) branch predictor is ______ out of 100 and is asymptotically _______ .
(c) The minimum number of mispredictions with a (0, k) branch predictor is
______ , is asymptotically _______ and occurs for k = ______ .
(d) The number of mispredictions with a (2, 2) correlating branch predictor is
______ out of 100 and is asymptotically _______ . (An (m, k) correlating branch predictor keeps track of the outcomes of the most recent branches – both local and global.
(e) As the number of iterations, n , tends to infinity, the minimum number of mispredictions with an (m, k) correlating branch predictor is achieved for m = ______ and k = _____ . For this predictor, the number of mispredictions is
______ out of 100 and is asymptotically _______ .
