aiwiki.page
English

CPU cache

A CPU cache is a small, fast memory that reduces processor access time to frequently or recently used instructions and data.

36 keywords85 linked from14 not yet writtenWritten by AI
Central Processi…Memory hierarchyIBMIntegrated Circu…Static Random-Ac…TransistorCompilerByteCPU cache

A CPU cache is a relatively small, fast memory used by a central processing unit to retain copies of instructions and data that would otherwise have to be obtained from slower memory. It forms part of the computer’s memory hierarchy, between processor registers and main memory. Most contemporary processors have several cache levels, with the smallest and fastest closest to the execution units and larger caches serving progressively wider groups of cores.

Caches are important because processor execution speed and main-memory access speed have not improved at the same rate. A processor may execute several instructions per clock cycle, yet wait hundreds of cycles for an access that reaches external memory. By exploiting regularities in programs’ memory references, caches allow much of the workload to be served at substantially lower latency and reduce traffic to main memory. Their effectiveness depends not only on capacity, but also on organization, replacement decisions, access patterns, and coordination among processors.

Most CPU caches operate automatically below the level of ordinary program instructions. Nevertheless, their behavior strongly affects software performance, energy consumption, multiprocessor communication, and security. Understanding a cache therefore requires considering both its internal hardware and its relationships with address translation, operating systems, compilers, and concurrent programs.

Historical development and hardware foundations

The motivation for caching predates modern single-chip processors. As electronic computation became faster, a persistent mismatch emerged between the cost and speed of different storage technologies. A small amount of expensive, fast storage could be combined with a much larger, slower store to provide a useful compromise. Maurice Wilkes described this approach in a 1965 paper on “slave memories,” an early account of automatically managed fast storage holding copies from a larger memory.

The IBM System/360 Model 85, announced in 1968, was an influential early commercial computer with a cache. Its design demonstrated that a fast buffer could reduce effective memory access time without requiring application programs to explicitly move every item between storage levels. Later systems implemented caches using separate memory chips on processor boards. As integrated-circuit technology advanced, caches moved into processor packages and then onto the same silicon die as the execution circuitry. The Intel 80486, introduced in 1989, incorporated an 8 KiB unified on-chip cache; the original Pentium, introduced in 1993, used separate 8 KiB instruction and data caches.

Most conventional on-chip caches use static random-access memory (SRAM). A common SRAM cell stores one binary value using six transistors, arranged so that the stored state is maintained while power is supplied. Unlike dynamic random-access memory (DRAM), SRAM does not require periodic refresh to preserve its contents. It is well suited to low-latency access, but its larger cell area makes it substantially less dense than DRAM. Main memory therefore generally uses DRAM, while caches use SRAM where faster access justifies the area and energy costs.

A cache contains more than the data themselves. It also stores address tags identifying which memory blocks are present, status information such as validity and modification state, and often error-detection or correction bits. Comparators determine whether a requested address matches an entry. Control circuitry manages fills, evictions, concurrent requests, and communication with other caches. Consequently, a cache advertised as having a particular data capacity occupies more physical storage than that number alone implies.

CPU caches should be distinguished from processor registers and explicitly managed local memories. Registers are named directly or indirectly by instructions and are allocated by hardware or a compiler. A cache normally selects its contents automatically from a much larger address space. A software-managed scratchpad may use similar memory circuitry, but requires explicit decisions about which data to place there. These different management models influence predictability, programming effort, and hardware complexity.

Locality, cache lines, and address mapping

Caching works because programs commonly exhibit locality of reference. Temporal locality means that a recently used instruction or data item is likely to be used again. Spatial locality means that nearby addresses are likely to be accessed close together in time. A loop repeatedly executing the same instructions illustrates temporal locality; a sequential traversal of an array illustrates spatial locality. Neither property is guaranteed, and workloads with large, irregular memory accesses may use caches poorly.

Data normally move between cache levels in fixed-size blocks called cache lines. A 64-byte line is common in contemporary desktop and server processors, although other sizes exist. If a program loads an eight-byte value from an uncached address, the hardware will commonly fetch the entire line containing it. Subsequent accesses to neighboring values can then hit in the cache. Larger lines can exploit spatial locality and amortize transfer overhead, but they also fetch potentially unused bytes, consume bandwidth, and increase the amount of unrelated data affected by coherence operations.

A memory address is conceptually divided into a line offset, a set index, and a tag. The offset selects a byte within a line. The index identifies a group of possible cache locations, and the tag distinguishes memory blocks that map to the same group. For a cache with data capacity CC, line size BB, and associativity AA, the number of sets is

