Processor Datapath & Pipelining

Question 1

(a) Substitute the two models: (3) $\Theta(k) = \frac{1}{\bigl(1 + a(k-1)\bigr)\left(\frac{T}{k} + O\right)}.$ (1 mark each factor correctly placed; 1 for reciprocal form.)

(b) Maximising $\Theta$ ⟺ minimising the denominator (9) $D(k) = \bigl(1 + a(k-1)\bigr)\left(\frac{T}{k} + O\right).$ Let $b = 1-a$ so $1+a(k-1) = ak + b$. Then $D(k) = (ak+b)\left(\frac{T}{k}+O\right) = aT + akO + \frac{bT}{k} + bO.$ (2 marks expansion.) Differentiate: $D'(k) = aO - \frac{bT}{k^2}. \quad (2)$ Set $D'(k)=0$: $k^{*2} = \frac{bT}{aO} \implies \boxed{k^\* = \sqrt{\frac{(1-a)\,T}{a\,O}}}. \quad (2)$ Second derivative $D''(k) = \dfrac{2bT}{k^3} > 0$ for $b>0$, so this is a minimum of $D$ ⇒ unique maximum of $\Theta$. (2 marks: uniqueness + convexity.) Existence condition $k^\*>1$: $(1-a)T > aO$, i.e. $a < \dfrac{T}{T+O}$, and we need $a<1$ (so $b>0$). (1 mark.)

(c) With $T=20,\ O=0.5,\ a=0.05$: (5) $k^\* = \sqrt{\frac{0.95\cdot 20}{0.05\cdot 0.5}} = \sqrt{\frac{19}{0.025}} = \sqrt{760} \approx 27.57 \Rightarrow k^\*\approx 28.$ (2 marks.) At $k=28$:

• $T_{clk} = 20/28 + 0.5 = 0.7143 + 0.5 = 1.2143$ ns
• CPI $= 1 + 0.05(27) = 2.35$
• $\Theta = 1/(2.35\times1.2143) = 1/2.854 = 0.3504$ instr/ns.

(2 marks.) At $k=5$: $T_{clk}=20/5+0.5=4.5$, CPI$=1+0.05(4)=1.2$, $\Theta = 1/(1.2\times4.5)=1/5.4=0.1852$ instr/ns. So the optimum roughly doubles throughput vs. 5 stages ($0.350$ vs $0.185$). (1 mark comparison.)

(d) Real curves fall faster because: (3)

• Register overhead $O$ does not shrink and eventually dominates ($T/k \to 0$), so most of the cycle is pure latch overhead — diminishing returns are super-linear once $T/k \sim O$.
• Hazard cost is super-linear, not linear: deeper pipelines lengthen the branch-misprediction penalty and load-use distance, so mispredict flush cost grows with depth; also power/clock-skew and jitter worsen. Any two: branch penalty growth, increased forwarding complexity, power density, limits on further logic partitioning. (1.5 each, cap 3.)

Question 2

(a) Forwarding to ALU input A: (8)

ForwardA = 10  (EX/MEM) if:
   EX/MEM.RegWrite = 1
   AND EX/MEM.RegisterRd ≠ 0
   AND EX/MEM.RegisterRd = ID/EX.RegisterRs

ForwardA = 01  (MEM/WB) if:
   MEM/WB.RegWrite = 1
   AND MEM/WB.RegisterRd ≠ 0
   AND NOT( EX/MEM.RegWrite AND EX/MEM.RegisterRd≠0
            AND EX/MEM.RegisterRd = ID/EX.RegisterRs )   ← priority guard
   AND MEM/WB.RegisterRd = ID/EX.RegisterRs

(RegWrite guard, ≠0 guard, match term, priority-exclusion term — 1 mark each × two cases minus overlap ⇒ 5 marks.) Priority justification (3): if both EX/MEM and MEM/WB write the same register, the instruction in EX/MEM is younger and thus produced the value later in program order; the architecturally correct operand is the most recent write. Forwarding from MEM/WB would deliver a stale value. Hence EX/MEM must win.

(b) Producer availability vs. consumer need (6):

