Cache Memory Explained: Levels and Mapping
Cache memory is a small, fast SRAM store between the processor and main memory that keeps copies of recently used blocks. Processors use several levels, L1, L2 and L3, each larger and slower. A mapping scheme (direct, fully associative or set associative) decides where a memory block may be placed in the cache.
Cache memory exists because a processor core can execute instructions far faster than DRAM main memory can deliver them. Without a cache the core would wait on almost every load. A cache keeps copies of the data and instructions the program is likely to need next, so most accesses finish in a few cycles instead of making the long trip to main memory.
Why cache memory works: locality
Caches rely on the principle of locality, which Hennessy and Patterson describe as one of the most important program properties. It comes in two forms. With temporal locality, an item used now is likely to be used again soon, such as a loop counter or the instructions of a loop body. With spatial locality, items whose addresses are near each other tend to be used close together in time, such as consecutive elements of an array.
A cache does not fetch single bytes. It moves fixed size blocks (also called lines), so a miss on one element brings its neighbours in too. That is one reason contiguous data structures run faster, as shown in arrays vs linked lists.
Cache memory levels: L1, L2 and L3
Modern processors use a hierarchy of caches, each level larger and slower than the one above it.
The L1 cache is the smallest and fastest. It sits inside each core and is usually split into an instruction cache and a data cache, so the core can fetch an instruction and load data in the same cycle. This split is the modified Harvard idea explained in Von Neumann vs Harvard architecture. The L2 cache is larger and slower, usually unified (instructions and data together) and private to each core. The L3 cache is the largest on chip cache, usually shared by all cores, and the last stop before main memory.
For a real example, Hennessy and Patterson describe the Intel Core i7 6700 with a 32 KB, 8 way L1 instruction cache and a 32 KB, 8 way L1 data cache per core, a 256 KB, 4 way L2 cache per core, and an 8 MB, 16 way L3 cache shared by the cores, all using 64 byte blocks.
When the core issues a load, the L1 cache is checked first. On a hit the data comes back in the hit time. On a miss the request goes to L2, then L3, then main memory, and the block that contains the address is copied back up into the caches.
Cache memory mapping techniques
A cache holds far fewer blocks than main memory, so it needs a rule for where each memory block may go.
Direct mapping
Each memory block can go into exactly one cache line:
The hardware is simple and fast because only one tag is compared. The weakness is conflict misses: two frequently used blocks that map to the same line keep evicting each other, even when the rest of the cache is empty.
Fully associative mapping
A block can go into any line. The cache must compare the address tag with the tag of every line in parallel, which needs one comparator per line. It has no conflict misses but costs the most hardware and power, so it is used only for small structures such as translation lookaside buffers.
Set associative mapping
The cache is divided into sets of n lines each (n way set associative). A block maps to exactly one set, then may go in any line within that set:
Only n tags are compared per access. Direct mapping is the 1 way case and fully associative is the case of one set holding every line. Most processor caches are 2 way to 16 way set associative, as the i7 example shows.
How the address is split
For lookup, the cache divides the physical address into three fields:
| Field | Bits | Purpose |
|---|---|---|
| Tag | remaining high bits | Stored with the line and compared to confirm a hit |
| Index | log2(number of sets) | Selects the set (or the line in a direct mapped cache) |
| Block offset | log2(block size in bytes) | Selects the byte within the block |
Each line also holds a valid bit, and a write back cache adds a dirty bit. A hit requires the valid bit to be set and the stored tag to match.
- Given
- A 32 KB, 4 way set associative data cache with 64 byte blocks and 32 bit physical addresses. For the second part: L1 hit time 1 cycle, L1 miss rate 5 percent, L2 hit time 10 cycles, L2 local miss rate 20 percent, main memory access 100 cycles.
- Find
- (a) The tag, index and offset widths and where address 0x12345678 is placed. (b) The average memory access time (AMAT) with L1 alone and with L1 plus L2.
- Assumptions
- Byte addressable memory; the miss penalty equals the access time of the next level; the timing values are illustrative.
- Solution
- Lines = 32768 ÷ 64 = 512. Sets = 512 ÷ 4 = 128.
Offset = log2 64 = 6 bits. Index = log2 128 = 7 bits. Tag = 32 − 7 − 6 = 19 bits.
Address 0x12345678: offset = 0x12345678 mod 64 = 56; set = (0x12345678 ÷ 64) mod 128 = 89; tag = 0x12345678 ÷ 8192 = 0x91A2.
L1 alone: AMAT = 1 + 0.05 × 100 = 6 cycles.
With L2: miss penalty of L1 = 10 + 0.20 × 100 = 30 cycles, so AMAT = 1 + 0.05 × 30 = 2.5 cycles. - Answer
- Tag 19 bits, index 7 bits, offset 6 bits; the address goes to set 89 with tag 0x91A2 at byte 56. AMAT falls from 6 cycles to 2.5 cycles when the L2 cache is added.
- Limitations
- Real miss rates depend on the program. Out of order cores overlap some miss time with other work, and the model ignores write traffic and contention between cores.
For comparison, the same cache direct mapped would have 512 sets, so 9 index bits and a 17 bit tag; fully associative would have no index and a 26 bit tag.
Write policies
A write through cache updates both the cache and the next level on every write. It is simple and keeps memory up to date, but it creates heavy write traffic, so a write buffer is normally added.
A write back cache updates only the cache line and sets its dirty bit. The block goes to the next level only when it is evicted. That saves bandwidth, and it is the common choice for L2 and L3.
On a write miss, write allocate fetches the block into the cache and then writes it, while no write allocate writes straight to the next level. Write back caches usually use write allocate.
Replacement policies
In a set associative or fully associative cache, a miss in a full set must evict one line. Least recently used (LRU) evicts the line unused for the longest time, which suits temporal locality, but true LRU becomes costly at high associativity, so hardware often uses an approximation. First in, first out (FIFO) evicts the oldest line. Random replacement is simple to build and, for large caches, comes close to LRU in miss rate.
A direct mapped cache needs no policy because each block has only one possible line.
Types of cache misses
Hennessy and Patterson group misses into the three Cs:
- Compulsory misses happen on the first access to a block, which cannot be in the cache yet. Larger blocks reduce them.
- Capacity misses happen because the cache cannot hold every block the program needs. A larger cache reduces them.
- Conflict misses happen when too many blocks map to the same set. Higher associativity reduces them.
With several cores there is a fourth kind, coherence misses, which come from keeping private caches consistent with each other.
Key formulas for cache memory
| Quantity | Formula | Symbols and units |
|---|---|---|
| Number of lines | lines = cache size ÷ block size | bytes ÷ bytes |
| Number of sets | sets = lines ÷ n | n = associativity (ways) |
| Offset bits | log2(block size) | bits |
| Index bits | log2(sets) | bits |
| Tag bits | address bits − index bits − offset bits | bits |
| AMAT | hit time + miss rate × miss penalty | cycles or ns |
| Two level AMAT | hit time L1 + miss rate L1 × (hit time L2 + miss rate L2 × miss penalty L2) | cycles; miss rate L2 is local |
Cache memory interview and viva questions
- What is cache memory? A small, fast SRAM memory between the processor and main memory that holds copies of recently used blocks so most accesses avoid the slow DRAM.
- What is the difference between direct mapped and set associative caches? In a direct mapped cache each block has one possible line; in an n way set associative cache it maps to one set and may use any of n lines there, which reduces conflict misses.
- How is a memory address divided for cache lookup? Into a tag, an index that selects the set, and a block offset that selects the byte within the block.
- What is the difference between write through and write back? Write through updates the next level on every write; write back updates only the cache and writes the dirty block out when it is evicted.
- What are the three Cs of cache misses? Compulsory misses on first access, capacity misses when the working set is too large, and conflict misses when too many blocks map to one set.
Related reading
Frequently asked questions
Why is cache memory faster than main memory?
Caches are built from SRAM placed on the processor chip, close to the core, while main memory is DRAM on separate chips reached over a memory bus. SRAM needs no refresh and is faster per access, but it uses more transistors per bit, so it is more expensive and caches are kept small.
What is the difference between a cache hit and a cache miss?
A hit means the requested address is already held in the cache, so the data is returned in the hit time. A miss means it is not, so the cache must fetch the whole block containing that address from the next level down, which adds the miss penalty before the processor can continue.
Is a larger cache always better?
Not always. A larger cache lowers capacity misses, but it also takes more chip area and power and usually has a longer hit time. That is why processors use a small, fast L1 cache backed by larger and slower L2 and L3 caches instead of one big cache.
References
- J. L. Hennessy and D. A. Patterson, Computer Architecture: A Quantitative Approach, 6th ed., Morgan Kaufmann, 2017, Chapter 2 and Appendix B: Review of Memory Hierarchy
- D. A. Patterson and J. L. Hennessy, Computer Organization and Design, RISC-V Edition, 2nd ed., Morgan Kaufmann, 2020, Chapter 5: Large and Fast, Exploiting Memory Hierarchy
- W. Stallings, Computer Organization and Architecture, 11th ed., Pearson, 2019, Chapter 4: Cache Memory
- A. J. Smith, Cache Memories, ACM Computing Surveys, vol. 14, no. 3, 1982
- M. D. Hill and A. J. Smith, Evaluating Associativity in CPU Caches, IEEE Transactions on Computers, vol. 38, no. 12, 1989
Get one engineering email a week
New articles, worked examples and study notes every week. Free, no spam, unsubscribe any time.