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: v3 · 2026-09-19 · History
Domain-specific #: 1426
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomains: Computer Architecture, Multilevel Processor Cache Organization → Computer Science & Software Engineering
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.

How would you explain it like I'm…

Toy Box and Closet Rules

Imagine you have a small toy box and a big toy closet. One rule could be: anything in the toy box must also be in the closet. Another rule: a toy can never be in both places. A third rule: no promise either way. A computer picks one of these rules for its storage layers, and must keep following it as toys get moved in and out.

Can Data Be in Two Places?

Computers keep copies of data in layers of caches: a small fast one close to the processor, and a bigger one further out. A cache inclusion policy is the rule about whether the same data can be in both layers. "Inclusive" means everything in the small cache must also be in the big one. "Exclusive" means nothing can be in both. "Non-inclusive, non-exclusive" means there's no rule either way. The chosen rule has to be kept true every time data is brought in, thrown out, or moved, so for example an inclusive design must also remove data from the small cache when the big cache throws out its copy.

Cache-Level Residency Policy

A cache inclusion policy sets which data blocks may live in two or more levels of a processor's cache hierarchy at the same time. If A_I is the set of block addresses in an inner cache (closer to the processor) and A_O is the set in an outer cache, inclusive means A_I ⊆ A_O, exclusive means the two sets never overlap, and non-inclusive, non-exclusive (NINE) imposes neither rule. The policy is not just a picture; it has to be maintained through misses, fills, evictions, writebacks, invalidations, and coherence requests. In an inclusive design, evicting a block from the outer cache forces a back-invalidation that removes the copy from the inner cache. In an exclusive design, moving a block into the inner cache removes it from the outer one, and blocks evicted from the inner cache can be moved outward. Each choice has trade-offs: inclusion wastes space on duplicates but makes it easy to know whether inner caches hold a block, while exclusion saves space but requires moving lines around.

Cache inclusion policy specifies and maintains the permitted residency relation between block addresses in different levels of a cache hierarchy. With A_I the addresses resident in an inner cache and A_O those in an outer cache, an inclusive relation requires A_I ⊆ A_O, a strictly exclusive relation requires A_I ∩ A_O = ∅, and non-inclusive, non-exclusive (NINE) imposes neither invariant. The policy must hold across misses, promotions, fills, evictions, writebacks, invalidations, and coherence requests. Under inclusion, evicting an outer block whose address may remain in an inner cache requires back-invalidation or relocation before the outer tag disappears; under conventional exclusion, promoting a block inward removes it from the outer level, and inner victims may be demoted outward; under NINE, neither containment nor disjointness needs preserving, though an implementation may still duplicate or move lines. No choice is universally best. Inclusion lets an outer miss prove absence from included inner caches, simplifying snoop filtering and directory work, but it spends capacity on duplication and creates inclusion victims when outer evictions kill useful inner blocks. Exclusion increases unique capacity but requires line movement and cannot use data inclusion as a presence directory, and NINE may need separate tracking to find private copies. Modern designs can decouple tag or directory inclusion from data inclusion, keeping location information while the data arrays are non-inclusive or exclusive.

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.

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.

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?

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.

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.

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:

Relationships to Other Abstractions¶

Current abstraction Cache Inclusion Policy Domain-specific

Parents (1) — outgoing typed relations

Cache Inclusion Policy presupposes Caching Prime

Caching is the broader abstraction this entry instantiates.

Hierarchy paths (9) — routes to 7 parentless roots

Cache Inclusion Policy → presupposes Caching → presupposes Locality Of Reference → is a kind of Recurrence

Show alternative paths (8)

Neighborhood in Abstraction Space¶

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

Family — Unclustered & Miscellaneous (2769 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25