Memory Hierarchy & Caches

Question 1 (10 marks)

(a) Capacity $= 32\text{ KiB} = 32768$ B. Line size $= 64$ B.

• Offset bits: $\log_2 64 = 6$ bits. (1)
• Number of lines $= 32768 / 64 = 512$ lines. (1)
• 4-way: number of sets $= 512 / 4 = 128$ sets. (1)
• Index bits: $\log_2 128 = 7$ bits. (1)
• Tag bits $= 32 - 7 - 6 = 19$ bits. (2)

Why: offset selects a byte within a line, index selects a set, tag disambiguates lines mapping to the same set.

(b) Per line overhead $= \text{tag} + \text{valid} + \text{dirty} = 19 + 1 + 1 = 21$ bits. (2) Total lines $= 512$. Overhead $= 512 \times 21 = 10752$ bits $= 1344$ B. (2)

Question 2 (12 marks)

(a) Local miss rate $=$ misses at that level / accesses that reach that level. Global $=$ misses / total CPU accesses. For two levels: (2) $\text{AMAT} = t_{L1} + m_{L1}\,(t_{L2} + m_{L2}\,t_{mem})$ where $m_{L2}$ is the local L2 miss rate. (2)

(b) $\text{AMAT} = 1 + 0.08(12 + 0.25\times200) = 1 + 0.08(12+50) = 1 + 0.08\times62 = 1 + 4.96 = 5.96$ cycles. (4)

(c) New: $1 + 0.10(10 + 0.25\times200) = 1 + 0.10(10+50) = 1 + 0.10\times60 = 1 + 6.0 = 7.0$ cycles. (3) $7.0 > 5.96$ → not an improvement; the higher L1 miss rate dominates the small L2 hit-time gain. (1)

Question 3 (10 marks)

Stream: 1 2 3 4 1 2 5 1 2 3 4 5

(a) LRU (4 lines): (4 for trace, 1 for count)

Hits = 4, Misses = 8.

(b) FIFO (queue order = insertion): (4 for trace, 1 for count/comment)

Hits = 2, Misses = 10.

Comment: LRU beats FIFO here because it keeps recently-reused blocks (1,2); FIFO evicts by age regardless of reuse, so it discards still-hot blocks. (1)

Question 4 (8 marks)

(a) (5)

• Write-through, no-write-allocate: every write updates memory immediately. On a write miss, the block is not loaded into cache — write goes straight to memory. Simpler, always consistent with memory, but high write traffic. (3)
• Write-back, write-allocate: writes update only the cache line and set a dirty bit; the block is written to memory only on eviction. On a write miss, the block is loaded (allocated) into cache, then written. Lower traffic, needs dirty tracking. (2)

(b) Write-back + write-allocate. Repeated writes to the same block are absorbed in the cache line; memory is touched only once on eventual eviction, minimising traffic. (3)

Question 5 (12 marks)

(9) for table:

(Award ~1.8 per correctly reasoned step.)

MOESI Owned state (3): The O state lets a cache hold a modified-but-shared line (dirty, but other caches may hold read copies in S). It solves the problem that in MESI a dirty line must be written back to memory before it can be shared; O allows the owner to supply dirty data directly to other caches without a write-back, reducing memory traffic. (3)

Question 6 (8 marks)

(a) Page offset $= \log_2 4096 = 12$ bits. (1) VPN bits $= 48 - 12 = 36$ bits over 4 levels $\Rightarrow 36/4 = 9$ bits per level. (2) Entries per node $= 2^9 = 512$; each entry 8 B $\Rightarrow 512 \times 8 = 4096$ B $= 4$ KiB $=$ one page. ✓ (2)

(b) The TLB caches recent virtual→physical page translations so the multi-level page-table walk is skipped on a hit. (1) Effective translation time $= 0.98\times1 + 0.02\times100 = 0.98 + 2.0 = 2.98$ cycles. (2)

[
  {"claim":"Q1 tag bits = 19", "code":"offset=6; index=7; tag=32-offset-index; result = (tag==19)"},
  {"claim":"Q1 total overhead = 10752 bits", "code":"lines=512; per=19+1+1; result = (lines*per==10752)"},
  {"claim":"Q2b AMAT = 5.96", "code":"amat=1+0.08*(12+0.25*200); result = (abs(amat-5.96)<1e-9)"},
  {"claim":"Q2c AMAT = 7.0 (worse)", "code":"a=1+0.10*(10+0.25*200); result = (abs(a-7.0)<1e-9 and a>5.96)"},
  {"claim":"Q6 index bits per level = 9 and node fits page", "code":"vpn=48-12; per=vpn/4; entries=2**per; result = (per==9 and entries*8==4096)"},
  {"claim":"Q6 effective translation = 2.98 cycles", "code":"t=0.98*1+0.02*100; result = (abs(t-2.98)<1e-9)"}
]