Level 4 — ApplicationAdvanced Microarchitecture

Advanced Microarchitecture

⏱ 60 minutes60 marksprintable — key stays hidden on paper

Level: 4 (Application — novel/unseen problems, no hints) Time limit: 60 minutes Total marks: 60

Answer all questions. Show reasoning; state assumptions clearly.

Question 1 — Tomasulo Dataflow Trace (14 marks)

A single-issue out-of-order core uses Tomasulo's algorithm with register renaming via reservation stations (RS). Latencies: ADD/SUB = 2 cycles execute, MUL = 6 cycles execute, DIV = 12 cycles execute. One instruction issues per cycle (in order); execution begins the cycle after both operands are ready; the common data bus (CDB) broadcasts one result per cycle at write-back. Register file initially: F2=3.0, F4=5.0, F6=7.0.

I1:  MUL  F0, F2, F4
I2:  ADD  F8, F0, F6
I3:  SUB  F10, F4, F6
I4:  DIV  F12, F0, F8

(a) For each instruction give the cycle numbers of Issue, Execute-start, Execute-complete, and Write-back. Assume issue starts at cycle 1, only structural hazard is the single CDB, and no instruction may write back in the same cycle another does (lower-numbered instruction wins CDB ties). (8)

(b) Identify every RAW dependency that is resolved through the CDB rather than the register file, and state the producer→consumer pair for each. (3)

(c) I3 (SUB) has no dependency on I1/I2. Explain precisely why Tomasulo can complete I3's execution before I2's, and what hardware structure prevents I3 from corrupting program-visible state by finishing early. (3)

Question 2 — 2-bit Predictor & Tournament Design (12 marks)

Consider the branch pattern below for a single static branch, executed repeatedly. T = taken, N = not taken:

Sequence:  T T N T T N T T N T T N ...   (period-3 pattern, repeating)

(a) A 2-bit saturating counter (states: 00=SN, 01=WN, 10=WT, 11=ST; predict Taken if MSB=1) starts in state SN. Trace its predictions for the first 12 branches and compute the steady-state misprediction rate (per period) once behaviour stabilises. (6)

(b) A local-history predictor with a 2-bit history register indexing a table of 2-bit counters is applied to the same period-3 pattern. Argue whether it can reach 0% steady-state mispredictions, and justify using the distinct history contexts. (4)

(c) In a tournament predictor combining the schemes of (a) and (b), state which component the meta-predictor should learn to select for this pattern, and describe one branch behaviour where the opposite selection would win. (2)

Question 3 — Speculation, ROB & Recovery (12 marks)

A processor has a 6-entry ROB, issues in order, and commits in order. A conditional branch B is predicted taken and speculation proceeds down the taken path. The following occupy the ROB (head = oldest):

ROB0 (head): ADD  (completed)
ROB1:        B    (branch, resolved LATE)
ROB2:        LOAD (speculative, taken path, completed)
ROB3:        MUL  (speculative, taken path, completed)
ROB4:        STORE(speculative, taken path, completed exec, not committed)
ROB5:        ADD  (speculative, taken path, in execution)

(a) At commit, B resolves as not-taken (misprediction). List which ROB entries must be squashed and explain why the STORE in ROB4, despite having "completed execution," causes no memory corruption. (4)

(b) Explain what happens to the register renaming map (RAT) on this misprediction recovery, and why a speculative rename must not update the architectural register state. (4)

(c) The load in ROB2 accessed memory speculatively. Explain how this exact mechanism enables a Spectre-style side channel, and name the microarchitectural resource that leaks the secret even after the squash. (4)

Question 4 — VLIW vs Superscalar Scheduling (12 marks)

A code fragment (RISC-like, no delay slots):

I1: LOAD  R1, 0(R10)      ; load latency 3 cycles (result available 3 cy later)
I2: ADD   R2, R1, R3      ; 1 cycle
I3: LOAD  R4, 0(R11)      ; load latency 3
I4: SUB   R5, R4, R2      ; 1 cycle
I5: ADD   R6, R1, R4      ; 1 cycle

The machine has 2 issue slots per bundle/cycle: exactly 1 memory slot and 1 ALU slot.

(a) Schedule these 5 instructions as a statically scheduled VLIW (compiler fills bundles; NOPs allowed; respect latencies and slot constraints). Give the bundle table and total cycle count. (6)

(b) A 2-way out-of-order superscalar with the same functional units runs the same code (no reordering by the compiler). State whether it can match, beat, or only equal the VLIW cycle count, and explain the fundamental reason the two approaches can diverge on different code. (4)

(c) Give one concrete microarchitectural reason VLIW designs (e.g., Itanium-style) struggled commercially despite lower hardware complexity. (2)

Question 5 — Return Address Stack & BTB Interaction (10 marks)

(a) A program executes the call/return structure below. A 4-entry Return Address Stack (RAS) is used. Trace the RAS contents (top-of-stack labelled) immediately after each CALL/RET, and identify any misprediction the RAS produces. (6)

CALL A        ; from main, return addr = r0
   CALL B     ; return addr = r1
      CALL C  ; return addr = r2
      RET     ; from C
      CALL D  ; return addr = r3
      RET     ; from D
   RET        ; from B
