Pipelining

1. Definition

Pipelining is an implementation technique where multiple instructions are overlapped in execution, analogous to an assembly line. Each instruction is split into $k$ sequential stages; different stages of successive instructions execute concurrently using separate hardware resources.

Ideally $k$-stage pipeline can execute $k$ instructions simultaneously and achieve speedup $\approx k$.

2. Why Require Instruction Pipelining?

• Performance without increasing clock rate: Single-cycle CPU has long critical path (IF+ID+EX+MEM+WB). Pipelining breaks it into shorter stages -> higher clock frequency and throughput.
• Exploit Instruction-Level Parallelism (ILP): Sequential model wastes hardware when one unit is active, others idle. Pipelining keeps all units busy.
• CPI approaches 1: Without pipeline CPI = 1 (single-cycle) but long $T_{clk}$ or CPI >1 (multi-cycle). With pipeline, throughput = 1 instruction/cycle in steady state.
• Cost-effective speedup: No need for multiple CPUs; just pipeline registers.

3. Working Procedure (5-stage Classic RISC Pipeline)

Stages:

1. IF - Instruction Fetch: IR <- M[PC]; PC <- PC+4
2. ID - Instruction Decode/Register Fetch: decode opcode, read $Rs,Rt$, generate immediates.
3. EX - Execute/ALU: ALU operation or effective address ALUout <- Rs op Rt or Rs + imm
4. MEM - Memory Access: MDR <- M[ALUout] for LOAD or M[ALUout] <- Rt for STORE
5. WB - Write Back: Rd <- ALUout or Rd <- MDR

Pipeline registers between stages: IF/ID, ID/EX, EX/MEM, MEM/WB isolate stages.

Timing diagram (no hazards, 5 instructions):

Cycle:  1    2    3    4    5    6    7    8
I1:    IF | ID | EX | MEM| WB |
I2:         IF | ID | EX | MEM| WB |
I3:              IF | ID | EX | MEM| WB |
I4:                   IF | ID | EX | MEM| WB |
I5:                        IF | ID | EX | MEM| WB |

After 5 cycles (fill), one instruction completes per cycle.

Non-pipelined: 5 cycles per instruction sequentially -> 25 cycles for 5 instr. Pipelined: 9 cycles.

Hazards (practical issues)

• Structural: two instr need same resource (e.g., single memory for IF and MEM) - solve by separate I/D caches.
• Data hazard: I2 needs result of I1 (RAW) - forward/bypass or stall (bubble).
• Control hazard: branch target unknown until ID/EX - flush pipeline, branch prediction.

4. Pipeline Performance Measures

Let $k$ = stages, $t_p$ = time per stage, $t_{latch}$ = latch overhead, $n$ = number of instructions.

• Clock period: $T_{clk,pipelined}= \max(t_i) + t_{latch}$ vs $T_{clk,non-piped}= \sum t_i$

• Time for n instructions:
  $T_{non-pipe}= n \cdot k \cdot t_p$
  $T_{pipe}= k\cdot t_p + (n-1)\cdot t_p = (k+n-1)t_p$ (ideal)

• Speedup: $S = \frac{T_{non-pipe}}{T_{pipe}} = \frac{n k}{k+n-1}$. For $n \gg k$, $S \to k$ (ideal).
  With overhead: $S = \frac{k t_p}{t_p + t_{latch}} \cdot \frac{n}{n+k-1}$

• Efficiency: $\eta = \frac{S}{k} = \frac{n}{k+n-1}$ . For large $n$, $\eta \to 1$.

• Throughput: $W = \frac{n}{T_{pipe}} = \frac{1}{t_p}$ instr/sec in steady state (vs $\frac{1}{k t_p}$ non-piped). $n/(k+n-1)t_p$.

• CPI: Ideal CPI = 1, effective CPI = $1 + stalls/instr$ (due to hazards).

• Example: $k=5$, $t_p=2ns$, $n=100$: $T_{non}=1000ns$, $T_{pipe}= (5+99)*2=208ns$, $S=4.8$, $\eta=96\%$.

Pipeline improves throughput, not single-instruction latency (latency stays $k t_p$). Maximum speedup limited by stage imbalance, latches, and hazards.