Direct Memory Translation for Virtualized Clouds

Running a program inside a cloud virtual machine makes the CPU pay a brutal hidden tax on every memory access — a miss on the address-translation cache can trigger up to 24 sequential memory fetches, because the guest and host page tables must both be walked, and nesting a VM inside a VM makes it worse still; this work from Illinois builds DMT, a hardware-software redesign that skips the walk entirely by keeping each region's final translation entries in a contiguous array the hardware can index directly, cutting the fetches to just one, two, or three and speeding virtualized page walks 1.58 times.

The argument in one glance

Problem

Address translation is a bottleneck, and virtualization makes it worse

Every memory access needs its virtual address translated to a physical one, done by walking a multi-level page table on a translation-cache miss — four sequential fetches on native x86. Inside a virtual machine the walk becomes two-dimensional, because each step of the guest walk must itself be translated through the host page table, exploding to as many as 24 sequential fetches. For memory-intensive cloud workloads this can be over half of execution time, and it only grows with five-level tables and nested VMs.
What people did

Shorten, cache, or hash the page-table walk

Prior work attacks the walk from several angles: huge pages cut a level or two, prefetchers and caches try to hide the memory accesses, flattened page tables merge adjacent levels, and hash-based tables fetch entries by hashing rather than walking a tree. Each reduces the cost of the walk in some setting.
Why it fell short

None escapes the sequential walk while staying compatible and scalable

Huge pages cannot eliminate the sequential accesses; even with perfect caching the hardware still fetches tens of entries one after another, and the nested walk is a dependency chain that cannot be prefetched in parallel. Flattening still needs eight fetches in a VM. Hash-based tables get the step count down but demand hash computation, many parallel lookups, table resizing, and break x86 compatibility. And nested virtualization has no hardware translation support at all, forcing slow shadow paging with frequent VM exits.
This paper's idea

Index the final translation entry directly, skipping the walk

DMT observes that the whole radix walk exists only to locate the last-level entry that holds the actual translation. So it has the OS store each memory region's last-level entries in a contiguous physical array, and keeps the region-to-array mapping in a few hardware registers. On a miss, the hardware computes an offset and fetches the final entry directly — one reference natively, two in a VM, three when nested, growing linearly with virtualization depth instead of exploding.

Why this problem is worth solving

The reason virtualization turns a manageable cost into a crippling one is that the walk does not just get longer — it gets multiplied.

On native x86 the page table is a four-level radix tree, so translating an address the translation cache missed on takes up to four sequential memory fetches: read level four to find where level three is, read level three to find level two, and so on down to the last-level entry that finally names the physical page. Inside a virtual machine, though, the guest operating system runs on virtualized physical memory it does not truly own, so its guest-physical addresses are not real host addresses. The hardware must therefore run a two-dimensional walk: it walks the guest page table, but every single level it wants to read is itself a guest-physical address that must be translated through the host page table first. Four guest levels, each needing a four-level host walk to locate, plus a final host walk for the data, comes to as many as 24 sequential fetches for one translation, or 35 with five-level tables. The killer is that these fetches form a dependency chain — you cannot know where the next entry lives until you have read the current one — so they cannot be issued in parallel or fully hidden behind caches. This is why nested translation can eat more than half the execution time of a memory-intensive workload, and why it is the bottleneck worth attacking.

The insight that makes a direct shortcut possible is a fact about how programs actually lay out their memory.

An operating system organizes a process’s virtual address space into Virtual Memory Areas, or VMAs: contiguous regions that each hold one kind of data with one protection — the heap, the stack, the code, a memory-mapped file. A typical process has a few hundred VMAs, but the crucial empirical fact is that only a handful of them are large and heavily accessed. The authors measured real applications and the SPEC benchmark suites and found that in nearly every workload, just 16 VMAs cover 99 percent of the working set, with the heap region dominating; even Memcached, with 778 VMAs, collapses to two clusters once you merge neighbors separated by tiny gaps. And these regions are mostly created once at startup and rarely change during the run. That combination — few big regions, mostly static — is exactly what a hardware shortcut needs. If the mapping from each region to where its translations live can be described compactly, it fits in a few registers the hardware reads instantly, and because the regions rarely change, the cost of maintaining that mapping is paid once and amortized over billions of fast translations. DMT is built entirely on exploiting this structure.

What people did before, and where it broke

