Memory Hierarchy & Caches

Q1 (4 marks)

• Temporal locality (1): if a memory location is accessed, it is likely to be accessed again soon. Example (1): a loop counter / repeatedly used variable, instructions in a loop.
• Spatial locality (1): if a location is accessed, nearby locations are likely to be accessed soon. Example (1): sequential array traversal, sequential instruction fetch.

Q2 (6 marks)

• Number of lines = cache size / line size = $16\text{KB}/32 = 16384/32 = 512$ lines. (2)
• Index bits = $\log_2 512 = 9$ bits. (1)
• Block-offset bits = $\log_2 32 = 5$ bits. (1)
• Tag bits = $32 - 9 - 5 = 18$ bits. (2)

Why: offset selects a byte within a line, index selects the line, remaining high-order bits are the tag.

Q3 (6 marks) (2 each)

• Compulsory (cold) miss: first-ever reference to a block; unavoidable regardless of cache size.
• Capacity miss: cache cannot hold all blocks of the working set; occurs even with full associativity.
• Conflict (collision) miss: multiple blocks map to the same set and evict each other; would not occur in a fully associative cache of equal size.

Q4 (4 marks)

• Write-through: (a) memory updated on every write, immediately. (b) Advantage: simpler, memory always consistent / easier coherence. (2)
• Write-back: (a) memory updated only when a dirty line is evicted. (b) Advantage: fewer memory writes / lower bandwidth. (2)

Q5 (5 marks) AMAT = hit time + miss rate × miss penalty. (a) $2 + 0.05 \times 100 = 2 + 5 = \mathbf{7\ ns}$. (2) (b) $2 + 0.025 \times 100 = 2 + 2.5 = \mathbf{4.5\ ns}$. (2) Improvement = $7 - 4.5 = \mathbf{2.5\ ns}$. (1)

Q6 (6 marks) LRU, 2 ways. (MRU listed first.)

Total misses = 5 (1 hit). (mark: 0.5–1 per correct row + 1 for total)

Q7 (4 marks)

• Write-allocate: on a write miss, the block is loaded into the cache first, then written. (1.5)
• No-write-allocate: on a write miss, the write goes directly to memory; the block is not brought into the cache. (1.5)
• Pairing: write-allocate is normally paired with write-back, because subsequent writes to the same block hit in cache and are absorbed (accumulated) before a single write-back, exploiting locality. (1)

Q8 (5 marks) AMAT (from L1) = L1 hit + L1 miss rate × (L2 hit + L2 miss rate × mem). $= 1 + 0.10 \times (10 + 0.20 \times 100)$ $= 1 + 0.10 \times (10 + 20)$ $= 1 + 0.10 \times 30$ $= 1 + 3 = \mathbf{4\ ns}$. (5)

Q9 (6 marks) (1.5 each)

• Modified (M): dirty = yes; other copies = no (exclusive, owner must write back).
• Exclusive (E): dirty = no (clean); other copies = no.
• Shared (S): dirty = no (clean); other copies = yes (may exist).
• Invalid (I): line holds no valid data.

Q10 (4 marks)

• TLB (Translation Lookaside Buffer): a small, fast cache of recent virtual-to-physical page-number translations (page-table entries). (2)
• Why faster: avoids walking the page table in memory on every access; a TLB hit provides the physical frame in ~1 cycle. (1)
• On a TLB miss: the page table is walked (by hardware or OS) to fetch the translation, which is then inserted into the TLB. (1)

[
  {"claim":"Q2 tag bits = 18","code":"lines=16*1024//32; index=int(__import__('math').log2(lines)); offset=int(__import__('math').log2(32)); tag=32-index-offset; result = (lines==512 and index==9 and offset==5 and tag==18)"},
  {"claim":"Q5 AMAT values 7 and 4.5, improvement 2.5","code":"a=2+0.05*100; b=2+0.025*100; result = (a==7 and b==4.5 and (a-b)==2.5)"},
  {"claim":"Q8 two-level AMAT = 4 ns","code":"amat=1+0.10*(10+0.20*100); result = (amat==4)"},
  {"claim":"Q6 total misses = 5","code":"seq=['A','B','A','C','B','A']; cache=[]; misses=0\nfor x in seq:\n    if x in cache:\n        cache.remove(x); cache.insert(0,x)\n    else:\n        misses+=1\n        if len(cache)>=2: cache.pop()\n        cache.insert(0,x)\nresult = (misses==5)"}
]