Cache Inclusion Policy¶

A multilevel-cache policy that maintains an inclusive, exclusive, or unconstrained residency relation between cache levels through coordinated fill, movement, eviction, and invalidation actions.

Version: v2 · 2026-09-06 · History
Domain-specific #: 1426
Origin domain: computer architecture
Subdomain: multilevel processor-cache organization
Aliases: Cache inclusivity policy, Cache inclusion property, Multilevel cache inclusion policy

Core Idea¶

Cache inclusion policy specifies and maintains the permitted residency relation between data blocks in two or more levels of a processor-cache hierarchy. Let \(A_I\) be the set of block addresses resident in an inner cache, closer to a processor, and \(A_O\) the set resident in an outer cache. An inclusive relation requires \(A_I \subseteq A_O\); a strictly exclusive relation requires \(A_I \cap A_O = \varnothing\); and a non-inclusive, non-exclusive (NINE) relation imposes neither invariant, so an address may occur in both levels or only one.^[1]^[2]

The name denotes more than a static diagram. A policy must preserve its selected relation through cache misses, promotions, fills, evictions, writebacks, invalidations, and coherence requests. In an inclusive hierarchy, eviction of an outer-level block whose address may remain in an inner cache requires a back-invalidation or another operation that removes or relocates the inner copy before the outer tag disappears. In a conventional exclusive hierarchy, a block promoted into the inner cache is removed from the outer cache, while an inner victim may be demoted outward. Under NINE, fills and evictions need not preserve containment or disjointness, although a particular implementation may still choose to duplicate or move a line.^[2]^[3]

This is an architectural policy axis, not a claim that one organization is universally best. Inclusion can make an outer-level miss prove absence from all included inner caches, simplifying snoop filtering or directory work. It consumes data capacity through duplication and can cause inclusion victims when outer eviction invalidates useful inner blocks. Exclusion increases potential unique capacity but requires line movement and cannot use data-array inclusion alone as an upper-level presence directory. NINE relaxes the data-residency invariant but may need separate tracking to locate private copies. Modern designs can decouple tag or directory inclusion from data inclusion, retaining location information while allowing the data arrays themselves to be non-inclusive or exclusive.^[2]^[4]

Structural Signature¶

The recurring structure is:

ordered cache levels + address-residency sets + chosen containment/disjointness/no-constraint relation + event-specific preservation actions + location/coherence metadata → invariant-preserving cache-hierarchy behavior with characteristic capacity, traffic, and snoop consequences.

Eight roles are load-bearing:

At least two cache levels. Inclusion is relational. One cache in isolation has replacement and write rules but no cross-level inclusion policy.
A direction. The policy states which outer or farther level is inclusive, exclusive, or unconstrained with respect to which inner or nearer level. Level numbers alone can mislead across naming conventions, so the relation should be written explicitly.
A residency key. Usually the relation is over physical block addresses or tags, not over abstract values or byte-for-byte equality.
A selected relation. Containment, disjointness, or absence of either constraint must be stated rather than inferred from one observed fill.
Transition rules. Miss allocation, promotion, demotion, eviction, and invalidation must preserve the relation when it is mandatory.
Replacement interaction. Each level may select victims locally, but the inclusion rule determines whether a victim selection triggers work at another level.
Coherence and location support. An inclusive data or tag array can filter snoops; a non-inclusive data array may require a separate directory, snoop filter, or broader probe.
A cost profile. Duplicate capacity, unique capacity, internal traffic, metadata, latency, energy, and destructive back-invalidations form the policy's trade space.

For several private inner caches \(I_1,\ldots,I_n\) beneath a shared outer cache \(O\), full address inclusion is \(\bigcup_k A_{I_k} \subseteq A_O\). The equation is a recognition test, not a complete implementation: dirty ownership, coherence state, and data freshness still require their own rules.

What It Is Not¶

Cache inclusion policy is not Caching in general. Caching stores a fast local copy to exploit reuse. A web cache, memo table, or single CPU cache can instantiate Caching without any relation between multiple cache levels. Inclusion policy begins only when an architecture constrains which copies may coexist across levels and specifies how transitions preserve that constraint.

It is not a replacement policy. LRU, FIFO, random, RRIP, and other algorithms choose a victim within a cache set. Inclusion constrains the cross-level consequences of that choice. An outer inclusive-cache victim may force an inner invalidation; an inner exclusive-cache victim may be moved outward. Replacement and inclusion therefore interact without being aliases.

It is not a write policy. Write-through and write-back govern when modified data propagate. Address or tag inclusion can hold even when the outer data copy is stale because an inner cache owns the modified line. Some literature calls the maintained address relation space inclusion and reserves value inclusion for matching values.^[1] Inclusion must not be described as automatic byte equality.

