Situations that prevent starting the next instruction in the next cycle Structural hazards
– A required resource is busy Data hazard
– Need to wait for previous instruction to complete its data read/write
Control hazard
– Deciding on control action depends on previous instruction
Hazards Pipeline 1
CS@VT Computer Organization II ©2005-2015 McQuain
Conflict for use of a resource
In MIPS pipeline with a single memory
– Load/store requires data access
– Instruction fetch would have to stall for that cycle
Hence, pipelined datapaths require separate instruction/data memories
– Or separate instruction/data caches
– Or dual-ported memories
Structural Hazards Pipeline 2
CS@VT Computer Organization II ©2005-2015 McQuain
An instruction depends on completion of writeback by a previous instruction
add $s0, $t0, $t1 // writes $s0 from WB stage sub $t2, $s0, $t3 // needs value in ID stage
2-stage stall
Data Hazards Pipeline 3
CS@VT Computer Organization II ©2005-2015 McQuain
Use result when it is computed
– Don’t wait for it to be stored in a register
– Requires extra connections in the datapath (& more control logic?)
no stall
Forwarding (aka Bypassing) Pipeline 4
CS@VT Computer Organization II ©2005-2015 McQuain
Can’t always avoid stalls by forwarding
– If value not computed when needed
– Can’t forward backward in time!
1-stage stall
Load-Use Data Hazard Pipeline 5
CS@VT Computer Organization II ©2005-2015 McQuain
Reorder code to avoid use of load result in the next instruction C code for A = B + E; C = B + F;
lw $t1, 0($t0) lw $t2, 4($t0) add $t3, $t1, $t2 sw $t3, 12($t0) lw $t4, 8($t0) add $t5, $t1, $t4 sw $t5, 16($t0)
lw $t1, 0($t0) lw $t2, 4($t0) lw $t4, 8($t0) add $t3, $t1, $t2 sw $t3, 12($t0) add $t5, $t1, $t4 sw $t5, 16($t0)
stall
stall
Who reorders the code?
13 cycles 11 cycles
Code Scheduling to Avoid Stalls Pipeline 6
CS@VT Computer Organization II ©2005-2015 McQuain
Branch determines flow of control
Fetching next instruction depends on branch outcome Register comparison done in EX stage
Branch target address computed in EX stage MUX selection done in MEM stage
What instruction do we fetch when BEQ is in ID stage?
Control Hazards: beq Pipeline 7
CS@VT Computer Organization II ©2005-2015 McQuain
How can we deal with BEQ?
Stall until we know whether (& where) to branch? Make the decision and calculate the address earlier?
Guess whether the branch will be taken?
Control Hazards: beq Pipeline 8
CS@VT Computer Organization II ©2005-2015 McQuain
Wait until branch outcome determined before fetching next instruction
How many cycles does this cost?
Stall on Branch Pipeline 9
CS@VT Computer Organization II ©2005-2015 McQuain
What new hardware would be needed to decide earlier?
Must compare the registers before the EX stage
Must compute the branch target address before the EX stage
Can we know what to do by the time BEQ enters the ID stage?
Early Decision Pipeline 10
CS@VT Computer Organization II ©2005-2015 McQuain
Longer pipelines can’t readily determine branch outcome early – Stall penalty becomes unacceptable
Predict outcome of branch
– Only stall if prediction is wrong
In MIPS pipeline
– Can predict branches will not be taken
– Fetch sequential instruction after branch, with no delay
Branch Prediction Pipeline 11
CS@VT Computer Organization II ©2005-2015 McQuain
Prediction correct
Prediction incorrect
MIPS with Predict Not Taken Pipeline 12
CS@VT Computer Organization II ©2005-2015 McQuain
Pipelining improves performance by increasing instruction throughput
– Executes multiple instructions in parallel
– Each instruction has the same latency
Subject to hazards
– Structure, data, control
Instruction set design affects complexity of pipeline implementation
Pipeline Summary Pipeline 13
CS@VT Computer Organization II ©2005-2015 McQuain