Understanding execution of sequence of pipeline instructions with branching

Thread Starter

Mahesh Abnave

Joined Jan 12, 2016
I need help in understanding the solution from solution manual. The question is from the exercise 4.22.2 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 delay slots and that branches execute in the EX stage.

The solution given is as follows:

The solution

  • Why there is a stall (highlighted ***) in cycle 7 for LW (4th executed instruction)? I understand that LW reads R2 which is modified by OR ( executed in delay slot after BEQ, before LW). But OR reads it in cycle 6 in the EX stage. So LW should be able to execute EX stage in cycle 7 (since full forwarding is allowed). But why its not shown like that?
  • Also notice that in cycle (column) 4, for BEQ instruction (2nd instruction), their is a stall (i.e. ***). This is because BEQ reads R2 which is loaded by LW (1 st instruction) in its MEM stage. So BEQ has to wait till LW's MEM completes. However the same situation occurs in instructions 4 and 5. But in this case BEQ (5th instruction) is allowed to execute its EX stage in the same cycle as LW's (3rd instruction's) MEM stage. Shouldn't BEQ (5th instruction) be stalled again to make it wait till LW's (4th instruction's) MEW completes?
  • Also I noticed, there are two 4th stages. In some instructions, 4th stage is labeled MEM (for example 1st instruction LW, 4th cycle) and in some instructions, its labeled MEB (for example 2nd instruction LW, 6th cycle). What are the differences between MEM and MEB? I searched whole book, but their is no mention of MEB, only in solution manual, its specified. Or may be I might have missed some pages.
I dont whether the question related to the instruction pipelining is on topic or not. Beg me pardon if I shouldnt be posting this on this site.