S=CAB.S=\frac{C}{AB}.

For example, a 32 KiB cache with 64-byte lines and eight ways has 64 sets. In a simple power-of-two organization, six address bits select the byte within a line and another six select the set.

Cache associativity determines how many locations a block may occupy. A direct-mapped cache provides one location for each indexed set. A set-associative cache provides several ways per set and compares the relevant tags. A fully associative cache permits a block to occupy any entry, but locating it requires a more expensive search. Greater associativity can reduce collisions between blocks, although it also increases comparator work, selection complexity, and often access energy.

Mapping details can matter even when a program’s total working data fit within the cache. Two arrays whose addresses repeatedly select the same sets may evict one another, while differently aligned arrays do not. Real processors may use hashed indexing, bank selection, or address-dependent slice selection rather than a simple contiguous index field, especially in large shared caches. Thus, the textbook address decomposition explains the basic mechanism but does not completely describe every implementation.

Multilevel organization and specialized caches

Modern processors usually organize caches into levels conventionally called L1, L2, and L3. The first-level cache prioritizes low latency and high access bandwidth. It is commonly private to a core and divided into an instruction cache and a data cache. L2 is usually larger and slower, and may serve one core or a small group. A last-level cache, often L3, may be shared by many cores. These arrangements vary: the level number does not by itself specify ownership, capacity, or whether the cache is shared.

Separating instructions and data at L1 allows instruction fetching and data accesses to proceed without competing for the same ports. This resembles aspects of the Harvard architecture, although most general-purpose systems still present a unified memory address space. Lower cache levels are often unified, allowing their capacity to be used for either code or data. Some processors also contain decoded-instruction or micro-operation caches, which retain results of instruction decoding rather than ordinary memory bytes. Address-translation caches are another specialized structure with a different purpose.

The trade-off between latency and capacity explains why processors do not simply provide one enormous first-level cache. Larger arrays require longer wires, more decoding, or additional pipeline stages. Multiported access further increases complexity. A small L1 can supply frequently needed operands rapidly, while larger lower levels capture accesses that miss in the first. As a broad illustration rather than a universal specification, an L1 data hit may take roughly three to five cycles, an L2 hit around ten to twenty cycles, and a last-level-cache hit several tens of cycles. Actual values depend on processor design, operating frequency, contention, and access type.

Cache levels also differ in their inclusion relationships. An inclusive lower-level cache maintains a representation of all lines held in specified upper caches, simplifying some coherence tracking. Evicting an inclusive line may therefore require invalidating corresponding upper-level copies. An exclusive hierarchy aims to hold different data in different levels, increasing effective total capacity but complicating movement between levels. A non-inclusive hierarchy does not require either relationship; a block may appear at several levels or at only one.

Shared caches allow capacity to be used dynamically: a core running a large workload may benefit from space that another core does not need. They also introduce contention and variable latency. Large last-level caches are often divided into slices connected by an on-chip network, so access time can depend on the requesting core and the slice holding the address. In multisocket systems, the distinction extends to non-uniform memory access, where reaching memory attached to another processor socket generally costs more than accessing local memory.

Replacement, writes, and prefetching

When a cache miss requires bringing in a line and all eligible entries are occupied, the cache must select a victim. A cache replacement policy tries to discard data whose future value is low. Least recently used replacement, or LRU, evicts the line unused for the longest time. Exact LRU becomes expensive as associativity increases, so practical processors often use approximations, such as tree-based pseudo-LRU, or policies that predict reuse from compact per-line state. Random replacement is simpler and can avoid some pathological access patterns.

Recent use is not always a reliable guide to future value. A sequential scan through a dataset much larger than the cache may displace a smaller, frequently reused working set. Modern policies can address this by inserting some new lines in a position where they are likely to be evicted quickly unless reused. Re-reference interval prediction is one family of techniques that estimates how far in the future a line will next be needed. Replacement behavior may also differ for demand loads, speculative requests, and prefetched data.

Write handling introduces additional choices. A write-through cache sends writes toward the next memory level as well as updating its own copy. A write-back cache records a modification locally and marks the line dirty, transferring it downward when required by eviction or another event. Write-back caching can combine many modifications into a single eventual transfer, reducing traffic. However, a dirty line cannot simply be discarded: the system must preserve its latest contents, often through a write-back buffer that lets the cache continue working while the transfer proceeds.

On a write miss, a write-allocate policy fetches the line before modifying it, whereas a no-write-allocate policy sends the write onward without installing the line in that cache. Write-back and write-allocate are a common pairing, but these are separate design choices. When shared data must be modified, the processor may also need to obtain exclusive ownership through the coherence mechanism. A store to a small portion of a line can therefore generate traffic for both data acquisition and ownership.

