Mosaic Pages: Big TLB Reach with Small Pages

Krishnan Gosakan, Jaehyun Han, William Kuszmaul, Ibrahim N. Mubarek, Nirjhar Mukherjee, Karthik Sriram and 10 others

Every memory access needs a virtual-to-physical translation, cached in a tiny TLB whose "reach" — the memory it covers — is far too small for big-data working sets, and a miss triggers a slow page-table walk that can eat 20-80% of runtime; the standard fix, huge pages, boosts reach but demands large runs of CONTIGUOUS physical memory that fragment and bloat; Mosaic Pages (a theory-and-systems team) instead packs FOUR-or-more separate translations into a single TLB entry by a clever trick — restrict each page to one of just ~100 possible physical slots chosen by a hash, so its physical address compresses from 36 bits to 7 and several fit where one used to — multiplying TLB reach 4x to 64x while keeping ordinary 4 KB pages and needing no physical contiguity at all, cutting TLB misses by 59-98% on graph and database workloads.

The argument in one glance

Problem

The TLB is too small to cover a big-data working set

Every single memory access first needs to translate its virtual address into a physical one, and the CPU keeps a small cache of recent translations, the Translation Lookaside Buffer (TLB), so it does not have to walk the page tables each time. When a translation is not in the TLB — a TLB miss — the hardware performs a slow, multi-level page-table WALK to find it. For big-data applications these misses are a major tax: 20-30% of runtime typically, up to 83% in the worst cases. The reason is that the TLB's REACH — the total memory its entries can cover at once — is tiny: a TLB using 4 KiB pages might cover only about 8.6 MiB, while a graph application's working set is hundreds of megabytes. Most accesses fall outside the reach and miss.
What people did

Cover more memory per entry with huge pages

Since TLB reach is entries times page size, and you cannot easily add entries, the standard fix is to make each page bigger. HUGE PAGES (2 MiB or 1 GiB instead of 4 KiB) let one TLB entry cover far more memory, multiplying reach by 512x or more without adding a single entry. Operating systems ship transparent huge-page support for exactly this reason, and on a clean system the gains are real — a cold-cache Redis workload speeds up 29% moving from 4 KiB to 2 MiB pages.
Why it fell short

Huge pages need contiguous physical memory, which fragments and bloats

The catch is that a huge page must map to a large run of CONTIGUOUS PHYSICAL memory — a 2 MiB page needs 2 MiB of adjacent physical frames. That contiguity is expensive and fragile. Over time physical memory fragments, and finding a free 2 MiB run requires costly defragmentation and compaction; the same Redis workload that gained 29% on a clean system drops to only 89% of baseline throughput when memory is 50% fragmented. Huge pages also cause internal fragmentation and memory BLOAT — allocate 2 MiB to hold a few kilobytes and the rest is wasted — and they coarsen protection and accounting to 2 MiB granularity. Prior coalescing schemes that stitch small pages into bigger TLB entries still depend on residual physical contiguity and need complex hardware. The whole family of fixes is chained to physical contiguity, which the OS cannot cheaply guarantee.
This paper's idea

Pack many small translations into one entry, using virtual not physical contiguity

Mosaic Pages (a Stony Brook, Yale, and Rutgers theory-and-systems collaboration — Gosakan, Kuszmaul, Bender, Bhattacharjee, Farach-Colton, Johnson, Porter, and colleagues) increases TLB reach a completely different way: pack several discrete translations (say 4, up to 64) into ONE TLB entry, exploiting VIRTUAL contiguity for locality while requiring NO physical contiguity. The trick is compression by restricted placement. Normally a physical frame number needs about 36 bits because a page could be anywhere in memory; but if you restrict each page to only about 100 possible physical slots chosen by a hash of its virtual address, its location fits in just 7 bits — a compressed physical frame number. Four of those fit in the space a single ordinary translation used, so one TLB entry now covers four (or more) 4 KiB pages that are scattered anywhere in physical memory. The result: 4x to 64x more reach while keeping small pages and needing no contiguity — cutting TLB misses 59-98% on graph and database workloads.

Why this problem is worth solving

Address translation sits on the critical path of every memory access, so when the TLB cannot keep up, it taxes the entire machine — and that tax is growing, because the mismatch between what the TLB can cover and what applications need keeps widening. The quantity that matters is

