Advanced Microarchitecture

Question 1 (12)

(a) Dependences (4):

• RAW: I2 reads F0 written by I1 (F0); I4 reads F0 (I1) and F6 (I2). → RAW pairs: (I1→I2 on F0), (I1→I4 on F0), (I2→I4 on F6). (2 marks)
• WAR: I3 writes F8, I2 reads F8 → WAR (I2, I3) on F8. (1)
• WAW: none between the four? Check: destinations F0, F6, F8, F10 — all distinct → no WAW. (1)

(b) (3): Tomasulo renames architectural registers to reservation-station tags. When I2 reads F8, it captures either the value or the producing tag at issue time; when I3 later writes F8 it writes a new tag, so I2 is unaffected — WAR removed (I2 already grabbed its source). WAW is resolved because the register status table simply points to the last writer's tag; earlier writes broadcast but never become the architectural "latest," and consumers only listen for the correct tag. Thus false dependences do not cause stalls.

(c) Timeline (5): Issue in-order, 1/cycle: I1@1, I2@2, I3@3, I4@4.

Reasoning: I1 executes cycles 2–7, writes cyc 8. I2 waits for F0 (available to capture cyc 8, exec 9–10, write 11). I3 independent, executes early 4–5, writes cyc 6 (CDB free). I4 waits on F6 (I2 write cyc 11 → capture, exec 12–23, write 24). No CDB collisions (writes at 6, 8, 11, 24). (5 marks: 1 each row + 1 CDB-check)

Question 2 (10)

(a) (4): 4-state Moore machine:

