MIPS Pipeline

[changhengliou]

R type pipeline

Hazard: 1:25:30

• Structure hazard: hardware resources
• Data hazard: requires data from prior computation that is not ready
• Control hazard: need to know where should go next

Structure hazard

Data hazard

Solution:

• Insert dummy instruction nop, ex: sll $0, $0, 0
  • wasting computing resources
  • increase program size
  • violate the beauty of MIPS micro architecture, compiler writer has to consider the underlying 5 stages
• Hardware stall
  • detect destination register == source register
• Forwarding

Add-Add dependency

Add-Load dependency

Not working, because lw at execution stage is register address instead of register value. The only way to handle this is stall it.

[changhengliou]

Required control signal

• Execution stage
  • ALUOp: what ALU should do
  • ALUSrc: reg2 or immediate
  • RegDst: where to write destination
• Memory Stage
  • Branch: is branch instruction
  • MemRd: are we reading memory
  • MemWr: are we writing memory
• Write back Stage
  • MemtoReg: which value to write back
  • RegWrite: enable RF writing

Stall is a must when there is a dependency for lw and its next instruction

if (ID/EX.MemRead && // if at execution stage, the instruction is memory read; the only instruction is memRead is lw 
  ((ID/EX.RegisterRt == IF/ID.RegisterRs) || 
  (ID/EX.RegisterRt == IF/ID.RegisterRt))
)
  stall frontend and insert `NOP` in execution stage

Control hazard

We know branch is happened or not at the execution stage, which means intuitively, we have to stall 3 cycles.

Solution:

• Assuming branch is not happened
  • Possibly mis-run 3 stages
• Early branching We can actually know branch is happened in decode stage, because we already have everything we need. And thus, we save 2 cycles.

  36 sub $10, $4, $8
  40 beq $1, $3, 72
  44 and $12, $2, $5
  72 lw $4, 50($7)

  

[changhengliou]

[changhengliou]

Branch Prediction