Pipelined Control Overview
Pipeline Forwarding 1
This design shows the correct logic for synchronizing control signals and instructions, but lacks forwarding logic and hazard detection.
CS@VT
Computer Organization II
©2005-2015 McQuain
Consider this sequence:
sub $2, $1, $3 and $12, $2, $5
# value for $2 known end of EX stage; # stored in $2 in WB stage
# enters ID stage when sub enters EX; # and needs $s2 when enters EX stage; # sub is in MEM stage by then;
# $2 has not been written yet
Tick 0: Tick 1: Tick 2: Tick 3:
sub and
sub
and sub
and sub
Data hazard?
Data Hazards in ALU Instructions
Pipeline Forwarding 2
CS@VT Computer Organization II ©2005-2015 McQuain
So this sequence leads to a data hazard involving $2: sub $2, $1, $3
and $12, $2, $5
Can we resolve the hazard simply by forwarding?
Tick 0: sub Tick 1: and Tick 2:
Tick 3:
Yes!
sub
and sub
and sub
But we must deliver the computed value at the right time; the next tick. And, that value will be sitting in the EX/MEM interstage buffer.
Data Hazards in ALU Instructions
Pipeline Forwarding 3
CS@VT Computer Organization II ©2005-2015 McQuain
On the one hand, this is obvious. The first instruction writes a value into a register that is subsequently used as input by the second instruction:
sub $2, $1, $3 and $12, $2, $5
We must know the register numbers for both instructions in order to detect the hazard.
More precisely, we must know rd for the first instruction and both rs and rt for the second instruction.
So, we must save those register numbers, via the interstage buffers. Some notation will help us speak precisely about what’s going on:
B.RegisterRX = register number for RX sitting in interstage pipeline buffer B
Detecting the Hazard Pipeline Forwarding 4
CS@VT Computer Organization II ©2005-2015 McQuain
Passing the register numbers:
rs (left operand) register number
rt (right operand) register number
rd (destination) register number
Logic “box” that manages forwarding of operands
A Glance Ahead Pipeline Forwarding 5
CS@VT Computer Organization II ©2005-2015 McQuain
Passing the register numbers:
123
1: rd for instruction currently in EX stage
2: rd for instruction currently in MEM stage 3: rd for instruction currently in WB stage
They may all be different!
A Glance Ahead Pipeline Forwarding 6
CS@VT Computer Organization II ©2005-2015 McQuain
Now, for this sequence of instructions:
sub $2, $1, $3 and $12, $2, $5
So, we detect the hazard because we see that:
EX/MEM.RegisterRd == ID/EX.RegisterRs
Hence, we must forward the ALU output value from the EX/MEM interstage buffer to the
rs input to the ALU. Apparently, we’ll need to:
– pass (at least some) register numbers forward via the interstage buffers
– add a logic unit to compare those register numbers to detect hazards
– add data connections to support transferring data values being forwarded
– add some more selection logic (multiplexors)
Detecting the Hazard Pipeline Forwarding 7
CS@VT Computer Organization II ©2005-2015 McQuain
Now, consider this sequence:
sub $2, $1, $3 and $12, $2, $5
or $13, $6, $2
# value for $2 known in EX stage
# enters ID stage when sub enters EX
# enters ID stage when sub enters MEM; # $2 has not been written yet
Tick 0: sub Tick 1: and Tick2: or Tick 3:
Tick 4:
sub
and sub
or and sub
or and sub
Data hazard?
Data Hazards in ALU Instructions
Pipeline Forwarding 8
CS@VT Computer Organization II ©2005-2015 McQuain
Again, we have a data hazard:
sub $2, $1, $3 and $12, $2, $5
or $13, $6, $2
# value for $2 known in EX stage
# enters ID stage when sub enters EX
# enters ID stage when sub enters MEM;
Tick 0: sub Tick 1: and Tick2: or Tick 3:
Tick 4:
sub
and sub
or and sub
or and sub
Yes!
Now, we must deliver the computed value after a delay of one tick, from MEM/WB.
Data Hazards in ALU Instructions
Pipeline Forwarding 9
CS@VT Computer Organization II ©2005-2015 McQuain
Again, we have a data hazard:
sub $2, $1, $3 and $12, $2, $5
or $13, $6, $2
So, we detect the hazard because we see that:
MEM/WB.RegisterRd == ID/EX.RegisterRt
Hence, we must forward the ALU output value from the MEM/WB interstage buffer to
the rt* input to the ALU.
So… detecting data hazards is a multi-stage affair.
* QTP: why does this one go to the rt input?
Detecting the Hazard Pipeline Forwarding 10
CS@VT Computer Organization II ©2005-2015 McQuain
Now, consider this sequence:
sub $2, $1, $3 and $12, $2, $5 or $13, $6, $2
add $14, $2, $2
# value for $2 known in EX stage;
# enters ID stage when sub enters EX; # enters ID stage when sub enters MEM;
# enters ID stage when sub enters WB;
# $2 has not been written yet, but. . .
Tick 0: sub
Tick 1: and sub
Tick2: or and sub
Tick 4:
Tick 3: add or
and sub
add or and sub
Data hazard?
Data Hazards in ALU Instructions
Pipeline Forwarding 11
CS@VT Computer Organization II ©2005-2015 McQuain
Now, there’s almost a hazard… but not quite…
sub $2, $1, $3 and $12, $2, $5 or $13, $6, $2 add $14, $2, $2
# value for $2 known in EX stage;
# enters ID stage when sub enters EX; # enters ID stage when sub enters MEM; # enters ID stage when sub enters WB;
Tick 0: sub Tick 1: and Tick2: or Tick 3: add Tick 4:
Tick 5:
sub
and sub
or and sub
add or
and sub
add or and sub
Now, we deliver the computed value to the register file in the first half of tick 4, and it’s not read until the second half of that tick!
Data Hazards in ALU Instructions
Pipeline Forwarding 12
CS@VT Computer Organization II ©2005-2015 McQuain
Now, consider this sequence:
sub $2, $1, $3 and $12, $2, $5 or $13, $6, $2 add $14, $2, $2
# value for $2 known in EX stage;
# enters ID stage when sub enters EX; # enters ID stage when sub enters MEM; # enters ID stage when sub enters WB
sw $15, 100($2) # enters ID stage after sub is done
Tick 0: sub
Tick 1: and sub
Tick 2: or Tick 3: add Tick 4: sw Tick 5:
and sub
or and sub
add or and sub sw add or and
Data hazard?
Data Hazards in ALU Instructions
Pipeline Forwarding 13
CS@VT Computer Organization II ©2005-2015 McQuain
Here’s what we (seem to) know so far: ALU-related data hazards occur when
EX/MEM.RegisterRd = ID/EX.RegisterRs EX/MEM.RegisterRd = ID/EX.RegisterRt
MEM/WB.RegisterRd = ID/EX.RegisterRs MEM/WB.RegisterRd = ID/EX.RegisterRt
However, we have overlooked (at least) one thing…
Fwd from EX/MEM pipeline reg
Fwd from MEM/WB pipeline reg
Detecting the Need to Forward Pipeline Forwarding 14
CS@VT Computer Organization II ©2005-2015 McQuain
We don’t need to forward unless the forwarding (earlier) instruction does actually write a value to a register:
EX/MEM.RegWrite == 1 MEM/WB.RegWrite == 1
And we only forward if Rd for that instruction is not $zero:
EX/MEM.RegisterRd != 0 MEM/WB.RegisterRd != 0
Detecting the Need to Forward Pipeline Forwarding 15
CS@VT Computer Organization II ©2005-2015 McQuain
Value from register fetch in ID stage Value from WB stage
Value from ALU execution
Forwarding unit selects among three candidates for the register operands.
Datapath Change: ALU Operand Selection Pipeline Forwarding 16
CS@VT Computer Organization II ©2005-2015 McQuain
Datapath Change: ALU Operand Selection Pipeline Forwarding 17
CS@VT Computer Organization II ©2005-2015 McQuain
Select source for left operand rs
Select source for right operand rt
Possible rd numbers
rs and rt for the instruction in the EX stage,
ID/EX.RegisterR s
ID/EX.RegisterRt
Select correct rd number
rd # from WB stage, MEM/WB.RegisterRd
rd # from MEM stage, EX/MEM.RegisterRd
Forwarding Paths Pipeline Forwarding 18
CS@VT Computer Organization II ©2005-2015 McQuain
If ( EX/MEM.RegWrite and
EX/MEM.RegisterRd != 0 and
EX/MEM.RegisterRd == ID/EX.RegisterRs ) then
ForwardA = 10
If ( EX/MEM.RegWrite and
EX/MEM.RegisterRd != 0 and EX/MEM.RegisterRd == ID/EX.RegisterRt )
then
ForwardB = 10
QTP: could BOTH occur with respect to the same
instruction?
Conditions for EX Hazard Pipeline Forwarding 19
CS@VT Computer Organization II ©2005-2015 McQuain
If ( MEM/WB.RegWrite and
MEM/WB.RegisterRd != 0 and MEM/WB.RegisterRd == ID/EX.RegisterRs )
then
ForwardA = 01
If ( MEM/WB.RegWrite and
MEM/WB.RegisterRd != 0 and MEM/WB.RegisterRd == ID/EX.RegisterRt )
then
ForwardB = 01
QTP: could BOTH an EX hazard and a MEM hazard occur with respect to the same instruction?
Conditions for MEM Hazard Pipeline Forwarding 20
CS@VT Computer Organization II ©2005-2015 McQuain
Consider the sequence:
add $1,$1,$2
sub $1,$1,$3
or $1,$1,$4
Both hazards occur… which value do we want to forward?
Tick 2: or sub add
Tick 3: … or
sub add
Double Data Hazard Pipeline Forwarding 21
CS@VT Computer Organization II ©2005-2015 McQuain
Consider the sequence:
add $1,$1,$2
add $1,$1,$3
add $1,$1,$4
Revise MEM hazard condition:
– Only forward if EX hazard condition is not true
Double Data Hazard Pipeline Forwarding 22
CS@VT Computer Organization II ©2005-2015 McQuain
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 )
then
ForwardA = 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 )
then
ForwardB = 01
Revised Conditions for MEM Hazard
Pipeline Forwarding 23
CS@VT Computer Organization II ©2005-2015 McQuain
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 )
Instruction leaving MEM stage DOES write a value
Instruction leaving EX stage DOES NOT write a value
OR
it doesn’t write to Rs register of instruction leaving ID stage
Instruction leaving MEM stage DOES write a value to the Rs register of instruction leaving ID stage
then
ForwardA = 01
MEM Hazard Breakdown
Pipeline Forwarding 24
CS@VT Computer Organization II ©2005-2015 McQuain
Simplified Datapath with Forwarding Pipeline Forwarding 25
CS@VT Computer Organization II ©2005-2015 McQuain
Yes: add
sub and or slt sw
No: lw
beq j
This design shows the correct logic for synchronizing control signals and instructions, and forwarding logic, but lacks hazard detection.
Unsimplified Datapath with Forwarding Pipeline Forwarding 26
CS@VT Computer Organization II ©2005-2015 McQuain
Consider the following scenario:
add $t1, $t2, $t3 lw $t1, ($t2)
rs rt
The Forwarding unit design sees $t1 as an input register for the second lw…
So it would forward… needlessly. Is that a problem?
How could we fix this?
A Question to Ponder Pipeline Forwarding 27
CS@VT Computer Organization II ©2005-2015 McQuain