Processor Datapath & Pipelining

Question 1

(a) Single-cycle period = critical path of slowest instruction = load: $T = 200 + 100 + 150 + 250 + 100 = 800\text{ ps}$ Load sets it. (3 marks: path 2, sum 1)

(b) Multi-cycle cycle time = slowest single component = Data Memory = 250 ps. (1) Average CPI: $\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$ (2) Average instruction time = $4.05 \times 250 = 1012.5$ ps. (2)

(c) Single-cycle instruction time = 800 ps (all instructions take one 800 ps cycle). Multi-cycle avg = 1012.5 ps. Ratio multi/single = $1012.5 / 800 = 1.2656$. Single-cycle is faster here (by ~26.6%) because the multi-cycle CPI is high and its cycle time only saved a little. (4 marks: comparison 2, correct conclusion + factor 2)

Question 2

(a) RAW dependencies: (4, one each ≈1)

• I1→I2 on $t0
• I2→I3 on $t1
• I1→I3 on $t0
• I3→I4 on $t2
• I3→I5 on $t2

(b)

• I1(lw)→I2 on $t0: load-use hazard — value available only after MEM. I2 needs it in EX the cycle right after I1's MEM would produce it → 1 stall cycle inserted between I1 and I2. After stall, MEM/WB forwarding supplies it. (2)
• I2→I3 ($t1), I1→I3 ($t0, already old enough), I3→I4 ($t2), I3→I5 ($t2): all resolved by forwarding, no stalls. (2)
• Total stalls = 1.

(c) I3 reads $t1 produced by I2. When I3 is in EX, I2 is in MEM. Forward from EX/MEM pipeline register. Condition: $\text{EX/MEM.RegWrite} \land (\text{EX/MEM.Rd} \ne 0) \land (\text{EX/MEM.Rd} = \text{ID/EX.Rs or Rt})$ Here EX/MEM.Rd = $t1 = ID/EX.Rs → forward ALU result. (3)

(d) Without stalls, 5 instructions in 5-stage pipeline take $5 + (5-1) = 9$ cycles. Add 1 load-use stall → 10 cycles. (3)

Question 3

(a) Penalties per instruction:

• Branch: $0.20 \times 0.30 \times 2 = 0.12$
• Load-use: $0.15 \times 0.40 \times 1 = 0.06$

$\text{CPI} = 1 + 0.12 + 0.06 = 1.18$ (4)

(b) Cycle time = $1/(2.0\times10^9) = 0.5$ ns. $T = 10^9 \times 1.18 \times 0.5\times10^{-9} = 0.59\text{ s}$ (3)

(c) New penalties:

• Branch: $0.20 \times 0.30 \times 5 = 0.30$
• Load-use: $0.15 \times 0.40 \times 2 = 0.12$ $\text{CPI} = 1 + 0.30 + 0.12 = 1.42$ Cycle time = $1/(3.4\times10^9) = 0.29412$ ns. $T = 10^9 \times 1.42 \times 0.29412\times10^{-9} = 0.41765\text{ s}$ Speedup = $0.59 / 0.41765 = 1.4127$. Faster by ~1.41×. (5)

Question 4

(a) In steady state, five instructions occupy the five stages each cycle. A structural hazard occurs whenever the instruction in the MEM stage (a load or store performing a data access) needs the memory port in the same cycle as the instruction in the IF stage fetching the next instruction. Both demand the single unified port simultaneously. (4)

(b) Every memory instruction (fraction $f$) collides once, adding 1 stall cycle: $\text{CPI} = 1 + f$ (3)

(c) $f = 0.35$: CPI $= 1.35$. Slowdown vs ideal CPI 1 = $(1.35 - 1)/1 = 0.35 =$ 35% slower. (3)

Question 5

(a) An exception is precise if, when it is taken: (i) all instructions before the faulting instruction (in program order) have completed and updated architectural state; (ii) the faulting instruction and all instructions after it have not modified any architectural state; and (iii) the saved PC points exactly to the faulting instruction (or the next), enabling clean restart/resume. (3)

(b) On detecting I1's overflow in EX:

• Prevent I1 from writing back (squash its later MEM/WB effects). (1)
• Flush I2 (in ID) and I3 (in IF) — they must not complete, since they follow the faulting instruction. (1)
• Save I1's PC in EPC and set Cause register. (1)
• Redirect fetch to the exception handler address. Instructions older than I1 (already past EX) are allowed to finish. (1)

(c) Multiple exceptions can be pending in different stages in one cycle; to preserve program order semantics the exception of the oldest (earliest in program order) instruction must be taken first, because a precise exception requires all prior instructions to have completed and all later ones squashed — taking a later instruction's exception first would violate this. Between I1 (add, program order first) and I2 (lw, program order second), I1's exception takes precedence even though physically I2 might signal in a later cycle in the MEM stage. The pipeline handles exceptions in program order; I1 being older wins. (5)

[
  {"claim":"Q1a single-cycle load period is 800 ps","code":"result = (200+100+150+250+100)==800"},
  {"claim":"Q1b multi-cycle average CPI is 4.05","code":"cpi=0.25*5+0.10*4+0.45*4+0.15*3+0.05*3; result=abs(cpi-4.05)<1e-9"},
  {"claim":"Q1b avg instruction time 1012.5 ps","code":"result=abs(4.05*250-1012.5)<1e-9"},
  {"claim":"Q1c single-cycle faster, ratio ~1.2656","code":"result=abs((1012.5/800)-1.265625)<1e-6"},
  {"claim":"Q2d total cycles 10","code":"result=(5+(5-1)+1)==10"},
  {"claim":"Q3a CPI 1.18","code":"cpi=1+0.20*0.30*2+0.15*0.40*1; result=abs(cpi-1.18)<1e-9"},
  {"claim":"Q3b time 0.59 s","code":"result=abs(1e9*1.18*0.5e-9-0.59)<1e-9"},
  {"claim":"Q3c new CPI 1.42","code":"cpi=1+0.20*0.30*5+0.15*0.40*2; result=abs(cpi-1.42)<1e-9"},
  {"claim":"Q3c speedup ~1.4127","code":"t1=1e9*1.18*0.5e-9; t2=1e9*1.42*(1/3.4e9); result=abs(t1/t2-1.4127)<1e-3"},
  {"claim":"Q4c CPI 1.35 and 35% slowdown","code":"cpi=1+0.35; result=abs(cpi-1.35)<1e-9 and abs((cpi-1)/1-0.35)<1e-9"}
]