Parallel virtualized memory translation with nested elastic cuckoo page tables

Turning a memory address into a real one inside a virtual machine can take twenty-four memory accesses one after another, because the address table is a tree walked by following pointers and every step of the guest's four-step walk needs its own four-step host walk to resolve — and five-level tables push that to thirty-five; replacing the tree with a hash table collapses it to three, but this paper (Illinois and CMU) shows the obvious version of that gains almost nothing, because a hash lookup is not one access when you must hedge across page sizes and collision slots, and nesting SQUARES the hedge from nine parallel accesses to eighty-one.

Why this problem is worth solving

The cost is structural rather than incidental, and the arithmetic is worth doing slowly.

The alternative removes the chain, but introduces a different cost that this paper is really about.

What people did before, and where it broke

• Cache the translations. Multi-level translation buffers hold recent results, page-walk caches hold intermediate tree levels, and nested buffers cache the four-step host walk needed to reach each guest level. These are real and effective, and every shipping processor has them.
• But they are no longer sufficient. Translation still reaches more than half of execution time for some applications, buffer access times have overtaken second-level cache access times, and memory capacities heading into terabytes make the working sets worse.
• Use huge pages. Mapping 2MB or 1GB at a time shrinks the metadata and cuts levels off both walks, which genuinely helps and is measured here as a large effect.
• But it shortens the chain rather than removing it. The walk is still sequential, and applications that cannot use huge pages for their whole dataset get partial relief at best.
• Combine nested and shadow paging. Agile Paging exploits the observation that upper levels of the tree rarely change, switching between mechanisms to avoid redundant work.
• But it still leaves four sequential accesses in the best case, plus hypervisor intervention. Simulated in an idealised form with no hypervisor cost at all, it is still 16 percent behind the design here.
• Put a very large translation buffer in memory itself. This removes a substantial fraction of page walks outright.
• But a miss in it still costs a full walk, and the access to it is itself a memory access.
• The gap. Everyone was shortening or avoiding the sequential chain. Hashing eliminates it, and the prior work that made hashing practical for native systems existed — but nobody had checked what happens when you nest it, and the answer is that the parallel fan-out squares and eats the gain.

How the fan-out gets pruned back down

The idea

Parallelism does not remove work, it moves it from latency to bandwidth. The appeal of hashing is easy to state — twenty-four dependent accesses become three — and it is genuinely what happens to the critical path. What the naive version misses is what those three accesses cost. Because the page size is unknown and collisions put an entry in any of several slots, each lookup speculatively issues nine memory accesses and discards eight. In a native system that is a tolerable trade. Nested, each of those nine addresses is itself virtual and needs its own nine-way lookup, so the first step alone issues eighty-one. The paper’s most useful measurement is of the design it does not propose: taking a hashing scheme that works well natively and nesting it directly yields about 5 percent, because the traffic saturates the cache bandwidth the design depends on. Even the final system issues 13 to 15 percent more memory requests than the tree it replaces — it wins because those requests overlap. Recognising that a technique which looks free on the critical path is actually spending a different resource, and that the exchange rate can be brutal in a new setting, is the same check-what-you-are-actually-paying-with reasoning covered elsewhere on this site where a design accepts more of one quantity to buy less of another and must measure both.

Almost all the gain comes from the unglamorous part. The headline idea is the hash table; the contribution is the pruning. Small side structures record which page-size table and which slot really holds each translation, so the hardware can narrow the speculative fan-out — ideally to a single access — before issuing anything. This paper provides them for guest and host separately, managed by the guest operating system and the hypervisor respectively, and the measured split is stark: the plain nested hashing design is worth 5 percent, and the pruning techniques carry it to 19. One of them addresses a recursion that only exists because of nesting: when the structure that prunes GUEST accesses misses, reading it requires translating its own address, so a small dedicated cache is added for exactly those mappings. Ten entries suffice. Reporting that the novel-sounding mechanism contributes a quarter of the result while three supporting caches contribute the rest is the kind of honest decomposition covered elsewhere on this site where a paper’s own ablation shows which of its parts is actually load bearing.

