Electronics Guide

Snooping Protocols

Snooping protocols rely on a shared bus or interconnect where all cache controllers monitor transactions initiated by other processors. When one processor reads or writes a cache line, its controller broadcasts the address on the shared medium. All other controllers snoop this broadcast, checking their own caches and taking appropriate action if they hold a copy of the addressed data.

The MSI protocol represents the simplest snooping approach, defining three states for each cache line: Modified, Shared, and Invalid. A cache line in the Modified state contains data that differs from main memory and exists in only this cache. The Shared state indicates a clean copy that may exist in multiple caches. Invalid marks a line as not containing valid data. When a processor writes to a Shared line, the controller must first invalidate all other copies by broadcasting an invalidation request.

The MESI protocol extends MSI with an Exclusive state, indicating a clean copy that exists in only one cache. This optimization allows silent transitions from Exclusive to Modified without bus traffic, reducing coherence overhead for data accessed by a single processor. Many modern systems use MESI or further extensions like MOESI, which adds an Owned state to efficiently handle modified shared data.

Snooping protocols work well for small to medium-scale multiprocessors but face scalability limitations. As processor count increases, bus bandwidth becomes a bottleneck, and the requirement for all controllers to observe all transactions creates excessive traffic and power consumption.

Directory-Based Protocols

Directory-based coherence protocols address scalability by maintaining a central directory that tracks which caches hold copies of each memory line. Rather than broadcasting all requests, a controller sends coherence messages only to caches known to hold relevant data. The directory maintains presence bits or a sharer list for each cache line in memory, updating this information as lines move between caches.

When a processor requests a cache line, its controller contacts the directory. The directory responds with the data if no other cache holds a modified copy, or forwards the request to the current owner. For write operations, the directory sends invalidation messages only to caches in its sharer list, dramatically reducing traffic compared to broadcast invalidation. The scalability advantages make directory protocols standard in large-scale systems, though the directory storage overhead and additional indirection latency represent design trade-offs.

Hybrid approaches combine snooping within clusters of processors with directory protocols between clusters, balancing the low latency of snooping against the scalability of directories. Cache controllers in such systems implement multiple coherence state machines and must correctly handle the interactions between protocols operating at different levels of the hierarchy.

Least Recently Used

The Least Recently Used (LRU) policy evicts the line that has gone longest without being accessed, based on the temporal locality principle that recently used data is likely to be used again soon. True LRU requires tracking the relative access order of all lines in a set, demanding storage and update logic that grows rapidly with associativity. For an N-way set-associative cache, true LRU requires log2(N!) bits per set and complex priority updates on every access.

Due to these costs, most implementations use approximations to LRU. Pseudo-LRU schemes use a tree structure of single bits to track a binary decision path toward the least recently used line, requiring only N-1 bits per set. Tree-based pseudo-LRU does not guarantee eviction of the true LRU line but performs nearly as well in practice while dramatically reducing hardware cost.

Not Recently Used

Not Recently Used (NRU) policies maintain a single reference bit per cache line that hardware sets on each access. Periodically, software or hardware clears all reference bits. For eviction, the controller selects among lines with cleared reference bits, approximating LRU by distinguishing recently accessed lines from dormant ones. NRU requires minimal storage but provides coarser temporal information than LRU approximations.

Random Replacement

Random replacement simply selects a victim line using a pseudo-random number generator, requiring no access history tracking. Despite its simplicity, random replacement performs surprisingly well, particularly for highly associative caches where the probability of evicting soon-needed data is inherently low. Some high-performance processors use random replacement for last-level caches, trading a small hit rate penalty for reduced power and complexity.

Advanced Replacement Policies

Research has produced numerous advanced policies that consider additional factors beyond recency. Frequency-based policies track how often lines are accessed, protecting frequently used data even if not accessed recently. Re-reference interval prediction (RRIP) estimates the time until next access based on historical patterns. Dead block prediction identifies lines unlikely to be accessed again before eviction, enabling early eviction and better use of cache capacity.

