Exercises — Classic 5-stage pipeline (IF - ID - EX - MEM - WB)

1. IF — Instruction Fetch: read the instruction from instruction memory at the address in the PC; then PC ← PC + 4.
2. ID — Instruction Decode / register read: decode the opcode, read source registers from the register file, sign-extend the immediate.
3. EX — Execute: the ALU does arithmetic/logic, or computes a memory address, or checks a branch condition.
4. MEM — Memory access: loads read data memory, stores write it; everyone else idles here.
5. WB — Write Back: write the result into the register file.

Registers are read in ID and results are written in WB. Mnemonic: Decode reads, Write writes.

The four are IF/ID, ID/EX, EX/MEM, MEM/WB. Each carries data (operand values, the immediate, the ALU result, the loaded value) and control signals (RegWrite, MemRead, MemWrite, …). Control decided in ID must survive all the way to WB, four cycles later — the registers ferry it there.

Step (what): apply $\text{Cycles}(N)=k+(N-1)$. Why: $k=5$ cycles to fill the pipe (first result at cycle 5), then $N-1$ more results, one each subsequent cycle. $\text{Cycles}(8)=5+(8-1)=12.$ The first instruction finishes at cycle $k=5$ (it must pass all five stages). Look at Figure s01: the last coloured cell of the top row sits in column 5.

Step (what): take the max delay. Why: all stages share one clock; the cycle must be long enough for the slowest stage to finish, or that stage's result would not be ready to latch. $\max (250,120,180,250,100)=250\text{ ps (IF and MEM tie).}$ Step: add the latch overhead, because every cycle also spends $d$ writing into the pipeline register. $T_{clk}=250+15=265\text{ ps.}$

Step: cycles $=k+(N-1)=5+599=604$. Step: time $=604\times 265=160,060$ ps $=160.06$ ns. Why multiply cycles by $T_{clk}$? Each clock cycle lasts exactly $T_{clk}$, and the cycles happen one after another; so total wall-clock time is simply "how many cycles" times "how long each cycle is."

Single-cycle time per instruction: one giant cycle must fit all combinational work plus one latch: $T_{single}=(250+120+180+250+100)+15=900+15=915\text{ ps.}$ Pipelined time per instruction (large $N$): one instruction finishes every $T_{clk}=265$ ps. Speedup: $\frac{915}{265}\approx 3.45\times .$ Why this ratio and not $\frac{Nk}{k+N-1}$? Because the two machines have different cycle times here (915 vs. 265), so we compare wall-clock time per instruction directly, exactly as the intro formula box warned. Why not 5×? The stages are unbalanced: WB (100 ps) and ID (120 ps) waste much of their 265-ps slot, while IF/MEM (250 ps) set the pace. Ideal 5× requires every stage to be equal and $d=0$. See Clocking & Latch Overhead for why $d$ can never be zero.

• lw $t0, 8($s1) : IF · ID(read $s1)\cdot EX(addr=$s1+8) · MEM(read) · WB(write $t0). Uses all five.
• add $t2,$t3,$t4 : IF · ID(read $t3,$t4) · EX(add) · MEM(idle) · WB(write $t2).
• sw $t5, 0($s2) : IF · ID(read $s2,$t5) · EX(addr = $s2+0) · MEM(write) · no WB. Why keep idle slots? So every instruction has the identical 5-stage shape. Uniform shape ⇒ simple control ⇒ one instruction still finishes every cycle. Skipping stages would break the assembly line's steady rhythm.

• 5-stage: $T_{clk}=250+15=265$ ps.
• 10-stage: $T_{clk}=125+15=140$ ps. Step (what): form the throughput ratio $265/140\approx 1.89\times$. Why is that the throughput ratio? For a long stream, one instruction finishes every $T_{clk}$, so throughput = 1 / $T_{clk}$ (instructions per second). Comparing two throughputs is therefore $\frac{1/T_{clk}^{\text{old}}}{1/T_{clk}^{\text{new}}}=\frac{T_{clk}^{\text{old}}}{T_{clk}^{\text{new}}}=\frac{265}{140}$ — throughput scales as the inverse of the cycle time, so a smaller $T_{clk}$ is proportionally faster. The result $1.89\times$ is less than the naive 2× you'd hope for by doubling stages. Why? The latch overhead $d$ did not shrink; it is now $15/140\approx 10.7\%$ of the cycle instead of $15/265\approx 5.7\%$. As stages get thinner, $d$ eats a bigger fraction. Push far enough and speedup saturates or reverses.