the total amount of memory a TLB can hold translations for at one time, equal to its number of entries multiplied by the page size. It is what determines how much of an application’s working set can be accessed without a TLB miss. The problem is that reach is not keeping up with memory: application working sets and system memory have grown into the gigabytes and terabytes, but the number of TLB entries grows extremely slowly — a recent Intel server has only about 2,488 second-level TLB entries — so with 4 KiB pages the TLB reaches only a few megabytes, a vanishing fraction of a big-data working set. The reason entries cannot simply be added is that the TLB is consulted on EVERY memory access and must answer in a cycle or two, so it must stay small and fast; scaling it up would slow down every access. So reach cannot grow by growing the TLB — it has to grow by covering more memory PER entry

. That is the whole design space, and until Mosaic it had essentially one answer: bigger pages.

Bigger pages, though, buy reach with a currency that is scarce and getting scarcer. A huge page increases the memory covered per entry only by demanding

a large, unbroken run of adjacent physical page frames to back a single large virtual page — a 2 MiB huge page must be backed by 2 MiB of contiguous physical memory. This is the hidden cost of huge pages. As a system runs, physical memory becomes fragmented — free frames scattered among used ones — so finding a large contiguous run requires the OS to defragment and compact memory, which is slow and disruptive, and often it simply cannot, so the huge page is not granted and the benefit disappears. Contiguity also forces all-or-nothing allocation (map the whole 2 MiB even to store a few kilobytes, wasting the rest) and coarsens protection and dirty/accessed tracking to the huge-page granularity. Every prior scheme that enlarges TLB reach — huge pages, coalescing, contiguity-aware designs — leans on some form of this physical contiguity, which the OS cannot cheaply or reliably provide

. The deep observation behind Mosaic is that locality comes from VIRTUAL contiguity — the application allocates virtually-contiguous regions and accesses them with locality — and physical contiguity was only ever a means to compress the translation, not a requirement of the workload. Break that false dependency, and you can have big reach with small pages.

What people did before, and where it broke

Small (4 KiB) pages. The default. Fine-grained protection, low fragmentation, easy allocation — but tiny reach (about 8.6 MiB), so big-data workloads miss constantly and pay the page-walk tax.
Huge pages (2 MiB / 1 GiB). One entry covers far more memory, a real win on a clean system (29% on Redis). But they need large contiguous physical runs that fragment away (dropping to 89% at 50% fragmentation), cause internal fragmentation and bloat, and coarsen protection.
Coalescing / contiguity-aware TLBs (perforated pages, shadow page tables). Merge several small pages into one TLB entry when they happen to be physically contiguous. Cleverer than huge pages, but still dependent on residual physical contiguity — so the benefit still evaporates as memory fragments — and they add hardware complexity.
Bigger or more TLB entries. Just build a larger TLB. Blocked by the latency wall: the TLB is on every access’s critical path, so it cannot grow much without slowing every memory access.
The gap. No scheme increased TLB reach WITHOUT depending on physical contiguity and WITHOUT growing the TLB. Mosaic does, by compressing several scattered translations into one existing-width entry via restricted physical placement — decoupling reach from both page size and contiguity.

How Mosaic works

Group virtually-contiguous pages, compress their scattered addresses, and place them stably

Accept the bind: reach must grow without growing the TLB

The TLB is on every memory access's critical path, so entries cannot be added or widened without slowing the machine. Mosaic therefore targets the only remaining lever — cover more memory per existing entry — but unlike huge pages it does so without demanding physical contiguity.
↓ →
Group a run of virtually-contiguous small pages new

Mosaic bundles a (default 4, up to 64) virtually-contiguous 4 KiB base pages into one "mosaic page." The base pages stay small and independent, and their physical frames may be scattered anywhere — Mosaic uses the virtual contiguity purely for locality, not to imply any physical arrangement.
↓ →
Compress each physical address by restricting placement new

A physical frame number normally needs about 36 bits because a page could sit anywhere among billions of frames. Mosaic restricts each page to only about 104 possible physical slots, chosen by hashing its virtual address — so naming which slot it landed in takes just 7 bits, a Compressed Physical Frame Number. Four 7-bit CPFNs fit where one 36-bit translation did.
↓ →
Place pages with a stable hash table (Iceberg hashing) new