• The ALU consumer needs both operands at the start of its EX stage.
• An R-type producer computes its result at the end of its EX stage. If it is immediately followed by a dependent instruction (distance 1), the producer is in MEM while the consumer is in EX in the same cycle. EX/MEM forwarding delivers the result to the consumer's EX input in that cycle ⇒ 0 stalls. (3)
• A lw producer obtains its data only at the end of its MEM stage. A distance-1 consumer would need it at the start of its EX, which is the same cycle as the load's MEM — the data does not exist yet (it appears only at cycle end). No forwarding path can send data backward in time. Inserting one bubble pushes the consumer's EX to the cycle when the load is in WB, and MEM/WB forwarding then supplies it ⇒ exactly one unavoidable stall. (3)

(c) Load-use hazard detection condition: (4)

if ( ID/EX.MemRead = 1
     AND ( ID/EX.RegisterRt = IF/ID.RegisterRs
        OR ID/EX.RegisterRt = IF/ID.RegisterRt ) )
   → stall

(2 marks.) To create the bubble: freeze the PC and the IF/ID register (they retain their values — instruction re-fetched/re-decoded next cycle), and zero all control signals of the ID/EX register (set the EX/MEM/WB control bits to 0) so a no-op ("bubble") flows down EX/MEM/WB harmlessly. (2 marks.)

(d) Cycle-by-cycle for the given code: (4)

Total: 1 stall (load-use), plus forwarding paths as listed. (2 stall correct, 2 forwards correct.)

Question 3

(a) Precise exception (4): an exception is precise if, when the handler runs, the architectural state is exactly as if instructions executed strictly in program order up to the faulting one and none after. Two invariants: (i) all instructions before the faulting one have completed and committed their state; (ii) the faulting instruction and all instructions after it have committed no state changes. (2 marks each.)

(b) Oldest-first proof (8): Suppose instructions $I_i$ (older, in EX with overflow) and $I_j$ (younger, $j>i$, in IF with page fault) both fault in one cycle. If we serviced $I_j$ first, we would enter its handler while $I_i$ has not committed and while $I_i$ itself faults — violating invariant (i) that all pre-fault instructions complete, and forcing the handler to see partial/out-of-order state. Moreover $I_j$ should not even execute if $I_i$ faults, since in the sequential model control transfers at $I_i$ and $I_j$ is never reached. Therefore correctness requires servicing the oldest faulting instruction $I_i$ and squashing all younger in-flight instructions ($I_j$ and beyond). (4 marks.) Why in-order helps (4): in an in-order pipeline, "oldest in flight" is simply "furthest down the pipeline," so program order = pipeline position. By deferring the actual trap to a single commit point (say WB) and comparing exception flags in stage order, the hardware always picks the oldest flagged instruction automatically and flushes everything behind it — no reorder buffer needed. (4 marks.)

(c) Tagged/deferred exceptions (6):

• Advantage 1: Exceptions are handled at one point in a fixed stage, so multiple simultaneous faults are naturally prioritised by pipeline position (oldest = furthest along), guaranteeing invariant (i)/(ii). (2)
• Advantage 2: State updates (register/memory writes) happen at/after that point, so an instruction carrying an exception flag can be turned into a no-op — no younger instruction has committed, and the faulting instruction commits nothing — satisfying precision without rollback. (2)
• Subtlety: instructions with early side effects — a store writes memory in MEM, a branch redirects the PC — must have those effects suppressed if any older instruction is flagged. So the flush/squash logic must reach back and cancel memory writes and PC updates of instructions that are logically younger than an as-yet-unhandled fault. (2)

[
  {"claim":"k* = sqrt((1-a)T/(aO)) ~ 27.57 for T=20,O=0.5,a=0.05",
   "code":"T,O,a=20,0.5,Rational(1,20); kstar=sqrt((1-a)*T/(a*O)); result = abs(float(kstar)-27.5680975) < 1e-4"},
  {"claim":"Throughput at k=28 approx 0.3504 instr/ns",
   "code":"T,O,a=20,0.5,0.05; k=28; Tclk=T/k+O; CPI=1+a*(k-1); Th=1/(CPI*Tclk); result = abs(Th-0.35035) < 1e-3"},
  {"claim":"Throughput at k=5 approx 0.18519 instr/ns",
   "code":"T,O,a=20,0.5,0.05; k=5; Tclk=T/k+O; CPI=1+a*(k-1); Th=1/(CPI*Tclk); result = abs(Th-0.185185) < 1e-4"},
  {"claim":"Optimum beats k=5 (higher throughput)",
   "code":"T,O,a=20,0.5,0.05; f=lambda k:1/((1+a*(k-1))*(T/k+O)); result = f(28) > f(5)"}
]