Using a single memory introduces a structural hazard
Limits to pipelining: sometimes hazards prevent the next instruction from
structural hazards: HW cannot support this combination of instructions
data hazards: instruction depends on result of prior instruction still
in the pipeline
control hazards: pipelining of branches
Common solution is to stall the pipeline until the hazard is resolved
Data Hazard on r1
Option 1: Stall to Resolve Data Hazard
Option 2: compiler inserts indepdendent instructions
Worst case is NOPs
Option 3 But the data we want is available! - Forward it to where
it is needed.
HW Change for Forwarding (Bypassing):
Forwarding reduces Data Hazard for lw to 1 cycle:
Software Scheduling to Avoid Load Hazards
e.g. perform the following operations:
a = b + c;
d = e - f;
assume a, b, c, d ,e, and f are in memory.
Control Hazard on Branches
Branch Stall Impact: 3 cycles if write in cycle 5.
But, we can work out the branch during Decode cycle.
If CPI = 1 and 30% of instructions are branches, new CPI = 1.9!
Branch Delay now 1 clock cycle
Branch can stall for 1 cycle or we can have delayed branches.
Worst case, SW inserts NOP into branch delay
Where to get instructions to fill branch delay slot?
Before branch instruction
From the target address: only valuable when branch
From fall through: only valuable when don?t branch
Compiler effectiveness for single branch delay slot:
Fills about 60% of branch delay slots
About 80% of instructions executed in branch delay slots useful in computation
about 50% (60% x 80%) of slots usefully filled
When is pipelining hard?
Interrupts: 5 instructions executing in 5 stage pipeline
How to stop the pipeline?
What caused the interrupt?
IF Page fault on instruction fetch; misaligned memory access; memory-protection
ID Undefined or illegal opcode
EX Arithmetic interrupt
MEM Page fault on data fetch; misaligned memory access; memory-protection
Complex Addressing Modes and Instructions
Address modes: Autoincrement causes register change during instruction
Now worry about write hazards since write no longer last stage
Write After Read (WAR): Write occurs before independent read
Write After Write (WAW): Writes occur in wrong order, leaving wrong result
(Previous data hazard called RAW, for Read After Write)
Memory-memory Move instructions
Multiple page faults
Floating Point: long execution time
Suppose instruction i is about to be issued and a predecessor instruction
j is in the instruction pipeline.
Rregs ( i ) = Registers read by instruction i
Wregs ( i ) = Registers written by instruction i
° A RAW hazard exists on register r if there exists s where Rregs(
r ) intersection Wregs( s )
- Keep a record of pending writes (for inst's in the pipe) and compare
with operand regs of current instruction.
- When instruction issues, reserve its result register.
- When on operation completes, remove its write reservation.
° All instructions follow same pipeline order ("static schedule").
° Register write in last stage
- Avoid WAW hazards
° All register reads performed in first stage after issue.
- Avoid WAR hazards
° Memory access in stage 4
- Avoid all memory hazards
° Control hazards resolved by delayed branch.
° RAW hazards resolved by bypass, except on load results which
are resolved by delayed load or stall.
Substantial pipelining with very little cost or complexity.