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
enter image description here


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

Your doubts seem well founded, there could be an error in the solution manual. Also the MEM and MEB could be typos, I don't have the H&P textbook anymore, but I don't remember learning about two different memory stages.

Do you have a professor to ask that assigned this problem?

  • \$\begingroup\$ I found that many (almost all) solutions have two states MEM and MEB, so I dont really think this can be a typo, giving how good this book is and how many times this has repeated in the solutions. The author must really meant something out of that, but he failed to detail it. However I do once found one typo in the other solution. And nope am not having professor to ask this. I am doing job and learning this independently for an engineering entrance exam. \$\endgroup\$ – anir123 Jul 7 '17 at 13:14

Your Answer

