Lec 05-06-2025: Cache Misses, Associativity, Replacement Policies, and Snooping Protocols | CSCI 343

Types of Cache Misses

Cache misses can happen for different reasons, so it helps to categorize them because different types call for different solutions. For example, a compulsory miss can’t be fixed by changing the replacement policy.

1. Compulsory Misses:

   • Also known as cold-start misses.
   • Occur when a block is accessed for the first time and is not yet in the cache.
   • Unavoidable on first access.

2. Capacity Misses:

   • Occur because the cache is not large enough to hold all the blocks needed during execution.
   • These occur even in a fully associative cache (where placement is completely flexible) — the cache runs out of room regardless of where blocks are placed.

3. Conflict Misses:

   • Also known as collision misses.
   • Occur when multiple blocks compete for the same cache line or set, even though other lines are free.
   • For example, blocks 0 and 4 both map to line 0 in a 4-line direct-mapped cache, so accessing them alternately will cause repeated evictions — even if lines 1, 2, and 3 are sitting empty.

Cache Mapping and Associativity

The mapping strategy used determines how freely blocks can be placed in the cache, which directly affects conflict misses. The three strategies covered in the previous lecture — fully associative, direct-mapped, and set-associative — each make a different tradeoff between flexibility and hardware cost:

1. Direct-Mapped Cache:

   • Each block maps to exactly one line, making lookups fast and cheap.
   • The downside is a high conflict miss rate — blocks that share a line can thrash each other even when the rest of the cache is empty.

2. Fully Associative Cache:

   • Any block can go into any line, which eliminates conflict misses entirely.
   • The hardware cost is high: every line needs its own comparator for the parallel search, so this is only practical for small caches.

3. Set-Associative Cache:

   • A middle ground — the cache is divided into sets, and a block can go into any line within its assigned set.
   • An $n$-way set-associative cache gives each block $n$ possible locations, which is enough flexibility to significantly cut down on thrashing without needing comparators for every line in the cache.

Replacement Policies

When a cache set is full and a new block needs to come in, something has to go — a block must be replaced. The choice of which block to evict is the replacement policy. Common options:

1. Random Replacement:

   • Replace a randomly selected block in the set.
   • Simple to implement, but offers no guarantees — you might evict something that’s needed again very soon.

2. Least Recently Used (LRU):

   • Evict the block that hasn’t been accessed for the longest time.
   • Works on the intuition that recently used data is more likely to be needed again. Effective in practice, but requires tracking the access order of every block in the set.

3. First-In-First-Out (FIFO):

   • Evict the block that has been sitting in the cache the longest, regardless of how often it’s been accessed.
   • Simpler to implement than LRU (just track insertion order), but can make poor decisions — a block loaded early might still be heavily used.

4. Least Frequently Used (LFU):

   • Evict the block that has been accessed the fewest times overall.
   • Tracks usage frequency rather than recency. Can become expensive to implement, and frequency counts from the distant past can cause it to hold onto stale blocks.

Snooping Protocols and Cache Coherence

In multiprocessor systems, caching gets more complicated. Each processor has its own cache, and they all share the same main memory — so it’s possible for two processors to each hold a cached copy of the same block, and for one of them to write to it without the other knowing. This is the cache coherence problem: keeping all caches in sync so every processor sees a consistent view of memory.

One approach to solving this is the snooping protocol.

Overview of Snooping

All caches share a common bus, and every cache controller watches (or “snoops on”) all traffic on that bus. When a processor writes to a block, the other caches see that write on the bus and can react accordingly — either invalidating their copy or updating it.

Common Snooping-Based Protocols

1. Write-Invalidate:

   • When a processor writes to a block, all other caches invalidate their copies.
   • Works well when one processor writes to a block multiple times before others read it — subsequent writes don’t generate bus traffic since no other cache holds a valid copy.

2. Write-Update (or Write-Broadcast):

   • When a processor writes to a block, it broadcasts the new value to all other caches, which update their copies in place.
   • Works well when multiple processors read a block frequently after each write, since they all stay up to date without needing to fetch it again. Can incur high bus traffic otherwise.

Practical Considerations

• Snooping works best with a broadcast medium (e.g., a shared bus), since every cache needs to see every write.
• Protocols must ensure that only one processor can write to a block at a time. MESI (Modified, Exclusive, Shared, Invalid) is a widely used snooping-based protocol that tracks block state across caches to enforce this.
• In contrast, directory-based protocols are more scalable and are used in systems without a broadcast bus.

Summary: Mapping Strategy Tradeoffs

The choice of mapping strategy shapes how often your cache is useful:

• Fully associative gives complete placement flexibility but is expensive to build.
• Set-associative caches provide a good balance and are common in practice because it cuts conflict misses without requiring a comparator per line.
• The number of sets and the degree of associativity directly affect miss rates: more ways per set means fewer conflict misses, but also more hardware per set.