Cache mapping decides where a memory block can sit in the cache. So direct mapping gives each block exactly one legal line. So lookup is fast, but collisions hurt badly. Fully associative mapping lets a block sit anywhere among all the lines. So collisions disappear, but every tag needs a parallel check. Set-associative mapping sits in between the two extremes. A block maps to one set, then to any way inside it. Take a 64 KB memory with 16-bit addresses and 16-byte blocks. The cache holds 2 KB, or 128 lines. Under direct mapping, blocks 48, 176, and 304 all land on line 48. Each new access then evicts the block before it. Under 4-way set-associative mapping, the same three blocks share set 16 instead. That set holds four ways, so all three fit together.
A CPU cache is small and fast, while main memory is huge and slow. So every cache design needs one rule: where can a block from memory land inside it. That rule is called cache mapping. So three schemes handle it, each a different way: direct mapping, fully associative mapping, and set-associative mapping.
One example runs through this whole guide, so every number stays consistent. Main memory holds 64 KB, which gives a 16-bit address. Each block spans 16 bytes, so the offset always needs 4 bits. The cache itself holds 2 KB, which splits into 128 lines. A worked example later splits that same 16-bit address three separate ways, once per scheme.
Why a Cache Needs a Placement Rule
Main memory stores every block a program might ever touch. Our guide to computer architecture vs organization explains why that memory sits far from the CPU. A cache instead sits close to the CPU, built from fast SRAM cells. Our SRAM vs DRAM guide covers why SRAM costs more, yet runs faster.
Main memory splits into equal chunks, called blocks. The cache splits into chunks of the same size, called lines, though some texts call a line a frame instead. Main memory here holds 4,096 blocks, while the cache holds only 128 lines. So many blocks compete for far fewer lines. A mapping rule then decides which line, or which few lines, each block may use.
That block-and-line split echoes another one. Our paging vs segmentation guide compares a similar split. There, virtual memory splits into pages, while physical memory splits into frames.
Direct Mapping
Direct mapping gives each block exactly one legal line. The rule stays simple: line equals block number mod 128. Block 48 must sit on line 48, every single time, and no other line will ever hold it.
An address then splits into three fields: tag, index, and offset. Our logical vs physical addresses guide covers address translation in full. For this cache, the offset takes 4 bits, since each block holds 16 bytes. The index takes 7 bits, since 128 lines need 7 bits to number them. That leaves 5 bits for the tag. That is because tag bits equal address bits, minus index bits, minus offset bits.
Because each block owns exactly one line, direct mapping needs no replacement policy at all. Instead, nothing gets chosen; the rule simply sends the block where it belongs. That same rule also means only one comparator is ever needed, since only one tag can ever match. Total tag storage across all 128 lines comes to 640 bits.
Fully Associative Mapping
Fully associative mapping drops the index field completely. So a block may sit on any of the 128 lines, picked freely. The address then splits into only two fields this time: tag and offset. With no index bits left to narrow the search, the tag has to carry every remaining bit. That works out to 12 bits, the largest tag of the three schemes.
Because a block could be sitting anywhere, hardware must compare the incoming tag against every line at once. That comparison never runs line by line; it runs in parallel, using content-addressable memory. This cache needs 128 comparators, one per line, all wired to fire together. Our hardwired vs micro-programmed control guide looks at how control hardware drives comparisons like this one. Total tag storage climbs to 1,536 bits, the highest of the three schemes.
That parallel search is also why fully associative mapping costs the most, and carries the longest hit time. A miss on one line still leaves every other line open, so a replacement policy has to pick one. LRU, FIFO, or random selection all work; the scheme itself never cares which.
Set-Associative Mapping
Set-associative mapping blends the other two schemes. A block still maps to exactly one set, the way direct mapping maps a block to one line. Inside that set, though, the block may sit on any of a few ways. That freedom matches fully associative mapping, which allows any line at all.
Take this cache at 4-way associativity. The rule becomes: set equals block number mod 32. Block 48 must land in set 16, but any of the 4 ways inside that set will hold it. The address then splits into tag, set, and offset fields: 7 bits, 5 bits, and 4 bits.
Associativity can shift up or down from there. At 2-way, this same 128-line cache gives 64 sets instead, with a 6-bit tag and a 6-bit set field. At 8-way, it gives just 16 sets, with an 8-bit tag and a 4-bit set field. Higher associativity means fewer sets, but more comparators per set, and a wider tag.
Because a set still holds more than one way, set-associative mapping needs a replacement policy too. That policy only chooses among the ways inside one set, though, never across the whole cache. This scheme needs 4 comparators for the running example, one per way, and 896 bits of total tag storage.
Cache Mapping Techniques Compared
The table below lines up all three cache mapping techniques, field by field.
| Aspect | Direct Mapping | Fully Associative | 4-Way Set-Associative |
|---|---|---|---|
| Placement freedom | One legal line | Any of 128 lines | Any of 4 ways in one set |
| Tag bits | 5 | 12 | 7 |
| Index / set bits | 7 (line) | None | 5 (set) |
| Offset bits | 4 | 4 | 4 |
| Number of sets | 128 | 1 | 32 |
| Comparators needed | 1 | 128 | 4 |
| Total tag storage | 640 bits | 1,536 bits | 896 bits |
| Replacement policy needed | None | Yes, LRU, FIFO, or random | Yes, within the set only |
| Hit time | Shortest | Longest | Middle ground |
| Conflict misses | Worst behaviour | None, by design | Fewer than direct mapping |
| Hardware cost | Lowest | Highest | Middle ground |
| Associativity, N-way | 1-way | 128-way | 4-way |
| Placement formula | line = block mod 128 | any of 128 lines | set = block mod 32, then any way |
| Best fit in practice | Simple, cost-sensitive caches | Small structures worth the tag cost | Real CPU caches |
| Worst case | Repeated collisions on one line | Highest comparator and power cost | A set filled beyond its ways |
One more idea ties the three schemes together. Direct mapping is simply 1-way set-associative mapping, since each set then holds only one line. Fully associative mapping is 128-way set-associative mapping instead, since a single set covers the whole cache. The arithmetic still agrees either way. A cache with 128 sets of 1 way gives 7 set bits and a 5-bit tag, exactly the direct-mapping split. A cache with 1 set of 128 ways gives 0 set bits and a 12-bit tag instead. That is exactly the fully associative split. So all three schemes reduce to one formula, with associativity simply turned up or down. Most competing guides present the three as separate, unrelated ideas instead.
Worked Example: Splitting a 16-Bit Address
Every address in this cache is 16 bits wide, since main memory holds 64 KB. Splitting that address differently is exactly what separates the three schemes.
| Scheme | Tag bits | Index / set bits | Offset bits |
|---|---|---|---|
| Direct mapping | 5 | 7 (line) | 4 |
| Fully associative | 12 | none | 4 |
| 4-way set-associative | 7 | 5 (set) | 4 |
Start from the block size. Each block holds 16 bytes, so the offset always needs 4 bits, no matter which scheme is running. That part of the address never changes.
Direct mapping needs 7 index bits next, since 128 lines require 7 bits to number them all. Whatever remains becomes the tag: 16 minus 7 minus 4, or 5 bits.
Fully associative mapping skips the index step completely. So the tag absorbs every bit the offset does not use: 16 minus 4, or 12 bits.
4-way set-associative mapping needs 5 set bits instead, since 32 sets require 5 bits to number them. The tag then takes whatever is left: 16 minus 5 minus 4, or 7 bits.
Every split obeys the same rule: tag bits equal address bits, minus index or set bits, minus offset bits. Skipping that last step is a common mistake, and it throws off every tag width that follows it.
Where Direct Mapping Thrashes
Picture a loop that repeatedly touches blocks 48, 176, and 304, one after another. So under direct mapping, all three collide on the very same line.
Block 48 maps to line 48, since 48 mod 128 equals 48. So does block 176, since 176 mod 128 also equals 48. Block 304 lands on line 48 as well, since 304 mod 128 equals 48 again.
So every access after the first one misses. Each block evicts the block before it, then gets evicted right back on the very next pass. That pattern is called thrashing, and direct mapping has no way around it here.
Instead, 4-way set-associative mapping handles the same loop far better. Block 48 maps to set 16, since 48 mod 32 equals 16. Block 176 and block 304 map to set 16 as well. But that set holds 4 ways, so all three blocks fit inside it together. Only the first three accesses miss; every access after that hits.
Likewise, fully associative mapping does no worse here. All three blocks can sit anywhere among the 128 lines, so they never fight over one spot. The result is the same three cold misses, then nothing but hits.
So this example is the clearest argument for associativity. More ways per set simply means fewer blocks get forced to share one line.
When Each Mapping Wins
Direct mapping wins when hit time matters above all, and hardware budget stays tight. One comparator is cheap, and lookup never waits on a search. The cost only shows up when a workload keeps colliding on the same line, the way the loop above does.
Fully associative mapping wins when conflict misses cannot be tolerated at all. Every line stays available to every block, so a collision alone never forces one out. That freedom runs expensive, though, since every comparator fires on every single access.
Set-associative mapping wins for almost everything in between the two. It cuts conflict misses sharply, without paying the full comparator and tag cost of a fully associative design. That balance is also why real CPU caches lean on set-associative mapping, rather than either extreme.
Associativity itself works like a dial, not a fixed choice. A 2-way design spends fewer comparators than 4-way, but tolerates fewer collisions per set. An 8-way design spends more comparators. In return, it shrinks the set count to just 16, and tolerates far more collisions per set. So each step trades hardware cost against conflict-miss protection.
Interview Questions
Frequently Asked Questions
Wrapping Up
Direct, fully associative, and set-associative mapping all answer the same question, just with a different amount of freedom. Direct mapping gives a block one line, so lookup stays cheap, but collisions hurt. Fully associative mapping gives a block every line, so collisions vanish, but the search costs the most.
Set-associative mapping splits the difference, and that balance is why real CPU caches lean on it. Remember the exam essentials. Tag bits equal address bits minus index or set bits minus offset bits. N-way means N ways per set, never N sets. Direct mapping needs no replacement policy, while the other two schemes both do.
Related reading on DiffStudy:
- SRAM vs DRAM
- Computer Architecture vs Organization
- Hardwired vs Micro-Programmed Control
- Logical vs Physical Memory Addresses
- Paging vs Segmentation