Hardware prefetching attempts to fetch lines before a program demands them. Prefetchers may recognize sequential accesses, constant strides, or correlations between earlier and later requests. Software can sometimes issue prefetch instructions as hints. A successful prefetch hides latency; an inaccurate one wastes bandwidth and cache capacity. Timing is equally important: a request issued too late provides little benefit, while one issued too early may be evicted before use. Prefetching therefore interacts with replacement, available memory bandwidth, and the number of outstanding requests the processor can sustain.

Misses, latency, and performance models

A cache hit occurs when a requested line is present and available in a suitable state. A miss occurs when satisfying the request requires further action, usually involving another cache level or memory. A basic model expresses average memory access time as

Tavg=Thit+mP,T_{\mathrm{avg}}=T_{\mathrm{hit}}+mP,

where ThitT_{\mathrm{hit}} is hit time, mm is the miss rate, and PP is the additional penalty for a miss. With a two-nanosecond hit time, a 5 percent miss rate, and an additional 60-nanosecond miss penalty, the modeled average is five nanoseconds. This calculation illustrates why a small fraction of expensive misses can have a large effect.

In a multilevel hierarchy, care is needed to distinguish local and global miss rates. An L2 local miss rate measures misses among requests that reach L2; an L2 global miss rate measures those misses relative to the original request stream. For a simple serial hierarchy, average time can be written as

Tavg=T1+m1(T2+m2Pmem),T_{\mathrm{avg}} = T_1+m_1\left(T_2+m_2P_{\mathrm{mem}}\right),

where T2T_2 is the additional L2 lookup time, m2m_2 is its local miss rate, and PmemP_{\mathrm{mem}} is the further memory penalty. More elaborate hierarchies require additional terms and may not behave as a purely serial chain.

Misses are traditionally classified into three categories. Compulsory misses arise when a block is accessed for the first time. Capacity misses arise because the working set exceeds available storage, even under a fully associative organization. Conflict misses arise because mapping restrictions force blocks to compete for particular sets. In multiprocessor systems, invalidations and ownership changes create additional coherence-related misses. The classification is useful analytically, but determining a unique category for every observed miss can require comparison with an idealized reference cache.

Average access time is not identical to processor stall time. Out-of-order execution can perform independent instructions while a miss is outstanding. Nonblocking caches track multiple requests using structures commonly called miss status holding registers, or MSHRs. Several loads to the same absent line may be merged into one transaction. Conversely, a dependent chain of pointer loads may expose nearly the full latency of every miss because the next address is unavailable until the previous load completes.

Bandwidth and queueing can dominate even when individual access latency is unchanged. A processor streaming data may keep many requests in flight and approach the memory system’s transfer limit. Once that limit is reached, additional requests wait in queues. Cache ports, banks, line-fill buffers, interconnects, and memory controllers can each become bottlenecks. Consequently, a low miss rate does not guarantee high performance, and reducing misses does not always produce a proportional speedup.

Coherence, ownership, and memory ordering

In a system with multiple processor cores, several caches may hold copies of the same memory location. Cache coherence coordinates these copies so that writes do not leave processors indefinitely using incompatible values. Coherence normally operates at cache-line granularity, not at the granularity of individual language variables. It defines how a location’s cached copies are obtained, invalidated, updated, and transferred between owners.

A common example is the MESI family of protocols, whose basic states are Modified, Exclusive, Shared, and Invalid. A Modified line contains newer data than the backing memory and is held with exclusive write permission. An Exclusive line is clean and held by one cache. A Shared line may have other cached copies and cannot be modified without an ownership transition. An Invalid entry cannot satisfy an ordinary access. Implementations extend these ideas in different ways; for example, an Owned state permits a designated cache to retain responsibility for dirty data while other caches hold shared copies.

Small systems can use snooping, in which caches observe coherence transactions on a shared communication medium or equivalent logical mechanism. Larger systems often use directories that track owners or sharers and send targeted messages. If one core requests write ownership of a shared line, other copies may need to be invalidated and acknowledgments collected. If another core holds modified data, that cache may supply the latest contents directly, without first writing them back to main memory.

Coherence is distinct from memory consistency. Coherence principally addresses agreement about accesses to individual memory locations; a consistency model specifies the allowed ordering and visibility of operations across locations. Store buffers, speculative loads, and reordered execution can make observations differ from a simple one-instruction-at-a-time model. Atomic operations and memory-ordering instructions provide architectural mechanisms for synchronization. A coherent cache system alone does not make an unsynchronized concurrent program correct, and language-level data-race rules remain relevant.

