Memory Performance

Introduction

Memory performance often determines overall system performance — the fastest CPU in the world is only as useful as its ability to access data. This chapter covers how to measure, analyze, and improve memory system performance. The key insight: reducing average memory access time (AMAT) requires attacking both hit time and miss rate across all levels of the hierarchy.

Average Memory Access Time (AMAT)

The fundamental performance equation for the memory system:

For a multi-level hierarchy:

Worked Example

Given:

• L1: 1 cycle hit time, 5% miss rate
• L2: 10 cycle hit time, 20% local miss rate (of L1 misses)
• L3: 30 cycle hit time, 10% local miss rate (of L2 misses)
• Memory: 200 cycles

Compare to 200 cycles without any cache — 100× improvement!

Improving Memory Performance

Reducing Hit Time

• Smaller, simpler L1 cache (fast access at cost of higher miss rate)
• Way prediction (predict which way will hit, verify later)
• Virtual-indexed caches (overlap TLB access with cache access)
• Pipeline cache access (multiple cycles but pipelined)

Reducing Miss Rate

• Larger caches (reduce capacity misses)
• Higher associativity (reduce conflict misses)
• Better replacement algorithms (LRU or pseudo-LRU)
• Compiler optimizations (loop tiling, array padding)
• Prefetching (predict future accesses and load early)

Reducing Miss Penalty

• Multi-level caches (miss goes to fast L2, not slow memory)
• Write buffers (absorb write misses without stalling)
• Critical word first (deliver the needed word first, fill rest of line later)
• Early restart (start processing as soon as needed word arrives)
• Non-blocking caches (continue serving hits during a miss)

Memory Bandwidth

Bandwidth vs Latency

• Latency: Time for a single access (important for random access)
• Bandwidth: Data rate for bulk transfers (important for streaming)

You can improve bandwidth without improving latency:

• Wider buses (transfer more bits per cycle)
• Memory interleaving (overlap accesses to different banks)
• Burst mode (consecutive addresses without re-addressing)

Cache-Friendly Programming

Understanding memory performance helps write faster code:

Good: Sequential array access (spatial locality)

Bad: Strided array access (poor spatial locality)

Good: Blocking/Tiling (temporal locality)

Prefetching

Predict future memory accesses and start loading before the data is needed:

Hardware Prefetching

• Detect sequential access patterns
• Automatically prefetch the next cache line
• Stride prefetchers detect regular step patterns

Software Prefetching

• Compiler inserts prefetch instructions ahead of use
• __builtin_prefetch(addr) in C/C++
• Must prefetch early enough (but not too early or data gets evicted)

Key Takeaways

1. AMAT = Hit_time + Miss_rate × Miss_penalty — the master equation
2. Multi-level caches dramatically reduce effective AMAT (100× improvement typical)
3. Three strategies: reduce hit time, reduce miss rate, reduce miss penalty
4. Non-blocking caches allow hits during misses — overlapping latency
5. Prefetching hides latency by loading data before it's needed
6. Cache-friendly programming (sequential access, tiling) can provide 5-10× speedup
7. Memory performance often matters more than CPU speed for real-world programs