Q1. Given our 5-stage pipeline and the following sequence of instructions.
lw $5, 1000($1)
addi $11, $5,400
lw $2, 4($5)
lw $3, 8($11)
sub $4, $11, $2
add $4, $4, $3
or $8, $8, $1
If the pipeline has no forwarding or hazard detection, insert nops for maintaining the correctness during
execution of the above sequence. “No forwarding” includes regfile-regfile forwarding (i.e., a register read and
write in the same cycle returns the old value).
Q2. Given the code sequence in Q1, can you rearrange the instructions while maintaining the correctness and
insert fewer nops? Please show your solution.
Q3. (Forwarding will be covered in Tuesday’s lecture). For the code in Q1, what is the expected speedup for a
machine that has support for forwarding, vs one that does not (i.e., uses hardware stalls or adds sw nops)?
Since we cannot really calculate speedup in the traditional way for such a short sequence on a pipelined
machine, just explain how many stalls are saved each time the code is executed.
Q4. Indicate dependences for the following instructions:
or r1, r2, r3
or r2, r1, r4
or r1, r1, r2
Q5. Insert NOP to eliminate data hazards for the instruction sequence in Q4. Assume there is no forwarding
Q6. A program consists of the following: 20% add, 30% addi, 10% beq, 20% lw, and 20% sw. Assume that there
are no pipeline stalls. What fraction of total cycles is the data memory used? Assume the 5-stage MIPS pipeline
Q7. With the same instruction mix as Q6, what fraction of the total cycles is the output of the sign extension
block needed? (“needed” means it produces a result that is used in the instruction.) What is this unit doing in
cycles in which its output is not needed?