Huge pages (2 MB and 1 GB). Map memory in larger chunks, cutting one or two levels off the walk and improving translation-cache coverage. Where it broke. They shorten the walk but cannot eliminate its sequential nature, are less scalable, and still leave a multi-fetch walk on a miss; DMT is complementary and benefits from them.
Translation caching and PTE prefetching (for example, ASAP). Cache or prefetch upper-level entries so the walk hits in cache instead of memory. Where it broke. Even from cache the hardware still fetches tens of entries sequentially, orders of magnitude slower than a translation-cache hit, and the nested walk’s dependency chain cannot be prefetched in parallel.
Flattened page tables (FPT). Merge adjacent radix levels so a native walk needs two fetches instead of four. Where it broke. In a virtual machine the two-dimensional walk still costs eight sequential fetches, far from the ideal.
Hash-based page tables (ECPT). Fetch an entry by hashing the address rather than walking a tree, reaching a low step count. Where it broke. They require hash computation, issue many parallel lookups (up to 81 when nested), must resize their hash tables as entries are added or removed since the count is not known ahead of time, risk hash collisions, and are not backward-compatible with x86.
The gap. No design fetched only the final entry while staying simple, backward-compatible with x86, and scalable to nested virtualization. Hash tables got the step count down but were complex, incompatible, and needed resizing; radix, flattening, and prefetching could not escape the sequential walk. A direct, compatible, nesting-friendly shortcut was missing — which is what DMT provides.

How DMT works

From a 24-fetch nested walk to a direct index

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Fetch the answer directly instead of walking a structure to find it. The entire multi-level page-table walk exists for one purpose: to locate the last-level entry that actually holds the virtual-to-physical translation. Every earlier fetch is just navigation. DMT precomputes a direct index to that final entry and throws the navigation away, turning a four-step native walk into a single fetch. Replacing a sequential traversal of a lookup structure with one direct index into a precomputed array is the same move the concurrency-analysis data structure covered elsewhere on this site makes, answering a reachability question by indexing straight into a maintained structure rather than walking or rebuilding a graph each time.

Let a small, dominant subset stand in for the whole. A process has hundreds of memory regions, but only about sixteen large ones carry almost the entire working set, so DMT keeps just those in a handful of registers and serves over 99 percent of translations from them, letting the long tail fall back to the ordinary walker. Identifying the small concentrated subset that accounts for nearly all the cost and building the fast path solely around it is exactly the strategy the low-bit language-model serving work covered elsewhere on this site uses, spending its effort on the small cluster of values that dominate the difficulty and handling the common remainder cheaply.

Co-design the hardware and the operating system, without breaking the platform. DMT deliberately splits the work: a tiny hardware fetcher does the direct indexing, while the OS manages where the translation arrays live in physical memory, merging, splitting, and migrating them as regions change. Because it leaves the existing page tables, translation caches, and walker untouched and simply adds a fast path beside them, it stays backward-compatible with x86 and can always fall back. Pushing a memory-translation optimization into a careful cooperation between the OS’s control of physical memory and a modest hardware mechanism, rather than a disruptive redesign, is the same discipline the page-table replication work covered elsewhere on this site follows, having the operating system intervene in the virtual-memory machinery only where it pays and leaving the rest of the stack intact.

Following a guest memory access through DMT

Translating a guest address in two references

Tracing one access under pvDMT shows the 24-fetch nested walk collapse to two.

Step 1 of 5

The guest touches an address and the translation cache misses

A program inside a virtual machine reads memory, and the translation-lookaside buffer misses. Instead of launching a two-dimensional walk of up to 24 sequential fetches, the DMT fetcher takes over, because the address falls inside a guest region whose mapping is loaded in a register.

If the address were not covered by any register, DMT would simply fall back to the normal x86 walker.

Why it works

The walk was only ever navigation. The multi-level walk exists solely to locate the final entry → so precomputing a direct index to that entry removes every intermediate fetch → so a native translation drops from four sequential references to one.
A few regions cover almost everything. A process keeps its memory in a few big regions, about 16 covering 99 percent of the working set → so the region-to-array mapping fits in a handful of registers the hardware reads instantly → so over 99 percent of misses are served directly and the rest fall back cleanly.
The direct fetch targets the costliest access. The last-level entries are the ones least likely to be cached and sit at the very end of the dependency chain → so fetching them directly saves the most expensive, least-hideable accesses → so the benefit survives even when upper-level entries are cached or prefetched.
Paravirtualization collapses the second dimension. Placing guest arrays in contiguous host memory → lets the guest-virtual-to-host-physical path skip the guest-physical indirection → so a virtualized walk falls from up to 24 references to two, and a nested one to three.
Cost grows by addition, not multiplication. Each virtualization level adds just one reference rather than multiplying the walk → so nested virtualization becomes affordable in hardware for the first time → so shadow paging and its storm of VM exits can be dropped entirely.

