Cache (computing)

A store of selected information kept for faster reuse. A translation lookaside buffer is a memory cache of address translations; a buffer cache instead holds device-block contents.

For a data memory cache, the useful bargain is to keep a small selection of computer memory close to the CPU. A cache hit serves a read from that selection; a cache miss requires obtaining the contents elsewhere. Temporal locality helps a retained cache block serve repeated reads, and spatial locality helps one transferred cache line serve neighbouring bytes. Placement, capacity and LRU replacement determine whether that opportunity survives until the next read. ^[ref]

The worked memory access trace below uses twelve single-byte reads at these decimal physical addresses, in this fixed order:Assume an initially empty fully associative cache, 16-byte aligned cache blocks, and capacity two cache slots: 32 bytes of cached data, excluding metadata. Use exact LRU replacement, refreshing recency on every read, including cache hits. Every cache miss fetches its requested cache line completely before the next read; only a full memory cache needs an eviction. There are no writes, fetching ahead of requests, external invalidations, or overlapping reads. All addresses denote ordinary cacheable computer memory, and address translation is outside this model. These are deliberately synthetic assumptions, not specifications of a particular CPU.

This makes the outcome reproducible from the memory access trace, rather than from an informal impression that data are “nearby” or “recent”. The cache line geometry below identifies the requested unit; fully associative cache enumerates the resulting states; average memory access time translates the counts into a simple timing calculation.

Consistency requirements for cached copies of the same memory location, including agreement on its writes. Cache coherence does not itself impose sequential consistency across different locations.

Independent data in the same cache line cause unnecessary ownership transfers or invalidations when different CPU cores access them. A frequently written lock beside stable reader data can invalidate those data despite no logical conflict.

Loss of useful cached data because less useful data occupy the limited memory cache. Excessive cache prefetching can increase later demand cache misses by evicting useful cache lines.

A memory cache policy that sends a write miss onward without allocating the missed cache line in that level. Different levels of a cache hierarchy may use different write policies.

A memory cache policy that allocates the relevant cache line on a write cache miss. Fetching that cache line can delay a store instruction unless other mechanisms hide the delay.

Several levels of memory cache, typically combining a small low-latency first level with larger later levels. Each level reduces traffic reaching the next; local and global cache miss rates must be distinguished.

Fetching a cache line before a demand access requires it, to overlap transfer latency with useful work. A software prefetch is one way to request this; unnecessary requests can cause cache pollution.

A program-directed hint to fetch a cache line early. A useful nonblocking hint produces no destination processor register value and allows execution to continue before the transfer completes. Fault and dropping behavior depend on the specified instruction contract.

Keeping reusable copies in a cache.

A fixed-sized, aligned block of consecutive bytes transferred and tracked as a unit by a data memory cache. Here cache line and cache block name that unit of data, including its identity in backing computer memory; a resident slot holds a copy. Reading one element can bring neighbouring elements into the same cache line, exploiting spatial locality.

For a nonnegative integer physical address $a$ and a cache line size $B$ bytes, Euclidean division gives the backing cache block number $q$ and offset $d$:Here the brackets denote the floor function and $\mathrm{mod}$ gives the remainder. Cache line $q$ contains bytes at physical addresses $Bq$ through $Bq+B-1$. With $B=16$, read address 52 selects cache block 3, spanning addresses 48–63, and offset 4. Addresses 48 and 52 therefore request the same cache line; addresses 15 and 16 request different cache lines despite being adjacent.

For a cache line size $B=2^b$, the low $b$ bits give the offset. In a fully associative cache, all remaining bits identify the backing cache block as its cache tag; there are no address bits selecting a particular cache slot. An eight-bit illustration gives $52={00110100}_2$: four bits 0011 for cache block 3 and four bits 0100 for offset 4 in the binary numeral system. The eight-bit width is illustrative; the trace does not assume an actual eight-bit machine. ^[ref]

Distinguish this identity from a cache slot, which can hold different cache blocks over time. After read nine in the memory cache example, cache slot 0 contains cache line 3 and cache slot 1 contains cache line 0. Their cache tags identify 3 and 0; neither cache line number is its slot number. Some texts use “cache line” for the storage entry itself; this article reserves cache slot for that role.

A resident storage entry that can hold one cache block and metadata identifying its contents. Cache line identity belongs to backing computer memory; cache slot identity belongs to the consulted memory cache.

Metadata identifying which eligible backing cache block a valid cache slot currently holds. In the fully associative cache example, the cache tag is the full cache block number $q$; in the two-slot direct-mapped cache example, the slot supplies $q\mathrm{mod}2$ and the cache tag can store $\lfloor q/2\rfloor$ using the floor function.

A request whose required data are already available in the consulted memory cache. In the read-only model of spatial locality, a requested cache block being resident is sufficient for a cache hit.

The memory access trace under memory cache has cache hits at reads 2, 4, 9, 10 and 12. Read 2, at address 4, benefits from the cache line fetched by read 1 at address 0; read 9, at address 52, benefits from read 8 at address 48. These reads use different bytes of the same cache blocks, illustrating spatial locality. Read 4 returns to address 0 while its cache block remains resident, illustrating temporal locality.

A cache hit still takes time to identify the matching cache tag and obtain the requested byte. It is relative to the particular memory cache consulted: a cache miss in one level may be a cache hit in another. The model here has one consulted level and treats a valid matching resident copy as sufficient; it makes no prediction about writes or accesses whose permissions or contents change.

The fraction of $R>0$ memory references yielding cache hits, with $H$ their count: $h=H/R$. The two-slot fully associative cache example has $h=5/12$. Count the same reference unit and consulted level for both cache hit rate and cache miss rate.