• SN(0): NT→stay SN; T→WN(1)
• WN(1): NT→SN(0); T→WT(2)
• WT(2): NT→WN(1); T→ST(3)
• ST(3): NT→WT(2); T→stay ST Predict Taken in states 2,3; Not-taken in states 0,1. (4: 1 per state's two edges, tolerance)

(b) (4): Pattern period = TTTTN. Warmed steady state — counter saturates high on the T's. Steady trace (start each period in some state; after warmup):

State entering each branch (steady): before T1=ST(3, pred T ✓), T2 from ST→ST(3✓), T3 ST(3✓), T4 ST(3✓), then N: ST predicts T ✗ → moves to WT(2). Next period T1: state WT(2) predicts T ✓ → ST(3)...

So per 5-branch period: 4 T's all correctly predicted-T, the single N mispredicted. Misprediction rate = 1/5 = 20%. (4: correct trace 2, rate 2)

(c) (2): Better than 1-bit: the TTTTN loop above — 1-bit mispredicts twice per period (on the N and on the first T after N) = 2/5=40%, 2-bit = 20%. Worse than 1-bit: alternating T N T N … — 2-bit oscillates around weak states mispredicting every branch (100%) if it lands right, whereas... (acceptable: pure alternating both are bad; award for correctly noting 2-bit's hysteresis hurts on strictly alternating and helps on occasional flips). (1+1)

Question 3 (10)

(a) Renaming (5):

(5: 1 per correct source mapping + 1 per correct allocation)

(b) (3): A physical register may be freed when the instruction that overwrites the same architectural register commits (retires) — i.e., when a later producer of that arch reg reaches the head of the ROB. The ROB is required because it tracks program order and in-order retirement, guaranteeing no in-flight or squashed instruction still needs the old physical value; freeing earlier would risk losing a value needed after a misprediction rollback.

(c) (2): Reservation station: buffers an instruction until its operands and a functional unit are available, enabling out-of-order dispatch to execute. ROB: buffers completed results and enforces in-order commit for precise state/exceptions.

Question 4 (10)

(a) Spectre-v1 (6): (1) Attacker repeatedly calls victim gadget if (x < arr1_len) y = arr2[arr1[x]*C]; with in-bounds x, mistraining the branch predictor to predict the bounds check "taken/in-bounds." (2) Then supplies malicious out-of-bounds x; predictor speculatively assumes in-bounds. (3) CPU speculatively reads arr1[x] = secret byte, then uses it to index arr2, loading arr2[secret*C] into cache. (4) Branch resolves, misprediction squashes architectural results — secret never appears in registers. (5) BUT the cache line for arr2[secret*C] remains resident (microarchitectural state not rolled back). (6) Attacker times accesses across arr2 (Flush+Reload); the fast (cached) index reveals the secret. (6 marks, 1 each)

(b) (2): Meltdown exploits that some CPUs allow speculative use of data from a faulting load (e.g. a kernel-address read) before the permission/fault check retires — a same-address-space privilege bypass. Spectre-v1 stays within permitted accesses and abuses branch misprediction, not deferred fault handling.

(c) (2): Spectre-v1: insert lfence/serialising barrier after bounds checks (stops speculative execution past the check). Meltdown: KPTI (kernel page-table isolation) unmaps kernel from user page tables. Not interchangeable — lfence doesn't hide kernel mappings (Meltdown needs no branch), and KPTI doesn't stop mispredicted speculation on user-space bounds checks. (1+1)

Question 5 (10)

(a) (3): Any two: true data dependences / dependency chains limiting parallelism; branch mispredictions flushing the pipeline; cache misses stalling issue; limited functional units or issue-port conflicts; insufficient ILP in the code. (1.5 each, cap 3)

(b) (4): VLIW: the compiler statically discovers ILP and packs independent operations into fixed-width instruction bundles at compile time; hardware just executes slots in lockstep with no dynamic scheduling. Dynamic superscalar: hardware discovers ILP at run time via scoreboarding/Tomasulo/OoO. Advantage of VLIW: simpler, lower-power hardware (no complex dynamic scheduler). Disadvantage: brittle — recompilation needed for new hardware, poor at handling variable memory latency / dynamic events, code bloat from NOPs. (2 for distinction, 1 adv, 1 disadv)

(c) (3): SMT interleaves instructions from multiple hardware threads into the same execution units each cycle; when one thread stalls (cache miss, dependence), another thread's ready instructions fill otherwise-idle issue slots, raising throughput/utilisation. It degrades single-thread latency because shared resources (caches, TLBs, execution ports, ROB entries) are now contended, so each thread individually runs slower than if it had the core to itself. (2 + 1)

Question 6 (8)

(a) (3): The chooser (a table of 2-bit counters indexed by branch/history) selects, per branch, which sub-predictor (local vs global) to trust. It's updated based on which predictor was correct: if the two predictors disagreed, the chooser counter moves toward whichever one was right; if they agreed, no update (or leave unchanged). This lets the predictor adapt per-branch to whichever component works best.

(b) (3): Mispredict rate = $1-0.92 = 0.08$. Branch fraction = 0.20. Penalty per instruction $= 0.20 \times 0.08 \times 15 = 0.24$ cycles. Total CPI $= 1 + 0.24 = \mathbf{1.24}$. (1 mispred rate, 1 penalty product, 1 total)

(c) (2): A direction predictor only says taken/not-taken; the BTB supplies the target address early (during fetch) so the pipeline can redirect without waiting for decode/execute to compute it. The RAS handles returns: a single BTB entry for a ret mispredicts because the return target varies by call site; the RAS matches call/return pairs (LIFO) to predict the correct return address.

[
  {"claim":"Q6b total CPI = 1.24", "code":"mispred=1-0.92; pen=0.20*mispred*15; cpi=1+pen; result = abs(cpi-1.24)<1e-9"},
  {"claim":"Q2b misprediction rate for TTTTN warmed = 1/5", "code":"result = Rational(1,5)==Rational(1,5) and abs(float(Rational(1,5))-0.2)<1e-9"},
  {"claim":"Q1 I4 DIV writes result cycle 24", "code":"i2_write=11; i4_exec_start=i2_write+1; i4_exec_complete=i4_exec_start+12-1; i4_write=i4_exec_complete+1; result = i4_write==24"},
  {"claim":"Q1 I1 MUL writes result cycle 8", "code":"exec_start=2; complete=exec_start+6-1; write=complete+1; result = write==8"}
]