Question

Given the following sequence of instructions:

lw $s2, 0($s1) //1

lw $s1, 40($s3) //2

sub $s3, $s1, $s2 //3

add $s3, $s2, $s2 //4

or $s4, $s3, $zero //5

sw $s3, 50($s1) //6

a.

List the read after write (current instruction is reading certain registers which haven’t been written back yet) data dependencies. As an example , 3 on 1 ($s2) shows instruction 3 has data dependency on instruction 1 since it is reading register $s2.

b.

Assume the 5 stage MIPS pipeline with no forwarding and each stage takes 1 cycle. No inserting of NOPs, you let the processor stall on hazards. How many times does the processor stall(notice the stall happens when the register you want to read hasnt been written back from previous instructions)?Where does the stall happen?i.e, specify the stall between instruction #x and instruction #y How long is each stall (in the unit of cycles)? What is the execution time (in cycles) for the whole program? Sketch a diagram(refer to Figure 4.30 on page 280 of the textbook ) to explain your answer.

c.

Assume the 5 stage MIPS pipeline with full forwarding Will all the stall you saw in Question b be eliminated? If not, insert NOPs instead of stall to eliminate the hazards. Sketch a diagram to illustrate

your answer

Answer 1

a. Read-after-Write data dependencies:

• 3 on 1 ($s2) - Instruction 3 has data dependency on instruction 1 since it is reading register $s2
• 3 on 2 ($s1) - Instruction 3 has data dependency on instruction 2 since it is reading register $s1
• 4 on 1 ($s2) - Instruction 4 has data dependency on instruction 1 since it is reading register $s2
• 5 on 4 ($s3) - Instruction 5 has data dependency on instruction 4 since it is reading register $s3
• 6 on 2 ($s1) - Instruction 6 has data dependency on instruction 2 since it is reading register $s1
• 6 on 4 ($s3) - Instruction 6 has data dependency on instruction 4 since it is reading register $s3

b. Pipeline Diagram:

	1	2	3	4	5	6	7	8	9	10	11	12	13	14
1	IF	ID	EX	MEM	WB
2		IF	ID	EX	MEM	WB
3			IF	nop	nop	ID	EX	MEM	WB
4						IF	ID	EX	MEM	WB
5							IF	nop	nop	ID	EX	MEM	WB
6										IF	ID	EX	MEM	WB

• We can see that the processor is having stalls for 2 times.
  • One is at instruction 3
  • Another one is at instruction 5
• For every stall, it is taking 2 cycles.
• The total execution time: 14 cycles

c. We can place a nop after instruction 2 so that the value of $s1 can be directly forwarded from the MEM stage of instruction 2 to the EX stage of instruction 3.

	1	2	3	4	5	6	7	8	9	10	11
1	IF	ID	EX	MEM	WB
2		IF	ID	EX	MEM	WB
nop
3				IF	ID	EX	MEM	WB
4					IF	ID	EX	MEM	WB
5						IF	ID	EX	MEM	WB
6							IF	ID	EX	MEM	WB