Physical memory is organized as a bucketed hash table: each virtual page hashes to a small set of buckets and may occupy any of ~104 slots across them (front-yard bins plus a few power-of-choices backyard bins). Iceberg hashing is the key enabler — it gives low associativity, high utilization (98% before conflicts), AND stability (a page never moves once placed, so no migration cost).
↓ →
Store a Table of Contents per TLB entry new

One TLB entry, indexed by the mosaic virtual page number, holds a Table of Contents — the run of compressed frame numbers, one per base page — plus per-base-page valid bits. A small offset in the virtual address selects which CPFN to use, and the page table's leaves are modified to map mosaic pages to these Tables of Contents.
↓ →
Erase associativity conflicts with a 2% slack (Horizon LRU) new

If all ~104 slots a page could use are full of hot pages, an associativity conflict would force an eviction. Mosaic avoids ever hitting this by treating memory as about 2% smaller (a "horizon" timestamp plus ghost pages), so the system only ever sees ordinary capacity evictions, never associativity conflicts — the first conflict would otherwise appear only at 98% utilization anyway.

Evaluated in simulation with comparable hardware to a traditional TLB, on Graph500, BTree, XSBench, and GUPS, at mosaic arities from 4 (16 KiB) to 64 (256 KiB). The tabulation-hashing circuit synthesizes to 4 GHz at 28nm for about 13.8 kilogates — negligible cost. Prototype allocates 4 GiB to mosaic on a 4-core system.

The idea

Restrict where a page can go, and its address gets small enough to pack. The elegant core of Mosaic is a compression-by-constraint trade. An address is large because the thing it names could be anywhere — a physical frame number needs about 36 bits precisely because a page has billions of possible homes. Take away most of that freedom — restrict a page to only about 100 hashed slots — and naming its home now takes only 7 bits, small enough that four addresses fit where one used to. Mosaic spends placement freedom to buy address compression, and address compression is reach. This is the same fewer-possibilities-means-fewer-bits logic the site meets in quantization (an 8-bit number restricts the values a weight may take so it fits in fewer bits), applied here to WHERE a page may live rather than WHAT value a number may hold — a set-associative constraint on physical memory that turns placement latitude into TLB reach. The insight is that the freedom being given up (a page being able to live literally anywhere) was worth far less than the reach it buys.

Use the contiguity you have for free, not the kind that is scarce. Every prior reach-boosting scheme conflated two different things: virtual contiguity (the application allocates and accesses a contiguous virtual region, giving locality) and physical contiguity (the backing frames are adjacent, which let huge pages compress the translation). Mosaic’s deep move is to separate them — keep the virtual contiguity, which the workload provides for free and which is all that locality needs, and drop the physical contiguity, which the OS must expensively manufacture and which the workload never actually required. Reach was chained to physical contiguity only because that was the historical way to compress a translation; Mosaic compresses it a different way (restricted placement), so the chain falls off. This is the decouple-two-things- people-conflated discipline the site rewards — the persistent-memory page separating durability from the block format, the taint-analysis page separating where data enters from where you can trace it — and here it frees TLB reach from the physical contiguity that made huge pages so fragile.

Import deep theory so the constraint costs almost nothing. Restricting placement only works if the restriction does not itself create problems — pages that cannot be placed, sets that overflow, data that must be migrated. Mosaic’s feasibility rests entirely on recent hashing theory: Iceberg hashing gives low associativity, 98% utilization, and STABILITY (a page never moves after placement, so restricting its home costs no migration) all at once, which no earlier scheme achieved; tabulation hashing computes the placement on the TLB critical path with no added latency; and Horizon LRU turns rare associativity conflicts into ordinary capacity evictions by conceding about 2% of memory. This is the borrow-a-solved-model discipline the site keeps seeing — the tiered-memory page lifting a CountMin-Sketch from Row-Hammer defense, the compiler-autotuning page casting its problem as Bayesian optimization — where the systems contribution is recognizing that a hard practical constraint is exactly the problem some deep data-structure theory already solves.

Packing four translations into one TLB entry

From constant page-walks to a 4x-deeper reach

Increasing TLB reach for a big-data workload. Numbers from Mosaic's evaluation.

Step 1 of 5

The reach problem

A TLB with 4 KiB pages covers only about 8.6 MiB, but a graph workload touches hundreds of megabytes, so most accesses miss and trigger a slow page-table walk. You cannot fix this by adding TLB entries — the TLB is on every access's critical path and must stay small and fast — so the only lever is to cover more memory per entry.

