Questions: Cache Memory Design

Question 1

A program alternately accesses two arrays. Both arrays' base addresses happen to differ by exactly the cache size, so they map to the same cache lines. Performance is poor despite the working set fitting in cache. What type of miss is causing this?

• A. Compulsory miss — the data is accessed for the first time on each iteration
• B. Capacity miss — the combined working set is too large for the cache
• C. Conflict miss — the two arrays compete for the same cache lines, evicting each other
• D. Write miss — the cache write policy is causing repeated flushes

Answer: (C)

This is a conflict miss, the characteristic failure mode of direct-mapped caches. Each memory block maps to exactly one cache line (determined by address mod cache size). When two frequently accessed blocks map to the same line, each access evicts the other — even though the cache has many empty lines elsewhere. The working set fits in the cache; the problem is the rigid mapping. This is why set-associative design exists: allowing each block to reside in any of N ways within its set dramatically reduces conflict misses.

Question 2

Why are fully associative caches not used for large L1 caches, even though they eliminate all conflict misses?

• A. Fully associative caches have higher miss rates than set-associative caches
• B. Every cache access requires comparing the address tag against every line simultaneously, requiring parallel comparator hardware for each line — too expensive at scale
• C. Fully associative caches are incompatible with modern processor pipeline designs
• D. The replacement policy for fully associative caches is too slow to implement in hardware

Answer: (B)

In a fully associative cache, any block can reside in any line. To determine if a given address is cached, the hardware must check every line at once (a hit anywhere counts). This requires a parallel comparator for each cache line — hardware that grows linearly with cache size. For a small structure like a TLB with 32–64 entries this is feasible, but for an L1 cache with thousands of lines, the area and power cost is prohibitive. Set-associative design limits the parallel search to just N ways within the relevant set — manageable even for modern caches.

Question 3

Increasing cache size from 32KB to 256KB will eliminate compulsory (cold) misses on the first access to each memory block.

• T. True
• F. False

Answer: False

Compulsory misses occur on the very first access to any block — the data has never been in the cache before, so a miss is unavoidable regardless of cache size or associativity. Even an infinitely large cache would still incur a compulsory miss the first time each address is referenced. Cache size reduces capacity misses (where the working set exceeds the cache). Associativity reduces conflict misses. Neither can eliminate compulsory misses, though prefetching can hide their latency by fetching data before it is demanded.

Question 4

A cold (compulsory) miss occurs on the first access to a memory block and cannot be eliminated by increasing cache size or associativity.

• T. True
• F. False

Answer: True

Compulsory misses are unavoidable because they represent data that has genuinely never been in the cache. No matter how large or how associative the cache, the first time you access a block it will be a miss — there is nothing to hit. The three-C miss taxonomy (Compulsory, Capacity, Conflict) is precisely useful because it separates what you can fix (capacity misses with more cache, conflict misses with more associativity) from what you fundamentally cannot (compulsory misses, short of prefetching).

Question 5

Explain the conflict miss problem in direct-mapped caches and describe how set-associative design alleviates it.

Model answer: In a direct-mapped cache, each memory address maps to exactly one cache line (by the index bits). If two frequently accessed blocks share the same index — because their addresses differ by a multiple of the cache size — each access evicts the other, causing repeated misses even when most of the cache is empty. Set-associative design places multiple ways in each set, so a block can occupy any of N lines within its set. This means N blocks with the same index can coexist in cache simultaneously, dramatically reducing conflict evictions.

The direct-mapped conflict problem is deterministic and reproducible — it happens whenever two hot addresses are congruent modulo the cache size. With 4-way set associativity, you need at least 5 competing addresses mapping to the same set to cause an eviction, versus just 2 in direct-mapped. This is why most modern L1 caches are 4- to 8-way set-associative: the conflict miss reduction is substantial, the parallel comparator cost (4–8 comparisons per access) is manageable, and the latency overhead is minimal compared to a full main memory access.