Inclusive, Exclusive, and Non-Inclusive Last-Level Caches

A private L1 and a shared L2 can relate to each other in three ways. The L2 may contain everything the L1s contain (inclusive), nothing the L1s contain (exclusive), or be indifferent (non-inclusive). The choice sounds like an accounting detail about duplicate copies, but it determines where the information needed for coherence lives, what an eviction from the shared level must do, and how much silicon is spent storing lines that are already cached elsewhere.

Inclusion as a coherence shortcut

An inclusive hierarchy maintains the invariant that every line present in a private L1 is also present in the shared L2. The invariant’s value is that the L2 can answer a coherence question without contacting the L1s. When a core requests a line, the L2 checks its own tags: if the line is absent, no private cache can hold it, so no invalidation or data transfer is needed. If it is present, the L2’s own state tells it which private caches may hold copies, and it can send invalidations only to those.

That check is a snoop filter, and it removes the broadcast from the protocol. A snooping machine without a filter sends every coherence request to every cache, which is the arrangement MESI transitions and invalidation traffic describes before any filtering is added. With an inclusive L2, the request is checked against a single array whose state already encodes the sharing. The cost is the invariant itself: the L2 must track which L1s hold each line, which for a 16-way machine means 16 presence bits per line, or a compressed summary when the sharing set is large.

The invariant also gives the L2 a clean way to evict. When it evicts a line, inclusion requires that no L1 still hold it, so the L2 must send back-invalidations to every private cache that does.

/* With an inclusive L2, one entry per line records which private caches may
   hold it, so an eviction knows exactly whom to invalidate and a request
   needs no probe of the private caches. */
struct llc_entry {
    unsigned long tag;
    unsigned      state;    /* Modified, Exclusive, Shared */
    unsigned      sharers;  /* one presence bit per private cache */
};

void back_invalidate(struct llc_entry *e, void (*send_inval)(int), int cores)
{
    for (int c = 0; c < cores; c++)
        if (e->sharers & (1u << c))
            send_inval(c);          /* only the recorded holders are contacted */
    e->sharers = 0;
}

Those invalidations cost nothing when the line is not in any L1, which is the common case for a large L2 — most of its capacity holds lines that have been evicted from the small L1s. But for the lines that are hot in a private cache and cold from the L2’s perspective, an eviction triggers an invalidation, and the line disappears from the L1 even though the core was actively using it.

Back-invalidation is the price

The back-invalidation is not a bug; it is the mechanism that preserves the invariant. Its cost is that the effective L1 capacity depends on the L2’s replacement decisions. A line that is frequently used by one core but rarely re-referenced across the whole machine is exactly the line that an L2 policy evicts, and evicting it destroys a private-cache hit. Workloads with per-core working sets that are large relative to the shared cache suffer disproportionately: the L2 sees no reuse and evicts, while each L1 sees heavy reuse and loses its lines.

The effect is measurable as a gap between the L1 hit rate the cache would achieve in isolation and the one it achieves in the hierarchy. It is also the reason some designs use a replacement policy in the L2 that is biased toward keeping lines that are resident in private caches — a hint bit set on fill from a core and consulted at eviction. That bias is a partial inclusion policy: the L2 keeps lines it knows are duplicated, which reduces back-invalidations at the cost of retaining lines with no shared-level reuse.

An inclusive design has one further property that matters for correctness in some systems: it makes the L2 a complete map of what is cached anywhere, so a cache flush or a page-table invalidation can be performed by walking the L2 alone. Systems that must support a coherent view across a device or a hypervisor boundary sometimes require that completeness, which is why inclusion persists in designs where its performance cost is recognised.

Exclusive: a victim cache at machine scale

An exclusive hierarchy maintains the opposite invariant: a line resides in exactly one level at a time. A fill into the L1 removes the line from the L2; an eviction from the L1 places the line into the L2. The L2 becomes a victim cache for the private caches, and the aggregate capacity is the sum of all levels rather than the maximum.

