UART
Pipelining Hazards
Christopher Mar
Types of Hazards
Structural Hazards
Data Hazards
Control Hazards
Types of Hazards
Structural Hazards
Data Hazards
Control Hazards
Structural Hazards
Hardware limitations
Multiple instructions require a functional unit at the same time
Structural Hazard Examples
A register file only has one read port
All instructions that require two register reads (e.g. R-Type and branch instructions) would use the register file for 2 clock cycles
Next instruction address calculated by ALU rather than separate adder
Structural Hazard Creation
ALU
PC
Add
4
Instruction Memory
M
u
x
IF/ID
Register File
Sign Extend
16
32
M
u
x
M
u
x
ID/EX
EX/MEM
Comp.
Branch
Taken
Data Memory
MEM/WB
M
u
x
Use ALU to calculate PC + 4
Types of Hazards
Structural Hazards
Data Hazards
Control Hazards
Data Hazards
Multiple instructions being executed in parallel changes when values are available
A data hazard is when multiple instructions in the pipeline access the same data in an order other than the order of the instructions
3 Types of Data Hazards
Read After Write (RAW)
Write After Read (WAR)
Write After Write (WAW)
RAW Definition
Read After Write (RAW)
An instruction attempts to read a result that has not been saved yet
RAW Example
ALU
Reg
Mem
DM
Reg
ALU
Reg
Mem
DM
Reg
ALU
Reg
Mem
DM
Reg
Mem
ADDU R1, R2, R3
SUB R4, R1, R5
AND R6, R1, R7
OR R8, R1, R9
NOR R10, R1, R1
ALU
Reg
Mem
WAR Definition
Write After Read (WAR)
A later instruction writes to a location before an earlier instruction has read that value
Not possible in our pipeline because reads occur in ID (2nd state) and writes occur in WB (5th stage)
WAR Scenario
ALU
Reg
Mem
DM
Reg
ALU
Reg
Mem
DM
Reg
ADDU R1, R2, R3
SUBU R2, R4, R5
Note that the write of the SUBU will occur well after the ADDU has read R2 from the register
WAW Definition
Write After Write (WAW)
A later instruction writes to a location before an earlier instruction has write that value
Not possible in our pipeline because all writes occur in WB (5th stage) and instructions are executed in order
WAW Scenario
ALU
Reg
Mem
DM
Reg
ALU
Reg
Mem
DM
Reg
ADDU R2, R1, R3
SUBU R2, R4, R5
Not an issue in our pipeline because register writes occur in order
A potential problem when there are multiple processors
Data Hazard Solutions
Wait
Add bubbles (AKA stall)
Equivalent to a nop
Forwarding
Bypass or shortcut to data
Bubbles
ALU
Reg
Mem
DM
Reg
Reg
Mem
ADDU R1, R2, R3
Bubble
Bubble
Bubble
SUB R4, R1, R5
ALU
Forwarding
ALU
Reg
Mem
DM
Reg
ALU
Reg
Mem
DM
Reg
ALU
Reg
Mem
DM
Reg
Mem
ADDU R1, R2, R3
SUB R4, R1, R5
AND R6, R1, R7
OR R8, R1, R9
NOR R10, R1, R1
ALU
Reg
Mem
Types of Hazards
Structural Hazards
Data Hazards
Control Hazards
Control Hazards
When a branch is first fetched, we don’t know if it will be taken
Branch comparison hardware is located in the MEM stage so 2 or 3 instructions will be in the pipeline before the branch is resolved
Depends on if instruction is fetched at the start or end of a cycle
Control Hazards Solutions
We can fetch the next instruction in memory and assume the branch won’t be taken
If the branch is taken, any instructions fetched must be flushed (removed) from the pipeline
Control Hazard in Pipeline
ALU
PC
Add
4
Instruction Memory
M
u
x
IF/ID
Register File
Sign Extend
16
32
M
u
x
M
u
x
ID/EX
EX/MEM
Comp.
Branch
Taken
Data Memory
MEM/WB
M
u
x
Branch result passed back in MEM stage
If branch taken, instruction at this stage must be flushed
If branch taken, instruction at this stage must be flushed
This stage will fetch the correct instruction if branch is taken
Reduce Flushing Penalty
Add branch equality check hardware to ID stage
Requires forwarding target address calculation to ALU
This may require a stall for any data dependencies if values to be compared will be modified by instructions in the pipeline
Branch Prediction
Make an educated guess at whether a branch will be taken and use that to decide what instructions to fetch after a branch
Branch Prediction Methods
Dynamic branch prediction
Keep a table of addresses with branches and whether the last execution resulted in the branch being taken
Fetch instructions from same place they were fetched from last time
Branch Prediction Methods
Dynamic branch prediction
Keep a branch history table (or branch prediction buffer)
Table in memory that keeps lower portion of branch addresses as key
For each entry, saves the next instruction that ended up being where the branch went to
Saved address is where the branch goes to
Branch History Table
Last Hex Digit Of Address Branch Result Address
0x0
0x4
0x8
0xC
Branch instruction at 0x10000014 that was not taken, meaning next instruction was 0x10000018
Branch History Table
Last Hex Digit Of Address Branch Result Address
0x0
0x4 0x10000018
0x8
0xC
Branch instruction at 0x10000014 that was not taken, meaning next instruction was 0x10000018
Branch History Table
Last Hex Digit Of Address Branch Result Address
0x0
0x4 0x10000018
0x8
0xC
Branch instruction at 0x1000003C that was taken and branched to the target address, 0x10000200
Branch History Table
Last Hex Digit Of Address Branch Result Address
0x0
0x4 0x10000018
0x8
0xC 0x10000200
Branch instruction at 0x1000003C that was taken and branched to the target address, 0x10000200
Branch History Table
Last Hex Digit Of Address Branch Result Address
0x0
0x4 0x10000018
0x8
0xC 0x10000200
Branch instruction at 0x10000084 that was taken and branched to the target address, 0x10000200
Branch History Table
Last Hex Digit Of Address Branch Result Address
0x0
0x4 0x10000200
0x8
0xC 0x10000200
Branch instruction at 0x10000084 that was taken and branched to the target address, 0x10000200
Table entry overwritten
History Table Considerations
Larger table uses more memory, but could handle tracking a larger number of branches without evicting a previous prediction
Note: this is very similar to a hash map or CPU cache
Lecture Question
Suppose we have a loop where a branch is taken 6 times in a row and then not take once. Assuming the result stays in our branch history table and the processor initially predicts the branch is not taken, about what percent of the time is the prediction correct?
33%
67%
71%
80%
100%
Solution
Branch is prediction is incorrect both the first and last time the branch is executed
There are 7 total branches executed and 5 are correct = 71%
The branch is taken 6 out of 7 times or about 86% of the time
History Table Considerations
Many branches have a tendency towards being predominantly taken or not taken
A 2-bit prediction scheme is useful for this reason
2-Bit Prediction
Prediction is only changed if prediction is wrong twice
If the same loop is run twice, the second time it is run it will get the first prediction correct because the missed prediction at the end won’t change the next prediction
2-Bit Prediction
Predict taken
Taken
Predict taken
Not taken
Taken
Predict not taken
Not taken
Predict not taken
Taken
Not taken
Not taken
Taken
2-Bit Prediction
Implemented with counter
0 and 1 predict taken, 2 and 3 predict not taken
When taken, subtract if not 0
When not taken, add 1 if not 3
Software Considerations
Avoid conditionals like this:
if(a == 5) {
if(b != 6) {
if(c > 25) {
// Requires 3 branches to reach
}
}
}
Software Considerations
if( (a == 5) && (b != 6) && (c > 25) ) {
// Equivalent expression inside a single
// conditional
}
Types of Hazards
Structural Hazards
Hardware limitation
Data Hazards
Out of order data access
Control Hazards
Loading instructions that follow a branch