A cache is small, fast memory near the CPU. Address bits select a set, identify a block with a tag, and locate a byte with an offset. A resident block can be accessed without going to main memory.
A simulator showing cache placement, hits, and misses for memory accesses
1. Choose mapping and accesses (4 lines, 4-byte blocks, 8-bit addresses)
Run the same access sequence under different mappings. Two conflicting addresses repeatedly misses with direct mapping. Cycling through five blocks defeats this four-line LRU cache even when fully associative.
Split an address into three fields
Four-byte blocks require two offset bits to select a byte. Some bits above them form the set index; the remaining bits are stored as the tag. With a fixed total line count, increasing associativity reduces index bits and increases tag bits.
Three mapping strategies
Direct-mapped assigns each block one line. Lookup is simple, but alternating two blocks mapped to the same line causes repeated evictions. Fully associative permits placement in any line, avoiding mapping conflicts but requiring more tag comparisons. Many real CPU caches use the compromise of set associativity, for example 4–16 ways depending on the cache.
Locality in code
Temporal locality reuses recently accessed data; spatial locality accesses nearby addresses. Both improve cache behavior. Traversing a row-major 2D array in a[i][j] order reads neighboring values, while a[j][i] order can jump between distant addresses. Contiguous arrays often benefit from locality more than linked structures.