Level 5 — MasteryComputer Architecture (Deep)

Computer Architecture (Deep)

⏱ 90 minutes60 marksprintable — key stays hidden on paper

Level 5 — Mastery (cross-domain: math + physics + coding) Time limit: 90 minutes Total marks: 60

Answer all THREE questions. Show all reasoning, derivations, and where required, pseudocode/proofs. Numeric answers must be justified; state units and assumptions.

Question 1 — Cache & Memory Performance Modelling (20 marks)

A single-core RISC-V processor runs with the following memory hierarchy:

L1 cache: 32 KiB, 8-way set associative, 64-byte cache lines, LRU replacement, write-back + write-allocate.
Physical address: 40 bits.
L1 hit time: 1 cycle; L1 miss penalty (to main memory): 100 cycles.

The program executes $N = 10^9$ instructions. Empirically, 35% of instructions are memory-reference instructions (loads/stores). The measured L1 miss rate on memory references is $m$ .

(a) Derive the split of the 40-bit physical address into tag / index / offset fields for the L1 cache. Show the arithmetic for the number of sets and hence the width of each field. (5)

(b) Starting from first principles, derive a closed-form expression for the average memory access time (AMAT) in cycles, then for the CPI contribution from memory stalls $\text{CPI}_{mem}$ , given a base CPI of $1.0$ (ignoring memory stalls) and miss rate $m$ . (4)

(c) If the target is $\text{CPI}_{total} \le 1.5$ , prove the maximum tolerable miss rate $m^\*$ (to 3 significant figures) using your expression from (b). (4)

(d) The architect proposes switching to write-through + no-write-allocate. Assuming stores are 40% of memory references and write-through generates a memory write for every store, discuss quantitatively why this can increase memory traffic even if the read miss rate is unchanged. Give a formula for total memory-write transactions per $10^9$ instructions under each policy (assume write-back writes back a dirty line on eviction with dirty-eviction probability $d = 0.3$ per miss). (4)

(e) Physics cross-over: main memory is 10 cm from the core on the board. Given signal propagation $\approx 2\times10^{8}\,\text{m/s}$ along the trace, compute the round-trip time-of-flight and express it as cycles at 3 GHz. Comment on what fraction of the 100-cycle miss penalty this represents. (3)

Question 2 — Pipelining, Hazards & Speedup Proof (22 marks)

Consider the classic 5-stage MIPS/RISC-V pipeline: IF, ID, EX, MEM, WB. Each stage takes 1 cycle; the pipeline is ideally balanced.

(a) Derive, from first principles, the general formula for the number of cycles to execute $n$ independent instructions in a $k$ -stage pipeline, and hence the speedup over a non-pipelined machine as $n \to \infty$ . State the limiting speedup for this pipeline. (4)

(b) Consider the code fragment (RISC-V):

I1:  lw   x1, 0(x2)
I2:  add  x3, x1, x4
I3:  sub  x5, x3, x1
I4:  sw   x5, 0(x6)

Identify every data hazard, classify each (RAW/WAR/WAW), and name the producing/consuming stages. (4)

(c) Assume full forwarding/bypassing but that a load-use hazard still forces exactly one stall cycle. Draw the pipeline timing diagram (cycle-by-cycle stage occupancy) for I1–I4 and compute the total cycles. Compare against the no-forwarding case (loads and ALU results available only after WB). (6)

(d) A loop containing this fragment iterates $L = 1000$ times and additionally has one conditional branch per iteration. A 2-bit saturating counter predictor is used, starting in Strongly Not Taken. The branch is actually taken on every iteration. Trace the predictor state for the first 4 iterations, and derive the total branch mispredictions over the loop (each misprediction costs a 2-cycle penalty). Compute total branch-penalty cycles. (5)

(e) Prove or disprove: "For a strictly in-order scalar pipeline, forwarding can eliminate all RAW stalls." Give a rigorous argument, using the load-use case as your key example. (3)

Question 3 — Virtual Memory, Coherence & Concurrency (18 marks)

A multicore system uses 48-bit virtual addresses, 40-bit physical addresses, 4 KiB pages, and a single-level... (actually multi-level, but treat conceptually) page table. Each core has a private L1 with the MESI protocol.

(a) Compute the number of page-offset bits, the number of virtual page number (VPN) bits, and the number of physical frame number (PFN) bits. If a single-level page table had one 8-byte entry per virtual page, compute the page table size and explain why multi-level page tables are necessary. (4)

(b) A TLB has a 95% hit rate. TLB hit = 1 cycle; TLB miss requires a page-table walk costing 30 cycles (assume the translation then hits in cache). Derive the average address-translation time. Then combine with a 90%/1-cycle L1 data cache (100-cycle miss) to derive the effective time for a virtually-indexed-physically-tagged access where translation and cache indexing overlap only for the offset portion. State your overlap assumption clearly. (4)

