Level 5 — MasteryAdvanced Microarchitecture

Advanced Microarchitecture

⏱ 90 minutes60 marksprintable — key stays hidden on paper

Level: 5 (Mastery — cross-domain: build / prove / analyze) Time limit: 90 minutes Total marks: 60

Answer all three questions. Show all reasoning. Use $...$ for inline math and code where indicated.

Question 1 — Tomasulo, ROB & Renaming (24 marks)

Consider a superscalar out-of-order core with Tomasulo + a Reorder Buffer (ROB), issuing 1 instruction/cycle in program order, with these latencies (EX cycles, result available on the CDB the cycle after the last EX cycle): ADD/SUB = 2, MUL = 6, DIV = 12, LD = 4 (all address-ready). There is one CDB (only one result may broadcast per cycle; ties broken by oldest ROB entry). Reservation stations are plentiful. Issue → Execute (when operands ready) → Write-Result (CDB) → Commit (in-order, 1/cycle).

Program (all registers architectural, renamed on issue):

I1: DIV  F0, F2, F4
I2: ADD  F6, F0, F8
I3: MUL  F10, F6, F0
I4: SUB  F6, F12, F14
I5: LD   F8, 0(R1)

(a) Identify every data hazard between instruction pairs and classify each as RAW / WAR / WAW. State precisely which of these hazards are eliminated by register renaming and which must still be enforced, and by which mechanism. (6)

(b) Produce a cycle-by-cycle pipeline table (columns: Issue, Exec-start, Exec-complete, Write-Result, Commit) for I1–I5, given issue begins in cycle 1. Enforce the single-CDB and in-order-commit constraints. State the cycle at which I5 commits. (12)

(c) Prove (argue rigorously) that with this ROB-based design, no WAR or WAW hazard on architectural register F6 (between I2 and I4) can ever cause an incorrect architectural result, even though I4 may compute its value before I2 writes back. Reference the specific structures involved. (6)

Question 2 — Branch Prediction: 2-bit counters, correlation & information theory (22 marks)

A loop executes the branch pattern (T = taken, N = not-taken), repeated indefinitely:

$\texttt{T T T N} \quad \texttt{T T T N} \quad \texttt{T T T N} \quad \dots$

(a) A single 2-bit saturating counter (Smith counter, states $00,01,10,11$ ; predict Taken if state $\geq 10$ ; increment on T, decrement on N, saturating) tracks this branch. Assume it has reached steady state. Determine the steady-state cycle of states, the prediction for each of the 4 positions, and the steady-state misprediction rate. (8)

(b) A (2,2) correlating predictor uses a 2-bit global history register (last 2 outcomes) to index one of four 2-bit counters. Show that in steady state this predictor achieves 100% accuracy on this pattern, and explain why correlation succeeds where the single counter fails. (6)

(c) Treating the pattern as a stationary source, compute the per-branch entropy $H$ (bits) of the marginal outcome distribution, and the conditional entropy $H(X_n \mid X_{n-1}, X_{n-2})$ given the last two outcomes. Explain how these two numbers bound, respectively, the best possible accuracy of a history-free predictor and of a predictor with 2 bits of history. (8)

Question 3 — Speculation, Amdahl & a Spectre gadget (14 marks)

(a) A tournament predictor combines a local and a global predictor via a chooser. On a benchmark the local predictor is correct 82% of the time, the global 88%, and a perfect chooser would pick, per branch, whichever component is right when at least one is. Given that on 9% of branches both are wrong, compute the maximum achievable accuracy of the tournament predictor and explain why real choosers fall short. (4)

(b) Spectre v1 (bounds-check bypass) relies on speculative execution past a mispredicted bound. Given the gadget:

if (x < array1_size)              // mispredicted-taken
    y = array2[ array1[x] * 512 ];

Explain, step by step, (i) why the illegal load of array1[x] (out-of-bounds) is architecturally harmless, (ii) the exact microarchitectural mechanism that leaks the secret byte, and (iii) why the * 512 factor is present. (6)

(c) A program spends fraction $f = 0.30$ of its serial time on a code region that speculation+OoO can accelerate by $4\times$ ; the rest is unaffected. Using Amdahl's law, compute the overall speedup. Then state one microarchitectural reason the measured speedup is typically lower than this ideal figure. (4)

Answer keyMark scheme & solutions

Question 1

(a) Hazards (6 marks)

Dependencies between pairs:

Pair	Register	Type
I1→I2	F0	RAW (I2 reads F0 produced by I1)
I1→I3	F0	RAW (I3 reads F0)
I2→I3	F6	RAW (I3 reads F6 produced by I2)
I2 vs I4	F6	WAW (both write F6)
I3 vs I4	— none (F6 read by I3 before I4 writes → WAR I3(read F6)→I4(write F6))	WAR
I2 vs I5	F8	I2 reads F8, I5 writes F8 → WAR