It is not a coherence protocol. MESI-family states, directories, snooping, ordering, and ownership rules ensure that agents observe permitted values. Inclusion can simplify location discovery, but containment does not itself serialize writes, identify a dirty owner, or establish memory consistency.

It is not non-inclusive equals exclusive. Non-inclusive means containment is not guaranteed; duplicates may still exist. Exclusive positively requires disjoint data residency for the scoped levels. NINE is the intermediate no-constraint class, not a euphemism for exclusion.

Scope of Application¶

The home scope is multilevel hardware caches: private L1/L2 caches under shared last-level caches, multilevel accelerator and GPU caches, and other on-chip memory hierarchies that move addressed blocks among cache levels. The policy may be defined pairwise—L1 relative to L2, L2 relative to L3—or over a whole tree of private caches beneath a shared outer level.^[1]

The abstraction also applies when tags and data take different policies. An architecture can use a non-inclusive data array while maintaining an inclusive directory of inner-cache tags. That hybrid still has a precise inclusion policy: data residency is unconstrained or exclusive, while location metadata remains inclusive.^[2]

The term should not automatically be extended to every tiered store. Browser, CDN, database, and application caches often duplicate data across tiers, but unless they impose a stable containment or disjointness invariant and coordinate transitions to preserve it, calling their behavior an inclusion policy adds no explanation beyond Caching and replication. The defining scope is an engineered multilevel cache relation, not accidental overlap.

Clarity¶

The fastest diagnostic uses two snapshots and one counterfactual:

For every address in the inner cache, must a corresponding outer tag exist? If yes, the relation is inclusive.
May an address occupy both scoped data arrays at once? If no, the relation is exclusive.
If an outer line is evicted while an inner copy remains, must the inner copy be invalidated or relocated solely to preserve a membership rule? If yes, inclusion is being enforced; if no and duplicates are allowed, the relation is NINE.

This test separates architecture from incidental state. A NINE hierarchy may happen to be fully duplicated at one instant, but duplication does not make it inclusive unless future transitions are constrained to preserve containment. An exclusive hierarchy may briefly have transient copies inside an atomic movement operation; externally visible stable states and protocol guarantees, not a pipeline microstep, determine the policy.

Terminology should always name direction. Saying “L3 is inclusive of L2” means every scoped L2 address has a representative tag or block in L3. It does not mean every L3 block is in L2. “Lower” and “higher” are avoided where possible because authors use them inconsistently for numerical level and distance from the processor.

Manages Complexity¶

The abstraction compresses a large event table into one invariant. Instead of separately memorizing what every fill, hit, miss, replacement, coherence probe, and eviction does, an architect asks what action restores or preserves the selected set relation.

For inclusion, this reasoning immediately explains why an outer eviction can require back-invalidation, why the outer structure can act as a presence filter, and why contention in an outer set can evict a useful inner line. For exclusion, it explains promotion and demotion, reduced duplication, expanded potential unique capacity, and extra movement traffic. For NINE, it explains why outer absence no longer proves inner absence and why a separate snoop filter or directory may be valuable.^[2]^[4]

It also separates capacity numbers that are often added naively. If a hierarchy is fully inclusive, inner copies do not add the same amount of unique address coverage as their nominal bytes suggest. A strict exclusive pair can in principle approach the sum of both usable capacities because blocks are not duplicated. NINE offers workload- and policy-dependent overlap. Conflict mapping, reserved ways, metadata, coherence states, and replacement behavior keep these statements from being universal performance equations.

Abstract Reasoning¶

Inclusion-policy reasoning supports deduction from invariants before simulation.

Containment deduction. If \(A_I \subseteq A_O\) and an address misses in \(O\), it cannot be resident in \(I\), assuming the lookup and state are at a coherent protocol point. An outer tag lookup can therefore filter a probe of included inner caches.

Eviction deduction. If \(x \in A_I \cap A_O\) and an outer replacement would remove \(x\) from \(A_O\), inclusion would fail unless the protocol also removes or relocates \(x\) from \(A_I\). This predicts a back-invalidation or equivalent action without naming a processor.

Capacity deduction. Under strict exclusion, \(A_I \cap A_O=\varnothing\), so the unique resident-address count is \(|A_I|+|A_O|\). Under inclusion, the union is \(A_O\), so nominal inner capacity is duplicated from the standpoint of unique address coverage. This is a capacity opportunity, not a guaranteed hit-rate improvement.

Metadata deduction. If data inclusion is relaxed but the system still needs negative snoop filtering, the lost implication must be supplied elsewhere—by an inclusive tag directory, probe filter, or broader search. Intel's documented move from an inclusive to a non-inclusive LLC illustrates this exact substitution.^[4]