(c) MESI coherence trace. Two cores C0, C1 share variable A (initially in memory, not cached). Execute in order:

1. C0 reads A
2. C1 reads A
3. C0 writes A
4. C1 reads A

For each step, give the MESI state of the line in both C0 and C1 after the operation, and name the bus transaction issued (BusRd, BusRdX, BusUpgr, Flush). (6)

(d) Memory-model proof. Two threads on cores with TSO (store buffers), shared X=Y=0:

Thread A:  X = 1;  r1 = Y;
Thread B:  Y = 1;  r2 = X;

Prove that under sequential consistency the outcome $r1 = 0 \land r2 = 0$ is impossible, but under TSO it is possible. Explain the microarchitectural cause. (4)

Answer keyMark scheme & solutions

Question 1

(a) Address split (5)

Cache size $= 32\,\text{KiB} = 2^{15}$ B. Line size $= 64 = 2^6$ B → offset = 6 bits. (1)
Number of lines $= 2^{15}/2^6 = 2^9 = 512$ lines. (1)
8-way → number of sets $= 512/8 = 64 = 2^6$ → index = 6 bits. (2)
Tag $= 40 - 6 - 6 = \mathbf{28}$ bits. (1)

Layout: | tag 28 | index 6 | offset 6 |.

(b) AMAT & CPI (4)

$\text{AMAT} = t_{hit} + m\cdot t_{penalty} = 1 + 100m$ cycles. (2)
Memory-reference fraction $f = 0.35$ . Stall cycles per instruction $= f\cdot m\cdot t_{penalty} = 0.35\cdot m\cdot 100 = 35m$ . (1)
$\text{CPI}_{mem} = 35m$ ; $\text{CPI}_{total} = 1.0 + 35m$ . (1)

(c) Max miss rate (4) $1.0 + 35m \le 1.5 \Rightarrow 35m \le 0.5 \Rightarrow m^\* = 0.5/35 = 0.01428\ldots$ $\boxed{m^\* \approx 0.0143 = 1.43\%}$ (4; deduct 2 if only inequality set up)

(d) Write policy traffic (4) Let memory references $R = 0.35\times10^9 = 3.5\times10^8$ ; stores $= 0.40R = 1.4\times10^8$ ; misses $= mR$ .

Write-back + write-allocate: memory writes occur only on dirty eviction: $W_{wb} = d\cdot(\text{misses}) = 0.3\, mR$ . (2)
Write-through + no-write-allocate: every store writes memory: $W_{wt} = 0.40R = 1.4\times10^8$ (independent of $m$ ). (1)
Comparison: for small $m$ , $W_{wt} \gg W_{wb}$ (e.g. $m=0.0143$ : $W_{wb}=0.3\cdot0.0143\cdot3.5\times10^8 \approx 1.5\times10^6$ vs $1.4\times10^8$ ) → write-through massively increases write traffic. (1)

(e) Time-of-flight (3)

Round trip distance $= 2\times0.10 = 0.20$ m. $t = 0.20 / (2\times10^8) = 1.0\times10^{-9}$ s $= 1$ ns. (2)
At 3 GHz, cycle $= 1/3\,\text{ns} \approx 0.333$ ns → $1\,\text{ns}/0.333\,\text{ns} = 3$ cycles. This is $3/100 = 3\%$ of the miss penalty — propagation is negligible; the penalty is dominated by DRAM array/controller latency. (1)

Question 2

(a) Pipeline speedup (4)

Cycles for $n$ instructions in $k$ -stage pipeline: fill takes $k$ cycles for first instr, then 1 per instr: $T_{pipe} = k + (n-1)$ cycles. (2)
Non-pipelined: $T_{seq} = n\cdot k$ . Speedup $S = \dfrac{nk}{k+n-1}$ . As $n\to\infty$ , $S\to k$ . (1)
Here $k=5$ → limiting speedup $=\mathbf{5}$ . (1)

(b) Hazards (4)

I1→I2: x1 — RAW (produced by lw in MEM/WB, consumed by add in EX). (1)
I2→I3: x3 — RAW (add EX result → sub EX). (1)
I1→I3: x1 — RAW (still live). (1)
I3→I4: x5 — RAW (sub result → sw for store data in MEM). (1) (No WAR/WAW in in-order scalar with single write port — award note.)

(c) Timing (6) With forwarding, only I1(lw)→I2(add) is a load-use hazard needing 1 stall.

Cycle:    1    2    3    4    5    6    7    8    9
I1 lw:   IF   ID   EX   MEM  WB
I2 add:       IF   ID   **   EX   MEM  WB      (stall in cyc4, fwd from MEM)
I3 sub:            IF   **   ID   EX   MEM  WB
I4 sw:                       IF   ID   EX   MEM  WB

