Exercises — Multi-cycle datapath

(a) IR is written in IF — it holds the raw instruction bits Memory[PC]. (b) A and B are written in ID — they hold the two source-register values Reg[rs], Reg[rt]. (c) ALUOut is first written in ID — it holds the speculatively pre-computed branch target PC + (sign-ext(imm) << 2). (It is written again in EX for R-type/address results — but the first write is ID.) (d) MDR is written in MEM — it holds data read from memory during lw. Why this ordering? Each register is a "sticky note" catching a combinational value before the clock edge erases it, so a later cycle can read it.

(a) add = 4 (IF ID EX WB — no memory). (b) lw = 5 (IF ID EX MEM WB — the only 5-cycle instruction). (c) sw = 4 (IF ID EX MEM — finishes in MEM, no write-back). (d) beq = 3 (IF ID EX — PC updated in EX). (e) j = 3 (IF ID EX — PC updated in EX).

• IF = $200$ ps. Why? In IF two things happen in parallel: the memory read IR ← Memory[PC] (200 ps) and the PC+4 add on the ALU (200 ps). Because these run on independent hardware at the same time — the memory feeds IR while the ALU feeds PC — the stage delay is the maximum of the two, $\max (200,200)=200$ ps, not their sum. This is the crucial difference from ID (below), where the two operations are chained.
• ID = RegFile read $(100)$ then ALU branch-target calc $(200)$ in sequence in the same cycle $=100+200=300$ ps. Here the ALU needs the register-read result as an input, so it must wait for it — the delays add.
• EX = ALU = $200$ ps.
• MEM = memory access = $200$ ps.
• WB = RegFile write = $100$ ps. The clock must fit the worst step, so $T_{step}=\max (200,300,200,200,100)=300$ ps. Why ID dominates: it chains a register read and an ALU op (one feeds the other), so their delays add; IF avoids this because its memory read and PC+4 add are independent and parallel.

lw uses 5 cycles: $5\times 300=1500$ ps. Single-cycle lw = $800$ ps. So for lw alone, multi-cycle is slower ($1500>800$). Why this step: execution time = cycles × period. Never compare clock speeds; compare times.

beq uses 3 cycles: $3\times 300=900$ ps. This is close to the single-cycle 800 ps, but still slightly slower here because $T_{step}=300$ is not perfectly balanced.

$\text{CPI}=0.25(5)+0.10(4)+0.45(4)+0.15(3)+0.05(3)$ $=1.25+0.40+1.80+0.45+0.15=4.05$ Why each term: it is $f_i\times c_i$ — the fraction of the program that is type $i$ times that type's cycle count. Summing over all types gives the weighted average number of cycles a "typical" instruction costs.

$\frac{T_{single}}{T_{multi}}=\frac{N\cdot 800}{N\cdot 4.05\cdot 300}=\frac{800}{1215}\approx 0.66$ Since $0.66<1$, multi-cycle is slower on raw time for these numbers. Why: the ID stage (300 ps) is unbalanced — it hogs the clock period while other stages waste 100–200 ps of that period. Multi-cycle's guaranteed benefit here is less hardware (shared ALU and unified memory), not speed.

Break-even: $4.05\cdot T_{step}=800\Rightarrow T_{step}=800/4.05\approx 197.5$ ps. So multi-cycle beats single-cycle only when the worst step drops below ≈197.5 ps. Since one memory access already costs 200 ps, that's essentially impossible unless we also reduce CPI or memory delay. This quantifies why this particular machine loses on speed. Why this step: set the two program-times equal and solve for the unknown — the classic break-even technique.

beq uses IF, ID, EX — the ALU works in all three:

• IF: operands = PC and 4 → result PC+4, latched into PC (default next instruction). This ALU add runs in parallel with the memory read IR ← Memory[PC], so it does not lengthen the IF stage beyond 200 ps (see L2-Q1).
• ID: operands = PC and sign-ext(imm) << 2 → result = branch target, latched into ALUOut speculatively.
• EX: operands = A and B → the ALU subtracts to test $A=B$; if the zero-flag is set, PC ← ALUOut (the target from ID). Why three uses: multiplexers re-route the single shared ALU's inputs each cycle — that reuse is the point of multi-cycle. (See figure.)

(a) $\text{CPI}=0.50(4)+0.40(5)+0.10(3)=2.0+2.0+0.3=4.3$. (b) Time per instruction $=4.3\times 300=1290$ ps. (c) $1290>800$, so multi-cycle is still slower — the memory-heavy lw fraction pushes CPI up, not down. Why: more lw means more 5-cycle instructions, raising CPI. Multi-cycle helps only when the step delay advantage outweighs the cycle-count penalty — which it doesn't here.

sw writes memory: in MEM it does Memory[ALUOut] ← B. Its job — moving a register value into memory — is complete once memory is written. There is no register to update, so no WB. lw reads memory: in MEM it does MDR ← Memory[ALUOut], capturing the data in MDR. But the destination is a register, and the register file can only be written in a separate cycle (WB): Reg[rt] ← MDR. Hence lw needs the extra 5th step. Why the asymmetry: a store's destination is memory (written in MEM); a load's destination is a register (written in WB). The direction of data flow decides the last step.

New cycle counts (each +1): lw=6, sw=5, R-type=5, beq=4, j=4. (a) ${\text{CPI}}_{new}=0.25(6)+0.10(5)+0.45(5)+0.15(4)+0.05(4)$ $=1.50+0.50+2.25+0.60+0.20=5.05$. (b) Time/instr $=5.05\times 200=1010$ ps. (c) vs single-cycle: $800/1010\approx 0.79$ → still slower than single-cycle, but closer. (d) vs original multi-cycle: $1215/1010\approx 1.20$ → the rebalanced machine is 20% faster than the original multi-cycle. Why the trade-off matters: shortening the clock (300→200) more than paid for the extra cycle within the multi-cycle family, even though neither beats single-cycle on this mix. This is the exact tension pipelining resolves — see Pipelining.

Multi-cycle wins here — but for hardware, not speed. Reasoning:

• The workload is memory-heavy, so CPI is high (many 4–5 cycle instructions) → multi-cycle's time advantage is weak (we saw 0.66–0.79 speedups, i.e. slower).
• But the constraint is transistor budget. Multi-cycle uses one unified memory and one shared ALU across cycles, whereas single-cycle needs separate I/D memories and often multiple adders. That is the decisive saving for a tiny chip.
• Full Pipelining would give the best throughput but costs the most hardware (pipeline registers, forwarding, hazard logic) — wrong for a tiny budget. Conclusion: pick multi-cycle: its defining benefit — hardware reuse — matches the binding constraint. See CPI and CPU performance equation for the throughput trade-off and Control unit — FSM vs microprogramming for how the multi-step control is built.

Equal instruction counts $N$ cancel: $T_{multi}<T_{single}⟺\text{CPI}\cdot T_{step}<T_{single}⟺T_{step}<\frac{T_{single}}{\text{CPI}}.$ With $T_{single}=800$, CPI $=4.05$: need $T_{step}<800/4.05\approx 197.5$ ps (matches L3-Q3). The general rule: multi-cycle wins iff the longest step is shorter than the single-cycle period divided by the average cycle count. Why: this is just "program time smaller" with $N$ divided out — the cleanest statement of the whole trade-off.

Multi-cycle clock period equals the delay of the longest single step. Program time = N × CPI × T_step. R-type's four steps are IF, ID, EX, WB (it skips MEM). Multi-cycle beats single-cycle iff $T_{step}<$ T_single / CPI. Multi-cycle needs only one (unified) memory because IF and MEM happen in different cycles.