Multi-cycle datapath: Worked examples — Hardware deep dive

This is a child page of the parent topic. The parent built the why and the five steps. Here we drill every kind of question an exam can throw at you — every instruction type, every degenerate case (zero delays, balanced vs unbalanced stages), the limiting behaviour, a real-world word problem, and a nasty exam twist.

Before we start, a promise from the parent note we will keep honouring: an instruction takes exactly as many cycles as it has work, and the clock period is the longest single step, never the whole path. If a symbol shows up you have not seen, we define it on the spot.

Vocabulary we must fix before any example

The parent note used names like IR, A, B, IR[15:11], PC, and "sign-ext" freely. A 12-year-old meeting them cold would drown. So we define every one right here, once, and then every example just uses them.

Definition The internal "sticky-note" registers

An instruction is chopped into steps that run in different clock cycles. A value computed in one cycle would vanish at the clock edge unless we save it. These five edge-triggered registers are the save slots ("sticky notes"):

IR = Instruction Register. Holds the raw 32 bits of the instruction fetched in IF, so later cycles can still read it after memory is reused for data.
A = holds the value read from the first source register (the "rs" field).
B = holds the value read from the second source register (the "rt" field). A store like sw puts the value to be written into memory here.
ALUOut = holds whatever the ALU just computed (an address, a sum, or a branch target).
MDR = Memory Data Register. Holds the word just read from data memory (used by lw).

Definition The PC register and how PC+4 happens in IF

PC = Program Counter. It is its own dedicated 32-bit register (separate from the five sticky notes above) that always holds the memory address of the current instruction — "where in memory am I reading from right now." It is not optional scenery: every example below that changes control flow is really just writing a new value into PC. During IF two things happen at once:

Memory is read at address PC to load IR (the instruction bits).
The ALU is idle, so we reuse it to compute $PC + 4$ and write that result back into PC the same cycle: $PC \leftarrow PC + 4$ . Why +4? Instructions are 4 bytes long, so the default "next instruction" sits 4 addresses later. After IF, PC already points at the next instruction — unless a branch or jump later overwrites it. This is the phrase "PC already got PC+4 back in IF" used in Examples 4 and 5.

The scenario matrix

Cell	What is special	Covered by
C1 R-type, normal	4 cycles, skips MEM	Example 1
C2 `lw`, the long one	all 5 cycles	Example 2
C3 `sw`, ends at MEM	4 cycles, no WB	Example 3
C4 `beq`, ends at EX	3 cycles, branch taken vs not	Example 4
C5 `j`, why 3 not 2	PC written in EX	Example 5
C6 Degenerate: balanced stages	when multi-cycle wins	Example 6
C7 Limiting: memory dominates	memory delay ≫ others	Example 7
C8 Zero/degenerate delay	one unit has 0 ps delay	Example 8
C9 Real-world word problem	mixed program, wall-clock time	Example 9
C10 Exam twist	"add a step" / hidden trap	Example 10

Every numeric answer below is machine-checked in the verify block.

Two symbols we will lean on, defined once:

Throughout, unless a problem overrides them, we reuse the parent's component delays:

Look at the picture below — it is the "ruler" every example measures against.

Example 1 — R-type `add` (Cell C1)

List the work add needs. IF (get the instruction into IR), ID (read $t 1 in t o ‘ A ‘,$ t2 into B), EX (ALU adds them), WB (store the sum). It never reads or writes data memory. Why this step? We count cycles by work required, not by the number of defined steps — this is the parent's "no dummy cycles" rule.
So it skips MEM. Cycle count $= 4$ : IF, ID, EX, WB (not MEM). Why this step? MEM only exists for instructions that touch data memory; add does not, so its 4th cycle is WB.
Which register? In EX the sum lands in ALUOut (the sticky note that survives the clock edge). In WB, Reg[IR[15:11]] $\leftarrow$ ALUOut — i.e. the sum goes to the register named by the rd field $IR [15 : 11]$ (here $t0). Why this step? Combinational ALU output vanishes at the edge, so EX latches it into ALUOut for WB to read next cycle.
Time. $4 \times 300 = 1200$ ps. Why this step? Execution time = cycles × period.

Example 2 — `lw` the long instruction (Cell C2)

Work needed: IF, ID, EX (compute address $t 1 + 8$ ), MEM (read data memory), WB (write into $t0). All five steps. Why this step? lw is the only instruction using every canonical step, hence 5 cycles.
Register trail: IF→IR gets the 32 instruction bits (and PC gets PC+4); ID→A gets Reg[ $IR [25 : 21]$ ] = Reg[ $t 1$ ]; EX→ALUOut gets the effective address $A + sign-ext (IR [15 : 0])$ = $t 1 + 8$ ; MEM→MDR gets Memory[ALUOut]; WB→Reg[ $IR [20 : 16]$ ] = Reg[ $t 0$ ] $\leftarrow$ MDR. Why this step? Each sticky-note register carries one value forward one cycle. MDR = Memory Data Register; note lw's destination is the rt field $IR [20 : 16]$ , not rd.
Time. $5 \times 300 = 1500$ ps. Why this step? cycles × period.

