Memory Hierarchy & Caches

Question 1

(a) Capacity $= 32\,\text{KiB} = 2^{15}$ bytes. Line $= 64 = 2^6$ B ⇒ offset = 6 bits. (1) Number of lines $= 2^{15}/2^6 = 2^9 = 512$. (1) 4-way ⇒ number of sets $= 512/4 = 128 = 2^7$ ⇒ index = 7 bits. (2) Tag $= 40 - 7 - 6 = 27$ bits. (2)

(b) 1 MiB $= 2^{20}$ B ⇒ number of lines touched $= 2^{20}/2^6 = 2^{14} = 16384$. (1) Sequential streaming touches each line once; only the first access to each new line misses (compulsory). So misses = 16384, one per line. (1) Accesses = 16384 line-first accesses only? No — misses counted per line access. With one access per byte the hits come from spatial locality within a line: each 64-byte line has 64 accesses, 1 miss + 63 hits. Misses $= 16384$, total accesses $= 2^{20} = 1048576$. Hit rate $= 1 - 16384/1048576 = 1 - 1/64 = 63/64 \approx 98.44\%$. (1) All misses are compulsory (cold) — data never seen before; array (1 MiB) fits/streams without reuse so no capacity/conflict reuse effect. (1)

(c) No difference. Sequential first-touch traversal produces exactly the compulsory misses regardless of associativity — each line is loaded once and never re-referenced, so conflict misses cannot arise. Same 16384 misses. (2)

Question 2

(a) Global miss rate = product of local miss rates down the chain.

• L1 miss (global) = 8% = 0.08
• L2 global = $0.08 \times 0.25 = 0.02$ (2%) (1.5)
• L3 global = $0.02 \times 0.40 = 0.008$ (0.8%) (1.5)

(b) AMAT (in cycles), using local-miss-rate hierarchical form: $\text{AMAT} = t_{L1} + m_{L1}\big[t_{L2} + m_{L2}(t_{L3} + m_{L3}\cdot t_{mem})\big]$ (1) Inner: $t_{L3} + m_{L3} t_{mem} = 40 + 0.4(200) = 40 + 80 = 120$. (1) Next: $t_{L2} + m_{L2}(120) = 12 + 0.25(120) = 12 + 30 = 42$. (1) Outer: $1 + 0.08(42) = 1 + 3.36 = 4.36$ cycles. (2)

(c) New: $t_{L2}=16$, $m_{L2}=0.15$. Next level: $16 + 0.15(120) = 16 + 18 = 34$. (1) Outer: $1 + 0.08(34) = 1 + 2.72 = 3.72$ cycles. (2) Improvement $= 4.36 - 3.72 = 0.64$ cycles. Redesign reduces AMAT by 0.64 cycles — worthwhile. (1)

(d) L1 hit time is on the critical path of every memory reference and often sets the CPU clock period; a smaller/faster L1 (even with a slightly higher miss rate) can allow a higher clock frequency or shorter pipeline, and the modest extra misses are absorbed by a fast L2. (2)

Question 3

Cache = 4 lines, stream: 1 2 3 4 1 2 5 1 2 3 4 5

(a) LRU (MRU listed rightmost, evict leftmost):

LRU hits = 4. (4)

(b) FIFO (evict oldest-inserted):

FIFO hits = 2. (4)

(c) Bélády's anomaly: under FIFO (and some non-stack policies) increasing the number of cache/frame slots can increase the number of misses rather than reduce it — miss count is not monotonic in cache size. (This classic stream is the standard example.) (2)

Question 4

Total ops = 1000; reads = 700, writes = 300. Read misses $= 700 \times 0.10 = 70$. Write misses $= 300 \times 0.20 = 60$. (1 — setup)

(a) Write-through + no-write-allocate:

• Read misses fetch a line: $70 \times 64 = 4480$ B. (1.5)
• No-write-allocate: write misses do not fetch; writes go straight through.
• Every write (hit or miss) writes 4 B through to memory: $300 \times 4 = 1200$ B. (1.5)
• Read hits/misses cause no writeback (clean). Total $= 4480 + 1200 = 5680$ bytes. (1)

(b) Write-back + write-allocate:

• Every miss (read or write) fetches a line: total misses $= 70 + 60 = 130$. Refill traffic $= 130 \times 64 = 8320$ B. (2)
• Dirty evictions $= 30\%$ of misses $= 0.30 \times 130 = 39$ writebacks. Writeback traffic $= 39 \times 64 = 2496$ B. (2) Total $= 8320 + 2496 = 10816$ bytes. (1)

(c) Any one: multiprocessor/coherence scenarios where memory (or other caches) must always see up-to-date data; simpler coherence; DMA/I/O consistency; write-through avoids the dirty-line tracking and coherence complexity — preferable when data must stay consistent with memory or when write bandwidth is not the bottleneck. (2)

Question 5

(a) Offset for 4 KiB page $= \log_2 4096 = 12$ bits. (1) Remaining VA bits for indexing $= 48 - 12 = 36$ bits across 4 levels. (1) Per level $= 36/4 = 9$ bits. (1) (Check: each table has $2^9 = 512$ entries $\times 8$ B $= 4096$ B $=$ one page — consistent.) (1)

(b)

• TLB hit (98%): 1 (translation) + 1 (data) = 2 cycles. (1)
• TLB miss (2%): 4 levels $\times$ 3 = 12 cycles walk + 1 (data) = 13 cycles. (Include TLB probe 1 cycle before miss detected → 14; here take walk+data = 13 as the miss path cost; if TLB probe added, 14. Accept either with consistent statement.) (2) Using 13: Average $= 0.98(2) + 0.02(13) = 1.96 + 0.26 = 2.22$ cycles. (2)

(If the 1-cycle initial TLB probe is added to the miss path (14): $0.98(2)+0.02(14)=1.96+0.28=2.24$. Full marks for either consistent method.)

(c) TLB reach = (number of TLB entries) × (page size). Larger pages mean each TLB entry maps more memory, so a fixed-size TLB covers more of the working set ⇒ fewer TLB misses. Cost: internal fragmentation (wasted space within partially-used large pages) — also coarser protection/paging granularity and larger I/O on page faults. (3)

[
  {"claim":"Q1 tag width = 27 bits","code":"offset=6; index=7; tag=40-index-offset; result=(tag==27)"},
  {"claim":"Q1 hit rate = 63/64","code":"misses=2**14; acc=2**20; hr=1-Rational(misses,acc); result=(hr==Rational(63,64))"},
  {"claim":"Q2 baseline AMAT = 4.36 cycles","code":"inner=40+Rational(4,10)*200; mid=12+Rational(25,100)*inner; amat=1+Rational(8,100)*mid; result=(amat==Rational(436,100))"},
  {"claim":"Q2 redesign AMAT = 3.72 and improvement 0.64","code":"mid=16+Rational(15,100)*120; amat=1+Rational(8,100)*mid; result=(amat==Rational(372,100) and Rational(436,100)-amat==Rational(64,100))"},
  {"claim":"Q4a write-through no-allocate = 5680 bytes","code":"rm=700*Rational(10,100); total=rm*64+300*4; result=(total==5680)"},
  {"claim":"Q4b write-back write-allocate = 10816 bytes","code":"misses=70+60; refill=misses*64; wb=Rational(30,100)*misses*64; result=(refill+wb==10816)"},
  {"claim":"Q5b average latency = 2.22 cycles (13-cycle miss path)","code":"avg=Rational(98,100)*2+Rational(2,100)*13; result=(avg==Rational(222,100))"}
]