Direct-mapped, set-associative and fully associative caches compared
A cache's mapping decides where a block of memory is allowed to sit. In a direct-mapped cache every block has exactly one line it can go in: the index bits of the address pick the line and the tag bits are stored to check it. In a fully associative cache a block can go in any line, so every lookup compares the tag against all lines at once. A set-associative cache is the middle ground used in practice: the index picks a set of N lines (N ways), and the block can sit in any of them, so a lookup compares N tags. When a set is full, a replacement policy such as least recently used picks which block to evict. More associativity means fewer conflict misses but more comparators and more power; direct-mapped is the simplest, fully associative the most flexible.
What each one is good at
Direct-mapped caches are simple and fast: one comparator, one place to look, which is why they are the classic first example. Their weakness is conflict misses, when two busy addresses share an index and keep evicting each other. Fully associative caches never have conflict misses but need a comparator for every line, so they suit small structures. Set-associative caches tolerate most conflicts with only a few comparisons per lookup, which is why set-associative caches are the usual design in practice. Separately, a cache chooses a write policy: write-through updates memory on every write, while write-back writes only to the cache and copies a dirty line back when it is evicted.
Build one live in digiwleea
The direct-mapped cache in digiwleea is a real circuit you can run: a 4-line cache built from registers and multiplexers, where a 4-bit address splits into a 2-bit tag (A3 A2) and a 2-bit index (A1 A0), and the hit signal is the stored valid bit ANDed with a tag comparison. The cache lesson covers set-associative caches, eviction and write policies, and the memory hierarchy lesson shows where caches sit between registers and RAM.
One 4-bit address, three ways
| Direct-mapped (4 lines) | 2-way set-associative (2 sets) | Fully associative (4 lines) | |
|---|---|---|---|
| Index bits | 2 (pick 1 of 4 lines) | 1 (pick 1 of 2 sets) | 0 |
| Tag bits | 2 | 3 | 4 |
| Places a block can go | 1 | 2 | 4 |
| Tag comparisons per lookup | 1 | 2 | 4 |
Same 4 lines, same 16 addresses; only the split between index and tag changes. The live circuit is the direct-mapped column.
No sign-up is needed to start: open the lab and place your first transistor, or read the free theory course. The account (and the AI tutor) are optional.
More comparisons: Digital logic concepts compared
See for yourself: build a logic gate from transistors in the simulator, then follow the path from sand to an 8-bit CPU.
Open the digiwleea lab →Frequently asked
What is the difference between direct-mapped and set-associative cache?
In a direct-mapped cache each memory block can go in exactly one cache line. In an N-way set-associative cache the block's set has N lines and the block can go in any of them, which reduces conflict misses at the cost of comparing N tags per lookup.
What is a fully associative cache?
A cache where any block can be stored in any line, so there is no index: every lookup compares the address tag with every line's tag.
How is the address split in a direct-mapped cache?
Into a tag, an index and, for multi-byte blocks, an offset. The index selects the line, the tag is compared with the one stored there, and the offset picks the byte within the block.
What is the difference between write-through and write-back?
Write-through writes every store to both the cache and memory, so memory is always current. Write-back writes only to the cache and marks the line dirty, copying it to memory when the line is evicted, which saves bus traffic.