Pipelining - Basic Concepts

Pipelining is an implementation technique where multiple instructions are overlapped in execution, like an assembly line. An $k$-stage pipeline divides instruction execution into $k$ stages (classic RISC: IF-ID-EX-MEM-WB) operating concurrently.

Basic Operation

Each stage has combinational logic + pipeline register/latch. Clock period $T_p = \max(T_{stage}) + T_{latch}$. While stage $i$ processes instruction $n$, stage $i-1$ processes $n+1$.

For $k=4$, $n$ instructions: non-pipelined time $= n\cdot k\cdot T_p$, pipelined time $= (k+n-1)T_p$.

Speedup

$$S = \frac{T_{non-pipe}}{T_{pipe}} = \frac{n\cdot k}{k+n-1} \xrightarrow{n\gg k} k$$
Ideal speedup = number of stages. With stage imbalance and latch overhead: $S = \frac{k\cdot T_{seq}}{T_p}$.

Example $k=5$, $n=100$: $S = 500/104 \approx 4.8$.

Efficiency $\eta = S/k$, Throughput $= n/(k+n-1)T_p \xrightarrow{n\to\infty} 1/T_p$ instructions/sec = $f_{clk}$ (one per cycle).

Throughput

Rate of instruction completion. Non-pipelined: $1/(kT_s)$, Pipelined (steady): $1/T_p$. Improvement factor same as speedup. Supercalar/superpipelined increase further.

Pipeline Hazards - prevent next instruction from executing in next cycle

1. Structural Hazards: Hardware resource conflict (e.g. single memory for IF+MEM, single ALU). Solution: Separate I/D caches (Harvard), duplicate units, stalling (bubble).

2. Data Hazards: Dependency on previous result still in pipe.

• RAW (true) ADD R1,R2,R3 followed by SUB R4,R1,R5 (R1 not written back)
• WAR, WAW in out-of-order pipes.
  Solution: Forwarding/bypassing (EX→EX), compiler code scheduling, pipeline interlock + stall, register renaming.

3. Control Hazards: Branch/jump changes PC, next fetched instructions wrong.

• Unconditional: 1-cycle bubble
• Conditional: taken/not-taken decision at EX/MEM → flush.
  Solutions: Stall/flush, branch prediction (static: not-taken/backward-taken; dynamic: 2-bit saturating counter, BTB), delayed branch (branch delay slot, predication), speculative execution.

Additional classification Data hazards = load-use: LW R1,0(R2); ADD R3,R1,R4 requires 1 stall even with forwarding (mem latency).

Performance impact: $CPI_{pipe}= CPI_{ideal} + stall_{structural}+stall_{data}+stall_{control}$ ; $CPI_{ideal}=1$.

Ideal pipeline CPI=1, real $1.2\text{-}1.5$ due to hazards; longer pipe → higher hazard penalty.

Diagram should show 5 stages overlapped in time (Gantt chart) and hazard bubble insertion.