These deductions do not select a winner. Workload locality, sharing, outer-to-inner size ratio, mapping conflicts, interconnect costs, prefetching, core count, and coherence design determine whether saved duplication outweighs additional tracking and movement.

Knowledge Transfer¶

The abstraction transfers literally across processor families and research cache designs. An engineer can use the same set-relation and transition test for a private L1 under L2, several private L2 caches under a shared L3, or a CPU/GPU hierarchy. The labels remain exact only when address residency and preservation actions retain the same meaning.

Design knowledge transfers as conditional rules:

inclusive data is useful when the outer tag array should answer whether any included inner cache can hold an address;
exclusive data is useful when duplicate capacity is costly and movement traffic is acceptable;
NINE is useful when independent allocation and eviction are valuable, provided location and coherence are solved separately;
inclusive tags with non-inclusive data can retain filtering while reducing data duplication.

What travels outside cache architecture is merely set containment, mutual exclusion, redundancy, and state-invariant maintenance. Those are existing generic abstractions. Calling a warehouse or document system “cache-inclusive” without cache-level residency and event rules is metaphor, not transfer of this node.

Examples¶

Inclusive two-level trace. Initially \(A_I=A_O=\varnothing\). A miss for \(x\) allocates \(x\) in both levels, producing \(A_I=\{x\}\) and \(A_O=\{x\}\). Later the outer cache chooses \(x\) as a victim while the inner cache still holds it. The controller back-invalidates the inner copy before completing the outer eviction. The costly action is not a replacement-policy definition; it is the action required to preserve \(A_I\subseteq A_O\).

Exclusive promotion and demotion. Suppose \(x\in A_O\) and \(x\notin A_I\). An inner miss that hits on \(x\) promotes \(x\) into \(I\) and removes it from \(O\). If this displaces \(y\) from \(I\), the hierarchy may demote \(y\) into \(O\). Stable states keep the intersection empty. Zheng, Davis, and Jordan evaluate the capacity and performance effects of this organization against an inclusive hierarchy.^[3]

NINE with separate location tracking. An address fetched to an inner cache need not allocate data in the LLC. Its inner eviction may later place it in the LLC if reuse is predicted. Because an LLC miss no longer proves absence from private caches, a snoop filter tracks possible locations. Intel documents this organization in the Xeon Scalable-family change from a shared inclusive LLC to a non-inclusive LLC.^[4]

Inclusive directory, non-inclusive data. NCID separates the tag/directory array from the data array. Directory entries remain inclusive of private-cache locations, while outer data can be non-inclusive, semi-exclusive, or exclusive. The example demonstrates that “inclusion policy” must name what is included—data, tags, or both—rather than treating the entire cache level as one indivisible object.^[2]

Product-specific exclusivity. The AMD64 architecture manual notes that implementations can use an exclusive L2 that does not cache information contained in L1. This is evidence of recurrence, not a claim that every AMD implementation or every level in one processor has the same policy.^[5]

Structural Tensions¶

Snoop filtering versus data duplication. Full outer inclusion lets an outer miss rule out inner presence, but duplicates blocks and reduces unique capacity. Diagnostic: compare the cost of probes or directory metadata with the capacity and inclusion-victim cost.

Unique capacity versus movement traffic. Exclusion can use more nominal capacity for distinct blocks, but hits and evictions can require promotions, demotions, swaps, or writebacks. Diagnostic: measure internal traffic and latency, not capacity alone.

Independent replacement versus inclusion victims. An outer inclusive cache cannot always replace a block independently; its victim may force eviction of a hotter inner copy. Diagnostic: count back-invalidations and identify whether outer conflicts are destroying inner locality.

Data inclusion versus tag inclusion. Duplicating complete data supports a simple presence filter but is not necessary if an inclusive directory tracks inner residents. Diagnostic: state whether the invariant concerns addresses, tags, data bytes, or all three.

Local policy versus hierarchy-wide guarantee. Pairwise inclusivity does not automatically settle every relation in a three-level tree, especially when levels have different sharing scopes. Diagnostic: write the set relation for every relevant pair or union of child caches.

Address inclusion versus value freshness. A tag may be included while an inner write-back copy holds the current value. Diagnostic: keep residence, ownership, dirty state, and value equality as separate assertions.

Structural–Framed Character¶

The abstraction is predominantly structural (provisional framedness score: 0.20). Containment and disjointness are formal set relations, and the consequences follow from explicit state-transition invariants rather than human convention or institutional judgment. The same definition can be tested on different cache implementations.

Its vocabulary and optimization stakes remain computer-architectural. “Inner cache,” “outer cache,” “block,” “fill,” “back-invalidation,” and “snoop filter” refer to a specific engineered substrate. Whether a transient movement violates exclusivity and whether tag inclusion is sufficient depend on the architecture's observable-state and coherence conventions. These accents prevent the named policy from becoming a prime even though its internal reasoning is highly structural.

