Cache Mapping and Replacement Policies

The Core Problem: Where to Place a Memory Block?

A cache is significantly smaller than main memory. For example, a system might have 32 GB of main memory but only 8 MB of cache. The fundamental challenge is deciding where in the cache a specific block from main memory should be placed. This "placement policy" is what we call a cache mapping technique.

To understand mapping, we must first see how the system uses a physical memory address. When the CPU generates a physical address to fetch data, this address is broken down into parts to navigate the cache. For a byte-addressable system, a physical address is typically partitioned into three fields:

• Block Offset: Identifies the specific byte or word within a memory block. If a block size is $2^k$ bytes, the last $k$ bits of the address form the offset. This part is irrelevant for mapping; it's used after the correct block is found.
• Index: Specifies which cache line or set the memory block should be placed in.
• Tag: The remaining bits of the address. They are stored in the cache alongside the data block to verify if the block stored at a given index is the one we are looking for.

The way the Tag and Index fields are defined determines the mapping technique.

1. Direct Mapping

This is the simplest mapping technique. A particular main memory block can only be placed in one specific line in the cache. The mapping is determined by a simple modulo operation:

Address Structure:
The index field directly specifies the cache line.

How it works:

1. The Line Number bits of the address point to a single cache line.
2. The CPU compares the Tag bits of the address with the tag stored in that cache line.
3. If they match, it's a cache hit. If not, it's a cache miss.

• Advantage: Very simple and fast. Only one tag comparison is needed, so the hardware is cheap (a single comparator).
• Disadvantage: High potential for conflict misses. If a program frequently accesses two different blocks that map to the same cache line, they will constantly evict each other, leading to a terrible hit rate, even if the rest of the cache is empty.

2. Fully Associative Mapping

At the opposite end of the spectrum is fully associative mapping. A main memory block can be placed in any available line in the cache.

Address Structure:
There is no index field. The entire block address (excluding the offset) is used as the tag.

How it works:

1. To find a block, the CPU must compare the Tag of the incoming address with the tags of all lines in the cache simultaneously.
2. If any tag matches, it's a cache hit. If no tags match, it's a cache miss.

• Advantage: Maximum flexibility. This eliminates conflict misses entirely, offering the best possible hit rate for a given cache size.
• Disadvantage: Extremely expensive and complex. It requires a comparator for every single cache line, and all comparisons must happen in parallel. This is not practical for large caches.

3. Set-Associative Mapping: The Best of Both Worlds

Set-associative mapping is a practical compromise that combines the strengths of the previous two techniques. The cache is divided into a number of sets, and each set contains a certain number of lines (let's say, k lines).

A main memory block is first mapped to a specific set, but it can be placed in any of the k lines within that set. This is called k-way set-associative mapping.

Address Structure:
The index field now points to a set, not a single line.

How it works:

1. The Set Number bits of the address point to a specific set in the cache.
2. The CPU compares the Tag of the incoming address with the tags of all k lines within that set in parallel.
3. If any tag matches, it's a cache hit. If not, it's a cache miss.

• Advantage: It reduces the probability of conflict misses compared to direct mapping, as multiple blocks that map to the same set can coexist. The hardware complexity is manageable, as it only requires k comparators (where k is typically a small number like 2, 4, 8, or 16).
• Special Cases: Notice how set-associative mapping is a general form:
  • 1-way set-associative mapping is the same as direct mapping (each set has one line).
  • If a cache has N lines total, N-way set-associative mapping is the same as fully associative mapping (there is only one set containing all the lines).

To see these concepts applied to a concrete GATE-style problem, the following video provides an excellent numerical walkthrough and comparison.

Cache Replacement Policies: Deciding What to Evict

We have a new question. In set-associative or fully associative mapping, a miss might occur when the target set (or the entire cache) is already full. To make room for the new block, one of the existing blocks must be evicted. A replacement policy is the algorithm that decides which block to kick out.

Note that direct mapping requires no replacement policy. If a block needs to be placed in line i, it simply overwrites whatever is currently in line i. There is no choice to be made.

Let's discuss the most important policies for the GATE exam.

1. First-In, First-Out (FIFO)

This is the simplest replacement algorithm. It evicts the block that has been in the cache the longest, regardless of how often or how recently it was used. It treats the cache set like a simple queue.

• Advantage: Very easy to implement.
• Disadvantage: It can make poor decisions. A block that was loaded long ago might still be actively used, but FIFO would evict it anyway in favor of a newly loaded, potentially less useful block.

2. Least Recently Used (LRU)

This policy leverages the principle of temporal locality. It evicts the block that has been accessed least recently. The logic is that if a block hasn't been used in a while, it's less likely to be used in the near future compared to blocks that have been accessed recently.

• Advantage: Generally provides very good hit rates, often close to the theoretical optimal.
• Disadvantage: True LRU is complex and expensive to implement in hardware. It requires tracking the access order for all blocks in a set, which can be done with counters or a stack-like structure, adding overhead.

FIFO vs. LRU: A Comparative Example

Let's trace a reference string for a 3-block cache using both FIFO and LRU to see the difference in their performance.
Reference String: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2

As you can see, LRU makes more intelligent decisions. In step 6, FIFO evicts 0 because it was the first of 0,1,2 to be loaded. LRU, however, knows 0 was just used in step 5, so it evicts 1, which is the actual least recently used block. This pays off in step 7, where the request for 0 results in a hit for LRU but a miss for FIFO. This clearly demonstrates why LRU generally outperforms FIFO.

Conclusion

In this lesson, we have dissected the core mechanics of cache organization. We learned how mapping techniques and replacement policies work together to manage the limited space in a cache, directly influencing the hit and miss rates.

Key Takeaways:

• Cache Mapping Techniques determine where a memory block can be placed in the cache.
  • Direct Mapping: Simple and fast, but prone to conflict misses. One choice.
  • Fully Associative: Most flexible, no conflict misses, but very expensive. Any choice.
  • Set-Associative: A practical balance, allowing a block to be placed in any of a few (k) possible locations. Limited choice.
• Cache Replacement Policies decide which block to evict from a set when it is full.
  • FIFO (First-In, First-Out): Evicts the oldest block. Simple but can be inefficient.
  • LRU (Least Recently Used): Evicts the block that has been untouched for the longest time. More effective due to temporal locality, but harder to implement.
• These two design choices are fundamental to cache performance and are the primary determinants of the hit rate, which, as we learned previously, is a key parameter in the AMAT formula.

We have now explored how the system manages data flow between the CPU and main memory. Next, we will shift our focus to how the CPU communicates with the outside world. Our upcoming lesson will cover I/O techniques (programmed I/O, interrupt-driven I/O, and DMA) and algorithms for managing secondary storage, such as disk scheduling.