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).

A 32-bit address for a 16 KiB direct-mapped cache with 16-byte blocks: 1024 lines and 1024 sets, so bits 3 to 0 are the offset (4 bits), bits 13 to 4 the index (10 bits) and bits 31 to 14 the tag (18 bits). The index picks one of 1024 lines; the stored tag is compared with the address tag.
16 KiB, 16 B blocks, direct-mapped, 32-bit addresses: tag 18 | index 10 | offset 4.

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

  1. lines = cache size / block size
  2. sets = lines / ways
  3. offset bits = log2(block size in bytes)
  4. index bits = log2(sets)
  5. 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 blockssets × waystag · index · offset0x1144 goes tocomparators
direct-mapped8 × 19 · 3 · 4set 4, tag 0x0221
2-way4 × 210 · 2 · 4set 0, tag 0x0452
4-way2 × 411 · 1 · 4set 0, tag 0x08A4
fully associative1 × 812 · 0 · 4the one set, tag 0x1148
The 16 bits of 0x1144 drawn three times. Direct-mapped: tag 9 bits, index 3 bits (100 = set 4), offset 4 bits. 2-way: tag 10 bits, index 2 bits (00 = set 0), offset 4 bits. Fully associative: tag 12 bits, no index, offset 4 bits.
Same address, same offset: each doubling of the ways hands one index bit to the tag.

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.

addressdirect-mapped2-wayfully associative
0x1040miss, coldmiss, coldmiss, cold
0x1044hithithit
0x1140miss, out 0x020miss, coldmiss, cold
0x1040miss, out 0x022hithit
0x1144miss, out 0x020hithit
0x1240miss, out 0x022miss, out 0x041 (LRU)miss, cold
0x1048miss, out 0x024miss, out 0x045hit
hits1 of 73 of 74 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)

One line of the 128-byte direct-mapped cache: V 1 bit, tag 9 bits, data 16 bytes = 128 bits, 138 bits in all. Eight such lines make 1104 bits, of which 1024 are data and 80 are valid and tag bits, 7.2 percent.
Each line pays 1 + 9 bits of bookkeeping for its 128 bits of data: 1104 bits for a "128 B" cache.

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:

cachelinestagbits per linetotaloverhead
16 B blocks, direct-mapped89138110480 = 7.2 %
16 B blocks, fully associative8121411128104 = 9.2 %
32 B blocks, direct-mapped49266106440 = 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

Open the Computer Architecture mind mapComputerArchitectureAbstraction and numbers: layers and bit patternsAbstraction and numbersCombinational logic: output depends only on inputsCombinational logicSequential logic: state held by a clockSequential logicMIPS software: how C becomes machine wordsMIPS softwareThe processor: datapath plus controlThe processorPipelines and parallelism: more instructions at oncePipelines and parallelismMemory and I/O: small fast near, big slow farMemory and I/OMemory arraysMemory arraysdecoder picks wordline, bitlines readCPU cacheCPU cachetag, index, offset; hit or missCache address breakdownsets = lines/ways; tag = rest of addressCache Write PoliciesCache Write PoliciesWrite-back sends dirty lines at evictionLoop tiling and interchangeLoop tiling and interchangeWalk rows; tile so reused data fitsMemory hierarchyMemory hierarchyAMAT = hit time + miss rate × penaltyDRAM timingDRAM timingopen row is fast, row change is slowMESI and false sharingMESI and false sharinga write invalidates other copiesVirtual memoryVirtual memoryTLB caches the page tableEmbedded I/OEmbedded I/Odevices are addresses; poll or interruptOpen the Computer Architecture mind mapComputer Architecturesmall fast near, big slow farMemory and I/OMemory arraysMemory arraysdecoder picks wordline, bitlines readCPU cacheCPU cachetag, index, offset; hit or missCache address breakdownsets = lines/ways; tag = rest of addressCache Write PoliciesCache Write PoliciesWrite-back sends dirty lines at evictionLoop tiling and interchangeLoop tiling and interchangeWalk rows; tile so reused data fitsMemory hierarchyMemory hierarchyAMAT = hit time + miss rate × penaltyDRAM timingDRAM timingopen row is fast, row change is slowMESI and false sharingMESI and false sharinga write invalidates other copiesVirtual memoryVirtual memoryTLB caches the page tableEmbedded I/OEmbedded I/Odevices are addresses; poll or interrupt
This page on the Computer Architecture mind map · 46 pages in 7 branches · open it to see the whole map and test yourself in recall mode.