Cache Mapping Techniques
How does the cache decide where to store data? There are three main mapping techniques, each with different trade-offs between flexibility, speed, and hardware complexity.
1. Direct Mapping
In direct mapping, each memory block maps to exactly one cache location. It's like a hotel with assigned rooms - you always go to the same room.
Direct Mapping
+---------------------------------------------+
| |
| Main Memory Cache |
| +-----------+ +-----------+ |
| | Block 0 |-->| Set 0 | |
| +-----------+ +-----------+ |
| | Block 1 |-->| Set 1 | |
| +-----------+ +-----------+ |
| | Block 2 |-->| Set 2 | |
| +-----------+ +-----------+ |
| | Block 3 |-->| Set 3 | |
| +-----------+ +-----------+ |
| | Block 4 |-->| Set 0 | (conflict!) |
| +-----------+ +-----------+ |
| | Block 5 |-->| Set 1 | (conflict!) |
| +-----------+ +-----------+ |
+---------------------------------------------+
Address: | Tag | Index (2 bits) | Offset |
Index determines cache set directly
Pros: Simple, fast lookup. Only one location to check.
Cons: High conflict misses - if two blocks map to same set, they keep evicting each other.
2. Fully Associative Mapping
In fully associative mapping, any memory block can go anywhere in cache. It's like a hotel where you can choose any empty room.
Fully Associative Mapping
+---------------------------------------------+
| |
| Main Memory Cache |
| +-----------+ +-----------+ |
| | Block 0 |-->| Set 0 |<--+ |
| +-----------+ +-----------+ | |
| | Block 1 |-->| Set 1 | | |
| +-----------+ +-----------+ | |
| | Block 2 |-->| Set 2 | | |
| +-----------+ +-----------+ | |
| | Block 3 |-->| Set 3 | | |
| +-----------+ +-----------+ | |
| (any block can | |
| go anywhere) | |
+---------------------------------------------+
Address: | Tag | Offset |
Must search entire cache (comparator for each set)
Pros: No conflict misses - blocks go anywhere.
Cons: Expensive hardware - need to compare all tags simultaneously. Limited cache size.
3. Set-Associative Mapping
A compromise between direct and fully associative. Each memory block maps to a specific SET, but can go anywhere within that set.
Set-Associative (2-way)
+---------------------------------------------+
| |
| Main Memory Cache |
| +-----------+ +-----------+ |
| | Block 0 |-->| Set 0: | |
| +-----------+ | [Way0][Way1] |
| | Block 1 | +-----------+ |
| +-----------+ | Set 1: | |
| | Block 2 |-->| [Way0][Way1] |
| +-----------+ +-----------+ |
| | Block 3 |-->| Set 2: | |
| +-----------+ | [Way0][Way1] |
| | Block 4 | +-----------+ |
| +-----------+ | Set 3: | |
| | Block 5 |-->| [Way0][Way1] |
| +-----------+ +-----------+ |
+---------------------------------------------+
Address: | Tag | Index | Offset |
Index selects set, search within set
Pros: Good balance - fewer conflicts than direct, simpler hardware than fully associative.
Cons: More complex than direct mapping, still some conflicts.
Which is Best?
Most modern processors use set-associative caches (typically 4-way or 8-way) as the best compromise. L1 caches are often 4-way, while larger L3 caches may use higher associativity or different techniques.