Both IF and MEM are 250 ps. Splitting either drops its halves to 125 ps, but the other 250-ps stage still remains and re-sets the max. So one split alone does not lower $\max t_i$ below 250 — the new bottleneck is still the un-split 250-ps stage. $\max t_i=250\text{ ps still}\Rightarrow T_{clk}=250+15=265\text{ ps (unchanged!).}$ Insight: you must split both 250-ps stages to see any gain. Splitting only one wastes an extra latch for nothing. This is the core lesson: the second-slowest stage caps how much helping the slowest can achieve. Balance is global, not local.

Set pipelined time < single-cycle time: $(k+N-1)T_{clk}<N\cdot T_{single}$ $(5+N-1)(265)<N(915)$ $(N+4)(265)<915N$ $265N+1060<915N$ $1060<650N\Rightarrow N>\mathrm{1.63.}$ So from $N=2$ onward the pipeline already wins. Why so early? The single-cycle machine's per-instruction cost (915) is enormous next to 265; the fill penalty of only 4 extra cycles is paid off almost immediately.

(a) $\max (300,200,350,300,150)=350$; $T_{clk}=350+25=375$ ps. (b) Cycles $=k+(N-1)=5+999=1004$. (c) Time $=1004\times 375=376,500$ ps $=376.5$ ns. (d) Total work $=300+200+350+300+150=1300$ ps; single-cycle $=1300+25=1325$ ps/instr. Large-$N$ pipelined $\approx 375$ ps/instr. Speedup $=1325/375\approx 3.53\times$. (e) Balanced ideal: each stage $=1300/5=260$ ps, so $T_{clk}=260+25=285$ ps, giving $1325/285\approx 4.65\times$ — still not 5×. The theoretical 5× needs $d=0$ too, but latch overhead can never be zero (real flip-flops have setup + propagation time — see Clocking & Latch Overhead). Hazards would erode it further.

Recall a stall cycle = an inserted empty cycle that delays an instruction until its needed value is reachable. Lay both instructions on a timeline; rows are instructions, columns are clock cycles (c1…c7), each cell is the stage that instruction occupies that cycle.

**Step 1 — find when $t0isproduced(reachable).\ast \ast ‘add‘writes$t0 in its WB, which is cycle 5:

**Step 2 — find when sub needs $t0.\ast \ast ‘sub‘readsitssourcesin\ast \ast ID\ast \ast .Back-to-back,‘sub{‘}^{\prime }sIFisc2,soits\ast natural\ast IDisc3.\ast \ast Step3—applythehardwarerule.\ast \ast Nosame-cyclewrite-then-readmeans‘sub{‘}^{\prime }sIDcanonlyruninthecycle\ast \ast after\ast \ast ‘add{‘}^{\prime }sWB—i.e.‘sub{‘}^{\prime }sIDmustmovefromc3to\ast \ast c6\ast \ast .\ast \ast Step4—countthestalls.\ast \ast NaturalID=c3,requiredID=c6,so‘sub‘isdelayedby$6 - 3 = 3$ cycles → 3 stall cycles. The corrected timeline:

(the three "–" cells are the inserted bubbles). Step 5 — total cycles. Without stalls two instructions would take $k+(N-1)=5+1=6$ cycles; the 3 bubbles push sub back by 3, giving $6+3=9$ cycles total (last cell WB in c9). Why forwarding fixes it: the ALU result exists right after add's EX (c3) — feed it straight into sub's EX and all 3 stalls vanish, back to 6 cycles. This is the entire motivation for Data Forwarding / Bypassing.

Goal: show $\frac{Nk}{k+N-1}<k$. Step 1 — clear the fraction. Since $k+N-1>0$, multiply both sides by it without flipping the inequality: $\frac{Nk}{k+N-1}<k⟺Nk<k(k+N-1).$ Step 2 — expand the right side. Distribute $k$: $k(k+N-1)=k^2+kN-k.$ Step 3 — cancel the common $kN$ term. Both sides carry $kN$ (left is $Nk$), so subtract it: $Nk<k^2+kN-k⟺0<k^2-k.$ Step 4 — factor and interpret. $k^2-k=k(k-1)$. For any real pipeline $k\ge 2$, both $k$ and $k-1$ are positive, so $k(k-1)>0$ is always true — but notice this step used only $k\ge 2$, independent of $N$. Wait: we cancelled $kN$ assuming the strict form; the strictness in fact requires $N\ge 2$ so that the pipeline is genuinely overlapping (at $N=1$ both sides equal $k$). Hence for every finite $N\ge 2$ the strict inequality holds. Step 5 — the limit. Equality would need $k(k-1)=0$, impossible for $k\ge 2$; but as $N\to \infty$ the "$-1$" in $k+N-1$ becomes negligible and the ratio approaches $k$. Meaning: the fill/drain overhead of $(k-1)$ cycles can be amortized toward nothing but never actually removed for a finite stream.