Instruction Pipelining: short notes (Computer Organization & Architecture)

Introduction

Pipelining overlaps the execution of several instructions, the way an assembly line overlaps the building of several cars. The work of one instruction is cut into $k$ stages (for example fetch, decode, execute, memory access, write back). Each stage finishes its part in one clock cycle and hands the partial result to the next stage through a pipeline register (latch). Once the pipeline is full, one instruction finishes every cycle, although each individual instruction still needs $k$ cycles.

Pipelining improves throughput (instructions completed per unit time). It does not shorten, and usually lengthens, the latency of a single instruction. The key distinction is between those two ideas, and the clock period must be computed correctly when stages are unequal or latches add delay. Stalls caused by dependences and branches are the subject of Pipeline Hazards; this note covers the ideal pipeline and the performance arithmetic that hazards plug into.

Prerequisites

CPU Datapath and Instruction Cycle: the fetch, decode, execute steps that become pipeline stages, and the register file, ALU and memory interfaces each stage uses.

Core concepts

Term	Meaning
Stage	One step of instruction processing done by its own hardware in one cycle
Depth $k$	Number of stages
Pipeline register (latch, buffer)	Register between two stages that holds the outputs of the earlier stage for the later one
Latch overhead $d$	Delay added by a pipeline register (setup time plus clock-to-output delay)
Clock period $t_p$	Time of one pipeline cycle: $t_p = \max_i \tau_i + d$ , where $\tau_i$ is the logic delay of stage $i$
Fill (warm-up)	The first $k - 1$ cycles, before the first instruction completes
Steady state	One instruction enters and one leaves every cycle
Drain	The last $k - 1$ cycles, when no new instruction enters
Latency	Time from the start to the end of one instruction: $k \, t_p$
Throughput	Instructions completed per unit time: $1/t_p$ in steady state
CPI	Average clock cycles per instruction; 1 for an ideal pipeline in steady state

Clock convention used in all Gate CS Mastery notes. "Stage delay" means the logic delay of the stage alone. The pipeline clock period is the largest stage delay plus the latch delay. A non-pipelined (single-cycle) processor has no inter-stage latches, so its instruction time is the sum of the stage delays. If a question says the non-pipelined processor also pays one register delay per instruction, add it once; follow the question.

Ideal-pipeline assumptions. Every stage takes one cycle, stages are independent hardware, every instruction passes through every stage, and there are no stalls. Each assumption fails somewhere in practice: stages are unequal, memory is shared (structural hazard), instructions depend on one another (data hazard), and branches change the flow (control hazard).

The classic five-stage RISC pipeline

Stage	Work
IF	Fetch the instruction at PC from the instruction memory (or I-cache); PC <- PC + 4
ID	Decode; read source registers from the register file; sign-extend the immediate
EX	ALU operation, or effective-address calculation for loads and stores, or branch comparison
MEM	Data memory read (load) or write (store); nothing for ALU instructions
WB	Write the result into the destination register

Each stage needs its own resources in the same cycle, which is why such designs have separate instruction and data caches and a register file that can be read and written in one cycle (write in the first half, read in the second half).

How it works

Draw a space-time diagram: rows are instructions, columns are clock cycles, and each cell names the stage an instruction occupies. Instruction $I_j$ (counting from 1) enters IF in cycle $j$ and leaves WB at the end of cycle $j + k - 1$ .

Space-time diagram of four instructions in a five-stage pipeline — Figure 1. Four independent instructions in the five-stage pipeline IF, ID, EX, MEM, WB: $I_1$ occupies cycles 1 to 5, $I_4$ occupies cycles 4 to 8, so 4 instructions finish in $5 + 4 - 1 = 8$ cycles.

Reading Figure 1 column by column: in cycle 4, $I_1$ is in MEM, $I_2$ in EX, $I_3$ in ID and $I_4$ in IF. In cycle 5 all five stages would be busy if a fifth instruction existed. The first result appears at the end of cycle 5 ( $k$ cycles); after that one result appears per cycle.