Structural Core vs. Domain Accent¶

The liftable core is maintain a chosen containment, disjointness, or unconstrained relation between tiered state sets under updates. Set Inclusion, Mutual Exclusion, Invariant, and State Transition carry that substrate-neutral structure.

The domain accent supplies the candidate's explanatory value: addressed cache blocks; closer and farther storage levels; miss allocation; promotion and demotion; victim selection; back-invalidations; dirty ownership; snoop filtering; directory metadata; and the capacity-versus-traffic tradeoff. Remove these commitments and the result is generic set maintenance rather than cache inclusion policy.

The node is therefore domain-specific. Its recurrence across CPU and accelerator cache hierarchies is literal within computer architecture, while cross-domain comparisons are handled by the generic primes. Generic Caching is broader but does not determine the cross-level set relation.

Caching is the minimal proposed parent. Cache inclusion policy presupposes multiple caches within a reuse-accelerating hierarchy. Caching does not require multiple levels and does not choose a containment or disjointness relation, so the relation is strict.

Hierarchy supplies the ordered-level structure. Set Inclusion formalizes the inclusive case, while Mutual Exclusion formalizes the disjoint case. Invariant and State Transition explain preservation across events. Locality of Reference supplies the workload regularity that makes caches useful. Eviction Policy chooses victims, whereas inclusion policy specifies what cross-level action follows from the choice. Coherence and Directory mechanisms are implementation neighbors because inclusion changes how locations can be found, not because it independently guarantees coherent values.

Relationships to Other Abstractions¶

Current abstraction Cache Inclusion Policy Domain-specific

Parents (1) — more general patterns this builds on

Cache Inclusion Policy presupposes Caching Prime

Caching is the minimal proposed parent.

Hierarchy paths (9) — routes to 7 parentless roots

Cache Inclusion Policy → Caching → Locality Of Reference → Recurrence

Show alternative paths (8)

Neighborhood in Abstraction Space¶

Cache Inclusion Policy sits in a sparse region of the domain-specific corpus (89^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (1565 abstractions)

Nearest neighbors

Cache hierarchy — 0.80
Far Pointer — 0.80
False sharing — 0.79
Cache coherence — 0.79
CPU cache — 0.78

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With¶

Caching: the broader fast-copy pattern; it does not entail a multilevel residency relation.
Cache hierarchy: the existence and ordering of levels, irrespective of how their contents overlap.
Replacement policy: selection of a victim within one cache.
Write-through or write-back policy: propagation timing for modified data.
Cache coherence protocol: ownership, validity, and permitted observations among agents.
Memory consistency model: ordering constraints on memory operations visible to software.
Inclusive cache: one policy value, not the whole three-way policy abstraction.
Exclusive cache: disjoint residency, not merely absence of a containment guarantee.
Non-inclusive cache: a level that does not guarantee containment; it may still duplicate some inner blocks.
NINE: the explicit non-inclusive, non-exclusive class; neither containment nor disjointness is required.
Victim cache: a cache populated by displaced blocks; it often participates in exclusion but is a particular organization.
Cache partitioning or allocation: assignment of ways or capacity among cores or classes, not cross-level overlap.
Value inclusion: equality or freshness of duplicated values, which is stronger and depends on writes and coherence.
Directory or snoop filter: metadata that may preserve tag inclusion independently of data inclusion.

References¶

[1] Baer, J.-L., & Wang, W.-H. (1988). “On the Inclusion Properties for Multi-Level Cache Hierarchies.” 15^th Annual International Symposium on Computer Architecture, 73–80. University of Washington author-hosted PDF. See also doi:10.1145/633625.52400. registry ↩a ↩b ↩c

[2] Zhao, L., Iyer, R., Makineni, S., Newell, D., & Cheng, L. (2010). “NCID: A Non-inclusive Cache, Inclusive Directory Architecture for Flexible and Efficient Cache Hierarchies.” Computing Frontiers 2010. doi:10.1145/1787275.1787314. registry ↩a ↩b ↩c ↩d ↩e ↩f

[3] Zheng, Y., Davis, B. T., & Jordan, M. (2004). “Performance Evaluation of Exclusive Cache Hierarchies.” IEEE International Symposium on Performance Analysis of Systems and Software, 89–96. doi:10.1109/ISPASS.2004.1291359. Author-accessible PDF. registry ↩a ↩b

[4] Intel. “Intel Xeon Processor Scalable Family Technical Overview,” especially “Cache Hierarchy Changes.” Official technical overview. registry ↩a ↩b ↩c ↩d

[5] AMD. AMD64 Architecture Programmer's Manual, Volume 2: System Programming, cache-organization discussion. Official AMD documentation. registry ↩