Computer Architecture
Control Hazards + Branch Prediction
Prof. Sagnik Nath
CSE 120
Contents
2
• Control hazards strategies comparison
• Control Hazard Wrap up
• Structural Hazards
• Pipeline summary
•
Comparing Control Hazard Strategies
3
Control point Branch strategy Clock cycle penalty
Strategy 1:MEM
Stall pipeline till
branch resolved
(unconditional stall)
Pipeline always stalled for 2
extra cycles
Strategy 2: ID
Stall pipeline till
branch resolved;
(unconditional stall)
Pipeline always stalled for 1
extra cycle
Strategy 3: ID Predict not taken
Pipeline stalled for 1 extra
cycle if branch indeed taken,
else no stall if branch taken
• Strategy 1: Branch decision available in MEM stage => requires 2
NOPs after each
xBranch computed here
4
xBranch decision available here
5
Strategy 3: Most
efficient for
Static Branch
prediction!
Only 1 NOP
introduced in
pipeline and that
too if branch
turns out to be
indeed taken;
else pipeline
flows as is !
6
Comparing Control Hazard Strategies
9
• 15% branch frequency, 65% branches are taken
• Assume CPI=1 for non branch instructions
Control point Branch strategy Clock cycle penalty Global CPI
Strategy 1:MEM
Stall pipeline till
branch resolved
(unconditional stall)
Pipeline always stalled for 2
extra cycles
0.85 * 1 + 0.15 * (2+1)
=1.3
Strategy 2: ID
Stall pipeline till
branch resolved;
(unconditional stall)
Pipeline always stalled for 1
extra cycle
0.85 * 1 + 0.15 * (1+1)
=1.15
Strategy 3: ID Predict not taken
Pipeline stalled for 1 extra cycle
if branch indeed taken, else no
stall if branch taken
0.85 * 1 + 0.15 *0.65*
(1+1) + 0.15 * 0.35 *
1=1.098
Brief Idea of Structural Hazards
8
• Occurs when we try to read and write to the same resource at the same time
• Memory Access: In our processor design, we have different physical memory for
Instructions and Data. No structural hazard possible. Will be an issue for
processors with common physical memory (beyond scope of this course)
• Register file: For reading and writing to same register at the same time, this
could be an issue. Already covered in lecture on Data forwarding . If you have
fast register file (Write and read on different clock edge), this control hazard is
resolved.
Pipeline Timing Diagram Summary
9
Pipeline Timing Diagram Summary
• Compact way to represent state of pipeline over time
• Time is horizontal axis (1 column per cycle)
• Program order is vertical axis (1 row per instruction)
• Recommend having Datapath handy to visualize actual constraints
• For given example, assume forwarding available with datahazard stall and fast register file
12
Instruction Clock Cycle =>
0 1 2 3 4 5 6 7 8 9
ld x1, 0(x2) F D X M W
sub x4, x1, x3
and x6, x1, x7
or x8, x1, x9
Pipeline Timing Diagram Summary
• Compact way to represent state of pipeline over time
• Time is horizontal axis (1 column per cycle)
• Program order is vertical axis (1 row per instruction)
• Recommend having Datapath handy to visualize actual constraints
• For given example, assume forwarding available with datahazard stall and fast register file
12
Instruction Clock Cycle =>
0 1 2 3 4 5 6 7 8 9
ld x1, 0(x2) F D X M W
sub x4, x1, x3 F D D X M W
and x6, x1, x7 F F D X M W
or x8, x1, x9 F D X M W
Pipeline Timing Diagram Summary
• Compact way to represent state of pipeline over time
• Time is horizontal axis (1 column per cycle)
• Program order is vertical axis (1 row per instruction)
• Recommend having Datapath handy to visualize actual constraints
• For given example, assume forwarding available with datahazard stall and fast register file
12
Instruction Clock Cycle => stall available
0 1 2 3 4 5 6 7 8 9
ld x1, 0(x2) F D X M W
sub x4, x1, x3 F
F
D
D
D
D
X
D
M
X
W
M W
and x6, x1, x7 F F D X M W
F F F D X M W
or x8, x1, x9 F D
F
X
D
M
X
W
M W
* Assume no forwarding; but fast
register file and data hazard
13
END OF
COVERAGE FOR
MIDTERM
Midterm Preparation:
• Study all lecture videos and corresponding slides till this mark
• Go through HW 1,2,3,4