What it costs (trade-offs and scope)

It needs a few big, stable regions. DMT assumes a handful of regions cover the working set and change rarely; a workload with many fragmented regions that overflow the 16 registers, or one that constantly maps and unmaps memory, falls back to the normal x86 walk and gains little.
The translation arrays need contiguous physical memory. Each array must be physically contiguous, and although it is orders of magnitude smaller than its region (about 200 MB for 100 GB of data), contiguity is scarce on long-running, fragmented servers; DMT splits an array when it cannot find contiguity, at some cost.
It allocates the arrays eagerly. Space for a region’s entries is reserved up front — negligible in the evaluation, under 2.5 percent extra memory, but wasteful for a sparse mapping such as a huge memory-mapped file that is barely touched, which would want a smarter allocation policy.
Paravirtualization needs cooperation and a guarded channel. pvDMT requires both guest and host to run the modified OS plus the hardware, and exposing host memory to the guest opens a potential timing side channel that the isolation mechanism must carefully close; without full support DMT falls back to the radix walk.
It requires new hardware. DMT adds 16 registers and fetch logic per core; though modeled as cheap (a few milliwatts, a fraction of a square millimeter) and backward-compatible, it does not run on today’s CPUs, and the results come from a memory-hierarchy simulator combined with real measurements, not from DMT silicon.
The native application speedup is modest. Translation is a smaller share of native execution, so DMT’s native end-to-end speedup is only about 1.05 times; the large gains are in virtualized and especially nested settings where translation dominates.

The evaluation

Three ways to translate a virtual address

Property	Radix walk (x86 baseline)	Hash-based (ECPT)
Sequential fetches: native / virtual / nested		1 / 3 / not supported
How it locates the final entry		Cuckoo hash, many parallel lookups
Backward compatible with x86	Yes, it is the standard
Nested virtualization		Not supported

Three ways to translate a virtual address, evaluated on data-intensive workloads (Redis, Memcached, GUPS, BTree, Canneal, XSBench, Graph500) with a hybrid of real x86 measurement and memory-hierarchy simulation. DMT with paravirtualization cuts a virtualized page walk to two sequential fetches and a nested one to three, speeding virtualized page walks 1.58 times (1.65 times with huge pages) and applications 1.20 times, beating hash-based ECPT by 1.16 to 1.25 times and the ASAP prefetcher by 1.31 to 1.51 times — while staying backward-compatible with x86 and, uniquely, enabling hardware-assisted translation for nested virtualization (1.48 times application speedup there).Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

DMT is a clean, practical piece of hardware-software co-design: it takes the single most expensive thing about running memory-hungry workloads in the cloud — the exploding nested page-table walk — and collapses it to a direct fetch, cutting a virtualized walk from up to 24 references to two and a nested one to three, and becoming the first design to give nested virtualization hardware-assisted translation. It does this while staying backward-compatible with x86 and falling back gracefully, and the reported gains are solid (1.58 times on virtualized page walks, 1.20 times on applications, 1.48 times on nested-virtualization applications). Read the results with their scope. The whole approach rests on the empirical assumption that a handful of stable memory regions cover the working set; workloads with many fragmented or fast-changing regions get little benefit and fall back. The translation arrays demand contiguous physical memory, scarce on long-running servers, and are allocated eagerly, which can waste space on sparse mappings. Paravirtualization needs both guest and host to opt in and carefully guards a side channel it would otherwise open. And this is new hardware evaluated in a simulator plus real measurements, not shipping silicon, with native application speedups that are modest because translation is a smaller cost there. The durable lesson is that when an abstraction’s overhead comes from layers of indirection, the biggest win is often not a faster version of the indirection but a co-designed shortcut that removes it, paid for by exploiting the structure real programs happen to have.

Background

Why layered indirection is the tax, and collapsing it is the fix

It helps to see DMT against the general shape of virtualization: every layer of it buys isolation and flexibility by adding a layer of address indirection, and those layers do not add their costs — they multiply them, which is why one level of virtualization turns a 4-fetch walk into 24 and a second level would need a third dimension no hardware can bear. DMT’s answer is to refuse the multiplication: by placing the guest’s translation arrays directly in host memory, it makes each virtualization level cost one more fetch instead of scaling the whole walk, so depth adds up linearly. Keeping two dimensions of a system from compounding into each other’s cost is the same principle the resource-resizing work covered elsewhere on this site pursues, separating the axes it must control so that scaling one never blows up the other. The broad lesson is that the deepest performance problems in layered systems are rarely about making any single layer faster; they are about stopping the layers from multiplying, whether by collapsing indirection, decoupling dimensions, or co-designing across the boundaries the abstractions drew — so that a system’s cost grows with the problem, not with the number of layers you stacked to express it.

