MIPS Pipeline Forwarding (double data hazard)

Question

In the Patterson & Hennessy Book:

But can't this be handled as a EX hazard:

Why is forwarding done in the MEM stage? And how? With 1 stall (for the 2nd add, I will need result from EX in next EX)?

Answer 1

Document used http://www.cs.cornell.edu/courses/cs3410/2011sp/faq/faq_pa1.html

I'll rewrite EX and MEM hazard condition (dropping !=0 part for simplicity), before we will take in account "double data hazard" (original rules):

EX Hazard

 if (EX/MEM.RegWrite and (EX/MEM.RegisterRd == ID/EX.RegisterRs)  # =EX_h_Rs 
   ) ForwardA = 10
 if (EX/MEM.RegWrite and (EX/MEM.RegisterRd == ID/EX.RegisterRt)  # =EX_h_Rt
   ) ForwardB = 10

I'll call conditions EX_h_Rs and EX_h_Rt to keep formulas shorter

MEM Hazard (original condition)

 if (MEM/WB.RegWrite and (MEM/WB.RegisterRd == ID/EX.RegisterRs)) ForwardA = 01 
 if (MEM/WB.RegWrite and (MEM/WB.RegisterRd == ID/EX.RegisterRt)) ForwardB = 01

====

And our example with two types of hazard at once, between (1st and 3rd) & (2nd and 3rd) at same time:

add $1, $1, $2 
add $1, $1, $3 
add $1, $1, $4

or (promlem cycle is marked with ** on top and bottom)

                **   
add C+A -> A ... A
           v     ?  
     add B+A -> A
                v   
          add C+ A -> A     
                **     

According to my link, after taking into account double EX + MEM hazard: (without !=0 and reordered boolean terms), Updated rules of MEM Hazard:

Let's revise the forwarding conditions for MEM hazard to take care of 'double' data hazards

 if (MEM/WB.RegWrite and (MEM/WB.RegisterRd = ID/EX.RegisterRs) and 
  not (EX/MEM.RegWrite and (EX/MEM.RegisterRd == ID/EX.RegisterRs)) 
  ) 
   ForwardA = 01
 if (MEM/WB.RegWrite and (MEM/WB.RegisterRd = ID/EX.RegisterRt) and 
  not (EX/MEM.RegWrite and (EX/MEM.RegisterRd == ID/EX.RegisterRt)) 
 ) 
   ForwardB = 01

Or the same using short record of EX_h_*

 if (MEM/WB.RegWrite and (MEM/WB.RegisterRd = ID/EX.RegisterRs) and 
  not ( EX_h_Rs ) 
  ) 
   ForwardA = 01
 if (MEM/WB.RegWrite and (MEM/WB.RegisterRd = ID/EX.RegisterRt) and 
  not ( EX_h_Rt ) 
 ) 
   ForwardB = 01

which means:

Try to forward from MEM/WB to EX; if there is no forward into same input operand from EX/MEM pipeline registers.

Or the same

Don't even try to forward from MEM/WB to EX; if there is already forwarding of more recent result from EX/MEM.

I'll try to illustrate:

add C+A -> A     A'
                 v?  (forwarding to 3rd instruction) 
           A -> A''
                v?
          add C+A -> A          

so, for third instruction original rules will say that Both A' from first instruction and A'' from second instruction should be forwarded (but mux can't be fed from two sources at single moment of time). And modifying of MEM hazard condition says that A' should not be tryed to forward if there is active forwarding of A'' which is more recent.

So; your drawing is right, there will be 2 EX Hazards forwarding; But MEM hazard forwarding should not be tried if there is already active EX Hazard forwarding.

Answer 2

This is clearly an error in the book's 4th edition (the parenthesis are unbalanced, for one). Curiously the book's most recent edition (4th Edition Revised) adds a missing closing ')' but... ends up with an incorrect condition still:

I think this would be the correct version of the conditions:

if (MEM/WB.RegWrite
and (MEM/WB.RegisterRd ≠ 0)
and not(EX/MEM.RegWrite and (EX/MEM.RegisterRd ≠ 0)
       and (EX/MEM.RegisterRd = ID/EX.RegisterRs))
and (MEM/WB.RegisterRd = ID/EX.RegisterRs)) Forward = 01

if (MEM/WB.RegWrite
and (MEM/WB.RegisterRd ≠ 0)
and not(EX/MEM.RegWrite and (EX/MEM.RegisterRd ≠ 0)
       and (EX/MEM.RegisterRd = ID/EX.RegisterRt))
and (MEM/WB.RegisterRd = ID/EX.RegisterRt)) Forward = 01