MIPS language to avoid pipeline stalls

Question

Regarding the MIPS assembly language which is thought in the pattersson's book, I have a question with inserting NOP between instructions to avoid pipeline stalls.

Consider the following code

lw   $s5, -16($s5)
sw   $s5, -16($s5)
add  $s5, $s5, $s5

We see there is a RAW hazard for $s5 between lw and sw. There is also a WAW hazard for $s5 betwween sw and add. So we have to insert two NOPs to avoid stalls. In other words, the pipeline diagram is

lw      IF     ID     EX     MEM     WB
sw             IF     ID     ---     EX     MEM     WB
add                   IF     ID      EX     MEM     --     WB

When sw is going to be executed, it has be wait for lw to put the data in a register. Therefore, there is one bubble. Also, when add wants to write the final result, it has to wait for the completion of the previous instruction (sw). That is another bubble.

So the modified code is

lw
NOP
sw
NOP
add

But the solution propose the following code

lw
NOP
NOP
sw
add

Which one is correct? I think mine!

Kind of poor style to completely replace a question like that.. now my answer seems completely random/unrelated — harold
@harold : I'm tempted to rollback the last change for that reason. Temptation too strong, I've reverted back to the previous version. If mahmood wants an answer to his newer question he can simply ask a new question on SO. — Michael Petch
I first asked part of the exercise and got an answer which was reasnable but mine was different. Later I saw that the answer is not applicable to the second part of the exercise. So, I replaced that... If I did wrong, I have to say sorry... — mahmood
@mahmood : no problem. In cases like that you should leave the question as is, and if you have a more specific question(or a different one) it is best to ask a new question. That allows the questions/answers/comments to match so they make sense to a person who stumbles on this question in the future. — Michael Petch

harold harold · Accepted Answer · 2015-11-26T12:54:57

Assuming a fairly standard pipeline, that WAW hazard doesn't exist, it might look sort of hazardy in the program code (in the sense that there are multiple writes to the same register), but there is no mechanism by which the ADD can complete before (or during) the LW (that would mean it calculated the result before the input was available). The SW doesn't write to a register so it doesn't matter, but the ADD can't complete before it either. Actually WAW hazards don't exist at all in the standard pipeline because instructions simply write back in order.

Your solution for the RAW hazard assumes there is WB->EX forwarding, which judging by their solution, there isn't. Without forwarders, the soonest you can use a result is when the ID of reading instruction lines up with the WB of the writing instruction.

Why (WB) and (EX) are not executed in one cycle?

Because it doesn't work. It doesn't work in question a either so I'm not sure what happened there. The premise of the question is that there is no forwarding to EX, so same as before, the soonest you can use a value after it is produced is when you line the ID of the reading instruction up with the WB of the writing instruction. EX just reads its inputs from the ID/EX pipeline register.

Also, for (a), I don't see any WAR on $6 from I1 to I3. Do you??

No, since neither I1 nor I3 modify $6, it's impossible to have any hazard. RAR is not a hazard.

MIPS language to avoid pipeline stalls

1 Answers