Cache Performance and Average Memory Access Time
A processor that executes an instruction every cycle is useless if every load stalls for a hundred cycles. Cache performance analysis exists to answer one blunt engineering question. How much does memory actually slow the CPU down? And where should designers spend their transistor budget to fix it? The tool that makes this question precise is Average Memory Access Time, or AMAT. It is a single number that folds cache hit rate, hit latency, and miss penalty into one measurable quantity. Real systems live or die by this arithmetic. A server chip with a 97% L1 hit rate sounds excellent. But if a miss costs 300 cycles to reach DRAM, that stray 3% can dominate total execution time. Chip architects use AMAT-based models to decide cache sizes, associativity, prefetch depth, and the number of cache levels. They do this long before silicon is cut. Simulating every design candidate on real workloads is far too slow to explore the full design space. The big picture is a hierarchy: fast, small, expensive memory near the processor; slow, large, cheap memory far away. Cache Misses: The Three Cs classifies why misses happen. This article asks how much they cost and how that cost propagates into overall CPU time. AMAT is the bridge between a cache's miss rate — a property of the cache and the workload — and the CPU-time formula that management actually cares about: seconds per program. This article builds the AMAT formula from first principles. It extends the formula to multi-level hierarchies. It connects AMAT to CPU execution time through memory-stall cycles. It works through fully-numeric examples so the arithmetic is never left as an exercise. It closes with the pitfalls that trip up nearly every student encountering this material for the first time. In particular, it warns against the temptation to average hit rates instead of averaging times.
- AMAT = Hit Time + Miss Rate × Miss Penalty, a single number capturing average latency per memory reference.
- Miss penalty is recursive in a multi-level hierarchy: an L1 miss penalty is itself an L2 AMAT.
- CPU time = IC × (CPI_base + Memory-stall cycles per instruction) × Clock Cycle Time, linking AMAT to real seconds.
- Local vs. global miss rates matter: L2's local miss rate looks bad but its global miss rate is what affects CPU time.
- Small improvements in hit rate near 99% can matter more than large improvements near 90%, because miss penalty dominates.
- AMAT ignores overlap from out-of-order execution and non-blocking caches, so it is an approximation, not an exact stall count.
AMAT converts a cache's hit rate and miss penalty into one average latency number that predicts how memory stalls the CPU.
The idea
Average Memory Access Time (AMAT) is the expected number of cycles (or nanoseconds) a processor spends, on average, servicing one memory reference, accounting for both the common case (a hit) and the rare but expensive case (a miss). Formally, for a single-level cache: ``` AMAT = Hit Time + Miss Rate × Miss Penalty ```
Hit Time is the cycles needed to access the cache and return data when the reference is a hit — this includes index and tag comparison from Address Breakdown: Tag, Index, and Offset, way selection in a set-associative cache, and output multiplexing. Miss Rate is the fraction of references that miss, as characterized by the compulsory, capacity, and conflict taxonomy from Cache Misses: The Three Cs. Miss Penalty is the additional time needed to fetch the block from the next level of the hierarchy and deliver the requested word to the processor, on top of the hit time already paid. The formula is a weighted average over two disjoint, exhaustive outcomes of an access: hit (probability `1 − MissRate`, cost `HitTime`) and miss (probability `MissRate`, cost `HitTime + MissPenalty`). Expanding that weighted average algebraically: ``` AMAT = (1 − MissRate)·HitTime + MissRate·(HitTime + MissPenalty) = HitTime − MissRate·HitTime + MissRate·HitTime + MissRate·MissPenalty = HitTime + MissRate·MissPenalty ``` which recovers the compact formula above. This derivation matters: it shows the formula is not a heuristic but an exact expectation, provided the model's implicit assumptions hold — namely that a miss always costs a fixed, additive penalty on top of the hit path, and that memory accesses are serialized one at a time (no overlap between a miss and subsequent accesses). Both assumptions are approximations in real out-of-order, non-blocking-cache processors, a caveat revisited under Complexity & Correctness.
How it works
AMAT is used constructively, in three escalating steps: single-level, multi-level, and then folded into total CPU execution time.
Step 1 — Single-level AMAT. Given hit time, miss rate, and miss penalty for one cache, apply the formula directly. This is used to compare two candidate L1 designs, e.g., a smaller/faster direct-mapped cache versus a larger/slower 4-way set-associative cache.
Step 2 — Multi-level AMAT. In a hierarchy with L1, L2, and main memory, the miss penalty of L1 is itself an access to L2 — which has its own hit time and miss rate. This makes miss penalty recursive: ``` AMAT_L1 = HitTime_L1 + MissRate_L1 × MissPenalty_L1 MissPenalty_L1 = AMAT_L2 AMAT_L2 = HitTime_L2 + MissRate_L2(local) × MissPenalty_L2 MissPenalty_L2 = MemoryAccessTime ``` Two distinct miss-rate conventions appear here and must never be confused:
- Local miss rate: misses in this level ÷ accesses to this level. For L2, this only counts references that already missed in L1.
- Global miss rate: misses in this level ÷ accesses to the processor (i.e., total original references). For L2, `GlobalMissRate_L2 = MissRate_L1 × LocalMissRate_L2`.
Local miss rate at L2 looks alarmingly high (L2 only sees the hard references L1 already filtered), but the global miss rate — the one that actually determines how often main memory is touched per instruction — is small because it is scaled down by L1's miss rate. This distinction is a favorite exam trap and is treated explicitly in Common Pitfalls.
Step 3 — Folding AMAT into CPU time. The CPU-time equation from basic performance analysis is: ``` CPU time = Instruction Count × CPI × Clock Cycle Time ``` Memory stalls extend the effective CPI. Define `CPI_base` as the CPI assuming perfect memory (every access is a hit, or memory time is already inside `CPI_base`'s pipeline model), and add stall cycles per instruction: ``` CPI_stall = CPI_base + Memory-stall cycles per instruction Memory-stall cycles per instruction = Memory accesses per instruction × Miss Rate × Miss Penalty ``` If `HitTime` is already counted inside `CPI_base` (a common convention: every access, hit or miss, first pays the pipeline's normal load/store cycle), then only the extra miss penalty needs adding, exactly mirroring the `MissRate × MissPenalty` term in AMAT — reinforcing that AMAT and stall-cycle accounting are the same idea viewed from two angles. ``` CPU time = IC × (CPI_base + Mem accesses/instr × MissRate × MissPenalty) × Clock Cycle Time ```
Algorithm: computing AMAT and CPU time for an n-level hierarchy
``` function AMAT(levels, mem_access_time):
# levels[i] = (hit_time_i, local_miss_rate_i), i = 0 (closest to CPU) .. n-1
# mem_access_time = time to service a miss at the last level (main memory) n = length(levels) penalty = mem_access_time # base case: penalty beyond the last cache level for i from n-1 down to 0: hit_time_i, miss_rate_i = levels[i] amat_i = hit_time_i + miss_rate_i * penalty penalty = amat_i # this level's AMAT becomes the next-outer miss penalty return amat_i # after the loop, amat_i is AMAT at level 0 (L1) function CPU_TIME(instruction_count, cpi_base, mem_accesses_per_instr, global_miss_rate_L1, miss_penalty_L1, clock_cycle_time): stall_cycles_per_instr = mem_accesses_per_instr
- global_miss_rate_L1
- miss_penalty_L1
cpi_effective = cpi_base + stall_cycles_per_instr return instruction_count cpi_effective clock_cycle_time ``` The loop in `AMAT` runs from the innermost level (main memory, treated as a fixed access time with no further miss) outward to L1, because each level's miss penalty depends on the next level's AMAT — a bottom-up dynamic-programming pattern, not a coincidence. Running it top-down would require the answer before it is computed.
Complexity & correctness
Time complexity of the computation itself. Computing AMAT for an n-level hierarchy requires exactly one pass over the levels, from innermost to outermost, doing constant work per level: `O(n)` arithmetic operations. This is trivial computationally — AMAT is not an algorithm that processes data at runtime, but a closed-form performance model evaluated once at design time (or repeatedly across design points during design-space exploration, where `n` is at most 3–4 in essentially all real hierarchies, so the cost is effectively constant).
Space complexity. `O(n)` to store per-level hit times and miss rates; `O(1)` additional working memory for the recursion, since each level's AMAT is consumed immediately as the next level's miss penalty and need not be retained.
Correctness argument. The single-level formula was derived above as an exact expectation over the two-outcome partition {hit, miss}; this is not an approximation but algebra, given the model's cost assumptions. The multi-level extension is correct by induction on hierarchy depth:
- Base case (n = 1, i.e., just main memory beyond the last cache): the "AMAT" of main memory is simply its access time, since there is no further miss to account for — trivially correct as a degenerate one-outcome case.
- Inductive step: assume `AMAT_{i+1}` correctly represents the expected time to service a reference that has already missed at level i and must be satisfied from level i+1 onward. Level i's miss penalty is, by definition, exactly the expected time to service such a reference — which is `AMAT_{i+1}`. Substituting into the single-level formula for level i gives a correct `AMAT_i` by the same two-outcome expectation argument used in the base case. By induction, `AMAT_1` (the AMAT seen by the CPU) is correct for any hierarchy depth.
Honesty about assumptions and tradeoffs. The model's exactness rests on assumptions that real hardware routinely violates: 1. Fixed, additive miss penalty. Real DRAM latency varies with row-buffer hits/misses, bus contention, and refresh timing; AMAT uses a single average miss penalty, smoothing over this variance. 2. Serialized accesses. AMAT assumes each memory reference is fully resolved before the next begins. Modern non-blocking caches and out-of-order execution allow multiple outstanding misses (memory-level parallelism), so the effective stall seen by the CPU can be less than AMAT predicts, because miss latencies overlap rather than add. 3. Uniform treatment of loads and stores. Write policies (write-through/write-back, write-allocate/no-write-allocate — see Cache Write Policies) change the effective miss penalty for stores versus loads; a precise CPU-time model separates read miss rate/penalty from write miss rate/penalty rather than using one blended number. 4. No prefetching. Hardware or software prefetches can convert what would be a demand miss into a hit, effectively lowering the miss rate term below what static workload analysis alone would predict. Because of these simplifications, AMAT is best understood as a first-order performance model: extremely useful for comparing design points and reasoning about where bottlenecks lie, but not a cycle-accurate substitute for simulation on real, overlapping, out-of-order hardware.
Worked example
Consider a system with these measured parameters, and compute AMAT, then CPU time, then compare two design options.
Base system. Split L1 (already resolved into one effective miss rate for simplicity), unified L2, and main memory:
| Parameter | Value |
|---|---|
| L1 hit time | 1 cycle |
| L1 miss rate (local = global, since L1 is first level) | 4% |
| L2 hit time | 12 cycles |
| L2 local miss rate | 25% |
| Main memory access time | 100 cycles |
| CPI_base (no memory stalls, hit time already folded into base pipeline) | 1.0 |
| Memory accesses per instruction | 1.3 (includes instruction fetch + data references) |
| Clock cycle time | 0.4 ns (2.5 GHz) |
| Instruction count | 10⁹ |
Step 1 — AMAT bottom-up. ``` AMAT_L2 = HitTime_L2 + LocalMissRate_L2 × MemAccessTime = 12 + 0.25 × 100 = 12 + 25 = 37 cycles AMAT_L1 = HitTime_L1 + MissRate_L1 × AMAT_L2 = 1 + 0.04 × 37 = 1 + 1.48 = 2.48 cycles ``` So the average memory reference costs 2.48 cycles, despite the fast path being only 1 cycle — the rare-but-expensive misses through two levels drag the average up by nearly 1.5 cycles.
Step 2 — Global miss rate check. L2's global miss rate is `MissRate_L1 × LocalMissRate_L2 = 0.04 × 0.25 = 1%`. Only 1% of all CPU references ever reach main memory — even though L2's local miss rate (25%) looks large, because L2 is a filter applied only to the hard 4% that L1 already failed to satisfy.
Step 3 — CPU time. ``` Memory-stall cycles/instr = MemAccesses/instr × (AMAT_L1 − HitTime_L1) [since HitTime_L1 is already counted in CPI_base] = 1.3 × (2.48 − 1) = 1.3 × 1.48 = 1.924 cycles/instruction CPI_effective = CPI_base + Memory-stall cycles/instr = 1.0 + 1.924 = 2.924 CPU time = IC × CPI_effective × Clock Cycle Time = 10^9 × 2.924 × 0.4 ns = 1.1696 seconds ``` Memory stalls nearly triple the effective CPI (1.0 → 2.924) — this system is heavily memory-bound, a common real-world finding.
Step 4 — Compare a design change. Suppose an architect doubles L2 size, which historically tends to cut local miss rate roughly in half but adds 3 cycles of hit latency (bigger SRAM arrays are slower to access): ``` New L2: HitTime_L2 = 15, LocalMissRate_L2 = 12.5% AMAT_L2' = 15 + 0.125 × 100 = 15 + 12.5 = 27.5 cycles AMAT_L1' = 1 + 0.04 × 27.5 = 1 + 1.1 = 2.1 cycles Stall cycles/instr' = 1.3 × (2.1 − 1) = 1.3 × 1.1 = 1.43 CPI_effective' = 1.0 + 1.43 = 2.43 CPU time' = 10^9 × 2.43 × 0.4 ns = 0.972 seconds ``` Speedup = `1.1696 / 0.972 ≈ 1.203×` — a 20.3% speedup from the larger L2, despite its slower hit time, because the reduction in miss rate dominates the increased hit latency. This is exactly the kind of tradeoff AMAT is built to evaluate quantitatively rather than by intuition alone.
Common pitfalls & traps
| Pitfall | Why it happens | Fix |
|---|---|---|
| Averaging miss rates across levels instead of averaging times | Feels natural to add percentages | Always compute AMAT bottom-up; miss penalty of one level is the AMAT of the next, not its miss rate |
| Confusing local and global miss rate for L2/L3 | Both are called "miss rate" in casual speech | Global = misses ÷ total CPU references; local = misses ÷ references reaching that level. Always state which one a formula uses |
| Double-counting hit time in the CPU-time formula | Some textbook conventions bake hit time into CPI_base, others don't | Explicitly state the convention before plugging numbers; use `(AMAT − HitTime)` as the stall term when hit time is already in CPI_base |
| Treating AMAT as literal wall-clock stall cycles under out-of-order execution | AMAT assumes serialized, blocking accesses | Recognize AMAT as an upper-bound/first-order estimate when non-blocking caches and MLP are present |
| Forgetting "memory accesses per instruction" includes instruction fetch, not just loads/stores | Focusing only on data references | Count fetch + loads + stores per instruction, typically > 1 even without memory-heavy code |
| Ignoring separate read/write miss penalties under write-back vs. write-through policies | Blending all misses into one rate hides write-specific costs | Split read miss rate/penalty from write miss rate/penalty when write policy in Cache Write Policies significantly differs |
Pioneers & history
The AMAT formulation and its use in quantitative computer design is inseparable from the broader movement, in the 1980s and 1990s, to replace intuition-driven processor design with measured, formula-driven tradeoff analysis — the same movement that produced the CPU-time performance equation itself and popularized benchmarking as an engineering discipline.
Origins · 1 minJohn L. Hennessy and how this was discovered
Where this matters
Every modern general-purpose CPU — from smartphone application processors to server chips — is designed against AMAT-style tradeoffs when choosing L1/L2/L3 sizes, associativity, and latency budgets, because silicon area and power spent on cache capacity are the same resources that could go to execution units. Compiler teams use AMAT reasoning to justify loop tiling and data-layout transformations that improve locality and thus miss rate, since a compiler cannot change hit time or miss penalty but can change the miss rate term the hardware experiences. Cloud and database systems engineers use the same reasoning at a coarser grain — page cache hit rate versus disk access time follows an AMAT-shaped formula, foreshadowing the ideas developed fully in Virtual Memory: Concept and Motivation, where the "miss penalty" becomes a page fault serviced by disk or network storage and can be tens of thousands of cycles rather than hundreds. GPU and accelerator memory-system designers use AMAT-based models to decide how deep to make on-chip scratchpad or cache hierarchies before committing to a chip tapeout, since post-silicon changes are effectively impossible. Performance-engineering teams profiling real applications use measured cache miss rates (from hardware performance counters) plugged into the AMAT and CPU-time formulas to decide whether a slow application is memory-bound or compute-bound, directly guiding whether engineers should optimize data structures or optimize arithmetic.
Ask the tutor: How does AMAT change once a cache supports multiple outstanding misses (non-blocking, hit-under-miss)?
Why not just use miss rate alone to compare two cache designs?
Miss rate alone ignores the cost of a miss and the cost of a hit, both of which vary across designs. A cache with a lower miss rate but much higher hit time or miss penalty can have worse AMAT than a cache with a higher miss rate but faster access. For instance, a large but slow L2 might have a lower miss rate than a small fast L2, yet a higher AMAT overall if its hit time increase outweighs its miss rate improvement. AMAT is the correct comparison metric precisely because it weights miss rate by its actual cost in cycles, giving an apples-to-apples latency number rather than a bare probability that says nothing about time.
Does AMAT account for instruction fetch misses as well as data misses?
Yes, if computed correctly: AMAT should be evaluated per reference type or blended using "memory accesses per instruction," which typically includes one instruction fetch plus however many load/store data references that instruction performs. Many designs even use separate instruction-cache and data-cache AMATs, since I-caches and D-caches have different miss-rate behavior — I-caches tend to have very high hit rates due to sequential locality, while D-cache behavior depends heavily on the specific data access pattern. Blending them into a single "memory accesses per instruction" figure, as the CPU-time formula does, is a simplification that assumes a fixed mix, valid for a specific workload but not universal across all programs.
How does AMAT relate to the CPU-time performance equation studied earlier in architecture courses?
The CPU-time equation, `CPU time = IC × CPI × Clock Cycle Time`, treats CPI as a single number capturing all cycles per instruction, including any stalls. AMAT explains where the memory-stall component of that CPI comes from: `CPI = CPI_base + MemAccesses/instr × MissRate × MissPenalty`. In effect, AMAT decomposes the memory-related portion of CPI into hit time (already inside CPI_base) and miss penalty amortized by miss rate, so the two formulas are not competitors but different zoom levels of the same underlying accounting of cycles spent per instruction.
Why does a small increase in hit rate near 99% matter more than a large increase near 90%?
Because AMAT's miss-rate term is multiplied by miss penalty, and miss penalty is typically large (tens to hundreds of cycles). Going from 90% to 95% hit rate cuts miss rate from 10% to 5% — a reduction of 5 percentage points. Going from 99% to 99.5% hit rate cuts miss rate from 1% to 0.5% — only 0.5 percentage points, seemingly smaller. But in relative terms both are 50% reductions in miss rate, and since miss penalty stays roughly fixed, the AMAT reduction is proportionally the same. The real subtlety is that near very high hit rates, engineering effort (associativity, larger arrays, prefetching) often yields diminishing absolute miss-rate gains, so each remaining percentage point of miss rate becomes progressively harder and more expensive to eliminate, even though its impact on AMAT per unit is unchanged.
Is AMAT the same thing as average latency measured by hardware performance counters?
Not exactly. Hardware performance counters measure actual observed cycles, which already reflect real-world effects like memory-level parallelism, prefetching, and contention that the idealized AMAT formula assumes away. AMAT is a predictive model used at design time or for back-of-envelope reasoning, built from separately measured or estimated hit time, miss rate, and miss penalty. Performance counters, in contrast, report empirical outcomes on real silicon running real workloads. The two should be reasonably close for simple in-order, blocking-cache designs, but can diverge substantially on aggressive out-of-order machines, which is precisely why simulation and hardware measurement remain necessary complements to hand-computed AMAT.
Why is local miss rate reported at all, if global miss rate is what matters for CPU time?
Local miss rate is still useful diagnostically: it tells a cache designer how well that specific level is performing on the traffic it actually receives, independent of how much traffic upper levels filtered out. A high local L2 miss rate is not automatically bad — it may simply mean L1 already absorbed the easy, high-locality references, leaving L2 with the genuinely hard working-set-exceeding accesses. Global miss rate is what determines actual CPU-time impact, so it is the correct metric for cross-level or cross-design CPU-time comparisons, but local miss rate remains the right metric for judging whether a specific cache level's own design (size, associativity) is well-matched to the traffic pattern it receives.
Does AMAT change if the write policy is write-back versus write-through?
Yes — write policy changes the effective miss penalty and sometimes the effective miss rate experienced by store instructions, as covered in Cache Write Policies. Write-through caches send every store to the next level (often buffered), which can add sustained traffic that competes with miss-driven traffic and effectively increases effective miss penalty under contention. Write-back caches only write to the next level on eviction of a dirty block, but a dirty-block eviction on a miss requires writing back the old block before or while fetching the new one, which can increase the effective miss penalty for that particular miss. A fully rigorous AMAT model separates read AMAT and write AMAT rather than blending them, especially when write policy differences are significant.