Flexibility has a price, and here it closes off the obvious next step. The scheme uses cuckoo hashing so that collisions never require a chain, and resizes its tables while the process runs so they track its memory use. Both are why it works. Both also mean an entry’s physical location is not stable: inserting one translation can shuffle others between slots, and a resize migrates everything. That has a specific consequence the authors identify and accept. The three remaining accesses could plausibly become two, by caching the pointer found in the first step that says where the guest entry lives — the natural analogue of what existing processors already cache for trees. But those pointers go stale every time a rehash or resize moves the entry they point at, and keeping them correct would mean flushing. So the design declines the optimisation and stays at three. Identifying that the mechanism giving a design its flexibility is precisely what forbids a further improvement, and saying so rather than working around it, is the same name-the-cost-of-your-own-choice discipline covered elsewhere on this site where an approach’s enabling property turns out to also be its ceiling.

One address, three accesses, eighty-one hedges

the buffers that cache these results are effective but insufficient, with translation exceeding half of execution time on some applications
processors adding a fifth level take the worst case from twenty-four to thirty-five

Why it works

• Hashing removes the pointer chain entirely → three accesses replace twenty-four regardless of how many tree levels there would have been → so the design also absorbs the move to five-level tables that would take trees to thirty-five.
• Page size and collision slot are both unknown, and nesting requires translating every speculative address → the fan-out squares from nine to eighty-one → which is why nesting a natively-good design directly yields only about 5 percent.
• Side tables record where each translation really lives → the hardware narrows the fan-out before issuing anything → bringing measured averages to 2.8, 2.8 and 1.6 accesses per step and carrying the gain from 5 percent to 19.
• The finest-grained host structure helps some applications and thrashes for others → enabling it, watching its hit rate, and disabling it when poor lets each application settle → contributing about 4 percent that a fixed policy could not get for both groups.
• Sequential chains produce long latency tails while parallel bursts do not → the distribution changes shape, not just its mean → so walks that ran to several hundred cycles typically complete in about four memory-access times.

What it costs (trade-offs and scope)

• It uses more memory bandwidth, not less. The design issues 13 to 15 percent more requests to the cache hierarchy than the tree it replaces. It wins because they overlap, which means the benefit depends on there being bandwidth to spend.
• The headline mechanism is a small part of the result. Plain nested hashing gives 5 percent; the three supporting caches give the rest. One of the four contributions, exploiting knowledge that page tables use 4KB pages, is measured at 0.4 to 0.5 percent and the authors say so.
• Three accesses is a floor, not a target. Caching the pointer found in the first step would make it two, but rehashing and resizing move entries and would make those pointers stale, so the optimisation is declined.
• It needs new hardware and coordinated software. New caches in the memory management unit, plus side tables maintained separately by the guest operating system and the hypervisor. The migration path helps but does not remove this.
• Everything is simulated. Results come from full-system simulation of 500 million instructions per application after warm-up, not from hardware, though some huge-page behaviour was checked against real systems.

The evaluation

Eleven applications were simulated with footprints from 6.9 to 64 gigabytes — eight graph analytics kernels, a bioinformatics sequence matcher, a random-access HPC benchmark and a database workload — each run for 500 million instructions after a 50 million instruction warm-up, with a deterministic methodology that needs no error bars. Configurations covered nested and native, with and without huge pages, plus a hybrid in which only the host side is converted, and an idealised version of a competing technique given no hypervisor cost at all.

Check yourself

Sources

• Parallel Virtualized Memory Translation with Nested Elastic Cuckoo Page Tables (author PDF, Carnegie Mellon) — ASPLOS 2022; the full 14-page paper, read in full for this explainer.
• ACM Digital Library (DOI 10.1145/3503222.3507720) — published version.