Example 3 — `sw` finishes at MEM (Cell C3)

Work needed: IF, ID, EX (address = $t 1 + 8$ via $A + sign-ext (IR [15 : 0])$ ), MEM (write the value in B into memory). Why this step? During ID, sw reads register $t 0 in t o ‘ B ‘ (v ia$ \text{IR}[20{:}16]$); in MEM that value in B is pushed into Memory[ALUOut].
No WB. A store produces no result for the register file — nothing to write back. So it ends at MEM: 4 cycles. Why this step? WB exists only to update a register; sw updates memory, not a register.
Time. $4 \times 300 = 1200$ ps.

Example 4 — `beq`, taken vs not taken (Cell C4)

PC already advanced in IF. Back in IF, the ALU computed $PC \leftarrow PC + 4$ and PCSrc chose that value — so PC already points at the fall-through instruction before we even know this is a branch. Why this step? This is why a not-taken branch needs no extra work later: the default was done in IF.
Target pre-computed in ID. In step ID, while the ALU is idle, ALUOut $\leftarrow PC + (sign-ext (IR [15 : 0]) ≪ 2)$ . This is optimistic pre-computation. Why this step? Computing the target early means no extra cycle is needed if the branch is taken. The $≪ 2$ turns a word offset into a byte offset.
Decision made in EX. In EX the ALU computes $A - B$ (that is Reg[ $t 0$ ] − Reg[ $t 1$ ]); if $A = B$ then the PCSrc mux flips from PC+4 to ALUOut, so PC $\leftarrow$ ALUOut. Why this step? Equality is a subtraction check; the ALU does it, and PC is (conditionally) rewritten the same cycle via PCSrc.
(a) Taken = 3 cycles (IF ID EX). (b) Not-taken = also 3 cycles — PC already got PC+4 back in IF (step 1), so nothing more is needed. Both are 3. Why this step? Whether or not we overwrite PC, the instruction still ends at EX; the work is identical in length.
Time (both): $3 \times 300 = 900$ ps.

The figure below shows the two paths side by side — read it as two timelines stacked on top of each other:

Example 5 — `j` needs 3 cycles, not 2 (Cell C5)

