CPU Pipeline

CPU Pipeline

1. The Basic Concept of an Instruction Pipeline

The Principle of Pipelining

Basic idea:

• Decompose the execution of an instruction into several stages
• Different stages of different instructions can execute in parallel
• Raises the throughput of the CPU

The advantages of a pipeline:

• Higher throughput: several instructions execute in parallel
• Higher CPU utilisation: less idle time
• Higher performance: better performance at the same clock frequency

The Pipeline Stages

The five-stage pipeline:

• Fetch (IF): fetch the instruction from memory
• Decode (ID): analyse the instruction and read the operands
• Execute (EX): perform the operation
• Memory access (MEM): access memory
• Write-back (WB): write the result back

The pipeline registers:

• IF/ID register: holds the data between fetch and decode
• ID/EX register: holds the data between decode and execute
• EX/MEM register: holds the data between execute and memory access
• MEM/WB register: holds the data between memory access and write-back

2. Implementing the Pipeline

The Basic Pipeline Structure

The data path:

• An independent data path for each stage
• Pipeline registers connect the stages
• Control signals coordinate the work of the stages

The control logic:

• The pipeline control unit
• The hazard detection unit
• The pipeline stall and flush logic

The Timing of the Pipeline

Clock synchronisation:

• All pipeline registers update synchronously
• One stage advances per clock cycle
• Guarantees the consistency of the data

Filling and draining the pipeline:

• Starting the pipeline takes several cycles
• Draining the pipeline also takes several cycles
• Affects the performance of short programs

3. Pipeline Hazards

Data Hazards

Basic concept:

• A later instruction needs the result of an earlier instruction
• But the result has not yet been written back to the register
• Leads to a conflict caused by the data dependency

Types:

• RAW (read after write): the most serious data hazard
• WAR (write after read): can occur in out-of-order execution
• WAW (write after write): can occur in out-of-order execution

Solutions:

• Data forwarding: passes the result directly to the later instruction
• Pipeline stall: stalls the later instruction until the data is ready
• Register renaming: avoids false data dependencies

Control Hazards

Basic concept:

• A branch instruction changes the order of execution of the program
• The instructions already fetched in the pipeline may be invalid
• The pipeline has to be flushed and the fetch restarted

Impact:

• Performance loss: flushing the pipeline costs performance
• Misprediction: a wrong branch prediction costs even more
• Delayed slot: some architectures use a delayed slot to reduce the loss

Solutions:

• Branch prediction: predicts the direction of the branch
• Delayed slot: fills the slot after the branch with a useful instruction
• Speculative execution: executes the instruction along the predicted direction

Structural Hazards

Basic concept:

• Several instructions need the same hardware resource
• The resource conflict stalls the pipeline
• Not enough hardware resources

Common conflicts:

• Memory access conflict: several instructions access memory at the same time
• ALU conflict: several instructions use the ALU at the same time
• Register port conflict: several instructions access the registers at the same time

Solutions:

• Add resources: add ALUs, memory ports, and so on
• Pipeline stall: stalls the conflicting instruction
• Resource scheduling: schedules the instructions in a sensible order

4. Pipeline Optimisation

The Forwarding Technique

Basic concept:

• Passes the result of an operation directly to the later instruction
• Avoids waiting for the write-back stage
• Reduces the impact of data hazards

The forwarding paths:

• EX/MEM → EX: forwarding at the execute stage
• MEM/WB → EX: forwarding at the memory access stage
• MEM/WB → ID: forwarding at the write-back stage

The forwarding conditions:

• The source register is the same as the destination register
• The previous instruction writes back to that register
• The later instruction needs to read that register

Branch Prediction

Static prediction:

• Always predict not taken: suits loop structures
• Always predict taken: suits conditional branches
• Direction-based prediction: predicts according to the direction of the branch

Dynamic prediction:

• One-bit predictor: records the result of the last prediction
• Two-bit saturating counter: gives a more stable prediction
• Global history predictor: takes the global branch history into account

Advanced prediction:

• Branch target buffer (BTB): caches the branch target addresses
• Return address stack (RAS): predicts the return address of a function
• Hybrid predictor: combines several prediction methods

Out-of-Order Execution

Basic concept:

• Instructions do not execute in the order of the program
• They execute according to their data dependencies
• Raises the instruction-level parallelism

Implementation:

• Reservation station: holds the instructions waiting to execute
• Reorder buffer (ROB): maintains the order of instruction execution
• Register renaming: avoids false data dependencies

The advantages:

• Higher parallelism: makes full use of the hardware resources
• Fewer stalls: reduces the impact of data hazards
• Higher performance: significantly improves CPU performance

5. Superscalar Pipelines

The Basic Concept

Superscalar:

• Issues several instructions per clock cycle
• Several functional units work in parallel
• Raises the instruction-level parallelism

The issue width:

• The number of instructions that can be issued per cycle
• 2-issue, 4-issue, 8-issue, and so on
• Affects both the hardware complexity and the performance

The Implementation Techniques

Multiple issue:

• Static multiple issue: the compiler schedules the issue of the instructions
• Dynamic multiple issue: the hardware schedules the instructions dynamically
• Hybrid multiple issue: combines the static and the dynamic methods

The functional units:

• Several ALUs: execute arithmetic operations in parallel
• Several memory units: access memory in parallel
• Special-purpose units: floating-point operations, vector operations, and so on

Instruction scheduling:

• Register renaming: avoids false data dependencies
• Reservation station scheduling: schedules the execution of the instructions dynamically
• Out-of-order execution: does not execute in the order of the program

6. Pipeline Performance Analysis

The Performance Metrics

Throughput:

• The number of instructions completed per clock cycle
• In the ideal case it equals the number of pipeline stages
• In practice it is affected by hazards

CPI (clock cycles per instruction):

• The average number of clock cycles needed per instruction
• In the ideal case CPI = 1
• In practice CPI > 1

Speedup:

• The performance gain of the pipeline over the non-pipelined design
• In the ideal case it equals the number of pipeline stages
• In practice it is affected by hazards

Performance Optimisation

Reducing the hazards:

• Optimise the data forwarding
• Improve the branch prediction
• Add hardware resources

Raising the parallelism:

• Increase the issue width
• Add functional units
• Optimise the instruction scheduling

Compiler optimisation:

• Instruction reordering
• Loop unrolling
• Software pipelining

Exercises

Exercise 1

What is an instruction pipeline? What are its advantages?

Exercise 2

What is the difference between a hardwired control unit and a microprogrammed control unit?

---

Glossary