The Memory Gap and the Arithmetic of Average Access Time

A load instruction either produces its value from a structure a few cycles away or waits for a memory controller to finish with a DRAM row. Nothing else in a modern processor spans three orders of magnitude of latency, and almost every performance property of the machine follows from how often each case occurs. The hierarchy of caches exists to make the first case common, and the arithmetic that justifies it is small enough to do on paper.

Two technologies that cannot be combined

Static RAM holds a bit in four to six transistors and keeps it as long as power is applied. Dynamic RAM holds a bit as charge on a capacitor and needs one transistor, but the charge leaks and must be restored by a periodic refresh; reading it also destroys the value, so every access is followed by a write-back of the row. The density difference is large — a DRAM cell is roughly a tenth the area of an SRAM cell once the sense amplifiers and row wiring are accounted for — and the latency difference runs the other way. A six-transistor cell can be read in a couple of gate delays. A DRAM access has to drive a long word line, wait for charge sharing on a bit line to develop a differential, and then amplify it.

No single array is therefore both big enough to hold a program’s working set and fast enough to feed an instruction every cycle. The hierarchy is the standard resolution: a small SRAM close to the execution units, progressively larger arrays behind it, and DRAM at the bottom. Each level is roughly an order of magnitude larger than the one above and roughly two to four times slower, a ratio that has held across several decades of process generations.

On current server and desktop parts the approximate cycle counts, at a core clock of a few gigahertz, are: a register read inside the pipeline, an L1 hit in about four to five cycles, an L2 hit in ten to fifteen, an L3 hit in thirty to fifty, and a DRAM access in two hundred to three hundred and fifty. A cache line is 64 bytes on x86-64 and on most Arm implementations; some designs use 128. Capacities run from tens of kilobytes for L1 through a megabyte or two of L2 to tens of megabytes of shared L3, with DRAM three to four orders of magnitude beyond that.

The important trend is not the absolute nanoseconds but the ratio. DRAM latency in nanoseconds has improved slowly, perhaps halving over a decade, while the cycle time of the core has shrunk by more than that. Measured in cycles, the gap between a register and a row activation has widened in every generation. That is the entire reason a cache miss is treated as an event worth designing around rather than an occasional inconvenience.

One number for a whole hierarchy

The standard figure of merit is average memory access time, defined recursively. If level i has hit latency t_i and local miss rate m_i, then

$$ \mathrm{AMAT} = t_1 + m_1\left(t_2 + m_2\left(t_3 + m_3, t_{\mathrm{DRAM}}\right)\right) $$

Each level’s miss rate is local: the fraction of the accesses that reach that level and are not served by it. The fraction of original references that reach DRAM is the product of the local miss rates, the global miss rate. The distinction matters because a level-two miss rate of 20 percent sounds alarming until it is multiplied by an L1 miss rate of 5 percent, which makes it 1 percent of all references.

/* Recursive AMAT for three cache levels, using local miss rates. */
double amat(const double hit[3], const double local_miss[3], double dram)
{
    double t = dram;
    for (int i = 2; i >= 0; i--)
        t = hit[i] + local_miss[i] * t;
    return t;
}

The structure of that expression is the whole argument for a hierarchy. Put in approximate numbers for a two-level design: an L1 hit of 4 cycles, an L1 local miss rate of 5 percent, an L2 hit of 12 cycles, an L2 local miss rate of 20 percent, and DRAM at 250 cycles.

Level reached	Share of references	Latency contributed
L1 hit	95%	4 cycles
L2 hit	4%	12 cycles
DRAM	1%	250 cycles

AMAT is 4 + 0.05 × (12 + 0.2 × 250) = 4 + 0.05 × 62 = 7.1 cycles. The 1 percent of references that reach DRAM contribute 2.5 of those 7.1 cycles — a third of the total time is spent on one hundredth of the accesses. Adding a third level that catches most of the DRAM misses is worth far more than shaving a cycle off the L1, which is why real designs spend their area on the last level rather than on a marginally faster first level.

Why the required hit rate climbs with depth

The formula can be rearranged to state a requirement instead of a prediction. If a miss costs r times a hit, the average is t_hit (1 + m·r). Keeping the miss penalty below a tenth of the hit latency needs m·r ≤ 0.1. With r = 60 (250 cycles against 4), that demands a local miss rate below about 0.17 percent. No first-level cache achieves that on general-purpose code; a 5 percent local miss rate against the full DRAM penalty would add 12.5 cycles to every access, quadrupling an effective latency of four cycles.

The hierarchy rescues the arithmetic by dividing the penalty. A miss that reaches L2 pays 12 cycles instead of 250, so the effective r for the L1 decision is three, and a 5 percent miss rate costs 15 percent overhead — acceptable. The L2 then faces r ≈ 20 and needs a local miss rate near half a percent to keep its own contribution small, which is a demand it cannot meet from a megabyte. The third level faces the full DRAM penalty, which is why last-level caches are sized in tens of megabytes and built with high associativity: they are the last chance to avoid a two-hundred-cycle stall, and they see only the filtered residue that the upper levels could not hold.

There is a second constraint that the formula hides. A miss does not merely cost latency; it consumes bandwidth. Filling a 64-byte line from DRAM transfers 64 bytes, and the DRAM burst that produces it occupies the bus for a fixed number of cycles regardless of how many of those bytes the program uses. A workload with poor spatial locality can therefore be limited by the number of lines it touches rather than by the fraction of accesses that hit, and no amount of hit-rate improvement in the upper levels changes the traffic that reaches the memory controller.

Where the model stops describing hardware

The recursive average assumes one access at a time and a single outstanding miss, and neither assumption survives contact with an out-of-order core. A miss that is not the oldest instruction does not stall the machine; the scheduler continues issuing independent work, and several misses can be in flight at once. Under that regime the right model is throughput, not latency: the number of bytes the core can keep in flight, divided by the round-trip time, bounds the delivered bandwidth. A core with sixteen outstanding line fills against a 250-cycle latency sustains roughly one line per sixteen cycles no matter how fast its caches are on hits — the calculation behind miss status holding registers.

Prefetching breaks the model in a different way. If a line is fetched before the demand access arrives, the demand access hits, and the miss appears in the hit rate rather than in the latency. The average access time improves while the bandwidth consumption rises, so an AMAT figure computed without traffic counters can look better than the machine actually behaves; see stride prefetchers and prefetch distance.

The mean itself is the last problem. AMAT is an average over all references, and averages hide tails. A program whose accesses are 99 percent fast and 1 percent catastrophically slow has a reasonable AMAT and a terrible worst case; if the slow accesses are on a dependency chain, they serialise and the average stops being predictive. Real designs therefore care about the distribution of miss latencies, not only the rate, which is why the number of outstanding misses and the queueing at the memory controller enter the design before the hit rate does.

A last caveat concerns what counts as a hit. A load that hits in the L1 but misses in the TLB has already paid for a page-table walk before the cache is even consulted, and a store that hits may still wait in a store buffer. The hierarchy described by AMAT is the data path only; the address translation path that runs beside it is a separate hierarchy with its own hit rate, its own replacement policy, and its own reasons to be slow.