Algorithms and pseudocode

The counting procedure below gives the cycle count of an ideal pipeline and shows where each term comes from. Instructions are numbered from 1.

Text

PIPELINE-CYCLES(n, k)
  // n instructions, k stages, no stalls
  first <- k              // I1 completes at the end of cycle k
  rest  <- n - 1          // each later instruction completes one cycle after its predecessor
  return first + rest     // k + n - 1

PIPELINE-TIME(n, tau[1..k], d)
  tp <- max(tau[1..k]) + d
  return PIPELINE-CYCLES(n, k) * tp

For $n\ge1,k\ge1$ , scanning all $k$ stage delays costs $\Theta(k)$ in every case and $O(1)$ auxiliary workspace excluding the supplied stage-delay vector. No average distribution is needed because every entry is scanned. The formula assumes no stalls; add any stall cycles separately.

Mathematical explanation

Let $k$ be the number of stages, $\tau_1, \dots, \tau_k$ the stage logic delays, $d$ the latch delay and $n$ the number of instructions.

Clock period.

t_p = \max_{1 \le i \le k} \tau_i + d

Pipelined time for $n$ instructions (no stalls).

T_{\text{pipe}}(n) = (k + n - 1)\, t_p

Non-pipelined time. A single-cycle processor spends $t_{np} = \sum_i \tau_i$ per instruction, so $T_{\text{np}}(n) = n \, t_{np}$ .

Speedup.

S(n) = \frac{n \, t_{np}}{(k + n - 1)\, t_p}, \qquad \lim_{n \to \infty} S(n) = \frac{t_{np}}{t_p}

When all stages take the same time $\tau$ and $d = 0$ , $t_{np} = k\tau = k\,t_p$ , so

S(n) = \frac{nk}{k + n - 1} \to k.

So $k$ is an upper bound on the speedup of a $k$ -stage pipeline, for $k>1$ , reached only in the limit and only with perfectly balanced stages and no latch overhead. With unequal stages or latch delay, the limit is $\sum \tau_i / (\max \tau_i + d) < k$ when stages are unequal or latch delay is positive. For $k=1,d=0$ , speedup is exactly 1.

Efficiency and throughput. Efficiency (fraction of stage-cycles doing useful work) is $\eta = n/(k + n - 1)$ , which equals $S(n)/k$ in the balanced case. Throughput is $n / T_{\text{pipe}}(n)$ , which tends to $1/t_p$ .

With stalls. If the pipeline loses $s$ stall cycles per instruction on average, the steady-state CPI is $1 + s$ . Measuring against the same instruction count,

T_{\text{pipe}} \approx n\,(1 + s)\, t_p, \qquad S = \frac{t_{np}}{(1 + s)\, t_p}.

For balanced stages with $t_{np} = k\,t_p$ , $S = k/(1 + s)$ . The fill time $k - 1$ is usually ignored for large $n$ ; keep it when the question gives a small $n$ .

Comparing with a multicycle processor. A multicycle (non-pipelined) design uses a short clock $t_c$ and different numbers of cycles per instruction class. Its time per instruction is $\text{CPI}_{mc}\, t_c$ , where $\text{CPI}_{mc} = \sum_j f_j c_j$ for class frequencies $f_j$ and cycle counts $c_j$ . Then $S = \text{CPI}_{mc}\, t_c / (\text{CPI}_{pipe}\, t_p)$ .

Performance equation. For any processor, CPU time $=$ instruction count $\times$ CPI $\times$ clock period. Pipelining lowers the CPI towards 1 with a clock close to the multicycle clock; a single-cycle design has CPI 1 with a long clock.

Worked examples

Example 1: unequal stages and latch delay

A four-stage pipeline has stage delays 60, 50, 90 and 80 ps and a latch delay of 10 ps. The non-pipelined processor takes $60 + 50 + 90 + 80 = 280$ ps per instruction.