Insertion policies complement replacement policies by determining where in the priority order newly fetched lines should be placed. Traditional insertion places new lines at the highest priority, but this can pollute the cache with streaming data that displaces more valuable working set data. Adaptive insertion policies monitor cache behavior and adjust insertion priority to maximize hit rate for the observed access patterns.

Sequential Prefetching

Sequential prefetching exploits spatial locality by fetching cache lines adjacent to recently accessed addresses. The simplest form, next-line prefetching, fetches the immediately following cache line on every access. More sophisticated stream prefetchers detect sequential access patterns and prefetch multiple lines ahead, adjusting the prefetch distance based on memory latency and observed stream behavior.

Hardware stream prefetchers track multiple independent streams simultaneously, recognizing that modern programs often access several sequential regions concurrently. Each stream table entry records the current address and direction of a detected stream, triggering prefetches as accesses advance through the sequence. Training logic identifies new streams from sequences of cache misses to adjacent lines.

Stride Prefetching

Stride prefetchers handle access patterns with constant spacing between addresses, common in array traversals and matrix operations. By monitoring the differences between successive accesses, stride detection logic identifies regular patterns regardless of the stride value. Once detected, the prefetcher generates addresses by adding the observed stride to recent access addresses.

Reference prediction tables associate detected strides with the program counter addresses of load instructions, enabling accurate prefetching when the same instruction executes repeatedly with the same access pattern. This correlation improves accuracy by distinguishing multiple stride patterns originating from different code locations.

Correlation-Based Prefetching

Correlation prefetchers learn arbitrary relationships between memory accesses, capturing patterns that sequential and stride prefetchers cannot. By recording sequences of addresses observed during program execution, these prefetchers can predict future accesses based on recently observed addresses. Markov prefetchers treat the address sequence as a probabilistic state machine, predicting the next address from the current address and learned transition probabilities.

Content-directed prefetching examines data values to discover pointer chains and linked structures. When data loaded from memory contains addresses pointing to other memory locations, the prefetcher speculatively follows these pointers, fetching linked list nodes, tree children, or graph neighbors before the program traverses to them. This aggressive approach requires careful filtering to avoid excessive speculative traffic.

Prefetch Throttling

Aggressive prefetching can degrade performance by consuming memory bandwidth, polluting caches with unused data, and interfering with demand requests. Prefetch throttling mechanisms monitor prefetch accuracy and system resource utilization, adjusting prefetch aggressiveness dynamically. When prefetches frequently arrive late or remain unused, the controller reduces prefetch rate. When bandwidth is abundant and prefetches are accurate, throttling permits more aggressive speculation.

Write-Through

Write-through caches propagate every write operation immediately to the next level of the memory hierarchy. While the cache retains a copy of the written data for future reads, the write operation does not complete until acknowledged by the backing memory or next-level cache. This policy simplifies coherence by ensuring all levels of the hierarchy contain identical data and guarantees that main memory always holds current values.

The primary disadvantage of write-through is high memory bandwidth consumption. Programs with intensive write traffic generate continuous write operations to main memory, potentially saturating the memory bus and creating a performance bottleneck. Write buffers mitigate this issue by queuing outgoing writes, allowing the processor to continue execution while writes drain to memory. However, the buffer can fill during write bursts, eventually stalling the processor.

Write-Back

Write-back caches absorb write operations locally, modifying cached data without immediately updating lower levels of the hierarchy. A dirty bit associated with each cache line indicates whether the line has been modified and differs from the backing memory copy. Only when a dirty line is evicted does the controller write its contents back to memory, combining multiple writes to the same line into a single writeback.

Write-back policies dramatically reduce memory bandwidth consumption for write-intensive workloads, making them standard in modern processors. However, they complicate cache coherence because other processors cannot simply read main memory to observe writes by other cores. Coherence protocols must track dirty lines and forward requests to the cache holding modified data. System reliability considerations also arise because power loss before writeback causes data loss.

Write Allocation Policies

