ECM 1413 Pipelining Flashcards
The instruction cycle in the CPU divided into 3 stages
1) Fetch - Read an instruction from memory
2) Decode - identify the instruction
3) Execute - carry out the instruction
(Non-pipelined FDE cycle)
Rate of instruction execution =
Number of instructions * pipeline Stages
N*S clock cycles
(pipelined FDE cycle)
Rate of instruction execution =
Number of instructions + pipeline Stages - 1
N + S − 1 clock cycles
The clock cycle time of a CPU is
the time it takes to complete one pipelining stage
Clock speed =
1/Clock cycle time
Execution time
Clock cycles for program × Clock cycle time
The performance gains of pipelining are limited by:
1 control hazards
2 data hazards
What is a control hazard
A control hazard occurs when a (conditional) branch instruction changes the next instruction.
There are four ways to deal with control hazards:
(a) stall the pipeline
(b) assume branch not taken
(c) branch prediction
(d) branch delay slots
Control Hazard Management Method: Stall the Pipeline
The processor may stall the pipeline; when we realise that the next instruction is a branch instruction, stop the next instructions.
Pros: We don’t need to guess the next instruction
Cons: Time and resources are wasted
Control Hazard Management Method: Assume Branch Not Taken
The processor may assume branch not taken, squashing instructions if wrong.
Pros: We don’t need to guess the next instruction
Cons: Time and resources are wasted whenever the branch is taken
Control Hazard Management Method: Branch Prediction
The processor may try branch prediction based on past branches. If the prediction is incorrect, instructions are squashed.
Pros: Can significantly reduce the number of wasted clock cycles
Cons: Overhead associated with the branch prediction
Branch History Tables
Branch prediction is performed using branch history tables. The branch history can be:
- One bit to describe whether the branch was taken the last time
- Two bits to describe four different “branch prediction states”
Control Hazard Management Method: Branch Delay Slots
A branch instruction may be followed by delay slots (these are always executed).
Pros: May find useful instructions, e.g., when paths (taken/not taken) join
Cons: If no useful instruction is found, fill the slot with “No operation”
When does a data hazard occur
A data hazard occurs when an instruction requires a result from a previous instruction before that result has been computed/written