Level 1 — RecognitionMemory Hierarchy & Caches

Memory Hierarchy & Caches

⏱ 20 minutes40 marksprintable — key stays hidden on paper

Chapter: 5.4 Memory Hierarchy & Caches Difficulty Level: 1 (Recognition) Time Limit: 20 minutes Total Marks: 40

Section A — Multiple Choice (1 mark each) — 10 marks

Q1. Reusing the same memory location repeatedly over a short time span is an example of:

(a) Spatial locality
(b) Temporal locality
(c) Conflict miss
(d) Write allocation

Q2. In a direct-mapped cache, each memory block can be placed in:

(a) Any cache line
(b) Exactly one cache line
(c) Any line within one set
(d) The least-recently-used line

Q3. A 32-bit address, a cache with 64-byte blocks — how many bits are used for the block offset?

(a) 5
(b) 6
(c) 7
(d) 8

Q4. Which write policy updates both cache and main memory on every write?

(a) Write-back
(b) Write-allocate
(c) Write-through
(d) No-allocate

Q5. A miss that occurs on the very first access to a block, unavoidable regardless of cache size, is a:

(a) Capacity miss
(b) Conflict miss
(c) Compulsory miss
(d) Coherence miss

Q6. The AMAT formula is:

(a) $\text{Hit time} + \text{Miss rate} \times \text{Miss penalty}$
(b) $\text{Hit time} \times \text{Miss rate} + \text{Miss penalty}$
(c) $\text{Miss rate} \times \text{Hit time} + \text{Miss penalty}$
(d) $\text{Hit time} - \text{Miss rate} \times \text{Miss penalty}$

Q7. The TLB is a cache for:

(a) Recently used data blocks
(b) Recently used instructions
(c) Virtual-to-physical address translations
(d) Replacement policy metadata

Q8. In the MESI protocol, which state means the line is clean and may exist in other caches?

(a) Modified
(b) Exclusive
(c) Shared
(d) Invalid

Q9. In a fully associative cache, the number of sets is:

(a) Equal to the number of lines
(b) One
(c) Two
(d) Equal to block size

Q10. Fetching data before it is explicitly requested, to hide latency, is called:

(a) Write-back
(b) Prefetching
(c) Snooping
(d) Paging

Section B — Matching (2 marks each) — 12 marks

Q11. Match each cache miss/term to its description.

Term		Description
A. Compulsory miss		1. Line evicted then re-referenced due to limited set capacity
B. Capacity miss		2. First-ever reference to a block
C. Conflict miss		3. Working set larger than the whole cache

Q12. Match each replacement policy to its rule.

Policy		Rule
A. LRU		1. Evict the block loaded earliest
B. FIFO		2. Evict the block unused for the longest time
C. Random		3. Evict an arbitrary block

Q13. Match each cache level to its typical characteristic.

Level		Characteristic
A. L1		1. Largest, slowest, often shared by all cores
B. L2		2. Smallest, fastest, per-core
C. L3		3. Intermediate size and speed

Section C — True/False WITH Justification (3 marks each: 1 T/F + 2 justification) — 18 marks

Q14. Increasing cache line size always reduces the miss rate. (T/F + justify)

Q15. A write-back cache with write-allocate loads a block into the cache on a write miss. (T/F + justify)

Q16. Increasing associativity from direct-mapped to fully associative eliminates all conflict misses. (T/F + justify)

Q17. A multi-level page table saves memory compared to a single flat page table for sparse address spaces. (T/F + justify)

Q18. Sequential consistency allows the hardware to reorder any memory operations freely as long as each processor's program order is preserved in the final result. (T/F + justify)

Q19. In MESI, a cache line in the Modified state must be written back to memory (or supplied) before another core can read it. (T/F + justify)

Answer keyMark scheme & solutions

Section A (1 mark each)

Q1 — (b) Temporal locality. Repeated reuse of the same location over time = temporal; nearby-address reuse = spatial.

Q2 — (b) Exactly one cache line. Direct-mapped: block maps to a unique line via index = block# mod #lines.

Q3 — (b) 6. Offset bits $=\log_2(64)=6$ . Why: 64 = $2^6$ bytes per block.

Q4 — (c) Write-through. Writes propagate to memory immediately, keeping memory always up-to-date.

Q5 — (c) Compulsory miss. Cold/first-reference miss; independent of size or associativity.

Q6 — (a) $\text{AMAT}=\text{Hit time}+\text{Miss rate}\times\text{Miss penalty}$ .

Q7 — (c) Virtual-to-physical translations. TLB caches recent page-table entries.

Q8 — (c) Shared. Clean, possibly present in other caches. Exclusive = clean but sole copy.

Q9 — (b) One. Fully associative = a single set containing all lines.

Q10 — (b) Prefetching.

Section B (2 marks each — 1 per correct pair, capped at 2)

Q11: A→2, B→3, C→1. Why: Compulsory = first reference; capacity = working set exceeds cache; conflict = eviction from a specific set despite free space elsewhere.

Q12: A→2, B→1, C→3.

Q13: A→2, B→3, C→1. Why: Speed/size tradeoff increases from L1 (fast/small/private) to L3 (slow/large/shared).

Section C (3 marks: 1 T/F + 2 justification)

Q14 — FALSE. (1) Larger lines exploit spatial locality up to a point, but (2) beyond an optimum they waste bandwidth on unused data and, for fixed cache size, reduce the number of lines → more conflict/capacity misses (higher miss rate). So the relationship is U-shaped, not monotonic.

Q15 — TRUE. (1) Write-allocate means a write miss fetches the block into the cache; (2) this pairs naturally with write-back, where the modified block is later written to memory on eviction — allowing subsequent writes to hit in cache.

Q16 — TRUE. (1) Conflict misses arise because multiple blocks map to the same set; (2) fully associative has one set, so no block is ever evicted due to set contention — only compulsory and capacity misses remain.

Q17 — TRUE. (1) A flat table needs one entry per virtual page even for unused regions; (2) multi-level tables allocate lower-level tables only for regions that are actually used, so unmapped portions of a sparse address space cost no page-table storage.

Q18 — FALSE. (1) Sequential consistency requires operations to appear in program order for each processor and a single global interleaving; (2) it does not permit free reordering — the more relaxed models (e.g. TSO, weak ordering) allow that. SC is restrictive.

Q19 — TRUE. (1) Modified means this cache holds the only valid, dirty copy; (2) on a remote read request the owning cache must supply/write back the data so the reader gets current values and coherence is preserved (M→S transition).

[
  {"claim":"Q3: offset bits for 64-byte block = 6","code":"result = (log(64,2)==6)"},
  {"claim":"Q6 AMAT: with hit=1, miss_rate=0.05, penalty=100 gives AMAT=6","code":"hit=1; mr=Rational(5,100); pen=100; result = (hit+mr*pen==6)"},
  {"claim":"Fully associative 32KB cache with 64B lines has 512 lines in 1 set","code":"lines=(32*1024)//64; result = (lines==512)"},
  {"claim":"Direct-mapped index bits for 256 lines = 8","code":"result = (log(256,2)==8)"}
]