Write allocation policies determine cache behavior on a write miss. Write-allocate caches fetch the target line into the cache before performing the write, following the same miss handling as reads. This approach benefits workloads where written addresses are likely to be read or written again soon, keeping recently written data available in the cache.

No-write-allocate caches handle write misses by writing directly to the next memory level without loading the line into the cache. This policy avoids polluting the cache with written data unlikely to be accessed again, beneficial for streaming write patterns. Most write-back caches use write-allocate, while write-through caches often use no-write-allocate, though various combinations exist based on workload requirements.

Partial Writes and Write Combining

When writes modify only a portion of a cache line, the controller must handle partial write scenarios. For write-allocate caches, a partial write miss requires fetching the complete line before modifying the relevant bytes. Write combining buffers accumulate multiple partial writes to the same line before committing to the cache or memory, reducing the number of memory transactions for programs that perform many small writes.

Some memory types, particularly memory-mapped I/O regions, require uncached write-combining to ensure device registers observe individual writes in order while still benefiting from combining multiple writes to a write buffer. Cache controllers typically support multiple write combining modes configured per memory region.

Victim Cache Operation

On a cache miss, the controller searches both the main cache and victim cache in parallel or sequentially depending on timing constraints. A victim cache hit triggers a swap operation: the requested line moves from victim cache to main cache, while the evicted main cache line moves to the victim cache. This swap maintains the property that the victim cache contains the most recently evicted lines.

When the victim cache itself fills, it must evict its oldest entry to make room for newly evicted lines from the main cache. The victim cache replacement policy is typically simple due to its small size, often using FIFO or random selection. Evictions from the victim cache go to the next memory level, with writeback for dirty lines in write-back systems.

Exclusive and Inclusive Victim Caches

Victim caches can operate in exclusive or inclusive modes relative to the main cache. Exclusive victim caches hold only lines not present in the main cache, maximizing total storage capacity but requiring careful management during swaps. Inclusive victim caches may hold copies of main cache lines, simplifying coherence at the cost of redundant storage.

Miss Status Handling Registers

Miss Status Handling Registers (MSHRs) form the core mechanism enabling non-blocking operation. Each MSHR entry tracks one outstanding cache miss, recording the target address, requesting instruction, and other metadata needed to complete the miss when data arrives. The number of MSHRs limits how many concurrent misses the cache can handle; typical implementations provide four to sixteen entries.

When a cache miss occurs, the controller allocates an MSHR entry and initiates the memory request without blocking subsequent accesses. If another access targets the same cache line while the miss is outstanding, secondary miss handling merges the new request with the existing MSHR entry rather than generating duplicate memory traffic. This merging is crucial for efficiency when multiple processors or threads contend for the same data.

Hit Under Miss

Hit-under-miss operation allows cache hits to proceed while a miss is outstanding. This basic level of non-blocking behavior provides significant performance benefits because programs frequently hit in the cache even when a previous miss is in progress. The controller must ensure that hits and miss completions do not interfere, properly handling cases where they target the same or related cache lines.

Miss Under Miss

Miss-under-miss capability extends non-blocking operation to allow multiple simultaneous misses. This mode enables memory-level parallelism, overlapping the latency of multiple independent misses to hide memory access time more effectively. The controller manages multiple outstanding memory requests, tracking them in separate MSHR entries and completing them as responses arrive from the memory system.

The benefits of miss-under-miss scale with memory latency; as main memory becomes relatively slower compared to processors, the ability to overlap multiple misses becomes increasingly valuable. Modern processors support eight or more outstanding misses per core, enabling substantial latency tolerance for memory-intensive applications.

Structural Hazards in Non-Blocking Caches

Non-blocking operation introduces structural hazards that the controller must manage. Bank conflicts occur when multiple concurrent operations target the same cache bank. Port conflicts arise when more operations require cache access than available ports can service. MSHR exhaustion happens when all entries are occupied, forcing subsequent misses to stall. The controller arbitrates among competing requests and may prioritize demand requests over prefetches to maintain forward progress.