RET           ; from A

(b) A BTB predicts targets for indirect branches; the RAS predicts targets for returns. Explain why using the RAS for returns yields far higher accuracy than using the BTB alone for the same returns. (2)

(c) State one scenario in which the RAS itself mispredicts even with correct call/return nesting, and how the recovery is handled. (2)

End of paper.

Answer keyMark scheme & solutions

Question 1 (14 marks)

(a) Pipeline timing table (8 marks)

Issue is in order, one per cycle: I1@1, I2@2, I3@3, I4@4.

Inst	Issue	Exec-start	Exec-complete	Write-back
I1 MUL F0,F2,F4	1	2	7	8
I2 ADD F8,F0,F6	2	9	10	11
I3 SUB F10,F4,F6	3	4	5	6
I4 DIV F12,F0,F8	4	12	23	24

Reasoning (marks: 2 for I1, 2 for I2, 2 for I3, 2 for I4):

I1: operands F2,F4 ready → exec starts cycle 2, 6-cycle MUL completes cycle 7 (2..7), WB cycle 8. No CDB conflict.
I3: operands F4,F6 ready at issue (cycle 3) → exec starts cycle 4, 2-cycle SUB completes cycle 5, WB cycle 6. (WB@6 is free; no conflict with I1@8.)
I2: needs F0 from I1, delivered on CDB at cycle 8 → operand ready end of cycle 8, exec starts cycle 9, completes cycle 10, WB cycle 11.
I4: needs F0 (CDB cy 8) and F8 (from I2, CDB cy 11) → last operand ready end of cy 11, exec starts cy 12, 12-cycle DIV completes cy 23, WB cy 24. No CDB conflict.

(b) RAW resolved via CDB (3 marks)