TLB misses cost 20-30% of runtime typically, up to 83% for the worst applications
a recent server has only ~2,488 L2 TLB entries while memory scales to terabytes

Why it works

The TLB cannot grow (it is on every access’s critical path) and huge pages need scarce physical contiguity → Mosaic covers more memory per existing entry by packing several translations, using only virtual contiguity → reach grows 4x to 64x with small pages and no contiguity.
A physical frame number is large because a page could be anywhere → restricting each page to about 104 hashed slots shrinks its address to 7 bits → four compressed addresses fit where one 36-bit translation did.
Restricting placement risks unplaceable pages and migration → Iceberg hashing gives stability (no page ever moves) and 98% utilization before conflicts → the constraint costs no migration and almost no capacity.
A full slot-set would cause an associativity conflict → Horizon LRU concedes about 2% of memory so only capacity evictions ever occur → conflicts are eliminated with negligible overhead and no global LRU list.
Locality comes from virtual, not physical, contiguity → Mosaic keeps the virtual contiguity the workload provides for free and drops the physical contiguity the OS must manufacture → TLB misses fall 59-98% without the fragility of huge pages.

What it costs

About 2% memory overhead. Horizon LRU works by treating memory as slightly smaller to avoid conflicts, so roughly 2% of capacity is conceded; under very slight memory pressure this can make Mosaic swap a little more than Linux (it reverses as pressure grows).
Coarse-grained metadata. Permissions and dirty/accessed bits are tracked at mosaic-page granularity, not per base page, so a production design needs either alignment-aware recompilation or wider TLB entries to restore per-page protection.
No page sharing yet. The prototype does not support duplicate mappings of the same physical memory or sharing across address spaces, so shared library code is copied — trading extra DRAM for reach — and fork() inheritance of mosaic pages is unsupported.
Missing production features. A real deployment must integrate with memory encryption (Intel TME, AMD SEV), sub-page protection keys (MPK), trusted execution (SGX), and nested paging for virtualization — none handled by the prototype.
Locality-dependent benefit. The gains scale with how much virtual-contiguity locality a workload has; a truly random-access benchmark like GUPS gains far less (about 26%) than graph or database workloads.

The evaluation

Simulation with hardware comparable to a traditional TLB, on Graph500, BTree, XSBench, and GUPS, at mosaic arities from 4 (16 KiB mosaic pages) to 64 (256 KiB), compared against vanilla small pages and against fully-associative and huge-page baselines, plus an FPGA and 28nm synthesis of the hashing hardware.

Ways to increase TLB reach

Property	Small (4 KiB) pages	Huge (2 MiB) pages	Mosaic pages
Physical contiguity required
Fragmentation / bloat
Reach per TLB entry
Protection granularity
TLB miss reduction

Mosaic gets most of the reach benefit of huge pages while keeping the flexibility of small pages, because it decouples reach from physical contiguity — a direct-mapped Mosaic-8 TLB even beats a fully-associative traditional TLB on Graph500, BTree, and XSBench, at about 2% memory overhead and negligible hardware cost.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

Mosaic’s benefit tracks how much virtual-contiguity locality a workload has, so graph and database workloads gain a great deal (59-98% fewer misses) while a purely random benchmark like GUPS gains far less (about 26%). Its conflict-avoidance concedes roughly 2% of memory, which under very slight memory pressure can make it swap a bit more than Linux (reversing as pressure grows). The prototype tracks permissions and dirty/accessed bits at mosaic-page granularity rather than per base page, so restoring fine-grained protection needs alignment-aware recompilation or wider entries; it does not yet support page sharing, duplicate mappings, or fork() inheritance (shared code is copied, spending DRAM for reach); and a production deployment must still integrate memory encryption, protection keys, trusted execution, and nested paging. None of this undercuts the core idea — that TLB reach was needlessly chained to physical contiguity, and you can instead compress several scattered translations into one existing-width entry by restricting each page to a small hashed set of physical slots, so its address shrinks from 36 bits to 7 and several fit together, multiplying reach 4x to 64x with ordinary small pages, no contiguity, and about 2% overhead, made practical by hashing theory (Iceberg hashing for stable high-utilization placement, Horizon LRU to erase conflicts, tabulation hashing to run on the critical path).

