Questions: Cache Associativity and Address Mapping Strategies

Question 1

A direct-mapped cache has 16 lines. Two frequently used arrays, A and B, happen to map to the same cache line. What happens when the program alternates between accessing elements of A and B?

• A. The cache handles this efficiently by storing both arrays in the same line using compression
• B. Every access causes a conflict miss: A evicts B, then B evicts A, even though the other 15 lines are empty
• C. The CPU detects the conflict and automatically promotes the cache to 2-way associativity
• D. The cache falls back to fully associative mode for those two addresses only

Answer: (B)

This is the classic conflict miss in a direct-mapped cache. Because each address maps to exactly one line, A and B compete for the same location regardless of how much other cache space is available. Every time A is accessed, it evicts B. Every time B is accessed, it evicts A. The result is 100% miss rate for these accesses despite the majority of the cache being empty. This is the fundamental weakness of direct-mapped design — capacity is not the constraint, placement rigidity is.

Question 2

Why is fully associative mapping impractical for large L1 caches despite eliminating conflict misses entirely?

• A. Fully associative caches require more bits per address tag than direct-mapped caches
• B. On every access, the hardware must compare the requested address tag against every stored tag simultaneously, requiring a comparator per cache line — infeasible at thousands of lines
• C. Fully associative caches cannot use LRU replacement, limiting their hit rates
• D. Fully associative caches require the CPU to pause for one clock cycle per cache line checked, making lookups too slow

Answer: (B)

Full associativity requires simultaneous comparison of the incoming address tag against all stored tags to find a match in one cycle. This demands a hardware comparator for every cache line. For a TLB with 64 entries, 64 comparators is feasible. For an L1 cache with 4,096 lines, 4,096 parallel comparators would be enormous and power-hungry. The hardware cost scales linearly with cache size, which is why fully associative design is reserved for tiny, critical structures like TLBs.

Question 3

In a direct-mapped cache, a conflict miss can occur even when most of the cache lines are empty.

• T. True
• F. False

Answer: True

This is the core weakness of direct-mapped caches. Because each memory address maps to exactly one cache line, two addresses that happen to map to the same line will evict each other on every access — regardless of how many other lines are unused. The cache's overall occupancy is irrelevant to conflict miss frequency. This is why the miss rate of a direct-mapped cache can sometimes be worse than a smaller fully associative cache: it's not about total capacity, it's about placement flexibility.

Question 4

Doubling cache associativity generally doubles cache performance — a 4-way set-associative cache is typically twice as fast as a 2-way cache.

• T. True
• F. False

Answer: False

Associativity shows strongly diminishing returns. Going from 1-way (direct-mapped) to 2-way typically cuts conflict misses roughly in half — a substantial improvement. Going from 2-way to 4-way helps further but by a smaller margin. Beyond 8-way, improvements are minimal for most workloads, while hardware complexity and power continue growing. Performance depends on the specific access patterns: a workload with few conflicts sees little benefit from higher associativity; one with many conflicts sees large gains up to a point.

Question 5

Explain why set-associative caches are described as a 'middle ground' between direct-mapped and fully associative designs. What does each design trade off?

Model answer: Direct-mapped: every address maps to exactly one line — fast lookup (check one location) but vulnerable to conflict misses when multiple addresses compete for the same line. Fully associative: any address can go anywhere — no conflict misses but requires comparing every stored tag on every access, which is hardware-intensive and impractical for large caches. Set-associative divides the cache into sets; each address maps to one set (like direct-mapped, so lookup only checks N lines), but can occupy any of N lines within that set (like fully associative within the set, reducing conflicts). It limits search cost while gaining placement flexibility.

The design space of cache associativity is a continuous tradeoff between conflict miss rate and lookup hardware complexity. Direct-mapped minimizes hardware (one comparator) but maximizes conflicts. Fully associative minimizes conflicts but maximizes hardware. N-way set-associative uses N comparators per set and tolerates N competing addresses before conflicts arise. Most real L1 caches settle at 4-way or 8-way because that's where the conflict-miss curve flattens and the hardware cost is still acceptable.