Cache Mapping Techniques

Since cache memory is much smaller than main memory, we need a transformation process to determine which main memory block occupies a particular cache line. This process is known as Cache Mapping.

1. Direct Mapping

In direct mapping, each block of main memory is mapped to exactly one possible cache line. The mapping is usually done using the formula: $i = j \pmod m$, where $i$ is the cache line number, $j$ is the main memory block number, and $m$ is the number of lines in the cache.

• **Advantage:** Simple and inexpensive to implement.
• **Disadvantage:** High conflict miss rate; if two frequently used blocks map to the same line, they will constantly kick each other out (thrashing).

2. Fully Associative Mapping

In this technique, a main memory block can be loaded into any available line of the cache. The cache controller must search all lines simultaneously to find a match.

• **Advantage:** Most flexible; eliminates conflict misses entirely.
• **Disadvantage:** Very complex and expensive hardware required for simultaneous searching (comparators).

3. Set-Associative Mapping

This is a middle-ground approach. The cache is divided into a number of sets, and each set contains a fixed number of lines (k-way). A block from main memory maps to a specific set but can be placed in any line within 그 set.

• **Example:** In a 4-way set-associative cache, each set has 4 lines.
• **Advantage:** Balances the speed of direct mapping with the flexibility of associative mapping.
• **Usage:** Most modern CPUs (L1, L2, L3) use this method.

Comparison Table

Address Structure

The CPU generates a logical address which is divided differently based on the mapping technique:

Direct: [Tag] [Line Index] [Block Offset]
Associative: [Tag] [Block Offset]
Set-Associative: [Tag] [Set Index] [Block Offset]

Common Mistakes to Avoid

• Assuming 'Tag' size is the same across all mapping types.
• Confusing 'Block size' with 'Cache size'.
• Forgetting that fully associative caches don't use an index field in the address.
• Underestimating the hardware complexity of high-way (e.g., 16-way) set associativity.

Advanced Concepts

• Replacement Algorithms (LRU, FIFO, LFU)
• Victim Cache
• Cache Coherency (MESI protocol)
• Inclusive vs. Exclusive Cache Hierarchies
• Skewed Associative Caches

Practice Exercises

• Given a 64KB cache with 16B blocks, calculate the number of bits for the offset.
• Determine the mapping of memory block 12 into a 4-line direct-mapped cache.
• Why does a fully associative cache require more bits for the Tag field?
• Compare a 2-way set-associative cache vs a direct-mapped cache of the same total size.

Conclusion

Cache mapping is a critical design choice in computer architecture. While Direct Mapping is fast but prone to conflicts, and Fully Associative is flexible but expensive, Set-Associative mapping remains the industry standard for its balanced performance.