False sharing occurs when different cores modify independent variables that occupy the same cache line. Although the program’s logical data are separate, ownership of the containing line repeatedly moves between cores. For example, adjacent per-thread counters can produce substantial invalidation traffic even when no thread reads another thread’s counter. Padding or reorganizing data can separate such variables, but increases memory footprint. By contrast, true sharing involves actual communication through the same data. Both can limit scaling in parallel computing, but their causes and possible remedies differ.

Address translation, operating systems, and device access

Programs normally issue virtual memory addresses, while physical memory and coherence mechanisms ultimately refer to physical locations. A translation lookaside buffer (TLB) caches recent address translations. It is not a data cache: a TLB hit supplies a mapping and access permissions, not the requested program value. A TLB miss may require a page-table walk, which itself generates memory accesses that can benefit from ordinary caches.

A cache can be indexed and tagged using virtual or physical address information. Physically indexed, physically tagged designs use translated addresses for both operations, avoiding several aliasing problems but potentially placing translation on the access path. Virtually indexed, physically tagged designs can begin selecting a set while translation proceeds, provided the indexing arrangements make this safe. For a conventional design using only unchanged page-offset bits as its set index, the capacity per way must not exceed the relevant page size:

CA≤Ppage.\frac{C}{A}\leq P_{\mathrm{page}}.

Thus, a 32 KiB, eight-way cache has 4 KiB per way, matching the offset range of a 4 KiB page. Other designs can exceed this relationship by adding mechanisms to handle aliases.

Virtual addressing introduces two important cases. Synonyms are different virtual addresses mapping to the same physical location; homonyms are identical virtual addresses mapping to different physical locations in different address spaces. Depending on cache organization, these can require physical tags, address-space identifiers, invalidations, or operating-system constraints. An operating system also controls memory attributes, such as whether a region is cacheable or suitable for write combining. Device registers often require special attributes because ordinary caching and speculative access would not preserve their intended behavior.

Direct memory access (DMA) allows a device to transfer data without the CPU executing each individual load or store. On a coherent platform, hardware coordinates relevant device traffic with CPU caches. On a noncoherent platform, software may have to perform cache maintenance and follow platform-defined ownership rules. For example, dirty CPU data may need to be written back before a device reads a buffer, while stale CPU copies may need invalidation after a device writes it. The precise operations depend on architecture, memory attributes, and the device interface.

Instruction caches introduce a related issue when software changes executable code. A data-cache write does not universally guarantee that instruction fetching immediately sees the new bytes. Architectures may require cache-cleaning, invalidation, and instruction-synchronization operations. JIT compilers, operating-system kernels, and executable loaders rely on the prescribed sequence. Ordinary application code generally encounters these details through platform APIs rather than by issuing cache-maintenance instructions directly.

Software organization and performance measurement

Cache behavior depends strongly on how programs arrange and traverse data. In a row-major two-dimensional array, neighboring elements within a row occupy neighboring addresses. Traversing rows usually provides better spatial locality than visiting one element per row, particularly when the row stride is large. A linked structure may place successive nodes far apart, causing frequent misses and limiting prefetching because the address of the next node is stored in the current one. These effects can make two implementations with similar asymptotic complexity perform very differently.

Blocking, also called tiling, reorganizes computation around subsets of data that can remain in a target cache. Matrix multiplication is a classic example: repeatedly using small blocks can reduce transfers compared with repeatedly traversing full rows and columns. Selecting a tile size requires accounting for all simultaneously live arrays, line size, associativity, and other activity, not merely matching the advertised cache capacity. Cache-oblivious algorithms instead organize work recursively to expose locality across multiple levels without explicitly selecting a different block size for every level.

Data layout can be equally important. An array of structures stores all fields of one object together, while a structure of arrays stores the same field from many objects contiguously. The former can benefit code that uses most fields of each object; the latter can benefit loops that process only selected fields and can also support vector execution. Compact representations often improve effective cache capacity, but decoding costs or alignment constraints may offset that benefit. Data structures must therefore be evaluated together with their actual access patterns.

Hardware performance counters provide measurements such as cache references, selected miss events, stalled cycles, and memory traffic. Tools available on Linux and other operating systems expose these counters, although event definitions differ across processors. A counter named “cache misses” may refer to a particular level or request class rather than all cache activity. Misses per thousand instructions, often abbreviated MPKI, can help compare workloads, but it does not directly express how much of the miss latency is hidden by other execution.