If you remember only three things

1. Address translation is a major bottleneck for memory-intensive cloud workloads because virtualization multiplies the page-table walk: natively an x86 translation costs up to four sequential fetches, but inside a virtual machine every step of the guest walk must itself be translated through the host page table, ballooning to as many as 24 sequential fetches (35 with five-level tables) that form a dependency chain caching cannot hide. This can be over half of execution time, and nested virtualization (a hypervisor inside a VM) would need a third dimension current hardware cannot support, forcing slow shadow paging with frequent VM exits.
2. DMT (Direct Memory Translation) is a hardware-software co-design that skips the walk. Its insight: the walk only exists to locate the last-level entry that holds the actual translation, and a process keeps its memory in a few big regions (VMAs) — about 16 cover 99 percent of the working set and rarely change. So the OS stores each region's last-level entries in a contiguous physical array (a Translation Entry Area), and a few hardware registers (16 per core) hold the region-to-array mapping; on a miss the DMT fetcher computes an offset and indexes the final entry directly in one reference, or falls back to the normal x86 walker. Paravirtualization (pvDMT) places guest arrays directly in contiguous host memory, collapsing a virtualized translation to two references and a nested one to three, guarded by a host-controlled table that restricts each guest to its own arrays.
3. Evaluated on data-intensive workloads with a hybrid of real x86 measurement and memory-hierarchy simulation, pvDMT speeds virtualized page walks 1.58 times (1.65 with huge pages) and applications 1.20 times, beats hash-based ECPT by 1.16 to 1.25 times and the ASAP prefetcher by 1.31 to 1.51 times, and — as the first hardware-assisted translation for nested virtualization — speeds nested-virtualization applications 1.48 times by eliminating shadow paging, all while staying x86 backward-compatible with negligible memory (under 2.5 percent) and hardware cost. Its limits: it needs a few stable, contiguous-mappable regions (fragmented or fast-changing workloads fall back), allocates arrays eagerly, requires guest-host cooperation plus new hardware, and gives only modest native speedup since translation dominates only under virtualization.

Check yourself

Check your understanding

1. Why does running inside a virtual machine make address translation so much more expensive?
2. What structural fact about programs does DMT exploit, and how?
3. How does DMT actually translate an address, and what does paravirtualization add?
4. Which statement best reflects DMT's results and limitations?

Sources

The paper is “Direct Memory Translation for Virtualized Clouds” by Jiyuan Zhang, Weiwei Jia, Siyuan Chai, Peizhe Liu, Jongyul Kim, and Tianyin Xu, published at ASPLOS 2024, DOI 10.1145/3620665.3640358. The authors are at the University of Illinois Urbana-Champaign and the University of Rhode Island; the DMT prototype and artifacts are open-source at github.com/xlab-uiuc/dmt.

This explainer is written from the full 18-page text. Everything above comes from the paper’s own sections: the abstract and introduction framing nested translation as up to 24 sequential fetches and DMT’s one-two-three references; the background on radix page tables, two-dimensional nested paging, shadow paging and its VM exits, nested virtualization’s untenable three-dimensional walk, and the measured overheads (virtualization increasing execution time 1.46 times and nested 4.13 times, page-walk overhead of 21, 43, and 48 percent); the VMA characterization showing 16 VMAs cover 99 percent of the working set; the DMT design with Translation Entry Areas, the VMA-to-TEA register mapping and fetcher, the virtualization and nested-virtualization procedures, and pvDMT paravirtualization with its hypercall and gTEA-table isolation mechanism; the OS support in DMT-Linux for mapping merging and splitting, TEA management and migration, and huge-page support; the hardware extension and its CACTI-estimated cost; and the evaluation methodology (a hybrid of real Intel Xeon Gold 6138 measurement and DynamoRIO memory-hierarchy simulation) and results across the seven benchmarks — the 1.28-to-1.46-times native and 1.58-times (1.65 with huge pages) virtualized page-walk speedups, the 1.20-times application speedup, the 1.48-times nested-virtualization application speedup, the comparisons to ECPT, FPT, Agile Paging, and ASAP, and the negligible runtime, memory, and hardware overheads.