Community hub
Recent from talks
Contribute something
Nothing was collected or created yet.
Cache inclusion policy
View on Wikipedia | This article may require cleanup to meet Wikipedia's quality standards. The specific problem is: are 'lower' and 'higher' mixed up? (January 2025) |
Multi-level caches can be designed in various ways depending on whether the content of one cache is present in other levels of caches. If all blocks in the higher level cache are also present in the lower level cache, then the lower level cache is said to be inclusive of the higher level cache. If the lower level cache contains only blocks that are not present in the higher level cache, then the lower level cache is said to be exclusive of the higher level cache. If the contents of the lower level cache are neither strictly inclusive nor exclusive of the higher level cache, then it is called non-inclusive non-exclusive (NINE) cache.[1][2]
Inclusive Policy
[edit]
Consider an example of a two level cache hierarchy where L2 can be inclusive, exclusive or NINE of L1. Consider the case when L2 is inclusive of L1. Suppose there is a processor read request for block X. If the block is found in L1 cache, then the data is read from L1 cache and returned to the processor. If the block is not found in the L1 cache, but present in the L2 cache, then the cache block is fetched from the L2 cache and placed in L1. If this causes a block to be evicted from L1, there is no involvement of L2. If the block is not found in either L1 or L2, then it is fetched from the main memory and placed in both L1 and L2. Now, if there is an eviction from L2, the L2 cache sends a back invalidation to the L1 cache, so that inclusion is not violated.
As illustrated in Figure 1, initially consider both L1 and L2 caches to be empty (a). Assume that the processor sends a read X request. It will be a miss in both L1 and L2 and hence the block is brought into both L1 and L2 from the main memory as shown in (b). Now, assume the processor issues a read Y request which is a miss in both L1 and L2. So, block Y is placed in both L1 and L2 as shown in (c). If block X has to be evicted from L1, then it is removed from L1 only as shown in (d). If block Y has to be evicted from L2, it sends a back invalidation request to L1 and hence block Y is evicted from L1 as shown in (e).
In order for inclusion to hold, certain conditions need to be satisfied. L2 associativity must be greater than or equal to L1 associativity irrespective of the number of sets. The number of L2 sets must be greater than or equal to the number of L1 sets irrespective of L2 associativity. All reference information from L1 is passed to L2 so that it can update its replacement bits.
One example of inclusive cache is Intel quad core processor with 4x256KB L2 caches and 8MB (inclusive) L3 cache.[3]
Exclusive Policy
[edit]
Consider the case when L2 is exclusive of L1. Suppose there is a processor read request for block X. If the block is found in L1 cache, then the data is read from L1 cache and returned to the processor. If the block is not found in the L1 cache, but present in the L2 cache, then the cache block is moved from the L2 cache to the L1 cache. If this causes a block to be evicted from L1, the evicted block is then placed into L2. This is the only way L2 gets populated. Here, L2 behaves like a victim cache. If the block is not found in either L1 or L2, then it is fetched from main memory and placed just in L1 and not in L2.
As illustrated in Figure 2, initially consider both L1 and L2 caches to be empty (a). Assume that the processor sends a read X request. It will be a miss in both L1 and L2 and hence the block is brought into L1 from the main memory as shown in (b). Now, again the processor issues a read Y request which is a miss in both L1 and L2. So, block Y is placed in L1 as shown in (c). If block X has to be evicted from L1, then it is removed from L1 and placed in L2 as shown in (d).
An example of exclusive cache is AMD Opteron with 512 KB (per core) L2 cache, exclusive of L1.[3]
NINE Policy
[edit]
Consider the case when L2 is non-inclusive non-exclusive of L1. Suppose there is a processor read request for block X. If the block is found in L1 cache, then the data is read from L1 cache and returned to the processor. If the block is not found in the L1 cache, but present in the L2 cache, then the cache block is fetched from the L2 cache and placed in L1. If this causes a block to be evicted from L1, there is no involvement of L2, which is the same as in the case of inclusive policy. If the block is not found in both L1 and L2, then it is fetched from main memory and placed in both L1 and L2. Now, if there is an eviction from L2, unlike inclusive policy, there is no back invalidation.
As illustrated in Figure 3, initially consider both L1 and L2 caches to be empty (a). Assume that the processor sends a read X request. It will be a miss in both L1 and L2 and hence the block is brought into both L1 and L2 from the main memory as shown in (b). Now, again the processor issues a read Y request which is a miss in both L1 and L2. So, block Y is placed in both L1 and L2 as shown in (c). If block X has to be evicted from L1, then it is removed from L1 only as shown in (d). If block Y has to be evicted from L2, it is evicted from L2 only as shown in (e).
An example of non-inclusive non-exclusive cache is AMD Opteron with non-inclusive L3 cache of 6 MB (shared).[3]
Comparison
[edit]The merit of inclusive policy is that, in parallel systems with per-processor private cache if there is a cache miss other peer caches are checked for the block. If the lower level cache is inclusive of the higher level cache and it is a miss in the lower level cache, then the higher level cache need not be searched. This implies a shorter miss latency for an inclusive cache compared to exclusive and NINE.[1]
A drawback of an inclusive policy is that the unique memory capacity of the cache is determined by the lower level cache. Unlike the case of exclusive cache, where the unique memory capacity is the combined capacity of all caches in the hierarchy.[4] If the size of lower level cache is small and comparable with the size of higher level cache, there is more wasted cache capacity in inclusive caches. Although the exclusive cache has more unique memory capacity, it uses more bandwidth since it suffers from a higher rate of filling of new blocks (equal to the rate of higher level cache's misses) as compared to NINE cache which is filled with a new block only when it suffers a miss. Therefore, assessment of cost relative to benefit needs to be done while exploiting the choice between Inclusive, Exclusive and NINE caches.
Value Inclusion: It is not necessary for a block to have the same data values when it is cached in both higher and lower level caches even though inclusion is maintained. But, if the data values are the same, value inclusion is maintained.[1] This depends on the write policy in use, as write back policy does not notify the lower level cache of the changes made to the block in higher level cache. However, in case of write-through cache there is no such concern.
References
[edit]- ^ a b c Solihin, Yan (2016). Fundamentals of Parallel Multicore Architecture. Chapman and Hall/CRC. pp. 146–150. ISBN 9781482211184.
- ^ Culler, David; Gupta, Anoop; Singh, Jaswinder Pal (1999). Parallel Computer Architecture: A Hardware/Software Approach. San Francisco: Morgan Kaufmann Publishers. pp. 369–372. ISBN 1558603433.
- ^ a b c "Comparing Cache Architectures and Coherency Protocols on x86-64 Multicore SMP Systems". Proceedings of the 42nd International Symposium on Microarchitecture. MICRO’09.
- ^ Ying Zheng; Davis, B.T.; Jordan, M. (2004). "Performance evaluation of exclusive cache hierarchies". IEEE International Symposium on - ISPASS Performance Analysis of Systems and Software, 2004. pp. 89–96. doi:10.1109/ISPASS.2004.1291359. ISBN 0-7803-8385-0. S2CID 10784219.
Cache inclusion policy
View on GrokipediaOverview
Definition and Purpose
A cache inclusion policy defines the relationship between data blocks across multiple levels of a processor's cache hierarchy, specifying whether blocks present in an inner-level cache (such as L1, which is closest to the CPU core) must also reside in an outer-level cache (such as L2 or the last-level cache, LLC).[5] This policy ensures data consistency by dictating inclusion or exclusion rules, thereby facilitating efficient access patterns in systems where inner caches prioritize speed and outer caches emphasize capacity.[6] The purpose of cache inclusion policies is to optimize data duplication in multi-level hierarchies, striking a balance between maximizing usable cache capacity, minimizing access latency, and reducing the overhead associated with cache coherence protocols.[7] These policies emerged as a response to the widening performance gap between rapidly advancing CPU clock speeds and slower main memory latencies, enabling processors to exploit temporal and spatial locality more effectively without excessive redundancy.[7] By governing how data propagates between levels, they support scalable designs in both single- and multi-core architectures, where coherence complexity can otherwise escalate with additional cache tiers.[5] Cache inclusion policies were first formalized in academic research during the late 1980s, amid the rise of multi-level cache designs for multiprocessors.[5] They gained practical prominence in the 1990s with the commercialization of multi-level caches, notably in the Intel Pentium Pro processor released in 1995, which featured an on-package L2 cache integrated with the L1.[5] At a basic level, these policies manage eviction and fill operations in multi-level caches by ensuring that data movements between inner and outer levels preserve overall hierarchy integrity, such as propagating evictions from inner caches to outer ones to avoid inconsistencies or data loss.[6] This foundational mechanic underpins reliable data flow, allowing outer caches to serve as backing stores while inner caches deliver low-latency hits.[5]Role in Cache Hierarchies
In multi-level cache hierarchies common to modern processors, the structure typically features private Level 1 (L1) caches per core, which are small (often 32-64 KB) and optimized for low latency, followed by private or shared Level 2 (L2) caches of moderate size (256 KB to 1 MB per core), and a shared last-level cache (LLC, usually L3) that is significantly larger (several MB to tens of MB) to serve multiple cores.[8] Inclusion policies operate between these levels, dictating whether the contents of inner caches (L1 and L2) must be subsets of the outer caches (L2 or LLC), thereby influencing data placement and movement across the hierarchy.[5] This setup balances speed, capacity, and sharing, with inclusion applied primarily between L1-L2 and L2-LLC to manage locality and coherence in multi-core environments.[9] Inclusion policies interact closely with replacement policies, affecting how blocks are evicted and handled during cache misses or capacity overflows. For instance, in inclusive hierarchies, replacement algorithms in inner caches must notify outer caches to maintain the superset property, often using counters or inclusion bits to track and enforce data presence, which can complicate eviction decisions compared to non-inclusive setups.[5] In exclusive hierarchies, victim blocks from inner cache evictions are inserted into the next level. In inclusive hierarchies, evicted blocks remain in the outer level without insertion, allowing duplication and aligning with write-back policies where dirty data requires write-back to the outer level to update its copy, preserving coherence without immediate memory writes.[6][5] Cache coherence protocols, such as directory-based or snooping mechanisms, are significantly influenced by inclusion policies, which determine data copy locations and simplify protocol implementation. In inclusive hierarchies, the LLC serves as a natural snoop filter, containing all inner cache data, thereby limiting coherence probes to the outer level and reducing invalidation traffic across the interconnect—essential for scalable multi-core systems.[6] For example, snooping protocols benefit from inclusion by avoiding unnecessary checks in private L1 caches, as any shared data modification can be resolved at the LLC, minimizing coherence overhead compared to exclusive policies that require tracking unique placements.[5] Directory protocols similarly leverage inclusion to streamline state tracking, though they may incur higher directory storage if non-inclusive overlaps occur.[9] Capacity implications of inclusion policies highlight trade-offs in effective storage utilization within the hierarchy. Inclusive setups mandate that outer cache capacity exceeds the aggregate of inner caches (e.g., LLC size ≥ sum of all L1 and L2 sizes), leading to data duplication that reduces the outer cache's unique capacity—potentially by 20-50% in typical configurations—while exclusive policies eliminate overlap to maximize total unique capacity across levels.[5] This duplication in inclusive designs trades capacity for coherence simplicity, as the redundant copies shield inner caches from interference but limit the LLC's ability to hold additional data, impacting miss rates in memory-bound workloads.[6]Policy Variants
Inclusive Policy
In an inclusive cache policy, the contents of the inner-level cache (such as L1) form a strict subset of the outer-level cache (such as L2 or the last-level cache, LLC), ensuring that every cache block present in the higher-speed inner cache is duplicated in the slower outer cache.[8] This policy is typically applied between L1 and L2, as well as L2 and the shared LLC in multi-core processors. On an L1 miss, if the block is found in L2, it is copied into L1 while remaining in L2; if not present in L2, the block is fetched from the LLC or main memory and installed simultaneously in both L1 and L2 to maintain inclusion.[8] L1 evictions do not remove the block from L2, as the outer cache serves as a backing store; however, if the block in L1 is dirty, it is written back to L2 before eviction.[8] In contrast, evictions from L2 or the LLC require invalidating the corresponding block in L1 to enforce the subset property, often involving a check of L1 contents to select a suitable victim in the outer cache.[8] The primary advantages of inclusive policies stem from their impact on cache coherence in multi-core systems. By guaranteeing that the outer cache holds all inner cache data, the LLC acts as a centralized backing store, simplifying coherence protocols such as snooping, as probes need only target the LLC without redundant checks in private L1 or L2 caches.[10] This reduces inter-core snoop traffic and eases block location during coherence operations, since the presence of data in any core's inner caches is reflected in the shared LLC, enabling efficient filtering of unnecessary broadcasts.[11] Despite these benefits, inclusive policies introduce significant challenges related to capacity efficiency and performance overhead. The mandatory duplication wastes space in the outer cache, as inner cache blocks occupy portions of the LLC that could otherwise hold unique data, resulting in overhead from redundant storage of L1 and L2 contents.[8] Additionally, LLC evictions can force the removal of high-locality blocks from L1—known as inclusion victims—leading to unnecessary inner-cache misses and increased latency, particularly in workloads with moderate reuse patterns.[6] An early real-world implementation of inclusive policies appears in Intel's Nehalem microarchitecture (introduced in 2008), where the shared L3 cache inclusively mirrors all data from per-core L1 and L2 caches, prioritizing coherence simplicity in multi-core designs.[11]Exclusive Policy
In an exclusive cache policy, data blocks present in a higher-level cache, such as L1, are not permitted to coexist in the lower-level cache, like L2, ensuring no overlap between cache levels. This approach operates by treating the lower-level cache as a victim cache: upon an L1 hit, the L2 is not accessed, minimizing unnecessary traffic; L1 evictions push blocks exclusively into L2; and L2 evictions typically bypass L1 to avoid reintroduction. The policy requires precise management of block migrations, including invalidations when data moves between levels, to maintain consistency.[10][2] The primary advantage of exclusive policies lies in maximizing effective cache capacity, as the total unique blocks across levels approximate the sum of individual cache sizes without duplication. For instance, with an L1 of size and L2 of size , the effective total capacity is approximately , contrasting with inclusive policies that duplicate data and reduce usable space. This non-overlapping placement is particularly beneficial in multi-core systems, where it reduces duplication overhead and enhances overall hit rates by better utilizing the aggregate cache space.[10][2] However, exclusive policies introduce challenges in cache coherence and implementation. Maintaining exclusivity complicates protocols, as the lower-level cache lacks copies of upper-level data, often necessitating additional probes to L1 during L2 snoops or broadcasts in multi-core environments to track ownership accurately. This can increase latency for coherence operations and on-chip bandwidth due to frequent data movements on evictions and insertions. Furthermore, the policy demands equal block sizes across levels and precise invalidation mechanisms during migrations, adding hardware complexity and potential power overhead.[2][10] Real-world implementations of exclusive policies include the AMD Opteron processors, such as the K8 architecture introduced in 2003, where the L2 cache serves as an exclusive victim cache for the L1, enhancing capacity without overlap. Similarly, some ARM designs, like the Cortex-A9 processor, support an exclusive L2 mode that can be activated to enforce non-coexistence between L1 and L2, optimizing for embedded and mobile systems.[12]NINE Policy
The non-inclusive non-exclusive (NINE) policy, also known as NCID (non-inclusive cache, inclusive directory), allows flexible data placement in multi-level cache hierarchies without enforcing strict inclusion or exclusion rules between levels. Under this policy, data present in a higher-level cache, such as L1, may or may not reside in a lower-level cache like L2 or L3, making it non-inclusive; conversely, data in the lower-level cache may or may not be present in the higher-level cache, rendering it non-exclusive. To manage this flexibility while maintaining coherence, the policy employs a directory structure that tracks the presence of cache blocks across levels using tags or core-valid bits, without mandating data replication or eviction cascades. This decoupling of tag and data management enables efficient snoop filtering, where the directory acts as an inclusive tracker of higher-level cache contents, even if the actual data in the lower-level cache is selectively allocated.[13] A key advantage of the NINE policy is its ability to balance effective cache capacity and access latency by minimizing unnecessary data replication, thereby avoiding the "inclusion victim" problem where evicting a block from a lower-level cache forces its removal from higher levels. It permits controlled sharing of data across cores for coherence purposes, reducing inter-cache traffic compared to strict inclusive designs, while offering adaptability to diverse workloads through mechanisms like dynamic bypassing or quality-of-service (QoS) policies that adjust allocation based on data priority. For instance, selective insertion into the lower-level cache—allocating only a fraction of incoming blocks—can optimize performance, yielding up to 45% speedup in certain multi-core benchmarks by enhancing overall hierarchy efficiency.[13][2] However, implementing NINE policies introduces hardware challenges, including increased complexity for per-block tracking via expanded directory structures, which add overhead (approximately 2% area for a 256 KB L2 setup). This can lead to potential redundant copies if overlap is not tightly controlled, or additional misses in higher levels due to the unpredictability of data placement without rigid rules. Coherence maintenance relies on the directory's accuracy, demanding precise management to prevent inconsistencies in multi-core environments.[13][2] The degree of overlap between cache levels in a NINE policy can be quantified by the overlap ratio, defined as: This ratio typically satisfies , allowing optimization through techniques such as prefetching to anticipate shared data or bypassing to evict low-utility blocks, thereby tuning effective capacity without full exclusion.[13] An example of NINE adoption appears in modern Intel processors, such as Skylake-SP (2017) and Skylake-X (2017), where the L3 cache operates as a non-inclusive victim cache with an inclusive directory to mitigate the overhead of prior inclusive designs in large-core chip multiprocessors, improving scalability for server workloads.[14][15]Implications and Comparisons
Coherence and Performance Trade-offs
Cache inclusion policies significantly influence the design and efficiency of cache coherence protocols in multi-core systems. Inclusive policies simplify coherence mechanisms, particularly in broadcast snooping setups, by designating the last-level cache (LLC) as authoritative for all data present in private higher-level caches; this allows coherence actions to be resolved at the LLC without needing to probe private caches directly, reducing implementation complexity.[16] In contrast, exclusive policies demand more intricate point-to-point invalidation protocols, as data blocks cannot reside in both private and shared caches simultaneously, necessitating explicit tracking and messaging to maintain consistency across levels without duplication.[7] Non-inclusive non-exclusive (NINE) policies adopt a hybrid approach, often incorporating directory-based structures for partial sharing tracking, which balances flexibility but introduces variable overhead in coherence traffic compared to stricter inclusive or exclusive schemes.[3] Performance metrics reveal distinct trade-offs across these policies. Inclusive policies tend to exhibit higher miss rates in higher-level caches due to inclusion victims—blocks evicted from the LLC that must also be invalidated from private caches, amplifying dependency on lower-level locality.[16] Exclusive policies mitigate capacity waste from duplication, yielding lower overall miss rates and faster L1 hit latencies through maximized unique storage, though they may incur higher eviction rates in shared levels.[7] NINE policies offer variable latency profiles, with hits potentially quicker in private caches but misses more unpredictable due to non-strict inclusion. Power consumption is elevated in inclusive designs from data duplication, which increases tag array checks and coherence overhead, whereas exclusive and NINE approaches can reduce dynamic power through optimized data placement but at the cost of additional protocol logic.[3] These impacts can be modeled through trade-off relations, such as miss rate as a function of inclusion type and workload locality: for inclusive policies, the effective miss rate approximates a base rate plus the product of LLC eviction rate and private cache dependency (i.e., miss rate ≈ base rate + (L2 eviction rate × L1 dependency)), highlighting how evictions propagate upward.[16] Exclusive policies shift this toward lower base rates via non-duplication, while NINE introduces locality-dependent variability. Simulations from 2010s studies demonstrate these effects: exclusive policies improve instructions per cycle (IPC) by 5-10% in capacity-bound workloads by enhancing effective cache utilization, outperforming inclusive baselines in single-core scenarios.[7] In multi-core environments, NINE policies reduce coherence traffic by up to 20% through hybrid sharing mechanisms, aiding scalability in shared-memory systems.[3] Trends since the mid-2010s emphasize power efficiency gains in NINE designs for multi-core scaling, addressing limitations in earlier inclusive-heavy architectures.[7]Real-World Implementations
Intel's early 2010s processors, such as the Sandy Bridge architecture introduced in 2011, employed an inclusive policy for the last-level cache (LLC), ensuring that all data in the L1 and L2 caches was also present in the L3 to simplify coherence in multi-core systems.[17] This approach persisted through architectures like Ivy Bridge but began evolving with the Skylake family in 2015, where Intel shifted to a non-inclusive LLC in server variants like Skylake-X to improve utilization in high-core-count (8+ cores) chips by reducing redundancy and allowing more unique data storage.[18] Subsequent generations, including Cascade Lake and beyond, retained this non-inclusive design, often termed non-inclusive non-exclusive (NINE), to balance coherence overhead with capacity efficiency in scaling multi-core environments.[19] In client processors, starting with Raptor Lake in 2022, Intel introduced a dynamic inclusive/non-inclusive (INI) mechanism for the L3 cache, allowing the policy to switch based on workload to optimize for both single-threaded and multi-threaded performance.[20] This hybrid approach continued in later generations like Arrow Lake in 2024. AMD's Zen microarchitecture, debuting in 2017 with Ryzen processors, features an inclusive policy between the L1 and L2 caches per core, where the 512 KB L2 includes copies of L1 data to streamline access patterns, while the shared L3 operates as a victim cache that is mostly exclusive of the L2 to maximize effective capacity across core complexes.[21] In server-oriented EPYC processors based on Zen, this L2-L3 exclusivity aids multi-socket coherence by minimizing data duplication in the larger 32 MB+ L3 slices per chiplet, though some variants incorporate inclusive elements at the L2-L3 boundary to support efficient snoop filtering in NUMA configurations.[22] Later Zen iterations, such as Zen 2, Zen 3, Zen 4, and Zen 5, maintained this hybrid approach, optimizing for both single-thread performance and multi-core scalability in data center workloads. Early ARM designs, like the Cortex-A9 from 2009, supported an optional exclusive policy for the L2 cache relative to the L1, configurable to avoid duplication and enhance capacity in embedded multi-core systems, particularly when paired with external L2 controllers.[23] Modern ARM-based implementations in heterogeneous big.LITTLE configurations, such as Apple's M1 SoC released in 2020, adopt a NINE policy for the system-level cache (SLC), which is non-inclusive of CPU private caches to accommodate varying access patterns from high-performance Firestorm and efficiency Icestorm cores, while remaining inclusive toward GPU caches for unified memory benefits.[24] This design facilitates heterogeneous caching in mobile and edge devices, reducing latency in mixed workloads. Industry trends since the mid-2010s show a shift toward NINE and hybrid policies driven by the proliferation of multi-core (16+ cores) processors, as inclusive designs suffer from redundancy that hampers scalability in bandwidth-constrained hierarchies; studies indicate non-inclusive approaches can yield up to 10-20% better multi-core performance in shared-cache scenarios by improving hit rates and reducing coherence traffic.[2] Post-2015 developments, including Intel's NCID (non-inclusive cache, inclusive directory) in server chips and dynamic INI in client chips, underscore this evolution, with ongoing research emphasizing hybrids for future many-core systems.[25] In practice, inclusive policies face challenges from inclusion victims—data evicted from the LLC that must also be removed from private caches—leading Intel to implement bypassing mechanisms in 2019-era optimizations, such as selective prefetch filtering and victim-aware insertion policies in Coffee Lake and later, to mitigate unnecessary evictions and sustain performance in inclusive setups.[26]References
- https://en.wikichip.org/wiki/amd/microarchitectures/zen