Cache Memory & Locality
Cache is the secret sauce that makes modern computers feel fast! It's a small amount of very fast memory that sits between the CPU and main memory, storing frequently accessed data for quick retrieval.
How Cache Works
Cache Operation Flow
+---------------------------------------------+
| |
| CPU wants to access data |
| | |
| v |
| +-------------+ |
| | Cache | |
| | Lookup | |
| +------+------+ |
| | |
| +----+----+ |
| | | |
| v v |
| HIT! MISS! |
| | | |
| v v |
| Return Fetch from |
| data main memory |
| | | |
| v v |
| +------+ +------+ |
| | Update | | Store in| |
| | Cache | | Cache | |
| +------+ +------+ |
+---------------------------------------------+
Principles of Locality
Cache works because programs exhibit locality:
- Temporal Locality: If you access a location, you'll likely access it again soon
- Spatial Locality: If you access a location, you'll likely access nearby locations soon
Temporal vs Spatial Locality
+---------------------------------------------+
| |
| Temporal Locality Example: |
| for (i = 0; i < N; i++) { |
| sum += data[i]; // data[i] reused |
| } |
| |
| Spatial Locality Example: |
| int data[100]; |
| for (i = 0; i < 100; i++) { |
| data[i] = 0; // adjacent elements |
| } |
+---------------------------------------------+
Cache Performance Metrics
- Hit Rate: Percentage of accesses found in cache (typically 95-99%)
- Miss Rate: Percentage of accesses not found in cache (1-5%)
- Hit Time: Time to access cache (typically 1-4 CPU cycles)
- Miss Penalty: Time to fetch from main memory (typically 100+ cycles)
Even a small miss rate improvement can dramatically improve performance because miss penalties are so high!
Cache Organization
Cache is organized into blocks (also called cache lines), typically 64 bytes. When data is fetched from main memory, an entire block is loaded into cache, exploiting spatial locality.
Cache Block Structure
+---------------------------------------------+
| |
| Cache Block (64 bytes typical) |
| +-------------------------------------+ |
| | Tag | Index | Offset | Data | |
| | | | | (64 bytes) | |
| +-------------------------------------+ |
| |
| Tag: Identifies which memory block |
| Index: Which cache block to check |
| Offset: Byte within the block |
+---------------------------------------------+