Cache Memory Questions

Introduction

Cache memory questions are the bread and butter of computer architecture exams. They appear in GATE every single year, in university end-sems, and in hardware interviews. The good news is that once you master the systematic approach — breaking addresses into tag/index/offset, tracing accesses through the cache, and applying the AMAT formula — these problems become mechanical. This page drills you through every important cache question pattern with detailed solutions.

Question Type 1: Address Bit Breakdown

Q1: Direct-Mapped Cache Address Decomposition

Problem: A computer has 24-bit addresses, a direct-mapped cache of 16 KB with 64-byte blocks. Find: (a) number of cache lines, (b) number of tag, index, and offset bits, (c) total cache memory including tags and valid bits.

Solution:

Q2: Set-Associative Cache

Problem: A 4-way set-associative cache has total size 32 KB, block size 32 bytes, and the processor uses 32-bit addresses. Find the number of sets, tag bits, and total comparators needed.

Solution:

Question Type 2: Hit/Miss Trace

Q3: Trace Direct-Mapped Cache Accesses

Problem: A direct-mapped cache has 4 lines, block size 1 word. Trace accesses to block addresses: 0, 8, 0, 6, 8, 2, 0, 14, 6, 8. Determine hits and misses.

Solution:

Cache line = Block_address mod Number_of_lines = Block_address mod 4

Hit rate = 0/10 = 0%! This is a pathological case — blocks 0 and 8 both map to line 0, causing thrashing. A 2-way set-associative cache would fix this.

Q4: Same trace with 2-way set-associative

Problem: Same access sequence with 2-way set-associative cache (2 sets, 2 lines each). LRU replacement.

Solution:

Set = Block_address mod 2

Hit rate = 1/10 = 10%. Still poor because working set (5 blocks mapping to set 0) > set capacity (2).

Question Type 3: AMAT Calculations

Q5: Multi-level cache AMAT

Problem: A processor has:

• L1: 2 ns access, 8% miss rate
• L2: 15 ns access, 25% miss rate (of L1 misses)
• L3: 40 ns access, 10% miss rate (of L2 misses)
• Main memory: 200 ns

Calculate AMAT and effective CPI (assuming 1 GHz clock and base CPI of 1 with 1.5 memory accesses per instruction).

Solution:

Q6: Cache design trade-off

Problem: You can choose between: (A) 32 KB direct-mapped with 5% miss rate, 1-cycle access, or (B) 32 KB 4-way set-associative with 3% miss rate, 2-cycle access. Miss penalty is 100 cycles. Which is better?

Solution:

The 2% miss rate reduction saves more than the 1-cycle extra hit time costs. This is why real L1 caches are set-associative despite the latency penalty.

Question Type 4: Write Policy Questions

Q7: Write-back vs Write-through traffic

Problem: A program performs 1000 memory accesses: 700 reads, 300 writes. Cache has 80% write hit rate. Block size is 64 bytes. Compare memory bus traffic for write-through vs write-back.

Solution:

Write-back reduces memory bus traffic significantly, which is why modern caches use it despite the complexity of tracking dirty bits.

Question Type 5: Spatial and Temporal Locality

Q8: Block size impact

Problem: A cache with 1024 bytes total capacity. Compare miss rates for block sizes of 16, 32, 64, and 128 bytes for sequential array access of 4096 bytes.

Solution:

Larger blocks exploit spatial locality better (fewer compulsory misses) but reduce the number of cache lines (more capacity misses). The optimal block size balances these factors — typically 32-64 bytes for L1 caches.

Question Type 6: Cache Coherence

Q9: Multi-core cache coherence

Problem: Two cores share memory location X. Core 1 reads X, Core 2 reads X, Core 1 writes X. Explain what happens under MESI protocol.

Solution:

Practice Problems

1. A 64 KB, 4-way cache with 128-byte blocks uses 48-bit addresses. How many bits for tag, index, offset?
2. Calculate AMAT for: L1 hit=1ns (miss rate 4%), L2 hit=8ns (miss rate 15%), Memory=80ns
3. Trace block addresses 1, 4, 1, 8, 4, 1, 8 through 2-line fully associative cache with LRU
4. If doubling cache size reduces miss rate from 5% to 3.5%, and miss penalty is 50 cycles, is it worth the extra 1-cycle hit time?

Key Takeaways

1. Always decompose addresses into Tag | Index | Offset — this is the foundation of all cache problems
2. Direct-mapped conflict misses are eliminated by increasing associativity (at cost of hit time)
3. AMAT formula nests recursively for multi-level caches — each level's miss penalty includes the next level's AMAT
4. Larger blocks reduce compulsory misses (spatial locality) but may increase capacity misses (fewer lines)
5. Write-back reduces traffic but adds complexity; write-through is simpler but generates more bus traffic
6. Working set size relative to cache size determines whether capacity misses dominate performance