The benefit is capacity. For a machine with 8 cores, 32 KiB L1s, and a 16 MiB L2, the inclusive arrangement has 16 MiB of distinct lines; the exclusive arrangement has 16 MiB plus whatever the L1s hold, though the overlap is by definition zero, so the gain is at most the L1 total — 256 KiB here, under 2 percent of the shared cache. That is small, and the arrangement’s real cost is a swap on every transition: a fill into the L1 must first write the evicted line into the L2 and read the incoming one out, which doubles the traffic between the levels. The arrangement therefore pays off only when the private caches are large relative to the shared one, so that the capacity recovered is worth the extra transfer on every fill; when the shared level is an order of magnitude larger, as it is in a server part, the recovered capacity is a rounding error against the added traffic.

Exclusivity complicates the snoop filter. The L2 no longer contains a superset of the private caches, so it cannot answer “who holds this line” from its own tags alone. Designs pair an exclusive L2 with a separate directory or with a probe of the private caches, which reintroduces the broadcast that inclusion was meant to remove. That is the reason exclusive hierarchies are uncommon in machines with many cores and common in small ones where probing every cache is affordable.

Non-inclusive: no invariant at all

Most current server designs are non-inclusive. The L2 neither guarantees presence nor guarantees absence, and the coherence information lives in a separate structure — a snoop filter or a directory at the last level that tracks presence without constraining the data arrays.

The arrangement frees the last level to use its capacity for whatever it wants, which for a shared cache means lines with reuse anywhere in the machine. A line hot in one core’s L1 may be evicted from the shared level without consequence, because the shared level never claimed to hold it. That removes the back-invalidation problem entirely. The cost is that the snoop filter must be maintained independently: it is updated on every fill and eviction from any level, and it must be correct even when the data arrays disagree with it. A filter that says a core holds a line when it does not produces a spurious invalidation, which is harmless; one that says a core does not hold a line when it does produces a stale read, which is a correctness bug. Filters are therefore built conservatively, sometimes tracking a superset of the actual holders.

The storage cost of a filter is per-line and per-core. A presence vector of 16 bits per line for 16 cores, at 64 bytes per line, is 2 bytes per line — about 3 percent of the data array, which is cheaper than the inclusive design’s requirement that the shared cache hold every private line. That accounting is the reason the non-inclusive design won: inclusion pays capacity for coherence metadata, while a filter pays only metadata.

Choosing between them

The trade has three axes and the answer depends on which one the machine is limited by.

Property	Inclusive	Exclusive	Non-inclusive
Aggregate capacity	Shared level only	Sum of levels	Shared plus private
Coherence lookup	Free from shared tags	Requires probe or directory	Requires filter
Back-invalidation	On shared eviction of a private line	None	None
Inter-level traffic	One fill per line	Fill plus swap	One fill per line
Flush completeness	Shared level is complete	Not complete	Not complete

Inclusive wins when the shared level is small relative to the private caches and coherence simplicity dominates, which describes multi-socket machines of an earlier generation and describes the L1–L2 relationship within a core today: a 48 KiB L1 behind a 2 MiB L2 is nearly always inclusive, because the L2 is large enough that back-invalidations are rare.

Non-inclusive wins when the shared level is large and the core count is high, which describes the last-level cache of a current server part. The filter’s storage is small, the shared cache is free to hold only lines with genuine reuse, and the private caches keep their working sets.

A detail that cuts across all three: the property is about presence, not about state. It also determines what a back-invalidation does to the replacement state of the private line it removes. An inclusive hierarchy must propagate state changes downward as well as presence — a line invalidated in the L1 because another core wrote it must be reflected in the shared level’s sharing information. That propagation is the hidden cost of the inclusive design, and it is why the protocol’s transitions have to be defined at every level rather than only at the level that owns the line.