Clock period: $t_p = 90 + 10 = 100$ ps.
1000 instructions, pipelined: $(4 + 1000 - 1) \times 100 = 1003 \times 100 = 100{,}300$ ps $= 100.3$ ns.
Non-pipelined: $1000 \times 280 = 280{,}000$ ps.
Speedup: $280{,}000 / 100{,}300 \approx 2.79$ . For very large $n$ it approaches $280/100 = 2.8$ , well below the stage count 4.
Throughput in steady state: one instruction per 100 ps, that is $10^{10}$ instructions per second.
Latency of one instruction: $4 \times 100 = 400$ ps, longer than the 280 ps of the non-pipelined design.

Example 2: splitting the bottleneck stage

Split the 90 ps stage of Example 1 into two stages of 45 ps each. The stage delays become 60, 50, 45, 45, 80 ps, so $t_p = 80 + 10 = 90$ ps and $k = 5$ .

1000 instructions: $(5 + 999) \times 90 = 90{,}360$ ps.
Improvement over the four-stage pipeline: $100{,}300 / 90{,}360 \approx 1.11$ .
The new bottleneck is the 80 ps stage. Splitting the 90 ps stage cannot bring the clock below $80 + 10$ ps, and every extra stage adds one more latch delay to the latency (now $5 \times 90 = 450$ ps).

Example 3: how many instructions for a target speedup

A five-stage pipeline has equal stages and no latch overhead, so $S(n) = 5n/(n + 4)$ . For $S(n) \ge 4$ we need $5n \ge 4n + 16$ , that is $n \ge 16$ . Check: $S(16) = 80/20 = 4$ exactly, and $S(15) = 75/19 \approx 3.95$ . Even with $n = 1000$ , $S = 5000/1004 \approx 4.98$ : the bound 5 is never reached.

Example 4: CPI with load and branch stalls

In a five-stage pipeline with forwarding, 30% of instructions are loads, and 40% of the loads are immediately followed by an instruction that uses the loaded value (1 stall cycle each). 15% of instructions are branches; 60% of the branches are taken, the pipeline predicts not taken, and a taken branch costs 2 stall cycles.

Load stalls per instruction: $0.30 \times 0.40 \times 1 = 0.12$ .
Branch stalls per instruction: $0.15 \times 0.60 \times 2 = 0.18$ .
CPI $= 1 + 0.12 + 0.18 = 1.30$ .

Now suppose the pipelined clock period is 2 ns and a single-cycle processor needs 8 ns per instruction. For 100 instructions in this 5-stage pipeline, the 30 stall cycles give $100+5-1+30=134$ cycles, so the pipelined time is $134\times2=268$ ns; the single-cycle baseline is $100\times8=800$ ns. Speedup is $800/268=200/67\approx2.985$ . The value $8/(1.30\times2)\approx3.08$ is the steady-state approximation, which neglects the 4 fill cycles.

Example 5: pipelined versus multicycle

A multicycle processor with a 100 ps clock takes 5 cycles for loads, 4 for stores, 4 for ALU instructions and 3 for branches. The mix is 25% loads, 10% stores, 50% ALU and 15% branches.

$\text{CPI}_{mc} = 0.25 \times 5 + 0.10 \times 4 + 0.50 \times 4 + 0.15 \times 3 = 1.25 + 0.40 + 2.00 + 0.45 = 4.10$ .
A pipelined version needs a 110 ps clock (latch overhead) and achieves CPI 1.2.
Speedup: $(4.10 \times 100)/(1.2 \times 110) = 410/132 \approx 3.11$ .

Important properties and observations