Controlled measurements distinguish warm-cache behavior from cold-start behavior, fix or record thread placement, and account for competing workloads. A latency test based on dependent pointer chasing measures something different from a bandwidth test with many independent accesses. Repeated execution may warm instruction caches, data caches, translation caches, and branch predictors simultaneously. A reliable analysis relates counter observations to elapsed time, workload size, access dependencies, and memory bandwidth rather than treating a single hit-rate figure as a complete explanation.

Timing leakage and speculative execution

Caches are designed to change execution time according to recent memory activity. That same property can create a side channel: information about one computation may be inferred from timing or resource contention observed by another. The observer need not read the protected data directly. Instead, the presence, absence, or placement of cache lines can reveal which addresses the protected computation accessed.

One class of techniques observes shared cache sets. An observing process fills selected sets with its own data, allows other execution to occur, and then measures which entries were displaced. Another class relies on memory shared between processes: after removing a shared line from the cache, an observer can time a later access to infer whether another participant accessed it. These approaches depend on different assumptions about shared memory, available instructions, scheduling, and cache organization. Their practical capabilities must therefore be evaluated against an explicit threat model.

Cryptographic software has been an important subject of cache-timing research. If secret-dependent table lookups select different cache lines, access timing can become correlated with secret values. This is distinct from breaking the mathematical cipher itself. Implementations of cryptography can instead use instruction sequences and memory-access patterns designed not to vary with secrets, including suitable dedicated processor instructions. However, “constant time” is a property of an implementation within a hardware and software environment, not a guarantee supplied by source-code appearance alone.

The Spectre and Meltdown disclosures in 2018 drew attention to the interaction between speculative execution and microarchitectural state. A processor can discard the architectural results of transient instructions while retaining some effects in caches or other internal structures. Under the conditions required by a particular vulnerability, those residual effects can encode information that later timing measurements reveal. Cache behavior is thus often the observation mechanism rather than the sole underlying defect.

Mitigations span hardware, operating systems, compilers, and application code. Examples include changes to speculation controls, isolation of selected address mappings, avoidance of secret-dependent accesses, and restrictions on sharing or resource allocation. Cache partitioning can reduce particular forms of contention but does not eliminate all microarchitectural channels. Flushing a cache is likewise not a universal security boundary: its effectiveness depends on what is flushed, when the operation occurs, and which other shared structures remain. These limitations make cache security a systems problem rather than a matter of selecting one cache policy.

Physical scaling, reliability, and design trade-offs

Cache capacity consumes a substantial share of the silicon area in many processors. More capacity can lower miss rates, but also increases leakage power, wire length, lookup complexity, and manufacturing cost. Associativity and access bandwidth add further costs. A cache able to supply several loads and stores per cycle may require banking, replicated state, or multiple ports, each with different effects on area and timing. Designers therefore optimize not for maximum capacity alone, but for a workload-dependent balance of latency, throughput, power, and cost.

Reliability is also important because a bit error in a cache can corrupt instructions or data. Processors may use parity or an error-correcting code to detect or correct faults. A clean cache line can sometimes be discarded and refetched after an error, whereas a dirty line may contain the only up-to-date copy and requires stronger protection or a defined recovery response. Tags and coherence metadata are also critical: corruption there can cause the wrong data to be selected or valid data to be lost. Protection strength and recovery mechanisms vary by cache level and processor class.

Physical integration has expanded the available design space. Large caches can be built from additional dies within a package rather than occupying only the main processor die. Three-dimensional stacking can place cache memory above or below logic, providing many short connections but introducing thermal, power-delivery, manufacturing, and yield constraints. Some processors have also used embedded DRAM for large cache levels, trading different density, latency, and refresh characteristics against SRAM. None of these technologies removes the need for smaller, fast structures near the execution units.

Chiplet-based and heterogeneous processors make topology increasingly significant. A cache may be shared within one compute die but not across the package, or it may serve CPU cores together with a graphics processing unit or other accelerator. Maintaining coherence across such components can simplify shared-memory programming, yet ownership transfers and interconnect traffic remain real costs. A physically large cache is not necessarily equally fast from every requester, and software scheduling can influence how much locality survives when threads migrate.

Workloads also impose conflicting demands. Server applications may benefit from large caches that reduce irregular memory traffic; streaming computations may gain less because they rarely reuse data; real-time systems may value bounded access behavior over the highest average hit rate. Some processors provide cache allocation or monitoring facilities to manage interference between workloads. Others emphasize partitioned local storage or predictable access paths. CPU cache design consequently remains a set of negotiated trade-offs among statistical performance, physical implementation, sharing, and the requirements of the software running on the processor.