Chapter …
Morgan Kaufmann Publishers 6 November, 2018
Chapter 4 — The Processor 1
Chapter 4 — The Processor — 88
EX for Store
Chapter 4 — The Processor — 89
MEM for Store
Morgan Kaufmann Publishers 6 November, 2018
Chapter 4 — The Processor 2
Chapter 4 — The Processor — 90
WB for Store
Chapter 4 — The Processor — 91
Multi-Cycle Pipeline Diagram
Form showing resource usage
Morgan Kaufmann Publishers 6 November, 2018
Chapter 4 — The Processor 3
Chapter 4 — The Processor — 92
Multi-Cycle Pipeline Diagram
Traditional form
Pop Quiz
How many cycles would it take the
following instructions to complete?
A: 5
B: 6
C: 7
D: 8
Chapter 4 — The Processor — 93
add $t2, $t0, $t1
lw $t3, 0($t2)
add $t4, $t5, $t3
Morgan Kaufmann Publishers 6 November, 2018
Chapter 4 — The Processor 4
Pop Quiz (answer)
Chapter 4 — The Processor — 94
1. add $t2, $t0, $t1
2. lw $t3, 0($t2)
3. add $t4, $t5, $t3
1 2 3 4 5 6 7 8
—————
F D X M W
F D X M W
* * * * *
F D X M W
Chapter 4 — The Processor — 95
Single-Cycle Pipeline Diagram
State of pipeline in a given cycle
Morgan Kaufmann Publishers 6 November, 2018
Chapter 4 — The Processor 5
Chapter 4 — The Processor — 96
Pipelined Control (Simplified)
Chapter 4 — The Processor — 97
Pipelined Control
Control signals derived from instruction
As in single-cycle implementation
Morgan Kaufmann Publishers 6 November, 2018
Chapter 4 — The Processor 6
Chapter 4 — The Processor — 98
Pipelined Control
Chapter 4 — The Processor — 99
Data Hazards in ALU Instructions
Consider this sequence:
sub $2, $1,$3
and $12,$2,$5
or $13,$6,$2
add $14,$2,$2
sw $15,100($2)
We can resolve hazards with forwarding
How do we detect when to forward?
§
4
.7
D
a
ta
H
a
z
a
rd
s
: F
o
rw
a
rd
in
g
v
s
. S
ta
llin
g
Morgan Kaufmann Publishers 6 November, 2018
Chapter 4 — The Processor 7
Chapter 4 — The Processor — 100
Dependencies & Forwarding
Chapter 4 — The Processor — 101
Detecting the Need to Forward
Pass register numbers along pipeline
e.g., ID/EX.RegisterRs = register number for
Rs sitting in ID/EX pipeline register
ALU operand register numbers in EX stage
are given by
ID/EX.RegisterRs, ID/EX.RegisterRt
Data hazards when
1a. EX/MEM.RegisterRd = ID/EX.RegisterRs
1b. EX/MEM.RegisterRd = ID/EX.RegisterRt
2a. MEM/WB.RegisterRd = ID/EX.RegisterRs
2b. MEM/WB.RegisterRd = ID/EX.RegisterRt
Fwd from
EX/MEM
pipeline reg
Fwd from
MEM/WB
pipeline reg
Morgan Kaufmann Publishers 6 November, 2018
Chapter 4 — The Processor 8
Chapter 4 — The Processor — 102
Detecting the Need to Forward
But only if forwarding instruction will
write to a register!
EX/MEM.RegWrite, MEM/WB.RegWrite
And only if Rd for that instruction is not
$zero
EX/MEM.RegisterRd ≠ 0,
MEM/WB.RegisterRd ≠ 0
Chapter 4 — The Processor — 103
Forwarding Paths
Morgan Kaufmann Publishers 6 November, 2018
Chapter 4 — The Processor 9
Chapter 4 — The Processor — 104
Forwarding Conditions
EX hazard
if (EX/MEM.RegWrite and (EX/MEM.RegisterRd ≠ 0)
and (EX/MEM.RegisterRd = ID/EX.RegisterRs))
ForwardA = 10
if (EX/MEM.RegWrite and (EX/MEM.RegisterRd ≠ 0)
and (EX/MEM.RegisterRd = ID/EX.RegisterRt))
ForwardB = 10
MEM hazard
if (MEM/WB.RegWrite and (MEM/WB.RegisterRd ≠ 0)
and (MEM/WB.RegisterRd = ID/EX.RegisterRs))
ForwardA = 01
if (MEM/WB.RegWrite and (MEM/WB.RegisterRd ≠ 0)
and (MEM/WB.RegisterRd = ID/EX.RegisterRt))
ForwardB = 01
Pop Quiz
We can always ”forward” our way around
instruction dependencies:
A: True
B: False
Chapter 4 — The Processor — 105
Morgan Kaufmann Publishers 6 November, 2018
Chapter 4 — The Processor 10
Chapter 4 — The Processor — 106
Double Data Hazard
Consider the sequence:
add $1,$1,$2
add $1,$1,$3
add $1,$1,$4
Both hazards occur
Want to use the most recent
Revise MEM hazard condition
Only fwd if EX hazard condition isn’t true
Chapter 4 — The Processor — 107
Revised Forwarding Condition
MEM hazard
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))
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))
ForwardB = 01
Morgan Kaufmann Publishers 6 November, 2018
Chapter 4 — The Processor 11
Chapter 4 — The Processor — 108
Datapath with Forwarding
Chapter 4 — The Processor — 109
Load-Use Data Hazard
Need to stall
for one cycle
Morgan Kaufmann Publishers 6 November, 2018
Chapter 4 — The Processor 12
Chapter 4 — The Processor — 110
Load-Use Hazard Detection
Check when using instruction is decoded
in ID stage
ALU operand register numbers in ID
stage are given by
IF/ID.RegisterRs, IF/ID.RegisterRt
Load-use hazard when
ID/EX.MemRead and
((ID/EX.RegisterRt = IF/ID.RegisterRs)
or
(ID/EX.RegisterRt = IF/ID.RegisterRt))
If detected, stall and insert bubble
Chapter 4 — The Processor — 111
How to Stall the Pipeline
Force control values in ID/EX register
to 0
EX, MEM and WB do nop (no-operation)
Prevent update of PC and IF/ID
register
Using instruction is decoded again
Following instruction is fetched again
1-cycle stall allows MEM to read data for
lw
Can subsequently forward to EX stage
Morgan Kaufmann Publishers 6 November, 2018
Chapter 4 — The Processor 13
Chapter 4 — The Processor — 112
Stall/Bubble in the Pipeline
Stall inserted
here
Chapter 4 — The Processor — 113
Stall/Bubble in the Pipeline
Or, more
accurately…
Morgan Kaufmann Publishers 6 November, 2018
Chapter 4 — The Processor 14
Chapter 4 — The Processor — 114
Datapath with Hazard Detection
Chapter 4 — The Processor — 115
Stalls and Performance
Stalls reduce performance
But are required to get correct results
Compiler can arrange code to avoid
hazards and stalls
Requires knowledge of the pipeline
structure
The BIG Picture