Throughput versus latency. Pipelining raises throughput; the latency of one instruction stays the same or grows ( $k\,t_p \ge \sum \tau_i$ ).
Speedup is bounded by depth. $S\le k$ generally; $S<k$ for finite $n$ when $k>1$ . For $k=1,d=0$ , $S=1$ exactly, and $S \le \sum\tau_i/(\max\tau_i + d)$ even as $n \to \infty$ .
The slowest stage sets the clock. Speeding up any other stage does not change $t_p$ . Balancing stages matters more than adding stages.
Deeper is not always faster. Each extra stage adds a latch delay and makes hazards cost more cycles (a branch resolved later wastes more fetches). The useful depth is limited.
Fill and drain matter only for small $n$ . For $n$ much larger than $k$ , $k + n - 1 \approx n$ .
Same instruction set, same results. Pipelining is an implementation technique; it does not change the program's meaning, which is why hazards must be handled in hardware or by the compiler.
Common misconceptions.
- "A 5-stage pipeline is 5 times faster." Only with balanced stages, no latch delay, no stalls and infinitely many instructions.
- "Pipelining reduces the time of each instruction." It reduces the average time between completions.
- "CPI of a pipeline is $k$ ." Steady-state CPI is 1 plus stalls; each instruction's latency is $k$ cycles.

Related material. A superscalar processor issues more than one instruction per cycle into multiple pipelines, so its ideal CPI is below 1 (ideal IPC equals the issue width). Out-of-order execution and dynamic scheduling are beyond the GATE syllabus wording; they appear in Hamacher, Section 8.6.

GATE examination perspective

CLOCK PERIOD. Take the maximum stage delay and add the latch delay once; never average the stage delays.
NON-PIPELINED TIME. Usually the sum of stage delays without latches; read whether the question adds a register delay.
FILL CYCLES. For $n$ instructions use $k + n - 1$ cycles, not $nk$ and not $n$ . With a small $n$ the difference matters.
SPEEDUP VERSUS THROUGHPUT. Speedup is a ratio of times; throughput is a rate (instructions per second). A question may ask for one and give options for the other.
STAGE SPLITTING. Recompute $t_p$ from the new maximum after splitting, and count the extra stage in $k + n - 1$ .
STALLS IN CPI. Weight each stall by the fraction of instructions it affects: CPI $= 1 + \sum (\text{frequency} \times \text{penalty})$ .
BASELINE. Check whether the speedup is relative to a single-cycle, a multicycle, or an ideal pipelined processor; each gives a different number.

Summary

A $k$ -stage pipeline completes $n$ instructions in $k + n - 1$ cycles when there are no stalls.
Clock period $=$ largest stage delay $+$ latch delay.
Speedup over non-pipelined $= n\,t_{np}/((k + n - 1)\,t_p)$ ; its limit is $t_{np}/t_p \le k$ .
Balanced stages, zero latch delay and large $n$ are all needed to approach the ideal speedup $k$ .
Throughput tends to $1/t_p$ ; latency of one instruction is $k\,t_p$ .
With $s$ stall cycles per instruction, CPI $= 1 + s$ and speedup $\approx t_{np}/((1 + s)\,t_p)$ .
Splitting the slowest stage helps only until another stage becomes the bottleneck.
CPU time $=$ instruction count $\times$ CPI $\times$ clock period, for every design.

CPU Datapath and Instruction Cycle: prerequisite. The stages come from the instruction cycle.
Pipeline Hazards: dependent. Structural, data and control hazards and the stalls they cause.
Memory Hierarchy and Performance: related. Cache misses stall the IF and MEM stages; the same "CPI plus stall cycles" arithmetic applies.

Instruction Pipelining

Introduction

Prerequisites

Core concepts

The classic five-stage RISC pipeline

How it works

Algorithms and pseudocode

Mathematical explanation

Worked examples

Example 1: unequal stages and latch delay

Example 2: splitting the bottleneck stage

Example 3: how many instructions for a target speedup

Example 4: CPI with load and branch stalls

Example 5: pipelined versus multicycle

Important properties and observations

GATE examination perspective

Summary

Sources

Next steps

Introduction

Prerequisites

Core concepts

The classic five-stage RISC pipeline

How it works

Algorithms and pseudocode

Mathematical explanation

Worked examples

Example 1: unequal stages and latch delay

Example 2: splitting the bottleneck stage

Example 3: how many instructions for a target speedup

Example 4: CPI with load and branch stalls

Example 5: pipelined versus multicycle

Important properties and observations

GATE examination perspective

Summary

Related topics

Sources

Next steps