Pipelining & Dependencies

In a single-cycle machine, every instruction completes in one clock cycle. The clock period must be long enough for the slowest instruction (typically a load: IF + ID + EX + MEM + WB all in one cycle).

MIPS datapath stages (which become pipeline stages):

1. IF (Instruction Fetch): Read instruction from I-cache using PC
2. ID (Instruction Decode): Decode instruction, read register file
3. EX (Execute): ALU operation, address calculation, branch resolution
4. MEM (Memory Access): Load/store access D-cache
5. WB (Write Back): Write result to register file

Problem: The clock cycle time is determined by the longest instruction. A simple ADD doesn't need MEM, but it still takes the full cycle. This wastes time for fast instructions.

Solution: Pipelining — divide execution into stages and overlap multiple instructions.

Pipelining overlaps the execution of multiple instructions. While one instruction is in EX, the next is in ID, and the one after is in IF.

Ideal pipeline assumptions:

• All operations are identical (take the same time)
• All operations are independent (no dependencies)
• Sub-operations are uniform (all stages take the same time)

Throughput formula for k-stage pipeline processing N instructions:

BW = N / (k + N - 1) cycles

With latch (pipeline register) overhead S per stage:

BW_k = 1 / (T/k + S)

where T = total unpipelined delay, k = number of stages, S = latch delay per stage.

Ideal speedup: k (equal to number of stages). In practice, always less due to:

• Pipeline stalls: Dependencies force bubbles (empty cycles)
• Latch overhead: Each stage boundary adds S time
• Non-uniform stages: Clock period = longest stage → shorter stages waste time (internal fragmentation)
• External fragmentation: Not all operations use all stages (e.g., ADD doesn't need MEM)

Dependencies between instructions cause pipeline hazards that require stalls or special handling.

Types of data dependencies:

• RAW (Read After Write) — True dependency: Instruction B reads a value that instruction A writes. B must wait for A's result. ADD R1,R2,R3; SUB R4,R1,R5 (SUB reads R1 that ADD writes).
• WAR (Write After Read) — Anti-dependency: Instruction B writes a register that A reads. Only a problem in out-of-order execution. ADD R1,R2,R3; SUB R2,R4,R5 (SUB writes R2 that ADD reads).
• WAW (Write After Write) — Output dependency: Both A and B write the same register. Only a problem with out-of-order or multi-cycle operations. ADD R1,R2,R3; SUB R1,R4,R5.

In a simple in-order pipeline: Only RAW dependencies cause hazards (WAR and WAW are handled by in-order execution naturally).

Control dependencies: A branch instruction determines whether subsequent instructions should execute. If the branch is not yet resolved, subsequent instructions may be wrong-path.

Forwarding (bypassing) is a hardware technique to resolve RAW hazards without stalling (when possible).

Key insight: The result is computed at the end of the EX stage (or MEM for loads), but is not written to the register file until the WB stage. A dependent instruction needs the value at the start of its EX stage.

Without forwarding: Must stall until the producing instruction writes back (2 cycle bubble for EX→EX dependency).

With forwarding:

• Add multiplexers at ALU inputs
• Forward the result directly from the output of EX (or MEM) to the input of EX for the dependent instruction
• EX-to-EX forwarding: Result from EX of instruction i is forwarded to EX of instruction i+1. No stall needed.
• MEM-to-EX forwarding: Result from MEM of instruction i forwarded to EX of instruction i+1. Also no stall if available in time.

Load-use dependency: Even with forwarding, a load followed by a dependent instruction still requires 1 cycle stall. The load data is only available after MEM, but the dependent instruction needs it at EX — there's a 1-cycle gap that cannot be forwarded away.

The register file is a communication abstraction: Forwarding "short-circuits" the register file to get data to dependent instructions sooner.