Fast, Small, and Essential: Understanding Computer Cache Architecture
Cache memory is a small, fast memory placed between the CPU and main memory. It exploits the principle of locality of reference, significantly reducing average memory access time and improving overall system performance.
Faster than Main Memory
Typical Hit Rate
Words Capacity Range
Analysis of typical programs reveals two key patterns that make cache memory effective:
Recently accessed memory locations are likely to be accessed again soon
Memory locations near recently accessed locations are likely to be accessed
Program loops repeatedly access the same instructions and data
Programs spend 90% of time executing only 10% of code
When the CPU needs data:
Average Access Time = Cache Time Γ Hit Rate + Main Memory Time Γ Miss Rate
Example: With 10ns cache, 1000ns main memory, and 90% hit rate:
Average = 10Γ0.9 + 1000Γ0.1 = 109ns (much better than 1000ns!)
Cache memory stores blocks of words rather than individual words. Block sizes vary from one word to about 16 words. When a miss occurs, the entire block containing the requested word is transferred from main memory to cache.
Why blocks? This exploits spatial locality - if you need one word, you'll likely need nearby words too!
Three primary methods organize how main memory addresses map to cache locations:
Most Flexible
β’ Any block can go anywhere in cache
β’ Full address stored as tag
β’ All tags searched simultaneously
β’ Highest hit rate
β’ Most expensive hardware
Simplest & Fastest
β’ Each block has exactly one cache location
β’ Address = Tag + Index + Word
β’ Fast and simple
β’ Lower hit rate
β’ Conflicts if same index needed
Best Compromise
β’ Cache divided into sets
β’ Block can go in any location within set
β’ Combines benefits of both methods
β’ 2-way, 4-way, 8-way common
β’ Balanced cost and performance
| Mapping Type | Address Components | Search Method |
|---|---|---|
| Associative | Tag (full) + Word | Search all tags in parallel |
| Direct | Tag + Index + Word | Direct index lookup, compare one tag |
| Set-Associative | Tag + Set Index + Word | Index to set, search tags within set |
Updates both cache and main memory simultaneously
Advantages:
Disadvantage: Slower because every write waits for main memory
Updates only cache initially, writes to memory only when block is replaced
Advantages:
Implementation: Uses "valid bit" to track if cache block has been modified
When cache is full and a new block is needed, which block should be replaced?
Simplest method - randomly select a block to replace
First In, First Out - replace oldest block in cache
Least Recently Used - most common, best performance
LRU Performance: Selects the item that has been unused for the longest time. Both FIFO and LRU algorithms provide similar hit rates, with LRU having a slight advantage as set size increases.
When power is applied to the computer or when programs are loaded:
Important: The introduction of a new word automatically replaces invalid data. Thus initialization conditions are restored during normal operation.
System Configuration:
Performance Calculation:
Average access time = (0.9 Γ 10ns) + (0.1 Γ 1000ns) = 9ns + 100ns = 109ns
Result: Nearly 10Γ faster than accessing main memory directly! This is why cache is crucial for modern computer performance.
Cache sits between fast CPU and slower main memory, providing optimal balance
Programs naturally exhibit temporal and spatial locality, making cache effective
Associative = flexible, Direct = fast, Set-Associative = balanced compromise
Write-through = safer, Write-back = faster for typical workloads