The idea: three numbers give three fields
A cache keeps copies of blocks (lines) of memory. To find a byte, the hardware cuts its address into three fields. The low bits are the offset: which byte inside the block. The next bits are the index: which set of the cache to look in. The rest is the tag: it is stored with the line and compared, because many blocks share one set. How wide each field is follows from three numbers: the cache size, the block size and the number of ways (lines per set).
The page uses 16-bit addresses and tiny caches of 64 to 256 bytes, so every line fits on the screen. The arithmetic is the same for real sizes.
Five lines of arithmetic
- lines = cache size / block size
- sets = lines / ways
- offset bits = log2(block size in bytes)
- index bits = log2(sets)
- tag bits = address bits − index bits − offset bits
The page starts with a 128 B direct-mapped cache and 16 B blocks: 128 / 16 = 8 lines, 8 / 1 = 8 sets, offset log2 16 = 4 bits, index log2 8 = 3 bits, tag 16 − 3 − 4 = 9 bits. The panel at the top right of the canvas shows these five lines for whatever cache you pick.
Reading the fields off the binary
Write the address in binary and cut it from the right. 0x1144 is 0001 0001 0100 0100. The low 4 bits 0100 are offset 4. The next 3 bits 100 are index 4. The top 9 bits 0 0010 0010 are tag 0x022 (Demo 1). The cache is empty, so set 4 has no valid line: a miss, and block 0x1140–0x114F is loaded into it.
The same numbers come out without binary. offset = address mod block = 0x1144 mod 16 = 4. The block number is address / block = 0x114 = 276. index = 276 mod 8 = 4, and tag = 276 / 8 = 34 = 0x022.
More ways, longer tag
Keep the size and double the ways: the sets halve, so one bit moves from the index to the tag, and the set needs one more comparator (one per way, all working at once). A fully associative cache has one set and no index at all: the tag is everything above the offset (Demo 2).
| 128 B, 16 B blocks | sets × ways | tag · index · offset | 0x1144 goes to | comparators |
|---|---|---|---|---|
| direct-mapped | 8 × 1 | 9 · 3 · 4 | set 4, tag 0x022 | 1 |
| 2-way | 4 × 2 | 10 · 2 · 4 | set 0, tag 0x045 | 2 |
| 4-way | 2 × 4 | 11 · 1 · 4 | set 0, tag 0x08A | 4 |
| fully associative | 1 × 8 | 12 · 0 · 4 | the one set, tag 0x114 | 8 |
The offset never changes, because it depends only on the block size. A bigger block moves the line between offset and index instead: 32 B blocks need 5 offset bits.
One address stream, three caches
Demos 3 to 5 send the same seven reads into the 128 B cache with 1, 2 and 8 ways. Blocks 0x104, 0x114 and 0x124 are 256 B apart, so they have the same index bits: set 4 in the direct-mapped cache, set 0 in the 2-way one.
| address | direct-mapped | 2-way | fully associative |
|---|---|---|---|
| 0x1040 | miss, cold | miss, cold | miss, cold |
| 0x1044 | hit | hit | hit |
| 0x1140 | miss, out 0x020 | miss, cold | miss, cold |
| 0x1040 | miss, out 0x022 | hit | hit |
| 0x1144 | miss, out 0x020 | hit | hit |
| 0x1240 | miss, out 0x022 | miss, out 0x041 (LRU) | miss, cold |
| 0x1048 | miss, out 0x024 | miss, out 0x045 | hit |
| hits | 1 of 7 | 3 of 7 | 4 of 7 |
The direct-mapped cache has 7 empty lines and still misses 6 times: every block wants line 4. Two ways hold two of the three blocks, so the third one throws out the least recently used. Only the fully associative cache keeps all three. Why misses happen (cold, capacity, conflict), when LRU is the worst choice and what a miss costs are on CPU Cache: Associativity, LRU, Write-Back.
How many bits a cache really stores
The size in a cache's name counts only the data. Each line also stores a valid bit (V: does this line hold anything?) and its tag:
total bits = lines × (1 + tag bits + 8 × block size)
For the starting cache: 8 × (1 + 9 + 128) = 8 × 138 = 1104 bits, 138 bytes. 80 of those bits, 7.2 %, are valid and tag bits (Demo 6). Demo 7 compares three caches with the same 128 B of data:
| cache | lines | tag | bits per line | total | overhead |
|---|---|---|---|---|---|
| 16 B blocks, direct-mapped | 8 | 9 | 138 | 1104 | 80 = 7.2 % |
| 16 B blocks, fully associative | 8 | 12 | 141 | 1128 | 104 = 9.2 % |
| 32 B blocks, direct-mapped | 4 | 9 | 266 | 1064 | 40 = 3.8 % |
More ways cost tag bits on every line. Bigger blocks mean fewer lines, so fewer tags to store. The tag of the 32 B cache stays 9 bits: it gains an offset bit and loses an index bit.
A textbook case (Patterson and Hennessy, chapter 5): 16 KiB of data, 16 B blocks, direct-mapped, 32-bit addresses. That is 1024 lines, index 10, offset 4, tag 18, so 1024 × (1 + 18 + 128) = 150,528 bits, 147 Kibit, about 1.15 times the 128 Kibit of data. A real L1 data cache of 32 KiB, 8-way, with 64 B lines and 32-bit physical addresses has 512 lines in 64 sets: offset 6, index 6, tag 20, and 512 × (1 + 20 + 512) = 272,896 bits, of which 10,752 (3.9 %) are valid and tag bits.
Real caches store a few more bits, and exam questions often say which ones to count. A write-back cache adds a dirty bit per line (8 more bits for the starting cache). LRU needs state per set: 1 bit for a 2-way set; tree pseudo-LRU uses ways − 1 bits per set.
A recipe for exam questions
- Turn everything into bytes first. A block of 4 words of 4 bytes is 16 B; 16 KiB is 16 × 1024 bytes.
- Work out lines, sets, offset, index and tag in that order, and check that the three fields add up to the address width.
- For an address stream, write one row per access: tag, index, offset, hit or miss. Keep a small table of what each set holds. This is the canvas's worksheet.
- For the size, ask which bits per line to count: valid always, tag always, dirty for write-back, LRU bits per set if asked.
See also CPU Cache: Associativity, LRU, Write-Back for three caches running one trace side by side, the 3 C's of misses, write policies and AMAT.
See also One Load Through the Memory Hierarchy for what happens after a miss: L2, DRAM and disk, with a cycle count.
See also TLB and Page Walk: a virtual address splits the same way, into a page number and a page offset, before the cache sees it.
See also Cache Write Policies and the Three C's: what writes do to a cache line, with dirty bits, a write buffer and the three kinds of miss.
See also Cache-Friendly Loops: Traversal Order, Interchange and Tiling for how the order of a loop decides how many of its accesses miss.
What the page leaves out
- Tiny caches and 16-bit addresses; real L1 caches are hundreds of times bigger with 64 B lines.
- Reads only: no writes, dirty bits or write policies on the canvas (the bit count leaves out dirty and LRU bits; the text above says how to add them).
- No classification of misses into cold, capacity and conflict beyond "cold", and no timing.
- Physical addresses only: no virtually indexed, physically tagged caches, where the index must fit inside the page offset.
- Only power-of-two sizes. A 48 KiB 12-way cache still has 64 sets of 64 B lines; the formulas need the number of sets and the block size to be powers of two, not the cache size.
On the mind map
References
Cache placement policies (Wikipedia)
CPU cache (Wikipedia): address split, tag, index, offset
Patterson and Hennessy, Computer Organization and Design, Chapter 5: Large and Fast: Exploiting Memory Hierarchy (section 5.3, the bits in a cache)
Harris & Harris, Digital Design and Computer Architecture, Chapter 8: Memory and I/O Systems