Part 3 of 6 · 2 min read
Effective access time
In plain words: How much do the misses cost on average? The effective access time (EAT) answers this. It is the average time of one memory access, weighted by how often each case happens. With a hit ratio h:
EAT = h × (time of a hit) + (1 − h) × (time of a miss)
The numbers below are made up to show the idea. A memory access takes 100 ns. A TLB lookup takes 10 ns. A hit costs the lookup plus one access: 10 + 100 = 110 ns. A miss costs the lookup, then the page table reads, then the data access. With one table level, a miss costs 10 + 100 + 100 = 210 ns. With four levels, it costs 10 + 4 × 100 + 100 = 510 ns.
| Hit ratio | EAT, one level | Slowdown over 100 ns | EAT, four levels | Slowdown over 100 ns |
|---|---|---|---|---|
| 99% | 111 ns | 1.11 | 114 ns | 1.14 |
| 98% | 112 ns | 1.12 | 118 ns | 1.18 |
| 80% | 130 ns | 1.30 | 190 ns | 1.90 |
| 50% | 160 ns | 1.60 | 310 ns | 3.10 |
Check one cell by hand: four levels at 98% gives 0.98 × 110 + 0.02 × 510 = 107.8 + 10.2 = 118 ns. At 80%, it is 0.8 × 110 + 0.2 × 510 = 88 + 102 = 190 ns.
Two points follow from the table. First, at a hit ratio of 98% or better, the slowdown is under 20% even with four levels, so the TLB hides most of the cost. Second, the cost of a miss grows with the number of levels, so a low hit ratio hurts a deep tree much more than a shallow one: at 50%, four levels triple the access time. A program that scatters its accesses across many pages is the one that suffers.
Effective access time
The effective access time is the average time of one memory access, found by adding the time of each case multiplied by the share of accesses that fall into it; with a TLB, it is the hit ratio times the hit time plus the miss ratio times the miss time.
Example: with a 98% hit ratio, a hit time of 110 ns and a miss time of 510 ns, the effective access time is 118 ns.
Check yourself: 1. Compute the EAT for a 95% hit ratio, a 110 ns hit and a 210 ns miss. 2. Why does a deeper tree make a low hit ratio worse? 3. What is the miss time with three levels, a 10 ns lookup and a 100 ns access?