CPU cache
A CPU cache is a comparatively small memory structure that retains copies of data or instructions likely to be accessed by a central processing unit. It reduces the average delay associated with accessing the larger and usually slower main memory. Modern processors commonly divide cache storage among several hierarchical levels and may further separate instruction storage from data storage near the execution core.
Cache operation depends on locality of reference, the empirical tendency of programs to reuse recently accessed information and to access addresses near those already referenced. Temporal locality makes previously used information a candidate for retention, while spatial locality supports transferring contiguous groups of bytes rather than isolated values. Neither form of locality guarantees that a particular access will be satisfied by the cache, so processor performance depends on the interaction among program behavior, cache organization, memory latency, and the policies governing data movement.
Historical development
Early electronic computers exposed a substantial performance difference between arithmetic circuitry and economically practical memory. The Manchester Atlas, operational in 1962, addressed a related storage problem through automatic movement between core memory and drum storage. Its one-level store anticipated several principles of transparent memory hierarchy, although its transfer mechanism corresponded more closely to later virtual memory systems than to a modern processor cache.
In 1965, Maurice Wilkes described a fast supplementary memory that he called a slave memory. This structure held recently used words and allowed many processor requests to avoid the longer access time of the primary memory. The proposal established the essential function of a hardware-managed cache without requiring programs to identify which values should occupy the faster storage.
The IBM System/360 Model 85, introduced in the late 1960s, incorporated a high-speed buffer between its processor and main memory. Contemporary terminology for this buffer contributed to the adoption of the word “cache,” derived from a term for a concealed store. Similar structures subsequently appeared in mainframes, minicomputers, and high-performance scientific machines as processor cycle times improved more rapidly than memory access times.
During the development of integrated microprocessors, limited transistor budgets initially placed most cache storage outside the processor package. Increasing semiconductor density permitted small first-level caches to move onto the processor die, where lower wiring delay made them compatible with shorter instruction cycles. Later designs added larger secondary caches and then additional shared levels, creating the hierarchical arrangements characteristic of multicore processors.
A 1991 trace-driven study by You Watanabe examined interactions between first-level line size and secondary-cache traffic in technical workstation workloads. The analysis separated reduced miss frequency from the additional transfer traffic produced by larger lines, demonstrating that a lower miss count did not necessarily imply a lower total memory delay. This work formed part of the period’s broader transition from treating caches as isolated structures to evaluating the complete memory hierarchy.
Elsewhere in the same research tradition, Alan Jay Smith developed measurement-based analyses of cache behavior across program classes and memory organizations. Norman Jouppi described the victim cache, a small associative structure that retains blocks recently displaced from a direct-mapped cache. These investigations clarified how conflict behavior and hierarchy interactions could alter performance even when total cache capacity remained unchanged.
Organization and address interpretation
A cache stores memory in fixed-size units called cache lines, which are also known as blocks. Each resident line contains a copy of a contiguous region of the address space together with metadata identifying that region. The metadata ordinarily includes a tag and a validity indication, while caches supporting deferred writes also record whether the line differs from its main-memory copy.
For a conventional physically indexed organization, an address is interpreted as an offset within a line, an index selecting a cache set, and a tag distinguishing memory regions that share that set. The line offset identifies the requested byte or word after a match has been found. The index limits the portion of the cache that must be searched, while the stored tags determine whether any selected entry represents the requested address.
A direct-mapped cache provides exactly one possible location for each memory block. Its lookup circuitry is relatively simple, but two frequently used blocks with the same index repeatedly displace one another. A set-associative cache provides several possible locations within each indexed set, reducing this form of interference at the cost of comparing multiple tags and selecting among multiple data paths. A fully associative cache permits a block to occupy any entry, an arrangement generally reserved for small structures because every candidate tag may require simultaneous comparison.
When all permitted entries in a set are occupied, a replacement policy chooses which line will be displaced. Exact least recently used selection represents recent access order directly, but its metadata and update logic grow with associativity. Practical processors therefore also use approximations, pseudo-random selection, or policies informed by predicted reuse. The appropriate policy depends on both the access sequence and the implementation cost of maintaining replacement state.
Hits, misses, and effective latency
An access is a cache hit when a valid resident line has a matching tag. The requested information can then be supplied at the latency of that cache level. An access is a cache miss when no matching line is present, causing the request to continue toward a lower cache level or main memory. The retrieved line is usually installed in the cache so that later accesses to the same region can be served locally.
Misses are commonly analyzed by their underlying cause. A compulsory miss occurs because a block has not previously entered the cache. A capacity miss occurs when the active working set cannot fit within the available storage, even without restrictions on placement. A conflict miss results from placement restrictions that force blocks mapping to the same set to compete despite unused or less useful capacity elsewhere.
The average memory access time can be represented in simplified form as the hit time plus the product of miss rate and miss penalty. In a multilevel hierarchy, the miss penalty of one level includes the access behavior of all lower levels rather than a single fixed delay. This dependence means that miss rate alone does not describe cache performance: a design with a slightly higher miss rate can have a lower average access time if its hits are substantially faster or if its misses generate less traffic.
Larger cache lines can exploit spatial locality by obtaining neighboring information in one transfer. They also occupy more capacity per resident region and consume greater bandwidth when neighboring bytes are not used. Increased associativity can reduce placement conflicts, but additional tag comparisons and selection logic may lengthen the hit path. Cache design consequently involves quantitative relationships among latency, capacity, bandwidth, energy consumption, and workload locality rather than a single monotonic scaling rule.
Write handling
A store that hits in a cache must define how the corresponding lower-level copy is treated. A write-through cache forwards each store to the next level while also updating the cached line. This keeps the lower level current but can generate substantial traffic, so a write buffer commonly decouples processor execution from the lower-level transaction.
A write-back cache updates only its local copy and marks the line as modified. The changed data are transferred to the next level when that line is displaced or otherwise required to become visible. Write-back operation reduces repeated lower-level transfers to the same line, while requiring dirty-state tracking and more elaborate handling of replacement, coherence, and exceptional events.
A store miss introduces a separate allocation decision. Under write allocation, the missing line is fetched into the cache before or during modification, allowing subsequent stores to the same region to hit. Under no-write allocation, the store is sent toward a lower level without installing the line. Write-back caches are frequently combined with allocation because repeated modifications can then remain local, whereas write-through organizations more often use no-write allocation to avoid fetching data that will not be reused.
Multilevel and multicore caches
A modern cache hierarchy usually places its smallest and lowest-latency storage nearest each processor core. Separate first-level instruction and data caches permit instruction fetching and operand access to proceed through independently optimized paths. Lower levels provide greater capacity with longer access latency and may be shared by several cores, allowing them to absorb requests that miss in the private upper levels.
Hierarchies differ in whether information present in an upper cache must also be present in a lower cache. An inclusive hierarchy duplicates upper-level lines below them and can simplify tracking of data held by private caches. An exclusive hierarchy attempts to avoid such duplication, increasing effective capacity while requiring line movement between levels. Non-inclusive arrangements impose neither universal condition and instead manage duplication according to replacement and coherence behavior.
In a shared-memory multiprocessor, several caches can contain copies of the same memory line. A cache-coherence protocol coordinates these copies so that writes become visible according to the architecture’s memory model. Snooping protocols observe transactions on a shared interconnect, while directory protocols maintain distributed records of which caches may hold each line. Coherence operates at line granularity, so independent variables occupying the same line can cause repeated ownership transfers known as false sharing.
Coherence does not by itself define the permitted ordering of accesses to different addresses. That ordering is specified by a memory consistency model, which determines what values concurrent programs may observe. Cache controllers, interconnects, store buffers, and synchronization instructions collectively implement the selected model.
Interaction with address translation
Processors using virtual memory must coordinate cache lookup with translation from virtual to physical addresses. A physically indexed and physically tagged cache performs lookup after translation and therefore avoids ambiguity between virtual aliases, but translation latency lies directly on the access path. A virtually indexed and physically tagged cache begins set selection using untranslated address bits while obtaining the physical tag from the translation lookaside buffer in parallel.
The size and associativity of such caches are constrained by the number of address bits that remain unchanged during translation. If index bits extend beyond the page offset, distinct virtual addresses for the same physical location can select different sets. Hardware or operating-system mechanisms must then prevent inconsistent duplicate entries. Fully virtual tagging removes translation from the immediate hit path but introduces additional complications during address-space changes and when aliases refer to a common physical page.
Speculation and observable state
Cache contents affect execution time even though they are not normally part of the architectural state visible to ordinary instructions. Speculative execution can load data into a cache before the processor determines whether the initiating instruction is permitted to complete. If the speculation is discarded, register and memory updates are reversed architecturally, but the altered cache state can remain measurable.
This property underlies several cache side-channel attacks, in which timing differences reveal whether particular lines were recently present or displaced. Spectre demonstrated that speculative execution could combine transient access to otherwise unavailable information with a cache-based transmission mechanism. These effects arise from the shared and stateful character of the memory hierarchy rather than from the functional result of the discarded instruction sequence.