I1→I2 on F0 (1 mark)
I1→I4 on F0 (1 mark)
I2→I4 on F8 (1 mark) (I3's operands come from the register file, not the CDB.)

(c) Why I3 finishes early safely (3 marks)

I3 is independent (reads F4,F6, both available); Tomasulo dispatches from RS whenever operands ready, independent of program order (1). This is dynamic out-of-order execution.
Program-visible correctness is preserved because in-order commit via the ROB (or, in classic Tomasulo, the register write is tagged/in-order retire) ensures architectural state updates in program order; I3's early completion sits in the ROB until it becomes head (2).

Question 2 (12 marks)

(a) 2-bit counter trace (6 marks)

Start SN(00). Sequence T T N T T N ...

#	actual	state before	predict	correct?	state after
1	T	SN	N	✗	WN
2	T	WN	N	✗	WT
3	N	WT	T	✗	WN
4	T	WN	N	✗	WT
5	T	WT	T	✓	ST
6	N	ST	T	✗	WT
7	T	WT	T	✓	ST
8	T	ST	T	✓	ST
9	N	ST	T	✗	WT
10	T	WT	T	✓	ST
11	T	ST	T	✓	ST
12	N	ST	T	✗	WT

Marks: 3 for correct state trace, 1 for prediction column, 2 for steady-state analysis.

Steady state (from #7 onward the pattern per period is WT→ST→ST for T,T,N): predictions T,T,T vs actual T,T,N → 1 miss per 3 branches = 33.3% steady-state misprediction rate.

(b) Local-history 2-bit-history predictor (4 marks)

History register holds last 2 outcomes; the period-3 pattern produces recurring history contexts: after the pattern stabilises the distinct 2-bit histories seen are TT, TN, NT. Each always maps to the same next outcome:
- history TT → next is N
- history TN → next is T
- history NT → next is T (1 mark for identifying histories)
Since each history context deterministically predicts one outcome, each counter saturates correctly → 0% steady-state mispredictions after warm-up (2 marks). The 2-bit history is sufficient because the pattern period (3) is captured by these three distinct 2-bit contexts (1 mark).

(c) Tournament selection (2 marks)

Meta-predictor should learn to select the local-history predictor (it achieves 0% vs 33% for the simple bimodal) (1 mark).
Opposite selection wins for a branch with no correlation to recent local history but strong bias (e.g., ~95% taken random-ish), where the simple 2-bit bimodal captures the bias and the history predictor wastes/aliases state (1 mark).

Question 3 (12 marks)

(a) Squash on misprediction (4 marks)

Branch B is in ROB1. All entries younger than B (ROB2, ROB3, ROB4, ROB5) are on the mis-speculated taken path and must be squashed (2 marks). ROB0 (older, ADD) and B itself commit/resolve normally.
The STORE in ROB4 "completed execution" only means it computed its address/data; stores write memory only at commit (from the store buffer), and it never reaches commit because it's squashed → no memory corruption (2 marks).

(b) RAT recovery (4 marks)

On misprediction, the RAT (register alias table) must be restored to the state at branch B — via a checkpoint taken at the branch, or by walking the ROB to undo speculative mappings (2 marks).
Speculative renames only update the speculative/frontend RAT; the architectural (retirement) RAT advances only at commit. Keeping them separate means squashed speculative mappings never pollute committed architectural state, so recovery is clean (2 marks).

(c) Spectre channel (4 marks)

The speculative LOAD (ROB2) executes and accesses memory before the branch is resolved; even though architectural state is later squashed, the load's data influenced a subsequent speculative access (e.g., array2[secret*stride]) that brought a secret-dependent line into cache (2 marks).
The leaking resource is the cache (data cache state / cache line residency); squashing rolls back registers/ROB but not the cache, so a later timing probe recovers the secret (2 marks).

Question 4 (12 marks)

(a) VLIW schedule (6 marks)

Slots: MEM | ALU. Load result available 3 cycles after issue (usable in issue cycle+3).

Cycle	MEM slot	ALU slot
1	I1 LOAD R1	NOP
2	I3 LOAD R4	NOP
3	NOP	NOP (R1 ready end cy3, so cannot use until cy4)
4	NOP	I2 ADD R2,R1,R3
5	NOP	I5 ADD R6,R1,R4 (R4 ready from cy2 load)
6	NOP	I4 SUB R5,R4,R2 (needs R2 from cy4)

Total = 6 cycles. (Loads issued back-to-back cy1,cy2; R1 ready cy4, R4 ready cy5→ but issued cy2 so ready by cy5; I2 at cy4 needs R1(cy4 ready)—R1 result available after cycle 3, i.e., readable cy4 ✓; I5 cy5 needs R1,R4 ✓; I4 cy6 needs R4,R2 ✓.)

Marks: 3 for legal slot assignment, 2 for latency handling, 1 for cycle count. (Accept 6 cycles; award full if scheduling respects both slot constraints and load latencies. A tighter 5-cycle schedule is impossible because R4 (loaded cy2) is not available until cy5 and both I4,I5 depend on it → they cannot both go in cy5 with only one ALU slot.)

(b) Superscalar comparison (4 marks)

On this code (already near-optimally orderable), the OoO superscalar can equal the VLIW (6 cycles) because dynamic scheduling discovers the same independent load-issue-then-consume order (2 marks).
Fundamental divergence on other code: the OoO machine schedules using runtime information (actual latencies, cache-miss stalls, unresolved dependences), so it can hide variable-latency events VLIW cannot; conversely VLIW's compiler has whole-program visibility but must schedule for static/assumed latencies and stalls the whole bundle on a surprise (e.g., cache miss) (2 marks).

(c) VLIW commercial difficulty (2 marks) Any one: binary incompatibility across widths (code must be recompiled when issue width/latencies change); poor handling of variable memory latency (whole VLIW stalls on a cache miss); code bloat from NOPs; heavy reliance on compiler that couldn't match dynamic-scheduling performance.

Question 5 (10 marks)

(a) RAS trace (6 marks) — push return addr on CALL, pop on RET. Top-of-stack shown rightmost.

Op	RAS after (bottom→top)	Predicted target on RET	Correct?
CALL A	[r0]	—	—
CALL B	[r0, r1]	—	—
CALL C	[r0, r1, r2]	—	—
RET (C)	[r0, r1] → pop r2	r2	✓
CALL D	[r0, r1, r3]	—	—
RET (D)	[r0, r1] → pop r3	r3	✓
RET (B)	[r0] → pop r1	r1	✓
RET (A)	[] → pop r0	r0	✓

All returns predicted correctly (no mispredictions) because nesting is perfectly balanced and depth ≤ 4 (marks: 4 for correct stack evolution, 2 for identifying zero mispredictions with justification).

(b) RAS vs BTB for returns (2 marks) A given return instruction returns to different addresses depending on the caller; a BTB stores one last-seen target so it mispredicts whenever the caller changes. The RAS matches each return to its own call site's pushed address, giving

#	actual	state before	predict	correct?	state after
1	T	SN	N	✗	WN
2	T	WN	N	✗	WT
3	N	WT	T	✗	WN
4	T	WN	N	✗	WT
5	T	WT	T	✓	ST
6	N	ST	T	✗	WT
7	T	WT	T	✓	ST
8	T	ST	T	✓	ST
9	N	ST	T	✗	WT
10	T	WT	T	✓	ST
11	T	ST	T	✓	ST
12	N	ST	T	✗	WT

#	actual	state before	predict	correct?	state after
1	T	SN	N	✗	WN
2	T	WN	N	✗	WT
3	N	WT	T	✗	WN
4	T	WN	N	✗	WT
5	T	WT	T	✓	ST
6	N	ST	T	✗	WT
7	T	WT	T	✓	ST
8	T	ST	T	✓	ST
9	N	ST	T	✗	WT
10	T	WT	T	✓	ST
11	T	ST	T	✓	ST
12	N	ST	T	✗	WT

#	actual	state before	predict	correct?	state after
1	T	SN	N	✗	WN
2	T	WN	N	✗	WT
3	N	WT	T	✗	WN
4	T	WN	N	✗	WT
5	T	WT	T	✓	ST
6	N	ST	T	✗	WT
7	T	WT	T	✓	ST
8	T	ST	T	✓	ST
9	N	ST	T	✗	WT
10	T	WT	T	✓	ST
11	T	ST	T	✓	ST
12	N	ST	T	✗	WT