Total = 9 cycles (with forwarding + 1 load-use stall). (3)

No-forwarding: results available only after WB → each dependent instr stalls until producer's WB. I2 must wait for I1 WB (cyc5), I3 for I2 WB, etc. This inserts ~2 stalls per RAW dependence; total ≈ 13–15 cycles (accept a correct fully-drawn diagram; ~14). (3)

(d) 2-bit predictor (5) States: 00 SNT, 01 WNT, 10 WT, 11 ST. Start 00. Actual = Taken each time.

Iter1: predict NT → mispredict; update toward taken 00→01. (1)
Iter2: state 01 predict NT → mispredict; 01→10. (1)
Iter3: state 10 predict Taken → correct; 10→11.
Iter4: state 11 predict Taken → correct; stays 11. (1)
Total mispredictions = 2 (iterations 1 and 2 only; correct thereafter). (1)
Penalty cycles $= 2\times2 = \mathbf{4}$ cycles over the 1000-iteration loop. (1)

(e) Proof — forwarding cannot remove all RAW stalls (3) Disproven. Consider load-use: a lw produces its result at the end of MEM (cycle 4), but the dependent instruction needs the operand at the start of its EX (cycle 4). Since the value is not available until MEM completes and EX begins simultaneously, no forwarding path can supply it in time — the consumer must be delayed by ≥1 cycle. Forwarding removes ALU→ALU (EX→EX) stalls because the producer finishes EX one cycle before the consumer needs it, but it cannot beat the load's inherent 1-cycle result latency. Hence forwarding eliminates most but not all RAW stalls. ∎ (3)

Question 3

(a) VM sizing (4)

Page 4 KiB $=2^{12}$ → offset = 12 bits. (1)
VPN $= 48-12 = \mathbf{36}$ bits; PFN $= 40-12 = \mathbf{28}$ bits. (1)
Single-level PT size $= 2^{36}$ entries $\times 8$ B $= 2^{39}$ B $= \mathbf{512\ GiB}$ per process. (1)
Impossibly large & mostly unused → multi-level (or inverted/hashed) tables allocate only needed sub-tables, saving memory. (1)

(b) Translation + access time (4)

Avg translation $= 0.95\times1 + 0.05\times(1+30) = 0.95 + 1.55 = \mathbf{2.5}$ cycles. (Or $1 + 0.05\times30 = 2.5$ .) (2)
Overlap assumption: with VIPT, cache indexing uses offset bits available immediately, so index lookup overlaps translation; only tag compare waits for the PFN. Effective time $\approx \max(t_{trans}, t_{index}) + \text{tag compare} + \text{miss}$ . Taking translation ≈2.5 cy overlapping cache access, effective ≈ $2.5 + 0.10\times100 = 2.5 + 10 = \mathbf{12.5}$ cycles (accept reasoned variants stating assumption). (2)

(c) MESI trace (6) — 1.5 marks each

Step	Bus txn	C0 state	C1 state
1. C0 read A	BusRd	E (Exclusive)	I
2. C1 read A	BusRd (C0 snoops, supplies)	S	S
3. C0 write A	BusUpgr	M	I (invalidated)
4. C1 read A	BusRd (C0 Flush, →memory)	S	S

(Award per-line correctness; BusUpgr acceptable as BusRdX if line re-fetched.)

(d) Memory-model proof (4)

Under SC, there is a single total order of all memory ops consistent with program order. Suppose $r1=0$ and $r2=0$ . $r1=0$ means A's load of Y precedes B's store Y=1. $r2=0$ means B's load of X precedes A's store X=1. But program order requires X=1 before r1=Y (in A) and Y=1 before r2=X (in B). Chaining: $X{=}1 <_p r1{=}Y < Y{=}1 <_p r2{=}X < X{=}1$ — a cycle, contradiction. So $r1=r2=0$ is impossible under SC. (2)
Under TSO, each core has a FIFO store buffer. X=1 and Y=1 can sit in the buffers while the loads r1=Y, r2=X read the (still 0) values from memory/other core before the stores drain. Store→load reordering (a store's effect delayed relative to a later load in the same thread) is permitted → both loads see 0. Hence $r1=r2=0$ is possible. Microarchitectural cause: store buffering allows a load to bypass an earlier store to a different address. (2)

[
{"claim":"L1 tag field is 28 bits for 32KiB 8-way 64B-line, 40-bit PA","code":"cache=2**15; line=64; ways=8; lines=cache//line; sets=lines//ways; offset=15- (15) ; import math; offset_bits=int(math.log2(line)); index_bits=int(math.log2(sets)); tag=40-offset_bits-index_bits; result = (offset_bits==6 and index_bits==6 and tag==28)"},
{"