Every cache question comes down to one step: splitting a memory address into tag, index and offset bits. Once you can do that, hit/miss traces and "how many tag bits" questions follow mechanically.
The three fields
- Offset: which byte inside a block. With 16-byte blocks you need log₂ 16 = 4 offset bits.
- Index (or set): which line or set the block must go in. log₂(number of sets) bits.
- Tag: everything left over. It is stored with the block, so the cache can tell which of the many blocks that map to the same set is actually there.
offset bits = log₂(block size)
sets = (cache size ÷ block size) ÷ ways
index bits = log₂(sets)
tag bits = address bits − index bits − offset bits
Worked example
A 16-bit address, a 1 KB cache, 16-byte blocks. That is 1024 ÷ 16 = 64 lines.
| Mapping | Sets | Offset | Index | Tag |
|---|---|---|---|---|
| Direct-mapped (1-way) | 64 | 4 | 6 | 6 |
| 2-way set-associative | 32 | 4 | 5 | 7 |
| Fully associative (64-way) | 1 | 4 | 0 | 12 |
Doubling the associativity halves the number of sets, so one index bit moves into the tag. In a fully associative cache there is no index at all: a block can go in any line, and every tag must be compared.
Splitting one address
Take address 0x1A2B = 0001 1010 0010 1011:
- Direct-mapped: tag
000110= 6, index100010= 34, offset1011= 11. The block can only live in line 34. - 2-way: tag
0001101= 13, index00010= 2, offset 11. Either of the two lines in set 2. - Fully associative: tag
000110100010= 418, offset 11. Any line.
The offset is the same in all three: the block size didn't change.
A hit/miss trace
Now access these byte addresses in order: 0, 4, 16, 1024, 0, 2048, 16.
Direct-mapped (block = address ÷ 16, line = block mod 64):
| Address | Block | Line | Result |
|---|---|---|---|
| 0 | 0 | 0 | miss |
| 4 | 0 | 0 | hit (same block as address 0) |
| 16 | 1 | 1 | miss |
| 1024 | 64 | 0 | miss, evicts block 0 |
| 0 | 0 | 0 | miss, evicts block 64 |
| 2048 | 128 | 0 | miss, evicts block 0 |
| 16 | 1 | 1 | hit |
2 hits out of 7. Blocks 0, 64 and 128 all map to line 0 and keep throwing each other out: a conflict miss.
2-way set-associative with LRU (set = block mod 32): blocks 0 and 64 can now share set 0, so the second access to address 0 hits. When 2048 (block 128) arrives, the least recently used block in set 0 (block 64) is evicted. Result: 3 hits out of 7.
Common mistakes
- Forgetting to divide by the block size first. The index comes from the block number, not the byte address.
- Using lines instead of sets for a set-associative cache. Sets = lines ÷ ways.
- Mixing up KB and Kb, or bytes and words. If the question gives word-addressable memory, the offset counts words, not bytes.
- Assuming FIFO when the question says LRU (or the reverse). The replacement policy only matters in associative caches; a direct-mapped cache has no choice.
Check your answers
The cache mapping calculator splits any address for any cache size, block size and associativity, shows the tag storage needed, and runs a hit/miss trace with LRU replacement. For the rest of the memory unit, see memory allocation and page replacement.
For a related walkthrough, read Two's Complement: Signed Binary Explained.