A request whose required data are unavailable in the consulted memory cache. The model in spatial locality fetches the requested cache block and evicts a resident cache line only when capacity is full.

In the fixed memory access trace under memory cache, reads 1, 3, 5 and 8 first request cache blocks 0, 2, 1 and 3: four compulsory misses, also called cold misses. Reads 6, 7 and 11 revisit cache blocks that LRU replacement has evicted: three capacity misses. Read 5 is a compulsory miss even though it also causes an eviction; a full memory cache alone does not determine the classification. The fully associative cache permits every cache block in every cache slot, so this example has no conflict misses.

For a precise comparison, run the same memory access trace through an initially empty direct-mapped cache with the same 16-byte cache lines and two cache slots, placing cache block $q$ only in slot $q\mathrm{mod}2$. Read 3 brings in cache block 2 and displaces cache block 0, leaving the other cache slot unused. Read 4 consequently misses at address 0, whereas the fully associative cache still has cache block 0. That read is a conflict miss: increasing placement freedom at the same capacity removes it. The complete direct-mapped cache trace has eight cache misses: four compulsory misses, three capacity misses and one conflict miss.

The convention here classifies each cache miss by first asking whether its cache block has ever been requested. If so, compare with an initially empty fully associative cache of the same capacity and cache line size using LRU replacement on the same memory access trace: a miss there is a capacity miss, while a hit there identifies a conflict miss in the restricted design. This makes the comparison policy explicit; “capacity” is not a claim that no other replacement choice could save that individual read. The three categories describe this read-only demand model; external invalidations or fetching ahead of requests require additional reasoning. ^[ref]

The fraction of $R>0$ memory references yielding cache misses, with $M$ their count: $m=M/R$. When each reference is classified as exactly one cache hit or cache miss, $h+m=1$; the two-slot fully associative cache example has $m=7/12$.

A repeated cache block access that misses even in the comparison fully associative cache of the same capacity and cache line size using LRU replacement. In the memory cache example these are reads 6, 7 and 11. The replacement assumption matters to this classification.

A repeated cache block access that misses in a restricted design but hits in the comparison fully associative cache of the same capacity and cache line size using LRU replacement. Read 4 of the direct-mapped cache comparison under cache miss isolates this effect while another cache slot is unused.

The additional memory access latency charged for a cache miss beyond a common lookup time in the average memory access time model. It includes obtaining the requested cache block and making the read complete; this model excludes extra costs from writes and overlapping requests.

A cache miss on the first access to a cache block in an initially empty memory cache with no fetching ahead of requests. Larger capacity cannot eliminate these first fetches; subsequent cache misses can have other causes.

A memory cache allowing any cache block to occupy any resident slot. When full, its replacement policy chooses a victim from all resident cache lines. The examples in temporal locality and spatial locality use LRU replacement, so no additional placement restriction causes eviction.

The diagram enumerates every read of the fixed memory access trace under memory cache. Keep cache slots fixed: fill the lowest-numbered unused slot first, and subsequently reuse the victim's slot. Separately list recency from least recently used to most recently used. A cache hit refreshes that recency without moving the resident data to another cache slot.

After read 3, cache block 0 is older than cache block 2. Read 4 hits cache block 0, making cache block 2 older; read 5 must therefore evict cache block 2 to load cache block 1. Omitting recency updates on cache hits would choose the wrong victim. Read 6 immediately needs the evicted cache block 2, showing that LRU replacement uses past demand rather than knowledge of future demand.

With capacity four cache slots and the same cache line size, the same memory access trace has just its four compulsory misses and eight cache hits, since all four distinct cache blocks fit. Greater capacity helps this trace, but full associativity alone does not make LRU replacement optimal. Its attraction is freedom from placement restrictions; a hardware implementation must still identify a matching cache tag among eligible entries, and exact recency tracking adds work. ^[ref]

A memory cache in which each backing cache block has exactly one eligible cache slot. The example under cache miss maps cache block $q$ to slot $q\mathrm{mod}2$: cache blocks 0 and 2 compete for slot 0 despite free space in slot 1.

The time from a memory reference's request until the requested data become available. Average memory access time averages this delay in the stated serial model; it does not directly measure whole-program runtime.

The arithmetic mean of memory access latencies. Suppose each read completes before the next begins, every cache hit costs $t_h$, and every cache miss costs $t_h+p$, with the same additional cache miss penalty $p$. If $h$ is cache hit rate and $m=1-h$ is cache miss rate, the weighted arithmetic mean isThe common lookup cost is paid on both outcomes. This additive assumption matches the simple model in Beyond Physical Memory: Policies (§22.1, equation 22.1, pp. 1–2), where main computer memory acts as a memory cache for memory pages backed by disk; here the same accounting is applied to a toy data memory cache.

Assign synthetic values $t_h=2\mathrm{ns}$ and $p=30\mathrm{ns}$. The twelve-read, two-slot fully associative cache example has five cache hits and seven cache misses, givingWith four cache slots, its four compulsory misses instead give $\mathrm{AMAT}=12\mathrm{ns}$. This comparison holds the timing costs fixed as capacity changes, which is a model assumption rather than a hardware promise.

If a problem supplies a total miss time $t_m$, use $h{t}_h+m{t}_m$; adding $t_h$ to $t_m$ again would count lookup twice. Variable cache miss penalties, multiple consulted levels, or overlapping requests require a richer timing model. Real CPU work can overlap a pending read, so this arithmetic mean cannot by itself predict program speed or stall time. ^[ref]