Background

Trade freedom for compressibility, and use the contiguity you already have

Mosaic sits in the site’s memory-systems cluster, near the CXL tiered-memory and persistent-memory pages, and rhymes with several ideas covered elsewhere on this site. Its central move is a compression-by-constraint trade: an address is large because the thing it names could be anywhere, so restricting a page to a small hashed set of slots shrinks its address enough to pack several per entry — the same fewer-possibilities-means-fewer-bits logic the 8-bit-numerics page uses when it restricts the values a weight may take, applied to WHERE a page lives rather than WHAT a number is, and a set-associative constraint that turns placement freedom into TLB reach. Its deep insight is to separate two things prior work conflated — virtual contiguity (free, and all locality needs) from physical contiguity (scarce, and only ever a means to compress the translation) — the decouple-what-was-needlessly-coupled discipline the persistent-memory page uses to split durability from the block format and the firmware-taint page uses to split where data enters from where you can trace it. Its feasibility rests on importing deep theory to make a hard constraint cheap — Iceberg hashing for stable, high-utilization, low-associativity placement, tabulation hashing on the critical path, Horizon LRU to convert conflicts into capacity evictions — the borrow-a-solved-model move the tiered-memory page makes lifting a CountMin-Sketch from Row-Hammer defense and the autotuning page makes casting its search as Bayesian optimization. And its Horizon LRU trick — concede about 2% of memory so a hard corner case (associativity conflicts) never arises — is the spend-a-little-slack-to-erase-the-tail discipline the worst-case- provisioning family shares. Even the constraint that forces the whole approach — the TLB cannot grow because it is on every access’s critical path — is the keep-the-hot-path-small lesson the datacenter IO-control and persistent-memory-database pages turn on.

If you remember only three things

1. Address translation is on the critical path of every memory access, and the TLB that caches translations has a REACH (entries times page size) of only megabytes while big-data working sets are gigabytes, so misses trigger slow page-table walks that cost 20-83% of runtime; the TLB cannot simply grow (it must answer in a cycle or two), so the standard fix is huge pages — but those require large physically-contiguous memory runs that fragment away, bloat memory, and coarsen protection, chaining reach to a contiguity the OS cannot cheaply provide.
2. Mosaic Pages increase reach a different way: pack several discrete translations (4, up to 64) into one existing-width TLB entry using VIRTUAL contiguity for locality but no physical contiguity, by compressing each physical address — restrict every page to about 104 possible physical slots chosen by hashing its virtual address, so its location needs only 7 bits (a compressed frame number) instead of 36, and four fit where one did — made practical by Iceberg hashing (stable, no-migration, 98%-utilization placement), Horizon LRU (concede ~2% of memory to turn associativity conflicts into ordinary capacity evictions), and tabulation hashing on the critical path.
3. The result multiplies TLB reach 4x to 64x while keeping ordinary 4 KiB pages, cutting TLB misses 59-98% on graph and database workloads (a direct-mapped Mosaic-8 TLB even beats a fully-associative traditional one) at about 2% memory overhead and a negligible 4 GHz hashing circuit — with honest limits (locality-dependent benefit, coarse metadata, no page sharing yet, missing production features). The durable lessons: trade placement freedom for address compressibility, decouple the free structure (virtual contiguity) from the scarce one (physical contiguity), and import the data-structure theory that makes a hard constraint nearly free.

Check yourself

Check your understanding

1. Mosaic compresses a physical frame number from about 36 bits down to 7 by restricting where each page may be placed in physical memory. Predict how giving up placement freedom makes the address smaller.
2. Huge pages boost TLB reach but require contiguous physical memory; Mosaic boosts reach using only VIRTUAL contiguity. Predict why this distinction is the crux of the whole design.
3. Restricting each page to about 104 hashed slots risks a page having nowhere to go (all its slots full) or needing to be moved later. Predict why Mosaic's reliance on Iceberg hashing is essential rather than incidental.
4. Mosaic's Horizon LRU deliberately treats physical memory as about 2% smaller than it really is. Predict why conceding a little capacity is a good trade.

Sources

ACM DL: Mosaic Pages: Big TLB Reach with Small Pages — ASPLOS 2023 (full text read via the ACM PDF; no arXiv preprint).
Artifact (GitHub, oscarlab/mosaic-asplos23-artifacts) — open-source artifacts.