Processor Datapath & Pipelining

Question 1

(a) lw traverses: I-Mem → Reg read → ALU (address) → Data Mem → Reg write. $200 + 100 + 200 + 200 + 100 = 800\text{ ps}$ Critical path = 800 ps, so minimum clock period = 800 ps. (3 marks path, 2 marks total)

(b) In a single-cycle machine every instruction completes in exactly one clock cycle, so the clock period must accommodate the slowest instruction (lw, 800 ps). Clocking at the add delay (600 ps) would truncate lw before data memory + write-back complete → incorrect results. CPI = 1 (by definition, one cycle per instruction). (3 marks)

(c) Ideal per-instruction times: lw=800, sw=700 (I-Mem+Reg+ALU+DMem = 200+100+200+200), R-type=600, beq=500 (200+100+200), j=200. $\bar T = 0.25(800)+0.10(700)+0.45(600)+0.15(500)+0.05(200)$ $= 200+70+270+75+10 = 625\text{ ps}$ Speedup vs single-cycle (800 ps) = $800/625 = 1.28$. (2 marks)

Question 2

(a) EX hazard, ForwardA = 10:

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

(4 marks; 1 each for RegWrite, Rd≠0, Rd=Rs match, correct output code)

(b) MEM hazard, ForwardA = 01:

if (MEM/WB.RegWrite
    and (MEM/WB.RegisterRd ≠ 0)
    and NOT(EX/MEM.RegWrite and (EX/MEM.RegisterRd ≠ 0)
            and (EX/MEM.RegisterRd = ID/EX.RegisterRs))
    and (MEM/WB.RegisterRd = ID/EX.RegisterRs))
      ForwardA = 01

The NOT(...) term ensures the most recent (closer, EX/MEM) result is forwarded when both a MEM/WB and an EX/MEM instruction write the same register; without it, the stale older value from MEM/WB could override the newer one. (3 marks logic, 2 marks explanation)

(c) Register $0 is hardwired to zero and can never be written. If we forwarded on Rd = 0, an instruction whose destination is $0 (used as a no-op / discard) would incorrectly forward a garbage/computed value in place of the constant zero. The ≠ 0 guard prevents false forwarding. (3 marks)

Question 3

(a) Load-use hazard detection:

if (ID/EX.MemRead
    and ((ID/EX.RegisterRt = IF/ID.RegisterRs)
      or (ID/EX.RegisterRt = IF/ID.RegisterRt)))
      stall the pipeline

(4 marks; MemRead + Rt match against both source regs)

(b) In the stall cycle the control unit:

1. Freezes the PC (do not fetch next instruction).
2. Freezes the IF/ID register (hold the dependent instruction).
3. Inserts a bubble: zero the control signals in ID/EX (turn the EX/MEM/WB controls into a nop). (1 mark each)

(c) Pipeline diagram (F=IF, D=ID, X=EX, M=MEM, W=WB, *=stall bubble):

Cyc:   1  2  3  4  5  6  7  8
lw     F  D  X  M  W
add       F  D  *  X  M  W
sub          F  *  D  X  M  W

The lw result is available after its MEM (cycle 4) and forwarded into add's EX (cycle 5); one stall cycle is required. 1 stall cycle. (sub gets $t2 and $t0 by normal EX/MEM and MEM/WB forwarding, no extra stall.) (3 marks)

Question 4

(a) Fraction of taken branches = $0.20 \times 0.60 = 0.12$. Each taken branch costs 3 penalty cycles. $CPI = 1 + 0.12 \times 3 = 1 + 0.36 = 1.36$ (4 marks)

(b) Penalty now 1 cycle: $CPI = 1 + 0.12 \times 1 = 1.12$ Speedup = $1.36 / 1.12 = 1.214$ (≈ 1.21×). (3 marks)

(c) Resolving in ID requires moving the comparator and target-address adder into the ID stage, lengthening the ID-stage critical path (may raise clock period). It also introduces a data hazard: a branch that depends on a result still in EX/MEM cannot get its operand by normal forwarding in time, forcing an extra branch-comparison stall (or dedicated forwarding into ID). (3 marks)

Question 5

(a) Clock period: $T_{clk}(k) = \frac{1000}{k} + 40$ Ideal throughput (instructions/ps), one instr completes per cycle in steady state: $\text{Throughput}(k) = \frac{1}{T_{clk}(k)} = \frac{1}{1000/k + 40}$ (3 marks)

(b) $k=5$: $T_{clk}=200+40=240$ ps → throughput $=1/240 = 4.17\times10^{-3}$ /ps. $k=10$: $T_{clk}=100+40=140$ ps → throughput $=1/140 = 7.14\times10^{-3}$ /ps. Throughput keeps rising with $k$ but with diminishing returns — the fixed $\Delta=40$ ps overhead dominates as $1000/k \to 0$; the asymptotic ceiling is $1/40 = 0.025$ /ps. (4 marks)

(c) Effective throughput $=\dfrac{1}{CPI \cdot T_{clk}} = \dfrac{1}{(1+0.05k)(1000/k + 40)}$.

Throughput is still rising at $k=12$ among the sampled values; of the evaluated points $k=12$ gives the highest throughput. (Continuous optimum is near $k=\sqrt{1000\cdot0.05/(0.05\cdot40)}\approx 20$; among tested integers, 12 wins.) (3 marks)

Question 6

(a) A precise exception is one where, when the exception is taken, all instructions before the faulting instruction have completed and updated architectural state, and no instruction at or after the faulting instruction has modified architectural state — so the saved PC and register/memory state correspond to a single well-defined point in the sequential program order. (2 marks)

(b) In a deep/out-of-order pipeline, a later instruction may finish (write results) before an earlier instruction that then faults; architectural state is thus corrupted out of program order, making the exception imprecise. A reorder buffer holds results in program order and commits (retires) instructions in order: results are written to architectural state only at commit. If a faulting instruction reaches the head of the ROB, all earlier instructions have committed and all later ones are squashed before committing — restoring a precise state. (4 marks)

(c) Instructions must be handled in program order for a precise exception. The earlier instruction (further down the pipe) precedes the later one in program order; if the later one's exception were taken first, the earlier instruction would be abandoned, and the state would not correspond to a precise, in-order point. Priority to the oldest instruction guarantees the exception is reported at the correct architectural PC. (2 marks)

[
  {"claim":"Q1a lw critical path = 800 ps","code":"result = (200+100+200+200+100)==800"},
  {"claim":"Q1c average multicycle time = 625 ps and speedup 1.28","code":"avg=0.25*800+0.10*700+0.45*600+0.15*500+0.05*200; result = (avg==625) and (abs(800/avg-1.28)<0.005)"},
  {"claim":"Q4a CPI = 1.36 with 3-cycle penalty","code":"result = abs((1+0.20*0.60*3)-1.36)<1e-9"},
  {"claim":"Q4b CPI 1.12 and speedup ~1.214","code":"cpi=1+0.20*0.60*1; result = abs(cpi-1.12)<1e-9 and abs(1.36/1.12-1.2143)<0.001"},
  {"claim":"Q5b throughput k=10 = 1/140","code":"result = abs(1/(1000/10+40) - 1/140)<1e-12"},
  {"claim":"Q5c k=12 gives lowest CPI*Tclk among 5,8,10,12","code":"f=lambda k:(1+0.05*k)*(1000/k+40); vals={k:f(k) for k in [5,8,10,12]}; result = min(vals,key=vals.get)==12"}
]