Search code examples
assemblymipspipelinecpu-architecture

MIPS language to avoid pipeline stalls

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!

Solution

  • 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.