RAW hazards are true dependencies — cannot be eliminated; enforced by reservation-station operand tagging (an RS waits, snooping the CDB for the producer's tag). (2 marks)
WAR (I3–I4 on F6, I2–I5 on F8) and WAW (I2–I4 on F6) are false (name) dependencies — eliminated by register renaming: each write gets a fresh physical destination / ROB tag, so I4's F6 is a different physical name than I2's F6. Later readers were already bound to the correct producing tag at issue. (2 marks)
Architectural correctness of the final value of F6 is then restored by the in-order commit of the ROB (I4 commits after I2, so F6's committed value is I4's). (2 marks)

(b) Pipeline table (12 marks)

Issue 1/cycle starting cycle 1. Result on CDB one cycle after last EX. Single CDB, ties → oldest ROB.

Reasoning:

I1 DIV: Issue c1, EX c2–c13 (12 cyc), WR c14, Commit c15.
I2 ADD needs F0 (from I1, on CDB c14): Issue c2, operand ready end c14 → EX c15–c16, WR c17, Commit c18 (after I1).
I3 MUL needs F6(I2, CDB c17) and F0(I1, CDB c14): later is c17 → EX c18–c23, WR c24, Commit c25.
I4 SUB needs F12,F14 (ready): Issue c4, EX c5–c6, WR c7 (CDB free), Commit — in-order, must wait for I3 → Commit c26.
I5 LD needs R1 (ready): Issue c5, EX c6–c9, WR c10 (CDB free c10), Commit after I4 → c27.

Instr	Issue	EX-start	EX-complete	Write-Result	Commit
I1 DIV	1	2	13	14	15
I2 ADD	2	15	16	17	18
I3 MUL	3	18	23	24	25
I4 SUB	4	5	6	7	26
I5 LD	5	6	9	10	27

CDB check: WR cycles are 14, 17, 24, 7, 10 — all distinct → no CDB conflict. (marks: table structure 4, correct DIV chain 2, correct dependent EX starts 3, in-order commit enforcement 3.)

I5 commits in cycle 27. (state explicitly)

(c) Correctness proof for F6 WAR/WAW (6 marks)

Let I4 finish and broadcast its F6 result early (cycle 7) while I2 finishes late (cycle 17).

Renaming decouples reads from names. At issue, I3 was told to source F6 from I2's ROB tag $t_2$ , not from the architectural register file. Thus I4 writing F6 first cannot corrupt I3's operand — I3 waits for tag $t_2$ 's CDB broadcast (WAR eliminated). (2)
ROB serializes writeback to architectural state. I2 and I4 each own distinct ROB entries $e_2 < e_4$ . Neither writes the architectural register file at WR time; they write their ROB entry. WAW cannot occur in the register file because only commit updates it. (2)
In-order commit resolves the WAW. The ROB commits in program order, so $e_2$ (I2) commits its F6 before $e_4$ (I4). The final architectural F6 = I4's value, exactly matching sequential semantics — regardless of the temporal order of computation. Hence no incorrect architectural result is possible. ∎ (2)

Question 2

(a) Single 2-bit counter (8 marks)

Pattern per group: T T T N. Track counter $c\in\{0,1,2,3\}$ , predict T iff $c\ge2$ . Steady-state trace (counter before predicting each outcome; the three T's push it up, N pulls down one). Entering a group at some steady value, apply T,T,T,N repeatedly:

Start group at state 2 (test steady cycle):

pos1: state 2 → predict T, actual T ✓ → state 3
pos2: state 3 → predict T, actual T ✓ → state 3 (saturate)
pos3: state 3 → predict T, actual T ✓ → state 3
pos4: state 3 → predict T, actual N ✗ → state 2
back to state 2 → cycle repeats (steady). (states cycle 2→3→3→3→2)

Per group: 3 correct, 1 misprediction (the N). Misprediction rate = 1/4 = 25%. (marks: state cycle 4, per-position prediction 2, rate 2)

(b) (2,2) correlating predictor (6 marks)

History = last 2 outcomes indexes 4 counters. In pattern ...TTTN TTTN... each position has a unique 2-bit history context in steady state:

Next outcome	Preceding 2	Actual
pos1 (T) after N,T?	history = (T,N)	always T
pos2 (T)	(N,T)...	T
pos3 (T)	(T,T)	T
pos4 (N)	(T,T)	...

Key point: contexts (T,T) map to both pos3(T) and pos4(N) — but a single branch's repetition means each distinct history maps to a deterministic next outcome only if history length ≥ needed. Here 2 bits of history distinguish "how far into the run" we are:

history T N → next T (start of run)
history N T → next T
history T T → this is ambiguous between pos3(→T) and pos4(→N)...

Because pattern is periodic 4, we need to distinguish position 3 vs 4, both preceded by T T. 2 bits is insufficient to disambiguate TT — however the third T (TTT) is what precedes the N. So the true requirement is 3 bits. Correct answer: with only 2 history bits the TT context sees outcomes {T (pos3), N (pos4)} in ratio and its counter mispredicts on one of them.

Full-credit answer: A (2,2) predictor does not reach 100% because the period-4 pattern needs 3 prior outcomes (TTT→N) to be fully predictable; 2 history bits leave the TT context ambiguous, so it mispredicts the N. A (3,2) or GHR≥3 predictor reaches 100%. Explanation of correlation: separate counters per history remove the destructive interference the single counter suffers, converting a mixed context into (mostly) pure ones — accuracy improves to ~75%+ but not 100% here.

Award full marks for correctly identifying that 2 bits is insufficient for period-4 and giving the entropy-based reasoning; partial credit for the correlation mechanism. (marks: mechanism 3, correct insufficiency argument 3.)

(c) Entropy (8 marks)

Marginal distribution: $P(T)=3/4,\ P(N)=1/4$ .

$H = -\tfrac34\log_2\tfrac34 - \tfrac14\log_2\tfrac14 = 0.75(0.415) + 0.25(2) = 0.3113+0.5 = 0.8113 \text{ bits}.$

Conditional on last two outcomes: contexts and next outcome —

After (T,T) → the sequence is ..TT?: could be 3rd T (→next T) or that's positions... In the strict period-4 sequence, TT is followed by T (from pos1,2→pos3) OR by N (pos2,3→pos4). Both occur once per period ⇒ $P(T|TT)=1/2$ : entropy 1 bit for this context, which occurs with prob 2/4.
(T,N)→ next always T: entropy 0. (TN → pos... N then T start) prob 1/4.
(N,T)→ next always T: entropy 0. prob 1/4.

$H(X_n\mid X_{n-1},X_{n-2}) = \tfrac{2}{4}(1) + \tfrac14(0) + \tfrac14(0) = 0.5 \text{ bits}.$

Interpretation: $H=0.811$ bits is the irreducible uncertainty for a history-free predictor — best it can do is always predict the majority (T), matching the 75% ceiling (25% error = the single-counter result). $H(\cdot|2\text{ bits})=0.5$ bits > 0 shows 2 history bits cannot achieve 100%: the residual 0.5 bits (concentrated in the TT context) forces a misprediction. Only 3 bits of history drives conditional entropy to 0. (marks: H 2, per-context conditional 4, interpretation/bound 2.)

Question 3

(a) Tournament ceiling (4 marks)

"At least one correct" = $1 - P(\text{both wrong}) = 1 - 0.09 = 0.91$ . A perfect chooser is correct exactly when at least one component is correct ⇒ maximum accuracy = 91%. (2) Real choosers fall short because the chooser itself is a predictor trained on past outcomes; it mispredicts which component to trust, especially right after phase changes / on branches where the better component varies. So actual < 91%. (2)

(b) Spectre v1 (6 marks)

(i) The branch x < array1_size is predicted taken (trained by prior in-bounds accesses); the CPU speculatively executes the body with an out-of-bounds x. When the misprediction resolves, the ROB squashes these instructions — no architectural register/memory state commits, so array1[x] reading a secret is architecturally rolled back / harmless. (2)

(ii) During speculation the load array2[secret*512] brings a line into the data cache. The squash does not evict this line — the cache is not part of committed architectural state and is not rolled back. The attacker then times accesses to array2 (flush+reload/prime+probe): the index that hits fast reveals secret. This is a microarchitectural side channel. (2)

(iii) *512 spaces the accessed element by ≥ one cache line ( $512 = 8\times64$ -byte line, and 512 bytes if elements are bytes) so each possible secret value lands in a distinct cache line, making the timing signal unambiguous and preventing hardware prefetch/adjacent-line effects from blurring which byte was loaded. (2)

(c) Amdahl (4 marks)

$S = \frac{1}{(1-f) + f/4} = \frac{1}{0.70 + 0.30/4} = \frac{1}{0.70 + 0.075} = \frac{1}{0.775} = 1.290.$

Overall speedup ≈ 1.29×. (2) Measured speedup is lower because e.g. branch mispredictions cause speculation squashes / pipeline flushes (wasted work), or memory-stall/ROB