Computer Organization and Architecture

Pipelining

PreviousNext

Module VI: Pipelining. This module explores the foundational technique used to accelerate processor throughput: Pipelining. By overlapping the execution of multiple instructions, a processor can achieve significant theoretical speedups. Learners will analyze the canonical 5-stage MIPS pipeline, identify the "big three" hazards (Structural, Data, and Control), and examine exception handling.

1. Pipelining Concepts & 5-Stage Execution

Pipelining is an implementation technique where multiple instructions are overlapped in execution. It is analogous to a factory assembly line; while one instruction is finishing, the next is being processed in a earlier stage.

The Canonical 5-Stage MIPS Pipeline

IF

Instruction Fetch

ID

Instruction Decode

EX

Execute / Address Calc

MEM

Memory Access

WB

Write Back

Performance Improvement

The ideal speedup from pipelining is equal to the number of stages (k). However, due to unequal stage lengths and pipeline overhead, the actual speedup is:

Speedup = Time per instruction (non-pipelined) / Time per instruction (pipelined)

2. Pipeline Hazards

A hazard is a situation that prevents the next instruction in the stream from executing in its designated clock cycle.

A. Structural Hazards

Occur when the hardware cannot support a specific combination of instructions in the same clock cycle (resource conflict).

  • Example: A single memory unit used for both instructions and data causes a conflict when one instruction fetches code (IF) while another reads data (MEM).
  • Solution: Separate caches for instructions and data (Harvard Architecture).

B. Data Hazards

Occur when an instruction depends on the result of a previous instruction that is still in the pipeline.

  • Example: add $s0, $t0, $t1 followed immediately by sub $t2, $s0, $t3. The sub needs $s0 before the add writes it back.
  • Solution 1: Forwarding (Bypassing) - passing the result directly from the ALU to the next stage's input before write-back.
  • Solution 2: Stalling (Bubble) - inserting a delay until data is available.

C. Control Hazards (Branch Hazards)

Occur when the pipeline makes the wrong decision on a branch prediction, or must wait to calculate the target.

  • Solution: Branch prediction (Static or Dynamic) or Delayed Branching.

3. Pipelined Datapath and Registers

To isolate the five stages and allow them to operate independently, Pipeline Registersare inserted between each stage. These registers store intermediate results and control signals.

Register NameLocationPurpose
IF/IDBetween Fetch and DecodeHolds the fetched instruction and PC + 4
ID/EXBetween Decode and ExecuteHolds register values, sign-extended immediate, and control signals
EX/MEMBetween Execute and MemoryHolds ALU result, branch target, and write-data
MEM/WBBetween Memory and Write-BackHolds data read from memory or the ALU result

4. Handling Exceptions, Interrupts, and Traps

A robust pipeline must be able to handle unexpected changes in execution flow.

  • Exceptions: Internal events that disrupt execution (e.g., arithmetic overflow).
  • Interrupts: External events from I/O devices (e.g., keyboard, disk).
  • Traps: Software-generated exceptions used for system calls.

The Pipeline Challenge

When an exception occurs (e.g., an overflow in EX), the pipeline must:

  1. Flush the instructions following the offending instruction (turn them into nops).
  2. Save the address of the offending instruction in the Exception Program Counter (EPC).
  3. Transfer Control to a dedicated Exception Handler at a pre-defined memory address.
Building a DatapathMemory Hierarchy