PC is written in EX. The parent's rule: for a jump, the PCSrc mux selects the jump address, so PC $\leftarrow {PC [31 : 28], IR [25 : 0], 00}$ happens in the EX step (it glues the top 4 bits of PC, the 26-bit target field $IR [25 : 0]$ , and two zero bits). Why this step? The datapath's control FSM only routes the jump-target into PC (via PCSrc) during the EX state; there is no earlier path.
So it needs IF, ID, EX = 3 cycles. ID is still traversed (decode + register fetch happen for every instruction blindly, since we don't know the type until decode finishes). Why this step? ID is unconditional — the CPU cannot skip decoding an instruction it hasn't decoded yet.
Time. $3 \times 300 = 900$ ps.

Example 6 — When multi-cycle actually WINS (balanced stages) (Cell C6)

CPI first. $CPI = 0.25 (5) + 0.10 (4) + 0.45 (4) + 0.15 (3) + 0.05 (3)$ . Why this step? Frequency × cycle-count, summed — the definition of CPI.
Compute. $= 1.25 + 0.40 + 1.80 + 0.45 + 0.15 = 4.05$ . Why this step? Same mix as parent, so same CPI = 4.05; only the period changed.
Speedup $= \frac{N \cdot 800}{N \cdot 4.05 \cdot 200} = \frac{800}{810} \approx 0.988$ . Why this step? $T_{single} / T_{multi}$ with $T_{multi} = CPI \times T_{step}$ ; the same $N$ instructions cancel top and bottom.

Example 7 — Limiting case: memory dominates (Cell C7)

Single-cycle lw $= 500 + 100 + 100 + 500 + 100 = 1300$ ps. Why this step? Whole worst-case path: IMem + RegFile read + ALU + DMem + RegFile write.
Multi-cycle step delays: IF=500, ID=RegFile read(100)+ALU(100)=200, EX=100, MEM=500, WB=100. Longest = 500 ps. Why this step? Clock fits the worst single step; here memory-access steps (IF, MEM) tie at 500.
CPI = 4.05 (same mix). Time per instruction $= 4.05 \times 500 = 2025$ ps. Why this step? CPI × period.
Speedup $= \frac{1300}{2025} \approx 0.642$ . Why this step? $T_{single} / T_{multi}$ .

Example 8 — Zero / degenerate delay (Cell C8)

Recompute the step delays. IF=200, ID=0+200=200, EX=200, MEM=200, WB=0. Why this step? Each step's delay is the sum of the functional-unit delays it uses; RegFile now contributes 0 to both its read (in ID) and its write (in WB).
New period $= max (200, 200, 200, 200, 0) = 200$ ps. Why this step? Clock = longest step. Removing the 100 ps register read collapses ID from 300 to 200, so the whole clock drops to 200.
Cycle counts unchanged. Zero delay does not remove steps — WB still exists (it just costs 0 ps), so add is still 4 cycles. Why this step? Cycle count is about work needed, not how fast a unit is. A 0-ps step is still a step in the FSM.

Example 9 — Real-world word problem (Cell C9)

Total cycles $= N \times CPI = 1, 000, 000 \times 4.05 = 4, 050, 000$ cycles. Why this step? $N$ is the instruction count; CPI is cycles-per-instruction, so their product is total cycles.
Multi-cycle wall time $= 4, 050, 000 \times 300 ps = 1, 215, 000, 000$ ps. Convert: $1 μ s = 1 0^{6}$ ps, so $1, 215, 000, 000/1 0^{6} = 1215 μ s$ . Why this step? Total time = total cycles × clock period; we then convert ps → µs by dividing by $1 0^{6}$ , because a microsecond is a million picoseconds.
Single-cycle wall time $= N \times 800 ps = 1, 000, 000 \times 800 = 8 \times 1 0^{8}$ ps $= 800 μ s$ . Why this step? Single-cycle does 1 cycle per instruction at 800 ps each.
(c) Compare. Single-cycle (800 µs) is faster than multi-cycle (1215 µs) here; ratio $= 800/1215 \approx 0.658$ , i.e. multi-cycle takes about $1/0.658 \approx 1.52 \times$ longer. Why this step? Same speedup ratio as parent Example 3, because same mix and same periods — now scaled to a million instructions.

Example 10 — Exam twist: a hidden extra stage (Cell C10)

Does the clock change? The new stage = 150 ps, which is less than the current maximum (ID = 300 ps). So $T_{step}$ stays 300 ps. Why this step? Clock = longest single step; a stage shorter than the current champion cannot raise the maximum.
Does add's cycle count change? Yes — every instruction now has one more mandatory step. add: IF, ID, new-stage, EX, WB = 5 cycles. Why this step? The twist says the stage is mandatory for every instruction, so it adds exactly one cycle to each, regardless of type.
New time for add $= 5 \times 300 = 1500$ ps (was 1200). Why this step? cycles × period; the count went 4→5 while the period held at 300.

Recall gauntlet

Recall Why does

add take 4 cycles, not 5? It skips MEM (no data-memory access); its 4 cycles are IF, ID, EX, WB. ::: correct Why does add skip a step? ::: R-type never touches data memory, so it omits MEM and writes back in WB. Why is sw = 4 cycles while lw = 5? ::: sw has no WB (nothing to write to a register); lw writes loaded data back, needing WB. Why does j need 3 cycles, not 2? ::: The PC is written during the EX step (PCSrc selects the jump address), so the jump must reach EX. What sets the multi-cycle clock period? ::: The delay of the longest single step, not the whole instruction path. In the default machine, which step is the bottleneck and why? ::: ID = 300 ps, because it does a RegFile read (100) followed by an ALU branch-target calc (200) in one cycle. Does a 0-ps functional unit reduce cycle counts? ::: No — it shortens the clock period only; the step still exists in the FSM. What does sign-ext do and which unit performs it? ::: Copies the 16-bit number's top sign bit into the upper 16 bits to make a 32-bit value; a fixed sign-extend wiring block, not the ALU. What does IR[15:11] name? ::: The rd field — the destination register for an R-type instruction. What is the PC register? ::: The Program Counter — a dedicated 32-bit register holding the memory address of the current instruction. Where and why is PC+4 computed? ::: In IF, using the idle ALU; +4 because instructions are 4 bytes, so PC then points at the default next instruction. What does the PCSrc mux choose between? ::: PC+4 (default, IF), the branch target ALUOut (taken beq, EX), and the jump address (j, EX). What is multi-cycle's guaranteed advantage over single-cycle? ::: Less hardware — one shared ALU and one unified memory used across different cycles.

Where to go next

Back to the parent topic for the full step derivations.
Compare against Single-cycle datapath (one long clock, no shared hardware).
The natural upgrade: Pipelining (overlap the steps of different instructions).
The state machine that drives these steps: Control unit — FSM vs microprogramming.
The math behind our speedups: CPI and CPU performance equation.
Supporting hardware: ALU design and Memory hierarchy.
🇮🇳 5.2.02 Multi-cycle datapath (Hinglish)