What are Cache Memory Mapping Techniques?
Direct, fully associative, and set-associative cache mapping compared — trade-offs and examples, with an OS interview question answered.
Expected Interview Answer
Cache mapping techniques determine which cache line(s) a given main-memory block may be placed into, and the three classic strategies are direct mapping (each block maps to exactly one line), fully associative mapping (a block may go into any line), and set-associative mapping (a block maps to any line within one specific set), trading off hardware simplicity against flexibility and hit rate.
In direct mapping, a memory block’s address modulo the number of cache lines determines its single possible line, so lookup is a simple index into an array, but two blocks that map to the same line will constantly evict each other even if the rest of the cache is empty (conflict misses). Fully associative mapping allows a block into any line at all, which maximizes flexibility and minimizes conflict misses, but requires comparing the tag against every line in parallel, which is expensive in hardware and only practical for small caches. Set-associative mapping is the pragmatic middle ground used by real CPUs: the cache is divided into sets, each block maps to exactly one set (by index bits) but can occupy any of the N lines within that set (N-way associative), so a small parallel comparison over N tags balances hit rate against hardware cost. Each mapping also needs a replacement policy (like LRU) when the target line or set is full, and the choice of mapping directly shapes how often programs suffer conflict misses versus capacity misses.
- Direct mapping: simplest and cheapest hardware, O(1) lookup
- Fully associative: best hit rate, no conflict misses, costly hardware
- Set-associative: the practical balance used in real CPU caches
- Understanding it explains real cache-thrashing and performance bugs
AI Mentor Explanation
Direct mapping is like assigning every player a single fixed locker number based on their squad number, so two players with the same squad number modulo the locker count must fight over one locker even if others sit empty. Fully associative mapping is like a free-for-all locker room where any player can use any open locker, found by checking every locker’s name tag — flexible but slow to search. Set-associative mapping is the practical compromise: players are grouped into locker bays by squad number, and within their assigned bay they can use any of a few lockers, avoiding needless collisions without checking the whole room.
Step-by-Step Explanation
Step 1
Direct mapping
Address bits index exactly one cache line; simple and fast but prone to conflict misses.
Step 2
Fully associative mapping
A block can occupy any line; all tags are compared in parallel, maximizing hit rate at high hardware cost.
Step 3
Set-associative mapping
Address bits pick a set; the block may occupy any of the N lines within that set, balancing cost and hit rate.
Step 4
Replacement on a full set
When the target set/line is full, a policy like LRU decides which existing line is evicted.
What Interviewer Expects
- Correct definition of all three mapping strategies
- Trade-off reasoning: hardware cost vs hit rate vs conflict misses
- Understanding that set-associative is the practical real-world default
- Awareness that a replacement policy is still needed within a set
Common Mistakes
- Confusing set-associative with fully associative
- Thinking direct mapping never has misses if the cache is not full
- Forgetting that fully associative requires expensive parallel tag comparison
- Not mentioning replacement policy as part of the mapping scheme
Best Answer (HR Friendly)
“Cache mapping techniques decide where a piece of memory is allowed to be stored inside the cache. Direct mapping gives it exactly one possible spot, which is simple but can cause avoidable collisions; fully associative lets it go anywhere, which is flexible but expensive to search; and set-associative — what most real processors use — is a practical middle ground, grouping the cache into small sets so lookups stay fast while still avoiding most collisions.”
Code Example
#define CACHE_LINES 1024
#define LINE_SIZE_BITS 6 /* 64-byte lines */
struct cache_line {
int valid;
unsigned tag;
unsigned char data[1 << LINE_SIZE_BITS];
};
static struct cache_line cache[CACHE_LINES];
int cache_lookup(unsigned address, unsigned char *out) {
unsigned offset = address & ((1 << LINE_SIZE_BITS) - 1);
unsigned index = (address >> LINE_SIZE_BITS) % CACHE_LINES;
unsigned tag = address >> (LINE_SIZE_BITS + 10); /* log2(CACHE_LINES)=10 */
struct cache_line *line = &cache[index]; /* direct mapping: ONE possible line */
if (line->valid && line->tag == tag) {
*out = line->data[offset];
return 1; /* hit */
}
return 0; /* miss: fetch from lower memory, then install into this same index */
}Follow-up Questions
- What is a conflict miss and how does associativity reduce it?
- Why do most modern CPUs use 4-way or 8-way set-associative L1 caches instead of fully associative?
- How does the LRU replacement policy work within a cache set?
- What is the difference between a capacity miss and a conflict miss?
MCQ Practice
1. In direct mapping, a given memory block can be placed in?
Direct mapping computes a single fixed index for each memory block, so it has exactly one possible cache line.
2. Fully associative mapping trades off what for its flexibility?
Because a block can go anywhere, hardware must compare the address tag against every line simultaneously, which is costly to build at scale.
3. Set-associative mapping is best described as?
Address bits select a set, and within that set any of the N lines (N-way associative) may hold the block, balancing hit rate and cost.
Flash Cards
Name the three cache mapping techniques. — Direct mapping, fully associative mapping, and set-associative mapping.
What is the main drawback of direct mapping? — Conflict misses — two blocks that hash to the same line evict each other even if the cache is otherwise empty.
Why is fully associative mapping expensive? — It requires comparing the address tag against every cache line in parallel.
What do real CPUs typically use? — N-way set-associative caches, balancing hit rate against hardware/lookup cost.