CPU Cache Organization, Locality, and Associativity
How memory addresses decompose into Tag, Index, and Offset, why spatial and temporal locality drive hit rates, and how set associativity prevents conflict misses.
1. The Memory Hierarchy and Locality of Reference
A CPU core executes instructions in less than a nanosecond, while accessing main memory (DRAM) takes ~50–100 ns (hundreds of clock cycles). To bridge this speed gap, processors place small, fast SRAM caches (L1, L2, L3) between the CPU registers and DRAM.
A small cache achieves a high hit rate because real programs exhibit locality of reference:
- Temporal Locality (Locality in Time): If a memory address is accessed once, it is likely to be accessed again soon (e.g., loop counters, stack variables, inner-loop instructions). Caches exploit this by keeping recently accessed blocks.
- Spatial Locality (Locality in Space): If an address is accessed, nearby addresses are likely to be accessed soon (e.g., stepping sequentially through an array). Caches exploit this by fetching an entire cache block (cache line) of 16, 32, or 64 contiguous bytes on every miss.
Click RESET in the simulator (default: 2 KB, 2-Way, 64-byte blocks), then click SEQ (SPATIAL) 8 times. Each click steps forward by 8 bytes (0x1000, 0x1008, 0x1010…). The first access misses and loads the entire 64-byte block (0x1000–0x103F); the next 7 accesses are all Cache Hits (87.5% hit rate).
2. Address Decomposition: Tag, Index, and Offset
Suppose a cache has capacity C bytes, block size B bytes, and associativity E (ways per set). The cache is divided into S sets:
Number of Sets S = C / (B × E)
Offset bits b = log₂(B) (selects the byte within the B-byte block)
Index bits s = log₂(S) (selects which of the S sets to inspect)
Tag bits t = AddressBits − s − b (identifies which memory block is stored)
┌──────────────────────────┬────────────────────┬────────────────────┐
│ TAG (t) │ INDEX (s) │ OFFSET (b) │
└──────────────────────────┴────────────────────┴────────────────────┘
Worked Example: Set the simulator to 1 KB (1024 B), Direct Mapped (1-Way, E = 1), and 16-Byte blocks (B = 16):
S = 1024 / (16 × 1) = 64 sets→s = log₂(64) = 6 Index bits.B = 16 bytes→b = log₂(16) = 4 Offset bits.- Now enter address
1234(hex) and click ACCESS:
The cache goes directly to Set 35, checks the Valid bit and compares the stored Tag against0x1234 = 0001 0010 0011 0100₂ = [Tag: 000100₂ = 0x4] [Index: 100011₂ = 35] [Offset: 0100₂ = 4]0x4. Now enter1238and click ACCESS: Tag is still0x4and Index is still35(only the Offset changed from 4 to 8), resulting in a Cache Hit.
3. Associativity and the Three C's of Cache Misses
Every cache miss falls into one of three categories (shown in the simulator's red status bar on every miss):
- Compulsory (Cold) Miss: The very first access to a block that has never been in the cache.
- Capacity Miss: The program's active working set of blocks is larger than the entire cache capacity.
- Conflict Miss: The cache has plenty of free space in other sets, but multiple active blocks map to the exact same Set Index and repeatedly evict each other.
Seeing Conflict Misses in the simulator:
- Set CACHE CAPACITY = 1 KB, ASSOCIATIVITY = Direct Mapped (1-Way), and click RESET.
- Click STRIDED (CONFLICTS) twice. It accesses
0x1000and0x1400(which are 1024 bytes = 1 cache size apart). Both map to Set 0! Because a Direct-Mapped cache has only 1 way per set,0x1400immediately evicts0x1000from Set 0 while Sets 1–63 remain completely empty. - Type
1000and click ACCESS: the simulator reportsCACHE MISS (Conflict). - Now change ASSOCIATIVITY to 2-Way Set Associative (2 blocks per set), click STRIDED (CONFLICTS) twice (
0x1000and0x1400), and access1000again: now it is a CACHE HIT because both blocks coexist in Way 0 and Way 1 of Set 0!
4. Replacement Policies & Average Memory Access Time (AMAT)
When all E ways in a set are valid and a miss occurs, the cache chooses a victim way using its replacement policy:
- LRU (Least Recently Used): Evicts the block whose most recent access (hit or load) is oldest. Best at exploiting temporal locality.
- FIFO (First In, First Out): Evicts the block that was loaded earliest, regardless of how recently it was hit.
- Random: Picks a random way in the set; requires no age-tracking bits in hardware.
Overall cache performance is measured by Average Memory Access Time (AMAT):
AMAT = Hit Time + (Miss Rate × Miss Penalty)
Exercises
1. A 4 KB (4096 B) cache is 4-Way Set Associative with 64-byte blocks. Calculate the number of sets, Offset bits, and Index bits, then verify in the simulator.
Show solution
S = 4096 / (64 × 4) = 16 sets.• Offset bits
b = log₂(64) = 6 bits.• Index bits
s = log₂(16) = 4 bits (Sets 0 through 15).
2. If L1 Hit Time is 1 cycle, Miss Rate is 5% (0.05), and the Miss Penalty to fetch from DRAM is 100 cycles, what is the AMAT?
Show solution
AMAT = 1 + (0.05 × 100) = 6 cycles. Even a 5% miss rate increases average memory access time by 6×.Quiz
How many sets and index bits does a 2 KB (2048 B) Direct-Mapped (1-Way) cache with 32-byte blocks have?
S = 2048 / (32 × 1) = 64 sets, and log₂(64) = 6 index bits.
Stepping sequentially through an array (a[0], a[1], a[2]…) primarily benefits from which property?
Sequential array elements lie in the same contiguous cache block, turning subsequent accesses into hits.
Two frequently used variables map to Set 0 in a Direct-Mapped cache and repeatedly evict each other while Sets 1–63 are empty. What type of miss is this?
Conflict misses occur when multiple blocks compete for the same set even though total cache capacity is not exhausted.
If Hit Time = 2 cycles, Miss Rate = 10%, and Miss Penalty = 50 cycles, what is the Average Memory Access Time (AMAT)?
AMAT = 2 + (0.10 × 50) = 7 cycles.