Instruction Pipelining: Stages, Speedup & Hazards

Pipelining overlaps the execution of multiple instructions across independent hardware execution stages:

1. IF (Instruction Fetch): Fetch instruction from cache using PC; increment PC ≤ftarrow PC + 4.

2. ID / RF (Instruction Decode / Register Fetch): Decode opcode and read operand registers from the register file.

3. EX (Execute / ALU): Perform arithmetic/logical operation or compute effective memory address.

4. MEM (Memory Access): Read or write data cache (LOAD/STORE instructions only).

5. WB (Write Back): Write the result back into destination register.

Clock Cycle Time (T_{clock}):

The pipeline clock period is determined by the slowest stage plus the pipeline register latch overhead:

T_{clock} = \max(Stage Delay_i) + Latch Delay.

Pipeline Performance Metrics:

- Ideal CPI of an in-order pipeline = 1.

- Speedup (S) for n instructions on a k-stage pipeline:

T_{nonpipe} = n × k × T_{clock}

T_{pipe} = [k + (n - 1)] × T_{clock}

S = \frac{n × k}{k + n - 1}. As n \to \infty, S \to k.

A hazard is any condition that prevents the next instruction from executing in its designated clock cycle:

1. Structural Hazard: Two instructions compete for the same physical hardware resource in the same cycle (e.g., single memory port accessed by IF and MEM simultaneously). Solution: Separate L1 Instruction and Data caches (Harvard architecture).

2. Data Hazard (RAW - Read-After-Write): An instruction needs an operand produced by an earlier instruction that has not yet completed write-back. Three types exist:

- RAW (True Dependency): I_2 reads a register written by I_1. Occurs in in-order pipelines.

- WAR (Anti-Dependency): I_2 writes a register before I_1 reads it. Occurs only in out-of-order execution.

- WAW (Output Dependency): I_2 writes a register before I_1 writes it. Occurs only in out-of-order execution.

Remedies for RAW Hazards:

- Software/Hardware Stalls: Inserting bubble cycles.

- Operand Forwarding (Bypassing): Routing ALU result from EX/MEM or MEM/WB pipeline registers directly to the ALU input multiplexers, eliminating stalls for ALU-to-ALU dependencies!

- Load-Use Delay: A LOAD instruction produces its data at the end of the MEM stage. Even WITH forwarding, a dependent instruction immediately following a LOAD requires 1 stall bubble cycle.