I need help in understanding the solution from solution manual. The question is from the exercise 4.22.1 of chapter 4 in the book Computer Organization and Design by Patterson and Hannessey (4th edition). The question is about branching in instruction pipeline.

The question
We assume that the following MIPS code is executed on a pipelined processor with a 5-stage pipeline, full forwarding, and a predict-taken branch predictor. Consider the instruction sequence:
Label1: LW R2,0(R2)
BEQ R2,R0,Label ; Taken once, then not taken
OR R2,R2,R3
SW R2,0(R5)
Draw the pipeline execution diagram for this code, assuming there are no delay slots and that branches execute in the EX stage.

The solution given is as follows:

The solution
enter image description here

The doubt
I dont understand why in 4th cycle LW have *** (blue underlined). Cant we execute ID of LW in 4th cycle? Is it unsaid rule that if the branch-decision-making-stage (that is red underlined EX of BEQ) gets delayed (here due to data dependency on first LW for R2), then delay all the corresponding next stages in the following instructions?


1 Answer 1


So, "bubbles" or stalls due to dependencies are inserted after the instruction decode of the instruction with the dependency (the BEQ). It seems you are comfortable with this. However, as a result, the rest of the pipeline (containing the second LW) in it is stalled as well.

Consider it like this: it's not possible to stall an instruction and not stall the instructions following it. That would require two instructions to be in the same pipeline stage at the same time: if LW was not also stalled, then the EX of the BEQ and the EX of the LW would occur on the same clock cycle: not possible!

  • \$\begingroup\$ ok I think there is something more that added to my confusion: 3rd instruction LW is fetched immediately after 2nd instruction BEQ. But that is not the case with OR. It is fetched far after when preceding BEQ is in MEM stage. Is the LW still fetched after 2nd BEQ, before OR, but because prediction went wrong it was abandoned and OR` is fetched? Something like this:image \$\endgroup\$
    – Mahesha999
    Commented Jul 4, 2017 at 5:05
  • \$\begingroup\$ @Mahesha999 Yes, I believe that is correct. \$\endgroup\$
    – uint128_t
    Commented Jul 4, 2017 at 21:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.